"Sklepy cynamonowe" Markowa

Palił w piecach, studiował wielkimi skokami -- Pan bez fletu, cofający się w popiół. Będziemy wiecznie żałowali, żeśmy wtedy wyszli na chwilę musieli wesprzeć się o odrzwia, tak silnie szturmował wicher do bramy.

Nie, nie zacząłem pisać powieści ;) Powyższe zdania wygenerował automatycznie program komputerowy. I nie, nie jest to żadne przetwarzanie języka naturalnego, a bardzo prosty łańcuch Markowa. I prawdziwa powieść podana jako wejście, tutaj akurat "Sklepy cynamonowe" Bruno Schulza.

Jest to zbiór opowiadań opublikowany w 1933 roku. Dlaczego on? Bo to jeden z większych tekstów w języku polskim, jaki można znaleźć na stronach Projektu Gutenberg. OK, a o co chodzi z tym Markowem?


W latach 80-tych ubiegłego wieku na Usenecie udzielał się użytkownik Mark V Shaney (zbieżność wymowy z "markov chain" nieprzypadkowa). Użytkownikiem tym tak naprawdę był program komputerowy napisany przez dwóch pracowników laboratoriów Bell (jeden z tych panów stworzył później dobrze znany nam UTF-8 ;)). Mark pisał nowe posty wykorzystując poprzednie posty innych użytkowników w danym wątku, uzyskując tym samym nietypowe, ale nadal będące "na temat" odpowiedzi. Wszystko z użyciem łańcuchów Markowa.

Łańcuch Markowa to formalnie "ciąg zdarzeń, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego zdarzenia". Jeżeli za zdarzenie przyjmiemy napisanie jakiegoś wyrazu lub ciągu paru liter i przyjmiemy, że tekst jest ciągiem Markowa, to to jaki wyraz zostanie napisany zależy tylko od poprzedniego wyrazu. Oczywiście dla różnych wyrazów (ciągów liter) prawdopodobieństwa są różne - można je ustalić analizując jakiś istniejący tekst w danym języku.

W moim programiku w C# dzielę cały tekst zapisany w pojedynczym stringu na fragmenty o równej długości (paru znaków) - na początku przycinam długość wejściowego stringa tak, żeby był równo podzielny przez ustaloną liczbę znaków. Następnie tworzymy łańcuch Markowa w bardzo uproszczony sposób:

// słownik ciąg znaków -> lista możliwych ciągów, które po nim występują
// elementy na liście mogą się powtarzać, tak uzyskamy różne prawdopodobieństwa
Dictionary<string, List<string>> markov = new Dictionary<string, List<string>>();
// pomocnicza lista wszystkich kluczy z powyższego słownika
List<string> runs = new List<string>();
// poprzednio przetwarzany ciąg znaków
string prevRun = null;
// length to stała długość ciągu znaków
// fullText to string zawierający cały tekst powieści
for (int i = 0; i < fullText.Length; i += length)
{
  string run = fullText.Substring(i, length);
  runs.Add(run);
  if (prevRun != null)
  {
  // dodajemy aktualnie przetwarzany fragment do listy
  // fragmentów występujących po poprzednim fragmencie
    if (markov.ContainsKey(prevRun))
    {
    // do istniejącej listy
      markov[prevRun].Add(run);
    }
    else
    {
    // lub tworzymy nową listę i nowy wpis
      List<string> newList = new List<string>();
      newList.Add(run);
      markov.Add(prevRun, newList);
    }
  }
  // teraz aktualny stanie się poprzednim
  prevRun = run;
}

I tyle. Teraz aby na podstawie tak opracowanego łańcucha piszemy prostą funkcję wybierającą losowy element z listy:

private static T randElem<T>(List<T> list)
{
  Random rand = new Random();
  int index = rand.Next(list.Count);
  return list[index];
}

i w prostej pętli możemy generować tyle tekstu ile chcemy (tu np. 10*length znaków):

