Szövegbányászat - Házi feladat

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Felhasználói útmutató

Rendszerkövetelmények

A program futtatásához .NET 2.0 Framework és minél több RAM szükséges.

A program használata

1. Le kell tölteni az [origo] archívumot

(http://categorizer.tmit.bme.hu/~domi/Data/Origo.zip)

1. A korpusz létrehozása tabon meg kell adni a zip helyét, azt, hogy

az első hány dokumentumot dolgozza föl, és hogy legfeljebb milyen hosszú n-gramokat gyűjtsön ki.

1. A korpusz részletek tabon bele lehet lapozni a fába és meg lehet

nézni, hogy egy konkrét n-gramot hányszor talált meg az [origo] archívumban

1. Az ékezetesítés tabon

• • Be lehet tölteni egy korábban előállított n-gram fát.
  • Meg lehet nyitni illetve el lehet menteni egy szöveges

dokumentumot választott karakterkódolással.

• • Kétféle algoritmussal lehet ékezetesíteni a szöveget.
  • Ha a szöveg eleve ékezetes volt, a Teszt gomb hatására

kiszámolja, hogy az ékezetek törlése és az újraékezetesítés után mekkora lesz a hibaarány. A pontosságot a következő képlettel számolom: (eltalált magánhangzók száma) / (összes magánhangzó száma)

Teszt eredmények

Az archívum 10000 dokumentumából a legfeljebb 10 betűs n-gramokat kigyűjtve, a dinamikus programozási algoritmust választva a pontosság A katedrális és a bazár c. szöveg esetén 620 MB memóriahasználat mellett 98% volt.
A memóriahasználat felére csökkenthető egy 3000 dokumentumból generált korpusszal úgy, hogy a pontosság még mindig 97% fölött marad.

A program működése

Korpusz előállítása és tárolása

A korpusznak a TMIT oldalán megtalálható [origo] archívumot választottam. A program jelenleg csak ehhez tartalmaz parsert, de a provider modellen keresztül kis erőfeszítéssel más adatforrások is illeszthetők. A 200 MB-os origo.zip több mint 100000 file-t tartalmaz, ezért úgy döntöttem, hogy nem csomagolom ki az egészet, hanem a zlib könyvtárral mindig csak az éppen feldolgozandó dokumentumot bontom ki a memóriába.

A korpusz a feldolgozott dokumentumok összes, legfeljebb k hosszú n-gramját tartalmazza, ahol k alapértéke 10. Az n-gramok egy szófában (prefix tree, trie) vannak eltárolva annyi módosítással, hogy a gyökér gyerekei az utolsó karaktert tartalmazzák, és a fában lefele haladva visszafele tudjuk kiolvasni a kulcsokat. Egy csúcsnak legfeljebb 37 gyereke lehet. Megkülönböztetem a magyar ábécé egyjegyű betűit (26+9 karakter), a kötőjelet és a szóközt. A kis- és nagybetűket azonosnak veszem, mert elkülönítésük jelentősen megnövelné a fa méretét. Az írásjeleket szóközként kezelem.

A fát a következőképpen ábrázolom:

class NGramTreeNode {
	// kulcs (n-gram) következő karaktere
	public char character;

	// n-gram előfordulásainak száma a beolvasott szövegekben
	public uint frequency;
	
	// milyen karakterek (karaktersorozatok) előzhetik meg az kulcsot
	public NGramTreeNode[] children;
}

A fa felépítésekor egy n-gram és összes szuffixának felvétele darabonként 1 lefelé lépést és 0 vagy 1 beszúrást jelent a fában. A csúcsok gyerekeit karakter szerint rendezve tárolom. Ezzel ugyan lineáris lesz a beszúrás ideje, cserébe a keresésé O(log(n))-re csökken. Mivel a legtöbb csúcsnak kevés gyereke van, a lineáris futási idő is elfogadható. A fa formájú tárolásnak megvan az az előnye, hogy minden n-gram ábrázolható 1 karakterrel és egy pointerrel, tehát lényegesen kisebb a memóriaigénye, mint ha egy hash táblába raknám az <n-gram,gyakoriság> párokat.

A fát tömörítve mentem lemezre. Egy pár tárigényét sikerült 2,4 byte-ra leszorítani a következő kódolással:

• a gyakoriság nagyságrendje (2 bit)
  • 00: egyszer fordult elő
  • 01: legfeljebb 2^8-1-szer fordult elő
  • 10: legfeljebb 2^16-1-szer fordult elő
  • 11: legfeljebb 2^32-1-szer fordult elő
• csúcs távolsága a gyökértől (6 bit)
• karakter ISO-8859-2 kódolással (1 byte)
• karakter gyakorisága 0, 1, 2 vagy 4 byte-on

Az [origo] archívum első 10000 dokumentumából készített korpusz 17,8 millió különböző legfeljebb 10 karakteres n-gramot tartalmaz. A fát 41 MB-on tárolható ezzel az adatábrázolással. A struktúra finomításával körülbelül további 30%-ot lehetne spórolni, de nem ez a szűk keresztmetszet, hanem a memóriahasználat, ugyanis a .NET keretrendszer egy csúcsnak átlagosan 35 byte-ot foglal a memóriában. A 17,8 millió bejegyzés több mint 600 MB-ot jelent.

Az overheadet az objektumok pazarló tárolása okozza. Lényeges javulást csak egyedi memóriakezeléssel lehetne elérni, azaz egy nagy byte tömbben kellene tárolni az egész fát, és a fában való mozgás során minden lépésben kézzel kellene kiszámolni a következő címet. Ezzel a módszerrel becsléseim szerint harmadára lehetne visszaszorítani a memóriahasználatot.

Alternatív megoldásként elképzelhető a fa lemezen tárolása is. A gyökérhez közeli részfát lehetne memóriában tartani csökkentve a lemezhozzáférések számát, de még a gyorsítótárazás mellett is teljesítményproblémákat vetne fel a módszer. Egy 85 KB-os szöveg ékezetesítése jelenleg 3 másodpercig tart egy 1,6 GHz-es processzort tartalmazó laptopon. Lemezolvasásokkal együtt ez az érték több nagyságrenddel nőne, ami nem elfogadható.

Ékezetesítő algoritmus

Egy a₁a₂...a_n-1a_n n-gram relatív gyakoriságát úgy definiálom, hogy legyen egyenlő az a₁a₂...a_n-1a_n és az a₁a₂...a_n-1 gyakoriságának hányadosával. Ezzel tulajdonképpen azt adom meg, hogy az a₁a₂...a_n-1 karaktersorozat után mekkora valószínűséggel következik a_n.

Mohó algoritmus

Kétféle algoritmust próbáltam ki. A mohó algoritmustól nem vártam sokat, csak azért implementáltam, mert egyszerű volt és összehasonlítási alapot adott. Az ékezetesítést a teljes indukció elve alapján végzem. Felteszem, hogy a szöveg egy prefixe már ékezetesítve van. A következő karakter ha magánhangzó, legfeljebb négyféle lehet. Mindegyik esetre megkeresem a szuffixre illeszkedő leghosszabb n-gramot és az a betűt választom, amelyik n-gramjának legnagyobb a relatív gyakorisága. Az algoritmus hatékonysága kicsit javítható, ha a relatív gyakoriságot súlyozom az n-gram hosszával.

A mohó algoritmus problémája az, hogy azonnal dönt és csak a szavak előző karaktereit veszi figyelembe. A hatékonyság lényegesen javítható, ha csak a következő néhány karakter ismeretében hozzuk meg a döntést.

Dinamikus programozásos algoritmus

Tegyük fel, hogy k=10 karakteres n-gramokkal dolgozunk. Ekkor a program az összes lehetséges módon ékezetesíti a szöveg soron következő 10 karakterét (a_n, ..., a_n+9), és mindegyikhez kiszámolja a relatív gyakoriságok szorzatát. Utána eggyel jobbra csúsztatja az ablakot. Az új ablakban (a_n+1, ..., a_n+10) is veszi az összes lehetséges ékezetesítést. Az új ablak egy konkrét ékezetesítésére megkeresi a régi ablak bejegyzései közül azt, aminek az utolsó 9 karaktere megegyezik az új ablak első 9 karakterével. Egy új bejegyzéshez legfeljebb 4 régi tartozhat, mert az a_n karakternek legfeljebb négyféle ékezetes formája létezik. Az új 10-gram valószínűségét úgy kapjuk meg, hogy az illeszkedő régiek közül a legnagyobb valószínűségűt megszorozzuk a_n+10 relatív gyakoriságával és egy súlyozótényezővel.

[math] P(a_{n+1}, \dots, a_{n+k}) = \text{s\'ulyoz\'ot\'enyez\H{o}} \cdot \text{rel.gyak}(a_{n+k}) \cdot \max\limits_{a_n} P(a_n, \dots, a_{n+k-1}) [/math]

A feldolgozás végén a szöveg utolsó lehetséges 10-gramjai közül kiválasztjuk a legvalószínűbbet és visszakövetjük, hogy jutottunk oda. Így kapjuk meg a teljes szöveg ékezetesítését.

Az algoritmus hatékonyságának elemzése

Az algoritmusok hatékonyságát úgy mérem, hogy a szövegben lévő magánhangzók mekkora részének találja el helyesen az ékezeteit.

• Naiv algoritmus: sehova nem írok be ékezetet. Körülbelül 72% a találati arány.
• Mohó algoritmus: csak minimálisan jobb, 80-82%-os eredményt lehet vele elérni.
• Dinamikus programozásos algoritmus: a korpusz méretétől függően 96-98% az eredmény. Ha a szöveg sok idegen nyelvű kifejezést tartalmaz (pl. Elosztott rendszerek jegyzet), 95%-ra romlik a hatékonyság.

Tipikus hibák

• Az 1000 dokumentumos korpusznál a katedrális szót katédrálisra javította. Magyarázat: a katedrális nem szerepel egyik [origo] cikkben sem. Amikor a negyedik betűről kellene eldönteni, hogy e vagy é legyen, a "kate" 34-szer szerepel a fában, míg a "katé" egyszer sem. Ezért a következő leghosszabb szuffixszal, az "até"-val számolok, ami 456-szor fordul elő. Ezt az eltérést az n-gram hosszával való súlyozás sem tudja kompenzálni. A 3000 dokumentumból álló korpusszal már eltalálta a helyes ékezeteket.
• Az átkozottul szóból átközöttül lesz. Az ok hasonló. Az átkozott szó nagyon ritkán szerepel, a között sokkal gyakrabban, ezért végül az utóbbi mellett döntött a program még akkor is, ha nem szóköz szerepel előtte. A között szónak a leggyakoribb u/ú/ü/ű betűs folytatása a közöttük, innen jön az ü.

Kipróbáltam azt, hogy a valószínűségeket nem egyszerűen a n-gram hosszával súlyozom, hanem egy gyorsabban növekvő függvénnyel. A 2^hossz választás érezhetően javított a pontosságon, de efelett már nem volt mérhető a változás.

Továbbfejlesztési lehetőségek

• Memóriahasználat csökkentése. Hosszabb n-gramok használatához sokkal több memória kell, mert csökken a redundancia, így egyelőre nem végeztem velük teszteket.
• Kiértékelő függvény megváltoztata úgy, hogy elkerülje a jelenleg előforduló típushibákat.
• Korpusz gyorsabb betöltése lemezről.

-- Peti - 2007.01.25.