Szerepjátékos koromban a legnagyobb kihívást a jó karakter nevek kitalálása okozta. Rendszeresen valami nyögve nyelős, erőltetett nevet találtam ki, ami általános derültséget váltott ki a csapatban. Ha akkor ismertem volna a Markov láncokat, mindez nem jelentett volna problémát.
A Markov láncok nagyon egyszerűek: Semmi más, mint egymást követő elemek. Azt, hogy miként követik egymást az elemek, valószínűségekkel adjuk meg, amit átmeneteknek nevezünk. Vegyünk például egy tornasort. A magasabbak elől állnak, az alacsonyabbak hátul. Annak a valószínűsége, hogy a legmagasabb valaki után következzen, nulla. Tegyük fel, több, azonos magasságú ikerpár is van ezen a tornaórán. Az ő átmenetét 0.5-el jellemezhetjük, mert hol az egyik van előrébb, hol a másik.
A Markov láncok általában csak az egymást közvetlenül követő elemekre adják meg az átmeneteket, vagyis a korábbi elemek nem számítanak. Ez akkor érdekes, ha nem egy tornasorra gondolunk, hanem más hosszú láncokra, amelyek viszonylag kevés elemből állnak. Mint amilyen a DNS is.
A Markov láncok segítségével bármilyen hosszú DNS-t jellemezhetek, hiszen csak azt kell megadnom, hogy egyik nukleotid milyen valószínűséggel követi a másikat. Ha a nukleotidok teljesen random követnék egymást, akkor ez nem lenne túl érdekes, mert az átmenetek csak 0.25-t tartalmaznának. De tudjuk, hogy a kódoló és nem kódoló szakaszoknál ez más, sőt fajokban is eltérhet!
Tehát ha az átmeneteket egy mátrixba gyűjtöm, akkor bármilyen hosszú DNS szekvenciát jellemezni tudok. A mátrix mérete nem változik.
Sőt, a szabály ismeretében bármilyen hosszú DNS szekvenciát is tudok generálni. Ennek persze nem sok értelme van, és nem is segíti a megértést, ha szekvenciákkal szemetelem tele a képernyőt, ezért inkább Gyűrük Ura neveket fogok generálni demonstrálásként, amiket fantasy játékokban lehet használni.
Először is szükségünk van az átmenetekre. Ezeket már létező nevekből kapjuk meg. A Wikipédiaból kimásoljuk az összes nevet. Én eltávolítottam az összes ékezetet, kötőjelet és angol kötőszót, majd a szöveget kisbetűssé változtattam. Minden név egy sorban van.
import sys
import random
transition = dict()
letters = set()
for i in open(sys.argv[1]):
name = i.rstrip()
for j in range(1,len(name)):
pch = name[j-1]
ch = name[j]
if pch not in transition:
transition[pch] = dict()
if ch not in transition[pch]:
transition[pch][ch] = 0
transition[pch][ch] += 1
letters.add(pch)
A transition nevű változó fogja tárolni az átmeneteinket. Most még csak az átmenetek számát tartalmazza. Ebből nekünk valószínűségeket kell kapnunk.
for ch1 in transition:
s = 0
for ch2 in transition[ch1]:
s += transition[ch1][ch2]
for ch2 in transition[ch1]:
transition[ch1][ch2] = float(transition[ch1][ch2]) / s
Gyakorlatilag ez egy normalizálás, hogy 0 és 1 közötti értékeket kapjunk. Már csak a generálás van hátra. Ebben a programban csak 5 betűs neveket készítünk, de lehet kísérletezni más hosszúsággal is.
letters = list(letters)
ch1 = letters[random.randint(0, len(letters)-1)]
name = ch1
for i in range(5): # Length of the name
r = random.random()
s = 0.0
if ch1 not in transition:
break
for ch2 in transition[ch1]:
s += transition[ch1][ch2]
if r < s:
ch1 = ch2
name = name + ch2
break
print(name)
Néhány példa, hogy mi jött ki: Marwor, Frindo, Halanb, Brisen. Persze vannak teljesen használhatatlan nevek is: Hbelfr, Rgoron, Wirorf, Ndunha.
A bemeneti adatok most az összes karakter nevét tartalmazzák. Biztos érdekes lehet csak tünde, vagy csak hobbit neveken lefuttatni. Esetleg ha elég nagy listánk lenne, akkor nemek szerint is bonthatnánk. A következő posztban kicsit fejlesztjük a koncepciót és bemutatom a rejtett Markov láncokat.