string r = randElem(runs);
StringBuilder ret = new StringBuilder();
for (int ii = 0; ii < 10 * length; ++ii)
{
  ret.Append(r);
  r = randElem(markov[r]);
}


Ciekawe jest obserwowanie wyników dla różnej długości fragmentu, na który dzielimy tekst. Generalnie im dłuższe są fragmenty, tym wynik logiczniejszy i bardziej gramatyczny ;) Sprawdźmy jedno-zdaniowe wyniki:

Dla fragmentów 2-znakowych:
Iche trawiał się ronią do przepostronej i słończontykowej ham posobsła wstęskrakiego dwiedząc nieobrupaliństwóre jegoś na stu jakżenie i drzwię na i i otwaliniu padalonach mów cieniem w pień postarany zdłuchiszch spodzącącychwanie ch poszony zrozmnichety zmyślnicy.

Dla fragmentów 3-znakowych:
W ten za krótki skarpetkniętym inną z barastała wie głos jego dzielnicę.

Dla fragmentów 4-znakowych:
Nie mógł się jedną noc bezksiężycowego w trawagancji, zamknięte wiecowania gasła, mnożyła się i zmętny i niedbały, zapewne metody illegalne, zawalone pościelał na stanąć miały czarny melonialnej pstrokacizny.

Dla fragmentów 5-znakowych:
Ulica Krokodyli była koncesją naszego nie odłączał się całym ciałem ciężkiego, białe plamy słońca w szparach okna, na których płaszcze i gubił miękkie, subiekci wracali na obiad.

Dla fragmentów 6-znakowych (przy takich ustawieniach został wygenerowany pierwszy akapit tego posta):
Tu jest punkt wyjścia dla nowej apologii sadyzmu. Mój ojciec dał za wygraną, zeskoczył z wysokiego gzymsu i ruszył na lekkich obręczach. Ale kto w taką noc powierza się kaprysom nieobliczalnego dorożkarzy, ale w tej chwili Adela stanęła w otwartych drzwi podniósł firanki u okna, na których oczy, naczytane do syta i pełne są aż pod samą świecą, w złotym kręgu jej blasku, którego przebiegu nic z zewnątrz zmącić nie mogło pomieścić tego białego pokoju, przylgnąć uchem do szparami zdradza swą imitatywność.

Wygenerujmy też tekst używając podziału na 7-znakowe fragmenty. Tym razem podzielę wynik na fragmenty żywcem "przepisane" z oryginalnej książki:

1. Nakładając okulary, zbliżył się w paru krokach i obszedł dookoła
2. wieloramiennych lamp wiszących. Gdy ojciec
3. mój zapadał od czasu do czasu na całe godziny w gęsto zastawione gratami zakamarki, szukając czegoś zawzięcie. I nieraz bywało podczas obiadu, gdy zasiadaliśmy wszyscy do stołu, brakło ojca. Wówczas matka musiała długo wołać „Jakubie!” i stukać łyżką w stół, zanim wylazł z jakiejś szafy, oblepiony szmatami pajęczyny i kurzu, z wzrokiem
4. nieprzytomny na krawędzi nocy, chwytając piersiami powietrze, a pościel rosła dokoła niego, puchła i nakisała -- i zarastała go znowu zwałem ciężkiego,
5. białawy spokrewniał liście z atmosferą, dawał im srebrzysty, szary połysk fal powietrznych, cienistych zadumań między dwoma błyskami słońca.

Ciekawe, co nie? Fajnie by było przepuścić przez to jakiś tekst filozoficzny ;)

Więcej:
http://en.wikipedia.org/wiki/Mark_V_Shaney
http://en.wikipedia.org/wiki/Markov_chain
http://www.gutenberg.org/

PS.
Istnieje coś takiego jak "powieść automatyczna". Tutaj można znaleźć przykład takowej i opisany sposób w jaki powstawała: http://www.amazon.com/Exquisite-Cadaver-Semi-Automatic-Novel/dp/096436140X