David14: David14 átnevezte a(z) Nobr Szövegbányászat házi feladat br Ékezetesítő /nobr lapot a következő névre: Szövegbányászat - Házi feladat

2013-02-06T11:04:52Z

David14 átnevezte a(z) Nobr Szövegbányászat házi feladat br Ékezetesítő /nobr lapot a következő névre: Szövegbányászat - Házi feladat

← Régebbi változat	A lap 2013. február 6., 13:04-kori változata
(Nincs különbség)

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Valaszthato|SzovBanyaszEkezetesito}} TOC ==Felhasználói útmutató== ===Rendszerkövetelmények=== A program futtatásához .NET 2.0 Framewo…”

2012-10-22T11:47:03Z

Új oldal, tartalma: „{{GlobalTemplate|Valaszthato|SzovBanyaszEkezetesito}} __TOC__ ==Felhasználói útmutató== ===Rendszerkövetelmények=== A program futtatásához .NET 2.0 Framewo…”

Új lap

{{GlobalTemplate|Valaszthato|SzovBanyaszEkezetesito}}

__TOC__

==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===

# Le kell tölteni az [origo] archívumot
(http://categorizer.tmit.bme.hu/~domi/Data/Origo.zip)
# 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.
# 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
# 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
[http://magyar-irodalom.elte.hu/robert/szovegek/bazar/ 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 [http://www.codeproject.com/cs/files/sharpzlib.asp 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, [http://en.wikipedia.org/wiki/Trie 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:

<pre>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;
}</pre>

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 a1a2...an-1an n-gram relatív gyakoriságát úgy definiálom, hogy legyen egyenlő az a1a2...an-1an és az a1a2...an-1 gyakoriságának hányadosával. Ezzel tulajdonképpen azt adom meg, hogy az a1a2...an-1 karaktersorozat után mekkora valószínűséggel következik an.

====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 (an, ..., an+9), és mindegyikhez kiszámolja a relatív gyakoriságok szorzatát. Utána eggyel jobbra csúsztatja az ablakot. Az új ablakban (an+1, ..., an+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 an 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 an+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 2hossz 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.

-- [[PallosPeter|Peti]] - 2007.01.25.

[[Category:Valaszthato]]

Szövegbányászat - Házi feladat - Laptörténet

David14: David14 átnevezte a(z) Nobr Szövegbányászat házi feladat br Ékezetesítő /nobr lapot a következő névre: Szövegbányászat - Házi feladat

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Valaszthato|SzovBanyaszEkezetesito}} __TOC__ ==Felhasználói útmutató== ===Rendszerkövetelmények=== A program futtatásához .NET 2.0 Framewo…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Valaszthato|SzovBanyaszEkezetesito}} TOC ==Felhasználói útmutató== ===Rendszerkövetelmények=== A program futtatásához .NET 2.0 Framewo…”