Write letterz n shit, yo!

A minap eszembe jutott, hogy régen olvastam egy angol srác blogján, hogy készített egy hülye kis szöveg generátort ami a "megtanult" szöveg után valószínűségi alapon képes volt mondatokat generálni. Nem volt benne nagy varázslat de egy kis játszásnak elmegy.

A módszer 2 részből áll:

1. N-gramok:

Az N-gram egy véges gyűjteménye n hosszú dolgoknak. A dolog lehet betű, szó, mondat, protein szekvencia, stb. Első sorban szöveg feldolgozásnál használják és nagyobb szöveges dokumentumokból generálják le. Mindezek mellett hasznos még pl. helyesírás/kifejezés korrekcióknál, szöveg hasonlóság vizsgálatnál, stb.

Vegyük alapul a következő szöveget:

Hogyha lopnék kókuszdiót
Nem mondanám meg, hogy ki vót
A legnagyobb tragédia
Anyukámnak nincsen fia.

Ha n=2 és a szavak alapján akarjuk létrehozni, akkor 2-gramos (bigram) szekvenciát készítünk belőle ami nagyjából így nézne ki:

Hogyha lopnék

lopnék kókuszdiót

kókuszdiót Nem

Nem mondanám

...

Láthatjuk, hogy nincs benne semmi magic, egyszerűen végiglépkedünk kettesével a szöveg szavain (ha szavak alapján akarjuk generálni). 

Természetesen ha betűkkel szeretnénk dolgozni, akkor a harácsolás szóból a következő lesz 3-gramos (trigram) bontásnál:

har

ará

rác

ács

cso

sol

olá

lás

2. Markov láncok

Markov láncoknak hívjuk azokat a modelleket, ahol meghatározott s állapotok között p(i) valószínűséggel történhet átmenet, ahol i két s állapot közötti átmenetet jelöli. Egy állapot akár a saját állapotát is megtarthatja bizonyos valószínűséggel, nem kötelező neki váltani. Egy státuszból induló állapotátmenetek valószínűségeinek összege mindig 1 (100%)

Egyszerű példa:

E státus jelölje az evést, A jelölje az alvást. (Igen, csak lusta voltam készíteni egy saját ábrát, helyette itt van ez. Örüljetek! :) ) Az ábra alapján ha eszem, 30% eséllyel folytatom tovább, 70% eséllyel elalszom utána. Amennyiben alszom, 40% eséllyel felkelek és eszek, 60% eséllyel alszom tovább. 

Hogy lesz ebből szöveg generátor?

Mivel egy szöveg generátort akarunk létrehozni ezért kell valami módszer arra, hogy ha kiválasztunk egy random kezdő szót akkor az algoritmusunk úgy pakolja utána a szavakat, hogy a végén valami "értelmes" jöjjön ki belőle. Az N-gramjaink segítségével képesek vagyunk betanítani az algoritmusunkat arra, hogy minden egyes szólánchoz eltárolja, hogy milyen szavak követték a forrás szövegben. Ezen gyűjteményből képesek leszünk valószínűségi alapon eldönteni, hogy milyen szó kövesse a szóláncunkat egy véletlen kiválasztással. Az így kialakított mondatok természetesen maximum pszeudo-értelmesek lesznek, hiszen tartalmilag nem fogunk sok kohéziót találni bennük, mindössze a forrás alapján megtanult szófordulatok fognak visszaköszönni ránk.

Bigramoknál egy nagyobb forrásszövegben biztosan többször is elő fog fordulni egy szópáros (pl.: "azt hogy", "nem tudom", "és akkor"). Ha az összes szólánchoz rögzítjük, hogy milyen szavak követték, akkor a következő adatszerkezethez hasonlót kapunk:

[("azt", "hogy"): ("ne", "soha", "jó", "ne"),

("nem", "tudom"): ("hogy", "hogy", "miért") 

...]

Mint látható, ha egy szó többször követi a szóláncunkat akkor azt ugyanúgy többször letároljuk, ezzel is növelve az esélyét annak, hogy azt a szót dobja nekünk az algoritmus következőnek. Minél nagyobb szöveget választunk ki forrásnak, annál több és változatosabb fordulatokat tanul meg. 

Érdemes kicsi n értéket választani generáláshoz, különben nagyon sűrűn fog ismétlődni a szöveg. Nem valószínű, hogy túl sokszor fordul elő az "ó mily csodás teazsúr" kifejezés bármilyen szövegben. Minden ritka szóláncot szinte biztosan csak egy szó fog követni, ezzel megölve a generált szöveg változatosságát.

Lássuk a medvét

Írtam pythonban egy egyszerű kis alkalmazást ami a fenti logika alapján beolvas egy forrás szöveget, megtisztítja azt, legenerálja a megadott hosszúságú gramjainkat majd kiad általunk meghatározott hosszúságú mondatokat. (Aki nem szereti az angol nyelvet az tegye túl magát az angol kommenteken. Minden ami forráskód az csak angol nálam)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class ngramGenerator(object):

    def __init__(self, n):
        self.n = n
        self.words = list()
        self.ngrams = dict()

    def get_n(self):
        return self.n

    def get_ngrams(self):
        return self.ngrams

    def get_words(self):
        return self.words

    def read(self, file_path):
        file = open(file_path, 'r')
        lines = file.readlines()
        words = list()
        for line in lines:
            words.extend(line.split(' '))
        self.words = words

    def clear(self):
        if not len(self.words):
            raise IOError("No file was loaded. Use read(file)")
        cleaned_words = list()
        for word in self.words:
            word = word.lower()
            # Remove numbers and 'weird characters'
            word = re.sub(r'[\d,:;"()-_]+', '', word)
            # Remove apostrophes from beginning of words
            word = re.sub(r'([^\w]+|^)\'(\w+)', self.removeBeginningApostrophes, word)
            # Remove apostrophes from end of words
            word = re.sub(r'(\w+)\'([^\w]+|$)', self.removeEndingApostrophes, word)
            # Strip whitespace chars
            word = word.strip()
            if len(word):
                cleaned_words.append(word)
        self.words = cleaned_words

    def removeBeginningApostrophes(self, match):
        if not len(match.groups()):
            return match.group(0)
        return ' ' + match.group(1)

    def removeEndingApostrophes(self, match):
        if not len(match.groups()):
            return match.group(0)
        return match.group(1) + ' '

    def ngramize(self):
        for index in range(len(self.words) - self.n):
            ngram = tuple(self.words[index:index + self.n])
            next = self.words[index + self.n]
            if ngram not in self.ngrams:
                self.ngrams[ngram] = [next]
            else:
                self.ngrams[ngram].append(next)

Az ngramGenerator feladata, hogy beolvassa a forrásfájlt, eltávolítsa a zajt belőle majd legenerálja a szóláncainkat.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class markovGenerator(object):
    def __init__(self, words_to_generate, ngramGenerator):
        self.words_to_generate = words_to_generate
        self.ngram_generator = ngramGenerator

    def generate(self):
        from random import choice

        current = self.__get_random_ngram()
        output = list(current)
        for i in range(self.words_to_generate):
            if current in self.ngram_generator.get_ngrams():
                possibilities_next = self.ngram_generator.get_ngrams()[current]
                next = choice(possibilities_next)
                output.append(next)
                if re.match(r'[\w]+[.?!]', next) is not None:
                    current = self.__get_random_ngram()
                    output.append(' '.join(current))
                    continue
                current = tuple(output[-self.ngram_generator.get_n():])
            else:
                break

        return ' '.join(output)

    def __get_random_ngram(self):
        from random import randrange
        word_count = len(self.ngram_generator.get_words())
        word_index = randrange(word_count - self.ngram_generator.get_n())
        return tuple(self.ngram_generator.get_words()[word_index:word_index + self.ngram_generator.get_n()])

A markovGenerator feladata maga a mondatok generálása.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

ngram_generator = ngramGenerator(2)

file_path = 'koldus_es_kiralyfi'
ngram_generator.read(file_path)
ngram_generator.clear()
ngram_generator.ngramize()

markov_generator = markovGenerator(30, ngram_generator)
generated = markov_generator.generate()
print generated

A futtatásnál pedig a fenti 2 osztályt használom. Beolvasom a koldus_es_kiralyfi fájl tartalmát, megtisztítom a fölösleges karakterektől, majd legenerálom az N-gramokat. Ezt követően 30 szó hosszú "mondatokat" szeretnék létrehozni, amit a generate metódus ad vissza nekünk.

Konklúzió

A fenti kis gagyi példa egy egyszerű ki alkalmazás ami meglévő modelleket használ fel egy érdekes feladathoz. Próbáljátok ki különböző méretű forrás dokumentumokkal és nézzétek meg, hogy milyen mondatokat generál.

A forrást le tudod tölteni innen