Eötvös Loránd Tudományegyetem Informatikai Kar
Nyelvtechnológiai alkalmazások integrálása keres˝omotor(ok)ba
Dr. Prószéky Gábor
Orosz György
egyetemi docens
nappali tagozat
PPKE ITK
programtervez˝o matematikus
Budapest, 2010.
A diplomamunka bekötve kell, hogy tartalmazza a kitöltött és jóváhagyott diplomamunka témabejelent˝ot. Ennek a lapnak a helyére kell bekötni. ***
3
Tartalomjegyzék 1. Bevezetés
7
2. Természetes nyelv és keres˝ok kapcsolata 2.1. Nyelvi szöveg számítógépes reprezentációja 2.1.1. ASCII . . . . . . . . . . . . . . . . 2.1.2. ISO–8859 . . . . . . . . . . . . . . 2.1.3. Windows kódlapok . . . . . . . . . 2.1.4. Unicode . . . . . . . . . . . . . . . 2.2. Természetes-nyelvi feldolgozás . . . . . . . 2.2.1. Történet . . . . . . . . . . . . . . . 2.2.2. Alkalmazások . . . . . . . . . . . . 2.3. Keres˝orendszerek . . . . . . . . . . . . . . 2.3.1. Internetes keres˝ok története . . . . 2.3.2. Vertikális keresés . . . . . . . . . . 2.4. Nyelvi eszközök keres˝orendszerekben . . . 3. A megfelel˝o keres˝orendszer választása 3.1. Szempontok . . . . . . . . . . . . 3.2. Vizsgált keres˝orendszerek . . . . 3.2.1. OpenFTS . . . . . . . . . 3.2.2. Terrier . . . . . . . . . . . 3.2.3. Lucene . . . . . . . . . . 3.2.4. Datapark Search Engine . 3.2.5. Egothor . . . . . . . . . . 3.2.6. Xapian . . . . . . . . . . 3.2.7. ht://Dig . . . . . . . . . . 3.2.8. Lemur/Indri . . . . . . . . 4
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . .
8 8 9 9 10 10 11 12 13 13 15 17 18
. . . . . . . . . .
21 21 22 23 23 23 23 24 24 24 24
3.3. A Lemur és az Indri m˝uködése 3.3.1. Indexelés . . . . . . . 3.3.2. Lekérdezés . . . . . . 3.3.3. Egyéb alprogramok . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4. Nyelvi keres˝o létrehozása 4.1. Szótövez˝o modul . . . . . . . . . . . . . . . . . . . . 4.1.1. Lemur, Indri . . . . . . . . . . . . . . . . . . 4.1.2. Tövez˝o integrációja . . . . . . . . . . . . . . . 4.2. Tiltólistás szavak . . . . . . . . . . . . . . . . . . . . 4.2.1. Stopword sz˝urés az Indriben . . . . . . . . . . 4.2.2. Szavak választása, megvalósítás . . . . . . . . 4.3. Dátumok használata . . . . . . . . . . . . . . . . . . . 4.3.1. Motiváció . . . . . . . . . . . . . . . . . . . . 4.3.2. Dátumok kategorizálása . . . . . . . . . . . . 4.3.3. Dátumkezelés az Indriben . . . . . . . . . . . 4.3.4. Magyar nyelv˝u dátumok kezelése . . . . . . . 4.3.5. A megoldás korlátai . . . . . . . . . . . . . . 4.4. Mennyiségek használata . . . . . . . . . . . . . . . . 4.4.1. Motiváció . . . . . . . . . . . . . . . . . . . . 4.4.2. Mennyiségek indexelése, keresése az Indriben . 4.4.3. Általános megoldás mennyiségek használatára 4.4.4. Megoldatlan problémák . . . . . . . . . . . . 4.5. Szinonimák használata . . . . . . . . . . . . . . . . . 4.5.1. Motiváció . . . . . . . . . . . . . . . . . . . . 4.5.2. Rokon értelm˝u szavak használata az Indrivel . 4.5.3. Automatikus szinonimahasználat . . . . . . . . 4.5.4. A megoldás korlátai . . . . . . . . . . . . . . 5. Az elkészült rendszer értékelése 5.1. Teljesítmény . . . . . . . . . 5.1.1. Indexelési id˝o . . . . 5.1.2. Index mérete . . . . 5.1.3. Lekérdezési id˝o . . . 5.2. Relevancia . . . . . . . . . . 5.2.1. Módszer . . . . . . .
. . . . . .
. . . . . .
. . . . . . 5
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . .
25 26 29 30
. . . . . . . . . . . . . . . . . . . . . .
33 33 34 34 35 36 36 36 36 36 37 39 41 41 41 42 43 44 45 45 45 46 46
. . . . . .
47 47 47 48 49 50 50
5.2.2. Mérési eredmények . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Összefoglalás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52 53
Köszönetnyilvánítás
54
Függelék Tiltólistás szavak . . . . . Konfigurációs fájl . . . . . Felhasználói dokumentáció Fejleszt˝oi dokumentáció .
55 55 58 60 63
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
Irodalomjegyzék
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
87
6
1. fejezet Bevezetés Az elmúlt két évtizedben az internet elterjedésével a keres˝orendszerek népszer˝usége hatalmas mértékben növekedett. A világhálón található mérhetetlen információmennyiség használata, mára aligha lehetséges keres˝ok nélkül. Erre az igényre éreztek rá a múlt század végén olyan nemzetközi nagyvállalatok, mint a Google, Yahoo, Microsoft. Az is igaz, hogy a keres˝ok használata a mai ember számára már-már alapvet˝o szükség˝uvé vált, így a fejleszt˝o cégek nagy energiát fektetnek ezek használhatóbbá tételére. Az utóbbi néhány évben azt a tendenciát figyelhetjük meg, hogy mind gyakrabban találkozhatunk intelligens eszközökkel a keresések során. Ezen eszközökkel a vállalatok célja az, hogy minél közelebb vigyék a keres˝orendszert a felhasználókhoz. Magyarországon is egyre több cég érez potenciális üzleti lehet˝oséget intelligens keres˝ok fejlesztésében. Ilyen hazai próbálkozás például a PolyMeta, mely a világcégek keres˝oinek eredményeit aggregálva dolgozik. A fentebb intelligensnek nevezett modulok legtöbbször olyan szoftvert takarnak, melyek a természetes nyelvi megértést segítik. Nyilván az emberi kommunikáció számítógéppel való teljes megértése csak egy távolban lebeg˝o cél a kutatók el˝ott, de ezek szoftverek jó tulajdonságokkal rendelkezhetnek információ keresési alkalmazásokban. A dolgozattal és a hozzá tartozó programmal a – témakiíráshoz kapcsolódó – következ˝o feladatot oldottam meg: Vizsgáljuk meg a keres˝orendszerek m˝uködését, majd azt, hogy általában milyen lehet˝oségek kínálkoznak a rendszer teljesítményének javítására magyar nyelv˝u környezetben! Egy választott keres˝orendszert egészítsünk ki a MorphoLogic által rendelkezésre bocsátott szótövez˝ovel és szinonima szótárral, majd vizsgáljuk meg milyen további lehet˝oségek vannak még a keres˝o fejl˝odését tekintve! Készítsük el a rendszer fejl˝odését segít˝o eszközöket, majd mérjük meg az így kapott magyar nyelv˝u keres˝o eredményességét, teljesítményét! A fenti méréshez szolgáljon alapul az 1994 és 2008 között született parlamenti naplók adatbázisa! 7
2. fejezet Természetes nyelv és keres˝ok kapcsolata Ebben a fejezetben áttekintem a nyelvtechnológiával, keres˝orendszerekkel, szövegek tárolásával kapcsolatos alapfogalmakat és ezek kapcsolatát.[6]
2.1.
Nyelvi szöveg számítógépes reprezentációja
A ma használatos számítógépeken futó szoftverek egy dokumentumot karakterek halmazaként kezelik, így egy szöveg reprezentálása is egymást követ˝o karakterek reprezentálásával valósul meg. Nyilván egy természetes nyelven íródott szöveg szerkezete ett˝ol az egyszer˝u leképezést˝ol jóval összetettebb, de ezek a struktúrák is kifejezhet˝oek megfelel˝oen választott karaktersorozatokkal. Ha picit elid˝ozünk azon, hogy miért éppen egy karakter a tárolás alapegysége, elgondolkodhatunk azon, hogy más reprezentáció is létezhetne (pl.: a nyelv szavainak tárolásával), de ezek nem illeszkednének a digitális számítógép m˝uködési elvéhez oly mértékben, mint a jelenlegi. Folytatva a gondolatmenetet: egy dokumentum tárolásának feladata helyett, elegend˝o egy karakter tárolásának feladatát megoldani. Számítógépeink alapvet˝oen számokkal végzett m˝uveletek végrehajtására képesek, ezért a karakterek is számokként kerülnek tárolásra. Most a karakter alapú dokumentum tárolással kapcsolatos alapfogalmakat fogom áttekinteni.[6, 15]. Karakter A számítógép alapú kommunikáció alapegysége. Egy karakter lehet bet˝u, szám, írásjel vagy egyéb nem látható vezérl˝okarakter. A Unicode szabvány definíciója szerint az „adat szervezésére, ellen˝orzésére vagy megjelenítésére használt elemek halmazának egy tagja”. Karakterkészlet Karakterek rendezetlen halmaza. Egy karakterkészlet a gyakorlatban 8
úgy szokás megadni, hogy a karakterek nevei mellett annak képi ábrázolását1 , is megjelenítjük. Az is el˝ofordulhat, hogy több különböz˝o karakternek azonos a megjelenése. Karakterkód Minden karakterhez a karakterkészletb˝ol hozzárendelünk egy nem negatív egészet, így kapjuk annak kódját. Fontos megjegyezni, hogy ez a leképezés nem feltétlenül monoton. Karakterkódolás Olyan algoritmus, mely karakterkódokhoz oktettek2 sorozatát rendeli. Az alábbiakban egy szabványt teljesnek fogok nevezni, ha definiál karakterkészletet, karakterkódokat és karakterkódolást is. Az id˝ok során számos módszer alakult ki és terjedt el karakterek reprezentálására. Most áttekinteném a ma legszélesebb körben használatosakat.
2.1.1.
ASCII
Ebben a teljes szabványban a használható karakterek halmaza az angol ábécé bet˝uin kívül csak néhány speciális szimbólumból és vezérl˝okarakterekb˝ol áll. A karakterkészlet összesen 128 jelet tartalmaz, melyekhez a kódolás pontosan egy oktettet rendel. A szabványt a digitális kommunikáció h˝oskorában fejlesztették ki, amikor az adatátviteli technológiák még korántsem voltak tökéletesek, így az oktettek tárolásakor fennmaradó 1 bitet adatátvitel-ellen˝orzési célokra tartották fent. Legnagyobb hiányossága, hogy nem támogatja az angol ábécén kívül es˝o nemzeti írásjelek használatát. El˝onye ugyanakkor, hogy e nyelv használatára hatékony eszközt ad.
2.1.2.
ISO–8859
Az ASCII kódolás gyengeségeinek kiküszöbölését megcélozva jött létre az ISO–8859 szabvány. Ez tekinthet˝o el˝odje egy b˝ovítésének, mely a korábban ellen˝orzésre fenntartott 8. bitet is tárolásra használja, így lehet˝ové téve 256 karakter tárolását. A nemzeti írásjelek sokfélesége miatt a szabvány 15 variánssal rendelkezik, attól függ˝oen, hogy a fennmaradt 128 helyre mely nemzet(ek) különleges szimbólumai kerülnek. Néhány példa: • 8859-1 (Latin-1) - nyugat-európai nyelvek támogatása 1
más néven glifa 0 és 255 közötti egész szám - használata bájt alapú számítógépek esetén kényelmes, ekkor ugyanis minden oktet egy bájton tárolódhat 2
9
• 8859-2 (Latin-2) - közép-európai nyelvek támogatása (magyar is) • 8859-3 (Latin-3) - dél-európai nyelvek támogatása A szabvány teljes és kompatibilis el˝odjével, ami ebben az eseteben azt jelenti, hogy az els˝o 128 egészhez rendelt karakterek megegyeznek mindkét karakterkódolási eljárásban. Hátrányai között említend˝o egyrészt, hogy használata többnyelv˝u környezetben nehézkes, másrészr˝ol több karakterkódolást is tartalmaz egyes nemzetek karaktereihez (8869-4 / 8859-13).
2.1.3.
Windows kódlapok
Látva az ASCII hiányosságait a Microsoft is elkészítette saját kiterjesztését. Ez a módszer is teljes, és felülr˝ol kompatibilis el˝odjével. Az el˝oz˝oekhez hasonlóan csak korlátozott mennyiség˝u karakter használatát teszi lehet˝ové. Az eljárás úgynevezett kódlapokból áll, amik arra szolgálnak hogy az ASCII-t egy vagy több nemzet karaktereivel kiegészítve karakterkészletet, karakterkódokat és kódolást definiáljanak. Ezek közül a magyar ábécét teljesen egészében tartalmazó kódlap a CP-1250, a nyugat európai pedig a CP-1252. Legnagyobb különbség a 8859 szériához képest, hogy míg az ISO szabvány a 128-159 értékekhez csak vezérl˝o karaktereket rendel, addig a kódlapok ezen értékeken nyomtatható karaktereket is tárolnak. Ezzel sajnos elveszti az ISO–8859 szabvánnyal való kompatibilitását. A kódlapok bár széles körben használtak – különösen Windows operációs rendszerekben – nem képezik egyetlen nemzetközi szabvány részét sem.
2.1.4.
Unicode
Az internet megjelenésével, el˝oretörésével szükségessé vált, hogy többnyelv˝u szövegeket is tudjunk kezelni. Erre az igényre nem adott kielégít˝o választ egyik korábbi eljárás sem, hiszen lehet˝oségeik csak néhány nemzet ábécéjének tárolására korlátozódtak. Válaszolva a kor kihívásaira jött létre a Universal Character Set3 , ami a karakterkészlet minden eleméhez karakterkódot rendel. A szabvány4 folyamatosan b˝ovül és mára már több tízezer jelet tartalmaz. A Unicode szabvány az UCS egy olyan kiterjesztése, mely karakterkódolást is definiál. Ez a kódolás eredetileg az ún. UCS-2 volt, ami fix 2 bájton tárolja a karaktereket. Kés˝obb a karakterkészlet b˝ovülése során ezt elvetették, és helyette 3 4
UCS - Általános Karakterkészlet ISO 10646
10
az alábbi négy UTF5 kódolási algoritmus valamelyike használandó. Itt fontos még megjegyezni, hogy az egyszer˝ubb implementáció miatt, létezik egy jól körülhatárolt részhalmaza az UCS-nek, amit BMP6 -nek nevezünk és a 0..FFFF hexadecimális tartományban vannak a kódjai. UTF-32 Minden karakterkód 4 byte-os egészként reprezentálódik, így a jelenleg a szabványba tartozó összes jelet egyszer˝uen tudjuk kezelni. Hatékonysága viszont messze nem kielégít˝o, hiszen ha csak egyszer˝u angol nyelv˝u szövegekkel dolgozunk, akkor a tárigénye négyszeres az ASCII-hoz képest. UTF-16 A korábban említett UCS-2 kódolás szuperhalmaza, ami azt jelenti, hogy csak a BMP-re korlátozva az UCS-2 kódolást, az UTF-16–ot kapjuk. Az UTF-32–t˝ol eltér˝oen ez egy változó hosszúságú kódolás: BMP-beli elemeket 2 byte-on míg a többieket 4 byte-on tárolja. UTF-8 Ez a kódolási eljárás kompatibilis az ASCII-val, tehát a 0..128 tartományba es˝o kódokat ugyanúgy tárolja mint el˝odje, viszont az e fölöttiekre egy kissé bonyolult, de tárolási értelemben hatékony változó hosszúságú leképezést alkalmaz. UTF-7 Olyan változó hosszúságú karakterkódolás, melyben minden karakterkód legalább egy, legfeljebb négy 0..128 tartományba tartozó oktettel van reprezentálva. Nem kompatibilis az ASCII-val.
2.2.
Természetes-nyelvi feldolgozás
A természetes-nyelvi feldolgozás7 , az informatika olyan résztudománya, mely természetes nyelvi jelenségeket, problémákat az informatikai oldaláról közelíti meg.8 A tudományág a mesterséges intelligencia kutatások és nyelvészet határterületén van. A kutatások alapvet˝oen négy területre bonthatóak. Egyrészt beszélhetünk nyelvi elemzésr˝ol és generálásról, másrészt pedig a feldolgozás tárgya lehet írott szöveg, vagy maga a beszéd. Egy ett˝ol részletesebb kategorizálást találhatunk a Számítógépes Nyelvészet[5] c. könyvben. 5
Universal Transformation Format Basic Multilingual Plane - Alapvet˝o Többnyelv˝u Karakterkészlet 7 szakirodalomban NLP - Natural Language Processing 8 http://www.aclweb.org/archive/misc/what.html
6
11
2.2.1.
Történet
A tudományág gyökerei a második világháború végéhez nyúlnak vissza, amikor is tudósok az akkori számítógépeket a kódtörésen kívül automatikus fordításra is megpróbálták felhasználni. A korai lelkesedésre jellemz˝o, hogy ez id˝oben számos kutatás indult a gépi fordítás témakörében. Ekkoriban sokan még azt az egyszer˝u nézetet vallották, hogy a nyelvek közötti egyetlen különbség a szókincsük és a mondatok szavainak sorrendje. Így az akkor született megoldások is csak valamiféle automatikus szótározó rendszerek lettek. Mint azt ma már tudjuk, ez az út hamarosan zsákutca lett. Az ezt követ˝o években a korai sikertelenség miatt visszaesett a számítógépes nyelvészet iránti érdekl˝odés. Ezt a negatív folyamatot er˝osítette az ALPAC9 1966–os éves jelentése, mely a gépi fordítás ideájának akkori megvalósulását kétségbevonta. Mindeközben 1957–ben megjelent Chomsky cikke a generatív nyelvtanokról, ami új megvilágításba helyezte a számítástudomány és a nyelvészet viszonyát. Mint említettem a ’70 években bár jelent˝osen csökkent az érdekl˝odés a téma iránt, de a kutatások teljes egészében nem álltak le. Az ekkoriban folyó tudományos munkák els˝osorban jelentés reprezentációra és a számítástudomány világába a korábbiaktól jobban illeszked˝o elméletek kidolgozására összpontosult. Az elméleti kutatások mellet számos kézzel fogható eredmény is született, úgymint az • ELIZA - az els˝o mesterséges beszélget˝orobot, • SHRDLU - egy olyan szerkezet, ami képes volt angol nyelv˝u utasítások megértésére (persze csak korlátozott módon). Az évtized végére és a ’80 évek derekára el˝otérbe került a természetes nyelvi generálás problémaköre is, mint például a nyelvi feldolgozás statisztikai oldalról való megközelítése is. Az elmúlt két évtizedben eddig soha nem látott növekedésnek indult a tudományterület. Ez valószín˝uleg a megnövekedett számítási kapacitásoknak, az Internet el˝oretörésének és a növekv˝o mennyiség˝u elektronikus dokumentumhalmaznak köszönhet˝o. A ma használt szoftverek nagy részének már szerves alkotóját képezik nyelvi megoldások. Úgymint pl.: • Google keres˝o – automatikus szótövezés, szinonima keresés, 9
Automated Language Processing Advisory Committee of the National Academy of Science - National Research Council
12
• Microsoft Office irodai programcsalád – nyelvhelyesség ellenörz˝o, szinonima szótár, • Mozilla Firefox böngész˝o – helyesírás ellen˝orz˝o, • Webforditás.hu – online, többnyelv˝u gépi fordító rendszer, A Magyarországon folyó kutatások a ’90 évek elején kaptak nagy lendület, amikor is Dr. Prószéky Gábor vezetésével megalakult a MorphoLogic. A cég a kezdetekt˝ol fogva nyelvészet kutatásokat és azok gyakorlati alkalmazásait t˝uzte ki célul. Azóta számos, nap mint nap használt szoftver nyelvi modulját készítették el, továbbá jelent˝os eredményeket értek el a gépi fordítás és a nyelvi elemzés területen.
2.2.2.
Alkalmazások
Ma az informatika területén gyakorlatilag minden olyan feladatnak, problémának, mely szövegekkel dolgozik, célja lehet valamilyen NLP eszköz alkalmazása. A leggyakoribbak ezek közül: • Információ visszakeresési alkalmazások • Adatbányászati feladatok • Kérdés-válasz rendszerek • Szöveg kivonatolás • Gépi fordítás • Párbeszédes rendszerek
2.3.
Keres˝orendszerek
Napjainkban mind többször találkozunk olyan rendszerekkel, programokkal, melyek dokumentumok halmazához férnek hozzá, és ezekhez biztosítanak keresési szolgáltatást. Ilyen esetekben a felhasználótól a rendszer egy keres˝okifejezést vár, melyet értelmezve létrehozza az eredmények listáját. Ez a lista dokumentumhivatkozásokat tartalmaz, melyek tartalma a felhasználó szempontjából relevánsnak mondhatóak. Egy keres˝orendszer vázlatos felépítése látható a 2.1 ábrán. A vázolt feladat megoldására a legegyszer˝ubb módszer
13
Keres˝okifejezés
Dokumentumtár és keres˝ogép
Dokumentumlista
2.1. ábra. Keres˝orendszer egyszer˝usített felépítése
az, hogy ha a lekérdezést a rendszer egyszer˝u string keres˝o algoritmussal próbálja megoldani végigpásztázva a dokumentumtárat. Ennek id˝oigénye nyilván arányos a tár méretével, ami hatékonyság szempontjából nagyon rossz. Ehelyett az adathalmazt célszer˝u el˝o-feldolgozni Indexelésnek hívjuk azt a folyamatot, amikor a keres˝orendszer a rendelkezésére álló dokumentumok halmazából létrehoz egy ún. indexet, mely tartalmaz kulcsszavakat és dokumentumhivatkozásokat is. Alapvet˝oen kétféle indexet különböztetünk meg: • Kulcsszóindexet, mely létrehozásakor a dokumentumokhoz párosított kulcsszavakat tároljuk az adatbázisban. • Tartalomindexet, melyet úgy készítünk, hogy az összes feldolgozandó fájlt végigolvassuk, eközben minden egyes dokumentumnál összegy˝ujtjük a rá jellemz˝o szavak, kifejezések halmazát, majd ezeket tároljuk az adatbázisban. A gyakorlatban az a jellemz˝o, hogy a két módszert együttesen alkalmazzák. A feldolgozandó dokumentumok halmazát megkaphatjuk a felhasználótól, de gyakori az is, hogy a keres˝orendszer egy modulja végzi ennek létrehozását. Ez az alrendszer egy kezdeti dokumentumhalmazban található hivatkozásokat rekurzívan végigjárva igyekszik b˝ovíteni azt. Az ilyen alprogramokat, (web)crawler-nek, spider-nek vagy robot-nak hívjuk. Mint azt korábban említettem egy keres˝orendszeren lekérdezéseket futtatni keres˝okifejezésekkel lehet. Egy ilyen kifejezés általában nyelvi szavak és speciális karaktersorozatok kombinációja. Az hogy a rendszer milyen típusú kifejezéseket támogat jól jellemzi m˝uködését, használhatóságát: • Használhatunk-e reguláris kifejezéseket? • Szótövezést használ-e? • Korlátozhatjuk-e a keresést valamilyen el˝ore megadott típusú adatokra? (mez˝ok használata) 14
• Sz˝ukíthetjük-e a keresést dátumra, nyelvre, területre? • Használhatunk-e logikai m˝uveleteket? (Pl.:AND,OR,NOT. . . ) • Milyen egyéb m˝uveleteket használhatunk még? (Pl.:NEAR) Ezekt˝ol kicsit elrugaszkodva, feltehetjük még a kérdést, hogy a lekérdez˝onyelv támogatja-e természetes nyelvi kérdések használatát. Használat alatt itt azt értem, hogy a program megpróbálja értelmezni a kérdést, és arra választ találva létrehozni a találati listát. Egy lekérdezés futtatása után a találatok általában rendezett listában jelennek meg. Sok esetben az alkalmazás kigy˝ujti a keres˝okifejezéshez legszorosabban köt˝od˝o10 szavakat is, így tovább finomíthatjuk a találati listánkat. Keres˝ok teljesítményét, hasznosságát több szempont szerint szokás mérni: 1. számítási teljesítmény szerint: (a) indexelési id˝oben óránként feldolgozott adatmennyiség illetve az ehhez szükséges memória mérésével, (b) index mérete a tárolt adat mennyiségének viszonyában. (c) lekérdezés során az eredménylista elkészítéséhez szükséges átlagos id˝o alapján, 2. indexelt oldalak mennyisége alapján, 3. találati lista „alkalmassága” alapján. A találati lista értékelésér˝ol a 5. fejezetben írok részletesebben. Újragondolva a keres˝orendszer m˝uködését, tovább finomíthatjuk a keres˝orendszer m˝uködését bemutató ábrát. Ezt láthatjuk a 2.2 ábrán.
2.3.1.
Internetes keres˝ok története
Az internet h˝oskorában[13] még csak néhány számítógép volt hálózatba kapcsolva, így ezek nyilvántartása nem okozott különösebb nehézséget. Ezt a feladatot akkoriban Tim Berners-Lee látta el a CERNS szerverét használva. Aztán 1992–ben érkezett el az az id˝oszak, amikor a hálózaton lév˝o gépeket már nehézkessé vált nyilvántartani. 10
a találatokban a kifejezések egy környezetében leggyakrabban el˝oforduló szavak
15
Robot
új dokumentum keres˝okifejezés
dokumentumlista Indexkészít˝o gép
Keres˝ogép
Index
Dokumentumtár
2.2. ábra. Keres˝orendszer felépítése
A következ˝o mérföldk˝o a történetben Matthew Gray alkalmazása 1993–ból, ami a világ els˝o mai értelemben vett, webrobot-a. Ezzel célja a Web méretének meghatározása volt, amit 1995–ig sikeresen el is látott Az els˝o keres˝orendszernek az Aliweb-et nevezhetjük, mely 1993 novemberében t˝unt fel. Ez az alkalmazás még csak azt tette lehet˝ové, hogy a weboldalak gazdái metainformációkat töltsenek fel honlapjukkal kapcsolatban a rendszerbe, amin utána a felhasználók kereséseket futtathattak. Ugyanezen év decemberében jelent meg a JumpStation nev˝u alkalmazás, aminek a m˝uködési elve a mai napig is meghatározó (robot-indexelés-keresés). Sajnos ez még nem volt képes a dokumentumokban való keresésre, csak annak címében tárolt információkkal tudott dolgozni. Az egyik els˝o teljes tudású11 keres˝o a WebCrawler volt. Ezzel egy id˝oben jelent meg 11
a szó azon értelmében, hogy a rendszer rendelkezik robottal, indexszel, formon keresztül végezhetünk lekéréseket és a dokumentumok teljes szövegében is képes keresni
16
a Lycos, mely már üzleti sikereket is elért. Az ezt követ˝o években számos keres˝o jelent meg a piacon és tett nagy népszer˝uségre szert: Magellan, Excite, Infoseek, Inktomi, Altavista. . . Mindezek között mégis a Yahoo! volt a legnépszer˝ubb, melynek m˝uködése alapvet˝oen különbözött a többit˝ol. A Yahoo! a saját ún. web directory-jában végezte a kereséseket, ugyanakkor lehet˝oséget biztosított ennek böngészésére is. Az igazi áttörést a versenyben a Google hozta 2000 tájékán, az új eddigiekt˝ol különböz˝o relevancia meghatározási algoritmusával, a Pagerankkal. Ez a módszer azon alapszik, hogy a weboldalra mutató küls˝o hivatkozások számával iteratív módon próbáljuk becsülni a felhasználó oldalra jutásának valószín˝uségét, majd ezt felhasználva rendezzük a találati oldalakat. Ebben az id˝oben a Yahoo! az Inktomi technológiáját használta, majd csak 2003–ban váltott a Google-éra. 2004–t˝ol pedig saját fejlesztés˝u keres˝omotorral m˝uködött a Yahoo! Search, egészen a 2009–es Microsofttal kötött szerz˝odésig. 1998–ban indult útnak a Microsoft els˝o keres˝oje az MSN Search, amely akkor még szintén az Inktomi technológiáját használta. Kés˝obb a redmondi vállalat az Altavista-ét liszenszelte, majd 2004–ben állt el˝o sajátjával. Az óriásvállalat 2009–ben indította útjára megújított keres˝ojét a Bing-et.
2.3.2.
Vertikális keresés
A történeti áttekintésben sorra vett keres˝orendszerek többsége abból a célból született, hogy az interneten teljes tartalmán biztosítson hatékony keresést. Egy ilyen általános célú keres˝o sok esetben nem m˝uködik hatékonyan, nem ad releváns találatokat. Például, ha csak valamely tudományterület anyagai között szeretnénk keresést végezni, akkor egy általános felhasználású keres˝o, sok olyan találatot adhat, melyek nem relevánsak. Erre a problémára adott válasza a kor informatikusainak a vertikális keresés módszerének bevezetése. Vertikális keresésr˝ol beszélünk akkor, ha a keresés az internet egy szeletén, vagy valamilyen kritérium mentén sz˝ukített dokumentumhalmazon történik. Ez a kritérium leggyakrabban egy témakör, de lehet fájlformátum, dokumentumtípus, stb. is. Napjainkban egyre több vertikális keres˝o szolgáltatás jelenik meg a weben: • Google Books - digitalizált könyvek tartalmában való keresés • Google Scholar - tudományos cikkek közötti keresés • Árukeres˝o - kereskedelmi termékek közti keres˝o • Budapest Explorer - szórakozóhely keres˝o 17
• Használtautó.hu - használt autók keres˝oje • Kayak.com - utazás keres˝o • HealthMash - egészségügyi keres˝o
2.4.
Nyelvi eszközök keres˝orendszerekben
Ahogy azt a 2.2.2 részben is írtam, nyelvi eszközök informatikai alkalmazások számos területén jól használhatók. Most szeretnék rövid áttekintést adni arról, hogy melyek azok a módszerek, amelyek leggyakrabban megjelennek egy-egy keres˝orendszerben. Mint azt láthattuk az internet h˝oskorában a keres˝ok sokszor csak a fájlok címében, esetleg a hozzájuk kapcsolt metaadatok között tudtak keresni. A WebCrawler óta már a fájlok tartalmát is látjuk. Ez a korábbiakhoz képest nagy el˝orelépés, de egy átlagos felhasználónak még mindig nehéz dolga akad, egy olyan csekély tudású rendszerben, ami esetleg csak string-egyez˝oség alapján ad találatokat. Gondoljunk bele, sokszor mennyire nehéz jó keres˝okifejezést találni, hogy az eredmények közt szerepeljen a kívánt információ. Ráadásul számos agglutináló12 nyelv esetén a feladat még nehezebb, mert ekkor nem elég megtalálni a használandó kulcsszavakat, de a keresést úgy érdemes futtatni, hogy azok toldalékolt alakjaira is rábukkanhassunk. Ezt feladatot szokás szótövezéssel megoldani, mégpedig a következ˝o módon: indexeléskor a rendszer a szavakat, kifejezéseket tövezett alakban tárolja, majd kereséskor a kifejezésben is megkeresi a szavak tövét, végül az így kapott kulcsszavakkal történik a keresés az új indexen. Hasznos funkció még, hogy ha a keres˝orendszer - a felhasználó kérésére - lehet˝oséget biztosít szinonimák keresésére is. Ez a gyakorlatban azt jelenti, hogy a lekérdezés futtatásakor megadott keres˝okifejezésben, a megjelölt szavak szinonimáit tartalmazó dokumentumok is megjelenhetnek a találati listában. Angol nyelvterületeken jelent˝os eredményeket[2] értek még el szókapcsolatok statisztikai felismerésének használatával. A módszer általában a következ˝o: a dokumentumtár dokumentumait megvizsgálva kigy˝ujtjük azon szó-párakat, melyek nem tartalmaznak tiltólistás szót, majd a leggyakoribbakat felhasználjuk indexelésre is. Így tároljuk azokat a kifejezéseket, melyekr˝ol azt feltételezhetjük, hogy kereséskor gyakran el˝ofordulnak, ezzel segítve a nagyobb találati pontosságot. Ezen módszernél az igazi nehézség az, hogy tudnunk kell kezelni, megkülönböztetni olyan keres˝okifejezéseket, melyek a szóösszetétel egészére vonatkoznak, csak egy elemére, vagy egyikre sem. Például a „Nobel-díj” 12
toldalékokat halmozó
18
kifejezés esetén, mind a „Nobel”, mind a „díj”, mind pedig a „Nobel-díj” keres˝okifejezéseket jónak gondoljuk, míg a „New York” városnév esetén, csak a „New York”-ot egyben tartalmazó kifejezésekre szeretnék, ha megjelenne a találatok között az eredeti összetételt tartalmazó dokumentum. Számos nyelv, köztük a magyar is, képes összetett szavak képzésére. Ezeket megfigyelve felmerülhet a kérdés, hogy vajon az összetételek szétválasztásával és egyenkénti tárolásával lehetséges-e növelni a találati pontosságot. A válasz itt sem egyértelm˝u, hiszen szétválasztással az eredeti szó értelme elveszhet, jelent˝osen módosulhat. Egyszer˝u és nem is kifejezetten NLP technika, de gyakran alkalmazott módszer, hogy bet˝uszavak és rövidítések felismerésére tesznek kísérletet. Ezt általában szótárakkal valósítják meg. Nyilván nehéz általános, teljes szótárakat készíteni, viszont vertikális keres˝orendszereknél, ahol sz˝ukebb témájú dokumentumokkal dolgozunk, érhetünk el jobb eredményeket. Jelentés egyértelm˝usítési módszerek célja, hogy a többértelm˝u szavak szövegkörnyezetbeni jelentését meghatározzuk, és tároljuk. Keresésnél pedig lehet˝oséget biztosítsunk az ezek közti választásra. Ezekhez általában ún WordNet13 -et használnak. Gyakori az is, hogy a lekérdezés elindítás után a rendszer további kapcsolódó kulcsszavakat ajánl fel, melyekkel a találati lista mérete csökkenthet˝o. Ezt általában úgy valósítják meg, hogy az indexelt dokumentumokban leggyakrabban el˝oforduló szókapcsolatokat tárolják, majd kereséskor ezt használják fel a javaslatokhoz. Manapság egyre inkább el˝otérbe kerülnek, olyan technológiák, melyek az indexelt dokumentumokhoz, automatikusan metainformációkat rendelnek. Leggyakrabban a következ˝o tulajdonságokat használják: helyszín, id˝opont, valamilyen mennyiség (ár, súly mérték, hossz mérték). Ezen mez˝ok tárolásával kereshet˝ové válnak az említett tulajdonságok, ami ismét csak egy pontosabb találati listához vezethet. Mostanában el˝otérbe kerültek olyan szolgáltatások, melyek nyelvfüggetlenül tudnak keresést végezni. Ekkor szükséges, hogy a rendszer többféle nyelv˝u dokumentumokat is indexeljen. Egy ilyen alkalmazás a következ˝o módon m˝uködhet: 1. indexeléskor minden fájlhoz tárolják annak nyelvét (nyelveit) 2. keres˝okifejezés fordítása több nyelvre 3. keresés futtatása az összes dokumentumon 4. találati lista dokumentumainak forrásnyelvre való fordítása 13
„F˝oneveket, igéket, mellékneveket és határozószókat szervez kognitív szinonima halmazokba (synsetek), amelyeknek mindegyike eltér˝o fogalmat fejez ki.”
19
Ilyen például a Google valamint a Webfordítás. Talán a legösszetettebb szolgáltatást azok a keres˝ok nyújtják, melyek a felhasználó áltat megfogalmazott kérdésekre próbálnak választ találni az eredményhalmaz generálásakor. Ez a feladat igen bonyolult, hiszen nem elég a kérdésben megtalálni a kulcsszavakat, a kérdést meg kell érteni a gépnek, hogy válaszolni tudjon rá. Erre tett kísérletet például a Powerset keres˝o, mely tudásbázisként az angol nyelv˝u Wikipédia anyagát használja.
20
3. fejezet A megfelel˝o keres˝orendszer választása A dolgozat megírásával, célom annak megvizsgálása volt, hogy milyen lehet˝oségek vannak nyelvi eszközök használatára keres˝orendszerekben. Ennek gyakorlati aspektusait is szerettem volna megtapasztalni, ezért munkám végén tervem, hogy egy kész rendszeren méréseket végezzek az eszközök hatékonyságát illet˝oen. A gyakorlati oldalt illet˝oen alapvet˝oen három út állt el˝ottem: • Közismert keres˝orendszer felhasználása, kiegészítése. Pl.: Google, Bing . . . • Nyílt forráskódú keres˝orendszer kiegészítése. • Saját rendszer fejlesztése az alapoktól. Egy teljesen új rendszer fejlesztése túlmutatna e dolgozat céljain, lehet˝oségein. Közismert keres˝o választása és felhasználása nehéz feladat, mert ezek a rendszerek a legtöbb esetben zárt forráskódúak és alkalmazás-programozási felületük is nagyon korlátozott. Így úgy döntöttem, hogy a nyílt forráskódú rendszerek felé fordulok.
3.1.
Szempontok
Miel˝ott elkezdtem a volna a keres˝ok közötti böngészést és azok tanulmányozását, megfogalmaztam néhány olyan szempontot, melyekr˝ol azt gondolom, szükségesek ahhoz, hogy munkámban bármiféle sikert is érjek el. • A használandó alkalmazás C++ vagy JAVA nyelven íródjon mivel ezekben szereztem az elmúlt években jártasságot, és a dolgozat készítése során sokkal inkább a
21
feladatra, mint egy új nyelv elsajátítására szerettem volna koncentrálni. Ezt a szempontot er˝osítette az is, hogy a MorphoLogictól kapott nyelvi eszközök is C nyelv˝u API1 -val rendelkeznek. • Szerettem volna, ha a keres˝orendszernek van egy jól meghatározott alkalmazásprogramozási felülete, hogy a fejlesztés során megjelen˝o esetleges új verziók ne akadályozzák a munkámat. Azért is tartom lényegesnek ezt a kérdést, mert ennek hiánya esetén a kód b˝ovítése nehézkes, a vártnál sokkal több id˝ot igényelhet. • Elvártam a programtól, hogy létezzen stabil verziója, és legyen mögötte egy olyan fejleszt˝oi csoport, akik folyamatosan karbantartják. • El˝onyt élveztek a kiválasztás során azok a programok, melyek már rendelkeztek valamilyen természetes nyelvi feldolgozó eszközzel. Úgy gondolom, hogyha egy keres˝oben például már van szótövez˝o, akkor egy új tövez˝o integrálásához a létez˝o rendszer implementációja alapján találok útmutatást. • A fejlesztéshez szükséges, hogy a projekt jól dokumentált legyen. • Fontos, hogy a kiválasztott rendszer jól kezelje a magyar nyelven írott szövegeket, ehhez pedig az szükséges, hogy tudjon kezelni az alábbi karakterkódolások közül legalább egyet: – UTF valamelyik típusa, els˝osorban UTF-8 – ISO 8859-2 – WINDOWS CP-1250
3.2.
Vizsgált keres˝orendszerek
Munkám során igyekeztem a lehet˝o legtöbb rendszert górcs˝o alá vetni. Ezek felkutatásához els˝osorban az alábbi dokumentumokat vettem alapul: • Emmanuel Eckard és Jean-Cédric Chappelierés - Free Software for research in Information Retrieval and Textual Clustering[4] • Christian Middleton és Ricardo Baeza-Yates - A Comparison of Open Source Search Engines[9] 1
Application Programming Interface - Alkalmazás-programozási felület
22
3.2.1.
OpenFTS
Az OpenFTS2 fejlesztését már 5 éve leállították, továbbá a felhasználói fórumon kívül nem sok dokumentációt találtam. Egységes programozói felületet sem találtam az eszközhöz, így mindezek tekintetében nem is folytattam a vizsgálatot.
3.2.2.
Terrier
Ez az keres˝orendszer JAVA nyelven íródott, b˝ovíthet˝oségét biztosíték a jól dokumentált API. A programozási nyelv garantálja az UTF-8 támogatást, tehát a magyar nyelvi szövegek kezelésével sincs probléma. Indexelés folyamán a rendszer egy ún. pipeline3 -on keresztül dolgozza fel az indexelend˝o kifejezéseket. Fejlesztése folyamatos, a támogatás biztosított. Szótövez˝o használatára - az említett cs˝ovezeték kialakítás miatt - ad lehet˝oséget, de más nyelvi modulokat nem használ.
3.2.3.
Lucene
Lucene egy teljes érték˝u keres˝o, mely JAVA nyelven íródott. A Terrierhez hasonlóan a magyar nyelv írásjeleit is tökéletesen kezeli. Jól dokumentált alkalmazás-programozási felülettel rendelkezik. Legf˝obb er˝ossége, hogy jól skálázható és nagy teljesítmény˝u indexel˝o program biztosítja az adatok gyors feldolgozását. Képes dátumok szerinti keresésre, mez˝ok kezelésére, egyszerre több indexben való keresésre. Többféle lekérdezés típust támogat. A projekt rendkívül jól támogatott, dokumentált. Nyelvi eszközök kapcsán az mondható el róla, hogy többféle szótövez˝ot és azok integrálását támogatja.
3.2.4.
Datapark Search Engine
A Datapark Search egy C nyelven íródott keres˝o, melynek API-ja csak kis mértékben enged beavatkozni a rendszer m˝uködésébe. Ezt is els˝osorban olyan esetekben használják, amikor a szoftvert egy komplex programba, vagy weboldalba építik be. Némi dokumentáció is fellelhet˝o a világhálón, de ez korántsem teljes. Több karakterkészletet is támogat, viszont nyelvi eszközökkel csak nehézkesen gyarapítható. Szótövezés csak Aspell illetve 2
Open Source Full Text Search engine cs˝ovezeték - mint fogalmat metaforikusan használják a számítástechnikában akkor, amikor több program láncba való összekapcsolása történik. Ilyenkor az egyik elem kimenete a másik elem bemenetére kerül. 3
23
Ispell programokon keresztül valósítható meg, illetve szinonimák és mozaikszavak felismeréséhez csak szótárfájlok használatával van lehet˝oség.
3.2.5.
Egothor
Az Egothor egy 2006–ban készült nagy teljesítmény˝u keres˝orendszer. A rendszer motorját újratervezik és újraírják. A projekt dokumentáltsága olyannyira nem kielégít˝o, hogy nyelvi eszközökr˝ol csakúgy mint API-ról említést sem találtam. Így ezt a rendszert is idejekorán elvetettem.
3.2.6.
Xapian
A Xapian egy olyan eszközkészlet, melyet teljes egészében C++-ban írtak, de használható több más népszer˝u programozási nyelvvel, úgymint PERL, Python, PHP, JAVA, C#. . . Egy ráépül˝o népszer˝u keres˝orendszer az Omega, mellyel együtt számos fájlformátum indexelésére képesek. Továbbá jó néhány integrált nyelvi eszközzel rendelkezik, úgymint pl. szótövez˝o (magyar nyelv˝u is!), szinonima használat keresés közben. Képes még több adatbázis egyidej˝u indexként való használatára. A projekt jól dokumentált és folyamatosan karbantartott. Sajnos ennek az API-ját is úgy tervezték, készítették, hogy els˝osorban a program beágyazását tegye lehet˝ové, nem pedig a b˝ovítését.
3.2.7.
ht://Dig
A keres˝o több alprojektb˝ol áll, melyek fejlesztése 2002–ben abbamaradt. A rendszer amúgy angol nyelv˝u szavak szótövezését és szinonimák használatát is támogatja. Els˝osorban Internet oldalak keresésére készítették. Alkalmazás-programozási felületr˝ol nem találtam információt.
3.2.8.
Lemur/Indri
A Lemur eszközkészlet a Carnegie Mellon University és a University of Massachusetts támogatásával készült. Céljuk egy olyan keretrendszer létrehozása volt, mely nyelvmodellezési és adatbányászati kutatásokhoz jól használható. A program C++ nyelven íródott, de rendelkezik JAVA, PHP, és C# API-val is. A projekt több éves múltra tekint vissza, és félévente új kiadásokkal jelentkezik. A Lemur többféle dokumentum típus indexelését támogatja: HTML, XML, PDF, Szöveges fájl, Microsoft Word, Microsoft PowerPoint. Az angol nyelvi szövegeken kívül kínait és arabot is támogat, továbbá beépített angol 24
szótövez˝ovel és mozaikszó felismer˝ovel is rendelkezik. A rendszer a dokumentumok feldolgozását pipeline-szer˝uen végzi, képes több indexfájl egyidej˝u használatára. Beépített nyelvi eszközei: angol nyelv˝u szótövez˝o (2 db), arab nyelv˝u tövez˝o, bet˝uszó felismerés és stopword4 támogatás. Az Indri egy olyan keres˝orendszer, mely a Lemur eszközkészletére épül. A fentieken kívül fontos tulajdonsága, hogy támogatja az UTF-8 kódolású dokumentumokat is. A keres˝o rendelkezik még több fajta grafikus felhasználói felülettel. A projekt példákkal illusztrált, jól használható dokumentációval van ellátva.
A fentebb részletezett szempontok alapján az Indri keres˝orendszer t˝unt a legjobb választásnak, így a továbbikban ennek részletes m˝uködését vizsgálom meg.
3.3.
A Lemur és az Indri muködése ˝
A fejlesztés fázisa alatt a programcsomag 4.8-as verziója volt elérhet˝o, ezért ezzel foglalkozom5 . A Lemur eszközkészletet abból a célból hozták létre, hogy el˝osegítse információ visszakeresési (IR6 ) és nyelvmodellezési feladatok kutatását. A rendszer[7] alapja egy olyan architektúra, mely támogatja a következ˝o technológiákat: • ad-hoc és elosztott lekérdezések futtatása • nyelvek közötti lekérdezések futtatása • strukturált lekérdezések futtatása • mez˝o szerinti sz˝urések használata • dokumentum kategorizálás • összefoglalás készítés Az Indri eredetileg önálló keres˝orendszerként indult, majd az évek során a fejleszt˝ok beolvasztották a Lemur projektbe. Jelenleg az Indri nagy részben a Lemurra épül, bár 4
tiltólistás szavak - olyan szavak halmaza, melyek az indexelés és keresés szempontjából nem rendelkeznek releváns információ tartalommal 5 A dolgozat írása során jelentek meg újabb verziók is. 6 Infomration Retrival
25
nem támogatja, nem használja annak minden funkcióját, de számos új eszközzel egészíti ki. Ezek közül is talán a legfontosabb, hogy képes mez˝oket és metainformációkat7 kezelni és UTF-8 kódolással készült dokumentumokat használni. Mint a legtöbb keres˝orendszer, az Indri is tartalmaz indexel˝o, lekérdez˝o és robot alkalmazást. Ezeken kívül számos egyéb kisebb alprogram is a fejleszt˝ok, felhasználók rendelkezésére áll. Az alábbiakban részletesen ismertetem ezek m˝uködését, használatukat és ott ahol szükséges az alkalmazás-programozási felületet is. Általánosságban elmondható az Indri alprogramokról, hogy a felhasználóval való kommunikációra paraméter8 fájlokat használatnak, melyb˝ol kinyerik a futáshoz szükséges technikai információkat: mennyi memóriát használhat, dokumentumtár helye, szótövez˝o típusa stb.
3.3.1.
Indexelés
A Lemur projekt alprogramjai alapvet˝oen két féle index készítésére, használatára képesek. Ezek a következ˝ok: KeyFile Index, Indri Index. A két index típus közötti alapvet˝o különbségeket az 3.1 táblázatba gy˝ujtöttem össze. A projekt több alkalmazást is tartalmaz, melyek az indexelés fázisához kapcsolódnak. BuildIndex A Lemur alapértelmezett indexel˝o alkalmazása. Egyszer˝u szöveges fájlok feldolgozására alkalmas. Mez˝ok és metaadatok indexelését nem támogatja. IndriBuildIndex Az Indri alapértelmezett indexkészít˝o alkalmazása. Az Indri alkalmazás többi alprogramja, csak az ez által készített indexel dolgozik. Az alprogram képes feldolgozni többek közt PDF, DOC, PPT kiterjesztés˝u fájlokat is. Mez˝ok és metaadatok feldolgozására is fel van készítve. BuildPropIndex Az alprogram egy olyan indexet készít a rendelkezésre álló dokumentumok halmazából, melyben a szavakhoz, termekhez tulajdonságokat, metainformációt is rendelhetünk. BuildDocMgr Dokumentumkezel˝ot készít˝o alkalmazás. A gyakorlatban ez azt jelenti, hogy az indexelt dokumentumokat kés˝obbiekben az így készített adatbázison keresztül lehet elérni. 7
A fejleszt˝ok terminológiája szerint a mez˝ok a szövegben fellelhet˝o kiemelt információk, melyeket akár lekérdezések futtatásakor is igénybe vehetünk. Pl.:dátumok, nevek, helyszínek. . . Míg a metainformációkat tartalmazó mez˝ok, nem biztos, hogy láthatóak a szövegben, nem lehet az indexben tárolni o˝ ket mint kereshet˝o adatelemeket, de lekérdezéskor kinyerhet˝oek az adatbázisból. Pl.: URL, dokumentumsorszám. . . 8 A paramétere fájlok használatáról b˝ovebb információ: http://www.lemurproject.org/ doxygen/lemur/html/IndriParameters.html
26
3.1. táblázat. A Lemur index típusainak összehasonlítása Tulajdonság Keyfile Index Indri Index Tárolható dokumentumfor- TREC Text, TREC TREC Text, TREC mák Web, HTML, Szöveges Web, HTML, Szövefájl ges fájl, XML, PDF, MBox, Microsoft Word és PowerPoint Az index tárhely használata 1,2x 2x a dokumentumtár méretéhez képest Metaadatok használata igen igen Mez˝ok használata nem igen Létez˝o index b˝ovítése igen, de csak offline, igen, használat közben azaz ha éppen nincs is használatban Használható lekérdez˝onyel- InQuery Indri Query Language vek Helyettesít˝o karakterek nem igen használata (Pl.: *,?) Indexel˝o alprogramok BuildIndex IndriBuildIndex, BuildIndex Lekérdez˝o alprogramok RetEval IndriRunQuery, RetEval
A keres˝orendszer b˝ovítése során nyilván szükségem lesz egy indexel˝o alkalmazásra, és mivel ezt a munkát sem célom az alapoktól kezdeni, ezért közelebbr˝ol megvizsgálom a IndriBuildIndex alprogramot. El˝oször vegyük szemügyre, az alprogram API-ját, azt hogy milyen lehet˝oségeket kínál a fejleszt˝oknek. Az indexek kezelésére az API-ban az indri::api::IndexEnvironment osztály szolgál. Ennek m˝uveletei: • open(std::string &repositoryPath) – egy létez˝o index megnyitása • create(std::string &repositoryPath, IndexStatus *callback) – új index készítése • addFile(std::string &fileName) – egy fájl hozzáadása az indexhez (ez a fájl a függvény hívását követ˝oen feldolgozásra kerül) • addString(std::string &documentString, std::string &fileClass, std::vector
&metadata) – egy 27
string-ként tárolt dokumentum hozzáadása az indexhez (a dokumentum a függvény hívását követ˝oen feldolgozásra kerül) • addParsedDocument(indri::api::ParsedDocument *document) – egy már feldolgozott dokumentum hozzáadása az indexhez • setIndexedFields(std::vector<std::string> &fieldNames) – az indexelend˝o mez˝ok beállítását szolgáló függvény Látható, hogy az alkalmazásprogramozási felület nem sok hozzáférést enged az indexelés folyamatának bels˝o történéseihez. Így szükségesnek láttam, hogy a program egyes elemeit módosítva, nagyobb teret kapjak a nyelvi eszközök integrációjához. Ehhez jobban meg kellett ismernem a modul m˝uködését. Az IndriBuildIndex alkalmazást futtatva a következ˝o m˝uveletsor fut le: 1. A paraméter fájl beolvasása, feldolgozása. 2. Az index létrehozása, vagy ha már létezik, akkor megnyitása. 3. A dokumentumhalmaz állományainak egyenkénti, pipeline-szer˝u feldolgozása. (a) Fájl beolvasása. (b) Tokenizer9 meghívása a beolvasott dokumentumon. (c) Parser10 meghívása, a tokenekre bontott dokumentumon. (d) Transformation típusú objektumok meghívása az elemzett dokumentumon. Ebben a fázisban hajtódik végre például a szótövezés, dátumfeldolgozás, mez˝ok feldolgozása, tiltólistás szavak elhagyása, stb. 4. A teljesen feldolgozott adathalmaz tárolása az indexben. 5. Index bezárása. A fenitekb˝ol az látszik számomra, hogy ha egy új eszközt szeretnék a feldolgozási láncba beilleszteni, akkor, ahhoz a Transformation interfészt kell megvalósítanom, majd beillesztenem az indexelési pipelineba. 9 10
a bemeneti dokumentumot elemi egységekre ún. tokenekre bontja szintaktikai elemz˝o
28
3.3.2.
Lekérdezés
Már láttuk az indextípusok összehasonlításánál, hogy több lekérdez˝o alkalmazásunk is van, melyekhez más-más lekérdez˝onyelvet használhatunk. Az InQuery nyelvet használó alprogramok a ParseInQueryOp és a StructQueryEval, míg a RetEval és a IndriRunQuery az Indri Query Language-el dolgoznak. Ezeken az alkalmazásokon kívül lekérdezéseket futtathatunk még az alkalmazásprogramozási felületen keresztül és egy démon segítségével is. Mivel az Indri Query Language az InQuery nyelv egy kiterjesztése, így a továbbiakban ezt fogom használni. Most pedig megvizsgálom, milyen képességekkel rendelkezik. Az Indri Query Language egyik el˝onyös tulajdonsága, hogy automatikusan tövezi a keres˝okifejezés szavait, a választott indexnek megfelel˝oen. Ez azt jelenti, hogy ha egy saját szótövezést beépítettem az indexelés folyamatába, akkor az így létrehozott indexen futtatott lekérdezéseket is ez szótövez˝o fogja feldolgozni. Ezzel együtt a lekérdez˝onyelv, többféle operátort támogat, melyekkel pontosítható a találati lista. El˝oször is léteznek úgynevezett közelségi operátorok, melyekkel a kifejezésben megadott szavak egymástól számított távolságára11 adhatunk feltételeket. Pl.: #1(általános célú) – a két szó szomszédságára és sorrendjére adott feltétel. Használhatunk olyan kifejezéseket is, mellyel arra utasíthatjuk a lekérdez˝oprogramot, hogy a paraméterben kapott szavakat, tekintse rokon értelm˝u szavaknak, továbbá ezek között súlyozást is definiálhatunk.(#syn(...), {...}, <...>, #wsyn(...)) Lekérdezésekben helyettesít˝o karakterként *-ot használhatunk, melynek operátor párja a #wildcard(...). Mez˝okre sz˝urési lehet˝oséget is biztosít a nyelv. Ha például indexeléskor használtunk weight típusú mez˝ot, akkor az olyan dokumentumokat, melyekhez tárolt a rendszer ilyen típusú tulajdonságot, az #any(weight) operátorral tudjuk lekérdezni. Ha a mez˝o értékére is akarunk feltételt adni, arra a . operátort használjuk. Például ha a Erd˝os Pál dokumentumaira sz˝urnénk, – és indexeléskor az author mez˝ot is használtuk – akkor a #uw1(Erd˝ os Pál).author feltétellel tehetjük ezt meg. Úgynevezett számszer˝u12 mez˝oknél még több lehet˝oségünk van, ekkor ugyanis az értékre nemcsak egyenl˝oségi feltételt adhatunk, hanem relációs feltételekkel is élhetünk. A numeric típusú mez˝ok egy speciális fajtája használható dátum sz˝urésére is. Ezeken kívül használhatunk még logikai és súlyozható egyesít˝o13 operátorokat, és a dokumentumok közötti sz˝urésre, prioritások kezelésére is lehet˝oségünk van. Most pedig nézzük, hogyan történik egy a nyelvben meg11
két szó távolsága, úgy kapjuk, hogy ha a köztük lév˝o szavak számából levonunk egyet az alkotók terminológiájában numeric 13 két keres˝okifejezés összeolvasztására szolgál 12
29
fogalmazott kérés feldolgozása, kiértékelése. A lekérdezés folyamata 8 lépésb˝ol áll, melyet a 3.1 ábra[7] szemléltet. 1. Parser14 objektum létrehozása, mely megkezdni a felhasználó kérésének feldolgozását. Ez a lépés 3 részb˝ol áll: lexikális elemz˝o(k) létrehozása, szintaktikus elemz˝o(k) létrehozása, majd ezek egy objektumba zárása. 2. Szintaktikus elemzés: melynek során létrejön a szintaktikus fa. 3. Megszorítás a mez˝okre: ha a lekérdezésben valamilyen mez˝o(k)re van hivatkozás, akkor a szintaktikus fa felcímkéz˝odik, így a kés˝obbiekben a kiértékelés folyamán ezek megfelel˝o pontszámokat15 kapnak. 4. Azon ún. nyers16 csúcsok meghatározása a szintaktikus fában, melyek pontozhatóak. 5. Feldolgozatlan csúcsokhoz tartozó kifejezésekb˝ol statisztika készítése. 6. Csillapító paraméterek alkalmazása a fára. 7. A már feldolgozott kérés kiértékelés úgy történik, hogy az újonnan kapott fa leveleit átvizsgálva: az ún. Stopwords halmaz elemeit elhagyva, a fa leveleiben található szavakat tövezett formájával történik az indexben található dokumentumokkal való összevetés, majd pedig az eredményhalmaz létrehozása. 8. A találati lista sz˝ukítése és rendezése a pontok alapján.
3.3.3.
Egyéb alprogramok
Az eszközkészlet számos egyéb alprogramot is tartalmaz. Ezek közül számomra a következ˝ok fontosak: Daemon – megnyit egy Indri index fájlt, és lekérdezéseket futtató alkalmazások kéréseit szolgálja ki socketen keresztül. JAVA GUI – SWING alapú grafikus felület a lekérdez˝o és indexel˝o alkalmazásokhoz. PHP webes felület – PHP4 nyelven íródott grafikus felület, melyen keresztül lekérdezéseket hajthatunk végre. 14
szintaktikai elemz˝o ugyanis a találati lista elemeinek sorrendje a ún. pontok alapján kerül meghatározásra 16 feldolgozatlan 15
30
JSP webes felület – az el˝oz˝ohöz hasonló JSP technológiát használó webes interfész.
31
3.1. ábra. Indri Query Language egy kifejezésének feldolgozása 32
4. fejezet Nyelvi keres˝o létrehozása Ebben a részben áttekintem, hogy milyen új funkcionalitásokkal láttam el az Indrit, részletezem megvalósításukat és ezek korlátait. A fejlesztés során, sok esetben olyan döntéshelyzetbe kerültem, amikor több megoldás is jónak látszott, attól függ˝oen, hogy milyen korpusszal használjuk az alkalmazást. Ezért úgy döntöttem, hogy egy jól körülhatárolt témakör˝u szövegeken fogom futtatni az alkalmazást, így tudom majd ahhoz igazítani kiegészít˝o moduljaim egyes funkcionalitásait. Ezzel egy id˝oben konzulensemt˝ol, Dr. Prószéky Gábortól kaptam egy adatbázist, mely az Országgy˝uléseken elhangzott beszédeket tartalmazta. További munkáim alapját ez az anyag képezte.
4.1.
Szótövez˝o modul
Miel˝ott részletezném munkám technikai oldalát, kitérnék arra, hogy pontosan mit is jelent egy szó tövét meghatározni[6]. „A szót˝o-el˝oállítás vagy lemmatizálás olyan m˝uvelet, mely adott természetes nyelv (lehet˝oleg) minden szóalakjából el˝oállítja annak egyetlen tövét (szótári alakját, lemmáját). Ily módon a lemmatizálás a nyelv szóalakjait ekvivalenciaosztályokba sorolja, ahol az azonos t˝ore visszavezet˝o szóalakok tartoznak egy osztályba.” Sajnos ez az osztályokba sorolás mégsem tökéletes, különösen a magyar nyelvben, ahol a képz˝ok használata megsokszorozhatja a lehetséges tövek számát. Például az adósság szónál az els˝o szót˝o a adós lehetne, de fel kell ismernünk, hogy ez is egy képzett alak, így akár az adó vagy az ad is egy-egy szót˝o lehet. Másrészr˝ol az is el˝ofordulhat, hogy egy szó tövei egymástól nagyon eltér˝o jelentést hordoznak. Ilyenkor az ideális választás igazodik a szövegkörnyezethez. A modern keres˝orendszerek szerves részét képezik szótövez˝o algoritmusok, ez ért33
het˝o, hiszen jobban belegondolva, ezek nélkül rengeteg potenciálisan jónak mondható dokumentum kiesne a találati listából. Egy ilyen program létrehozása id˝oigényes, nehéz és mélyebb nyelvészeti ismereteket feltételez˝o feladat. Diplomamunkám célja alapvet˝oen keres˝orendszer fejlesztésére irányul, ezért egy nyelvészeti eszközöket tartalmazó modult kértem és kaptam a MorphoLogic Kft.-t˝ol. A továbbiakban ennek integrációjának részleteit írom le.
4.1.1.
Lemur, Indri
Els˝o ötletem az integrációval és a fejlesztéssel kapcsolatban az volt, hogy a Lemur eszközkészletet veszem munkám alapjául, és azt b˝ovítve haladok. Sajnos közelebbr˝ol vizsgálva a Lemurt rá kellet ébrednem, hogy bár többnyelv˝u környezethez fejlesztették mégsem támogatja a magyar nyelv egyes ékezetes magánhangzóinak használatát. Ez abból az egyszer˝u okból fakad, hogy a program indexel˝o részének Parser moduljai közt nincs olyan, ami a magyar nyelvvel kompatibilis karakterkódolást támogatna. Így újra kellett gondolnom a tervemet, és végül is az Indri kiegészítése mellett döntöttem. Szerencsére az említett keres˝o a dokumentumok bels˝o reprezentáláskor az UTF-8 karakter kódolási szabványt használja.
4.1.2.
Tövez˝o integrációja
A cégt˝ol kapott szótövez˝o az elemezend˝o karaktersorozatokat mindig valamely Windows kódlap karakterkódolása szerint értelmezik. Ezek közül a magyar írásjeleket tartalmazó a 852-es és 1250-es sorszámú. A 1250-es kódlap használata mellett döntöttem, mivel ez egy modernebb variánsa az 852-esnek. Az integrációhoz szükséges volt, hogy alkalmazzak egy karakterkonverziós lépést, mely az UTF-8 kódolással reprezentált stringeket CP-1250-es reprezentációra alakítja és vissza. Ehhez a konverzióhoz az iconv1 programkönyvtárat használtam. Mint korábban említettem, az Indri az indexelés folyamatában, a feldolgozandó dokumentumokat egy pipeline szer˝uen dolgozza fel. Ebben a folyamatban minden feldolgozó objektum a Transformation absztrakt osztály egy példánya. Így elég a 4.1 ábrán látható interfészt megvalósítani. A felsorolt m˝uveletekb˝ol egyedül a transform az ami igazán fontos, mert a többi m˝uvelet a pipeline elemeinek összekapcsolásáért felel˝os. Ennek a függvénynek az implementálásval lehet a paraméterként kapott dokumentum szavait egyenként feldolgozni. Az 1
http://www.gnu.org/software/libiconv/
34
indri::api::Transformation +handle(document:ParsedDocument*): void +setHandler(handler:ObjectHandler<ParsedDocument>&): void +-Transformation() +transform(document:ParsedDocument*): ParsedDocument* 4.1. ábra. A Transformation típus
általam megvalósított integráció a következ˝oképen m˝uködik: 1. üres2 term vagy szám esetén továbblép, hiszen ezek nem szavak 2. Humor tövez˝o meghívása az aktuális szóra 3. a szótövez˝ot˝ol kapott tövek közül az els˝o tárolása(ha létezik) Az Indri és ezzel együtt az általam készített továbbfejlesztése is alkalmas arra, hogy egy szóhoz, több tövet is tároljon. A megfelel˝o szót˝o megtalálása, mint korábban írtam, egyáltalán nem egyszer˝u feladat, és nem is képezi dolgozatom vizsgálódásának tárgyát, ezért szelekció nélkül a lemmatizáló modul által visszaadott els˝o tövet eltároltatom. A másik lehet˝oségem az lett volna, hogy minden szóhoz az összes szótövet tárolom, ezt viszont azért nem találtam praktikusnak (és vetettem el), mert lekérdezéskor túl nagy zajt okozhat a sok szót˝o.
4.2.
Tiltólistás szavak
A legtöbb keres˝orendszer az indexelés és lekérdezés folyamán bizonyos szavakat nem indexel, nem vesz figyelembe. Róluk azt mondjuk, hogy a Stopwords halmazba, más néven tiltólistás szavak halmazába tartoznak. Ezek egy adott nyelvben azon leggyakoribb szavak, melyek nem hordoznak jelent˝os információtartalmat és tipikusan: köt˝oszavak, nével˝ok, igeköt˝ok, határozószavak, névmások. Sok esetben ez a halmaz nem határozható meg egyértelm˝uen, így fontos, hogy az adott célra - különösen vertikális keresés esetén testreszabjuk, átgondoljuk, hogy mely szavakat szeretnék kihagyni az indexelés, lekérdezés folyamatából. 2
nulla hosszú string
35
4.2.1.
Stopword szurés ˝ az Indriben
A használt keres˝o két opciót is kínál a tiltólistás szavak sz˝urésére. Egyrészt lehet˝oségünk van az indexeléskor megadott paraméter fájl kiegészítésére, másrészt a feldolgozási lácba f˝uzhetünk egy saját készítés˝u Stopper típusú objektumot. Nyilvánvalóan a második opció szabadabb kezet ad a szavak sz˝urésében, de a legtöbb esetben elég a listás megoldás használata is.
4.2.2.
Szavak választása, megvalósítás
Mivel adatbázisom témái és nyelvezete elég jellegzetesek, úgy döntöttem, hogy a szövegekben található szavakból gyakorisági statisztikát készítek. Tehát megvizsgáltam, mik a legtöbbször el˝oforduló szavak, és ezek közül kiválasztottam azokat, amik megfelelnek a fent adott definíciónak. Ezekhez még hozzávettem egy az interneten fellelhet˝o3 általános magyar nyelv˝u stopword halmazt. Az így kapott szóhalmazt hozzáf˝uztem az paraméterfájl megfelel˝o szekciójához. A kiválasztott szavak jegyzéke a függelékben található.
4.3.
Dátumok használata
4.3.1.
Motiváció
Országgy˝ulési naplókban gyakoriak az utalások különböz˝o eseményekre, dátumokra. Másrészr˝ol minden lejegyzés egy adott nap felszólalásait tartalmazza. Látható hogy az egyes dokumentumok több id˝ohöz kapcsolódó információt is hordoznak. Így arra gondoltam, hogy nagy könnyebbség lenne a végfelhasználóknak, ha tudnának a dokumentumok között dátum szerinti kereséseket is végezni. Ugyanakkor tudom azt, hogy dátumokat a magyar nyelvben és különösen írásos szövegekben nagyon sokféleképpen lehet kifejezni. Így célom az volt, hogy készítend˝o modul m˝uködése testreszabható legyen, és a lehet˝o legtöbbféle formában megjelen˝o egységeket legyen képes felismerni, kereshet˝ové tenni.
4.3.2.
Dátumok kategorizálása
Ehhez el˝oször megvizsgáltam, hogy milyen típusú dátumok léteznek nyelvi szövegekben. 3
http://snowball.tartarus.org/algorithms/hungarian/stop.txt
36
Pontosság szerint: • évszázad pontos, pl.: XX. század, Kr.e. 3. sz. • évtized szerint pontos, pl.: kilencvenes évek • évre pontos, pl.: 1986 • hónap vagy évszak pontos, pl.: 1956 o˝ sze, 1848 márciusa • napra pontos, pl.: 2009. szeptember 1. • órára, percre, napszakra stb.-re pontos, pl.: 1986. április 30. reggele, 2009.09.01. 12:00 Környezetfügg˝oség szerint: • környezetfügg˝onek nevezek olyan dátumokat, melyek csak a szövegkörnyezetükben értelmezhet˝oek pl.: tegnap, el˝oz˝o héten • környezetfüggetlennek nevezek minden olyan dátumot, mely önmagában is egy id˝opontot jelöl, pl.: 1989, 1986.04.30.
4.3.3.
Dátumkezelés az Indriben
Az általam használt keres˝orendszer rendelkezik dátumok kezelésének képességével. Ez a funkció nem csak az index létrehozásakor elérhet˝o, hanem – ahogy arról a 3.3.2 részben is kitértem – lekérdezésekkor is kit˝un˝oen használható. Indexeléskor a rendszer olyan dátumokat képes tárolni az adatbázisban, amiket a felhasználó a feldolgozandó dokumentumban dátummez˝oként el˝ore jelzett. Ezek közül is csak azokat dolgozza fel, amik a következ˝o formában vannak megadva: • dd month yyyy • dd-MON-yy • dd-MON-yyyy • Month dd yyyy • mm/dd/yy • mm/dd/yyyy 37
Ahol a(z) • dd hónap egy napját jelöli, mely lehet egy vagy két számjegy˝u. • month kisbet˝us angolul írt hónapnév. • Month nagybet˝uvel kezd˝od˝o angolul írt hónapnév. • MON egy hónap angol nevévenk els˝o három bet˝uje. • mm egy hónap sorszámát jelöli. • yy két jegy˝u év jelölés, mely 1900-tól kezd˝od˝oen értelmez˝odik. • yyyy évet jelöl. Ezeket a speciális date típusú fieldeket, a feldolgozási láncban egy Transformation típusú objektum dolgozza fel, mégpedig úgy, hogy minden felismert dátumhoz hozzárendel egy egész számot. Ennek a megfeleltetésnek az alapja 1600 január elseje, aminek az indexben tárolt értéke 0. Minden ett˝ol eltér˝o dátum az azóta eltelt napok számával kerül tárolásra (negatív értékek is). Dokumentumok közti keresésnél úgy tudunk dátumokra sz˝urni, hogy ha a lekérdezésbe beillesztjük az alábbi operátorok egyikét: • #dateafter(D) – D utáni dátumokra illeszkedik • #datebefore(D) – D el˝otti dátumokra illeszkedik • #datebetween(DA DF) – DA és DF közé es˝o (szigorú értelemben) dátumokra illeszkedik • #dateequals(D) – D dátumra illeszkedik A D, DA és DF paraméterek az indexelésnél említett formában használhatóak. Ezekb˝ol látható, hogy a rendszer csak az el˝ore beégetett (angol nyelvterületen használt) dátumformákat képes kezelni. Ezért úgy döntöttem, hogy továbbfejlesztem a rendszert úgy, hogy az a lehet˝o legtöbb formájú dátumot tudja kezelni.
38
4.3.4.
Magyar nyelvu˝ dátumok kezelése
Úgy gondolom, hogy a dátumok kereshet˝ové tétele akkor használható egyszer˝uen, ha nem a felhasználónak kell az indexelend˝o dokumentumokban egyesével bejelölnie az általa dátumnak gondolt szövegrészeket. Ezért mindenképpen szerettem volna egy olyan eszközt is biztosítani, beépíteni a keres˝obe, ami a felhasználó helyett elvégzi ezt a feladatot. Mindezzel együtt, az alábbi két megoldási utat láttam: 1. A szövegfeldolgozási láncba beavatkozva, a szöveg tokenekre bontása el˝ott feldolgozni és felülírni a dokumentumot reprezentáló objektumot úgy, hogy az összes dátum kerüljön megjelölésre. A dátumok feldolgozását ezután egy általam készített modul végezné, ami az eredetit helyettesíti. 2. A feladat két részre (külön alkalmazásra) bontása. El˝oször a szöveges fájlokat tartalmát módosítanám, majd az el˝oz˝oekhez hasonlóan a dátumfeldolgozó modult cserélném le. Azt tapasztaltam, hogy az els˝o megoldási út, nem szerencsés, mivel módosítani egy fájl tartalmát, csak a szintaktikus elemz˝o után tudnám. Ez viszont azért problémás, mert az elemz˝o a beolvasás során az egyes termekhez, pozíciókat is rendel, és felülírva a tartalmat, a hivatkozások érvénytelenné válnának. A második út már nehézségek nélkül megvalósítható, viszont itt azzal a kényelmetlenséggel kell számolni, hogy a felhasználónak az indexelés el˝ott futtatnia kell egy el˝ofeldolgozó programot. Így a második út mellett döntöttem, tehát egy el˝ofeldolgozó programot, és egy dátumfeldolgozó modult készítettem. Figyelembe véve az Indri dátumfeldolgozását a dátumtípusok közül is csak azokkal tudtam foglalkozni, melyek legalább napra pontosak. Azzal a könnyítéssel is éltem még, hogy csak a környezetfüggetlen dátumokkal foglalkoztam, hiszen a környezetfügg˝oek értelmezése a szöveg mélyebb elemzését igényli. Ez pedig, indexelési id˝oben az Indrivel nem kivitelezhet˝o. A két részfeladatból az els˝o tehát az, hogy az annotáló program a felismert dátumokat a szövegben dátum mez˝okké alakítsa. Így például egy elvárt m˝uködés, hogy a 2009.10.01.-b˝ol 2009.10.01.-t készítsen. Az alkalmazás a dátumformákat egy konfigurációs fájlból4 olvassa. A megadható dátumformák halmaza, megegyezik az alábbi nyelv elemeivel. (Ahol a Σ ábécé a Unicode karakterkészletnek felel meg.) 4
A konfigurációs fájlról b˝ovebben a függelék megfelel˝o fejezetében írok.
39
hDatei→hForm1i|hForm2i|hForm3i|hForm4i|hForm5i|hForm6i hForm1i→hSepsihYearihSepsihMonthihSepsihDayihSepsi hForm2i→hSepsihYearihSepsihDayihSepsihMonthihSepsi hForm3i→hSepsihMonthihSepsihYearihSepsihDayihSepsi hForm4i→hSepsihMonthihSepsihDayihSepsihYearihSepsi hForm5i→hSepsihDayihSepsihMonthihSepsihYearihSepsi hForm6i→hSepsihDayihSepsihYearihSepsihMonthihSepsi hYeari→yyyy|yy hMonthi→mm|m|month|mon hDayi→ddd hSepsi→hSepsihSepi|hSepi hSepi→hAvailablei|ε hAvailablei→Σ \ hReservedi hReservedi→y|d|m|o|n|t|h
A program úgy dolgoz fel egy dátumformát, hogy reguláris kifejezéssé alakítja. Az így kapott új kifejezést, pedig már könny˝uszerrel használhatjuk a Boost Regex függvénykönyvtárral[1], melynek replace m˝uveletét felhasználva megtörténik a dokumentumszöveg módosítása. Jól látható, hogy a program lényegi része egy leképezés, mely a dátumnyelvb˝ol reguláris kifejezést készít. Ez a következ˝oképpen történik. yyyy→\d{4} yy→\d{2} mm→(01;02;03;04;05;06;07;08;09;10;11;12) m→(1;2;3;4;5;6;7;8;9;10;11;12) month→(január;. . .;december) mon→jan;. . .;dec dd→((0[1-9])|[12][0-9]|30|31) d→(([1-9])|[12][0-9]|30|31)
A második program, beépülve az Indri mez˝oket-feldolgozó folyamatába, dátum fieldeket dolgoz fel. Els˝o lépésként a kapott dátumban megpróbálja meghatározni az év, hónap, nap mez˝ok sorrendjét, ezek után 1600.01.01.-t˝ol számított egész számmá alakítja azt.
40
Fontos megjegyezni, hogy nem javasolt az olyan dátumformák megadása a konfigurációs fájlban, melyek a ütközhetnek. Két dátumformát ütköz˝onek nevezek, ha létezik olyan dátum, mely mindkét formának megfelel. Például: mm/dd/yy, dd/mm/yy és a hozzájuk tartozó dátum: 01/10/09. Ekkor ugyanis nem dönthet˝o el egyértelm˝uen, hogy pontosan milyen id˝opontot is jelöl a dátum.
4.3.5.
A megoldás korlátai
Ahogy korábban is írtam környezetfügg˝o és nem legalább napra pontos dátumokkal nem foglalkoztam. Ezeken kívül a dátumformák toldalékos alakjaival adódhat még problémája a programnak. Ha a megadott forma yyyy. month d. és a dátum 2009. január 11. de a szövegben úgy szerepel mint „2009. január 11-én”, akkor a ez indexel˝o nem dolgozza fel. Ennek kiküszöbölésére két út lehetséges. Az els˝o, hogy a szótövezést el˝obb használjuk, mint a dátumfelismerést, így minden dátumnak csak az eredeti alakjával kellene foglalkoznunk. Sajnos ez az Indri esetében ez kivitelezhetetlen, ugyanis a feldolgozási láncban a a mez˝ok feldolgozása, megel˝ozi a szótövezést. A másik járható út az, hogy a felhasználóban tudatosítjuk a rendszer korlátait, és ebben az esetben arra buzdítjuk, hogy egészítse ki a konfigurációs fájlt a példának megfelel˝o yyyy. month d- formával is.
4.4.
Mennyiségek használata
„A mennyiség egy mérés eredményére vonatkozó kifejezés, mely a dolgok számát, irányát, számosságát határozza meg, vagy dolgok csoportjának, gy˝ujteményének megnevezést ad a számossága alapján (például tucat). Többnyire a mennyiséget számmal jelöljük (mér˝oszám), amelyet egy mértékegység követ (ha szükséges), majd ezután megemlítjük magát a dolgot, aminek mennyiségét meghatározzuk. A pontos fogalmazáshoz mindkét részre szükség van.”
4.4.1.
Motiváció
Írásos dokumentumainkban gyakran használunk sokféle mennyiséget, melyek különleges információtartalommal bírnak. Sajnos a legtöbb keres˝orendszerben nincs lehet˝oségünk mennyiségek mentén sz˝ukíteni a találatainkat, mivel az indexel˝oprogramok gyakran csak egy-egy szó tárolásával foglalkoznak, szókapcsolatok, kifejezések elemzésével már
41
nem. Így fordulhat el˝o, hogy egy olyan kifejezésnek mint pl.: 1000 euró-nak a valódi jelentése elveszhet, és az indexbe csak mint egy szám és egy szó tárolódik. Ha a dolgozatom témáját tekintem, azaz az országgy˝ulési naplókat, akkor az figyelhet˝o meg, hogy ezekben a szövegekben gyakran esik szó pénz mennyiségr˝ol. Ezen kívül csak elvétve találunk más mennyiséget, úgy mint a hosszmérték. Adódott az ötlet, hogy megvizsgáljam miként lehetséges mennyiségeket kezelni az Indri keres˝orendszerben. A vizsgálódásomat az alábbi szempontok mentén végeztem: • Lehetséges-e több féle mennyiség kezelése? Ha igen, hogyan? • Lehetséges-e a felhasználó által megadott mértékegységek használata, kereshet˝ové tétele? • Használhatunk-e negatív értékeket? • Használhatunk-e nem egész értékeket is? • Hogyan végezhetünk kereséseket? Lehet-e valamilyen módon mennyiségi összehasonlításokat használni? • Azonos mennyiséget jelöl˝o, különböz˝o formában adott mennyiségek kezelhet˝oek-e egységesen? Pl.: 1000 g = 1 kg? • Lehetséges-e bet˝uvel írt mennyiség értékének indexelése? És ha igen, hogyan? Ezek után pedig úgy b˝ovítettem a rendszert, hogy az említett két mennyiségi információt indexelés és keresés során a lehet˝o legjobban kezelje a rendszer.
4.4.2.
Mennyiségek indexelése, keresése az Indriben
Els˝o megközelítésben azt állapítottam meg, hogy az Indrivel maximum arra van lehet˝oségem, hogy az összertozó mennyiségi kifejezéseket együtt tároljam. Aztán közelebbr˝ol megvizsgálva a rendszert azt láttam, hogy keres˝ovel használhatóak számszer˝u mez˝ok. Ez pedig a következ˝o módon m˝uködik: Az indexeléskor használt paraméterfájlban megadhatjuk, hogy mely mez˝oket kezelje, ezek számszer˝uek-e, illetve mely elemz˝o dolgozza fel o˝ ket. A dátumokhoz hasonlóan ezek a mez˝ok is el˝ojel nélküli egészként tárolódnak. Így az indexelés folyamán, a már korábban látottakhoz hasonlóan, beiktatható egy újabb saját modul, ami a jelölt mennyiségeket feldolgozza. Kereséshez az alábbi kulcsszavakkal állnak rendelkezésünkre: 42
• #less(fieldName value) – fieldName mez˝ok értékei közül azokat választja ki, melyek kisebbek value-nál • #greater(fieldName value) – fieldName mez˝ok értékei közül azokat választja ki, melyek nagyobbak value-nál • #between(fieldName value1 value2) – fieldName mez˝ok értékei közül azokat választja ki, melyek value1 és value2 között vannak • #equals(fieldName value) – fieldName mez˝ok értékei közül azokat választja ki, melyek értéke pontosan value
4.4.3.
Általános megoldás mennyiségek használatára
A numerikus mez˝ok el˝onyös tulajdonságaira alapozva az alábbi megoldást dolgoztam ki. A megvalósított kiegészít˝o modul a dátumfelismeréshez hasonlóan, két részb˝ol áll. Az els˝o rész, a korábban leírtakhoz nagyon hasonlóan azt hivatott szolgálni, hogy a forrásfájlokban mez˝oket hozzunk létre, melyek mennyiségeket jelölnek. A fentiekhez képest itt annyival nehezebb a feladat, hogy tudnunk kell különbséget tennünk mértékek között. Ezt úgy sikerült elérnem, hogy a fieldek létrehozásakor, minden mértékhez más-más címkét rendelek. Pl.: súlymérték esetén a konfigurációs fájlban megadott weight címkét rendelek a kg,g,dkg,stb. mértékeggel rendelkez˝o mennyiségekhez, pénzösszegek esetében pedig a deviza kulcsszót használom. A magyar nyelvben a jelz˝os szerkezeteknek kötött a formája: a jelz˝o megel˝ozi a jelzett szót. Mivel így tekinthetünk egy mennyiségi kifejezésre is, ezért joggal feltétezhettem, hogy egy mértékegység láttán, az azt megel˝oz˝o szóval vagy számmal biztosan összetartoznak. Ezeket tudva, az els˝o modul m˝uködése odáig egyszer˝usödött, hogy elég megtalálni egy mértékegységet jelz˝o szót, és az azt megel˝oz˝ovel/megel˝oz˝oekkel létrehozni egy mez˝ot. A gyakorlatban azonban ez a módszer messze nem tökéletes, mert el˝ofordulhat - és el˝o is fordul - olyan szövegkörnyezet, ami például magáról a mértékegységr˝ol szól. Ekkor az el˝otte álló szóval ritkán alkot mennyiségi kifejezést. Pl.: „A gramm a súlymérték alapegysége.” „. . . az euró bevezetése. . . ” Ilyen esetekben a modulom, a mez˝ohöz extremális értéket rendel, hogy kereséskor minél inkább elkerüljem a rossz találatokat. Egy másik olyan hiba, amivel a program fejlesztése során találkoztam, az hogy az országgy˝ulési naplókban gyakoriak az olyan pénzösszegeket kifejez˝o mennyiségek, melyekben vegyesen használnak bet˝uvel és számmal írt mennyiséget, pl.: „70 milliárd forint”. Felfedezve 43
ezeket a kivételeket javítottam az alprogram m˝uködésén, hogy az ilyen kifejezéseket is megtalálja, tárolja. A második modul, mely beépül a szövegfeldolgozási láncba, a mez˝ok feldolgozásáért, reprezentálásáért felel˝os. Ez mikor végigjárja az indexelend˝o dokumentum összes mez˝ojét, csak azokat dolgozza fel, melyek mértékegységet tartalmaznak. Ezeket pedig úgy, hogy a mennyiségeket átváltjuk az SI megfelel˝ojükre. Nem egészek tárolása - az Indri korlátaiból fakadóan - csak egészként valósíthatóak meg, mégpedig úgy, hogy a tárolható számok mennyiségét csökkentve, helyet nyerve a tizedes jegyeknek. A készített modul egy gyakorlatban is sokat alkalmazható funkcionalitása, hogy képes bet˝uvel írt5 számok felismerésére, átváltására. Ezt úgy sikerült elérnem, hogy amikor elemzésre kerül a mennyiségi érték, és a modul felismeri hogy nem numerikus alakról van szó, meghív egy szövegfelismer˝o függvényt. Ez a magyar nyelv sajátosságait kihasználva a számot milliárdos, milliós, ezres, százas illetve tízes egységekre bontja, majd ezeket egyenként kiértékeli és összeadja.
4.4.4.
Megoldatlan problémák
A modul nem kezel olyan tört számokat, melyek hagyományos – tehát nem tizedes – alakban fordulnak el˝o. Ezek indexeléskor kimaradnak az adatbázisból így nem lesznek kereshet˝oek. Az intervallumként megadott értékeknél a program a várttól eltér˝oen m˝uködik. Pl.: 10-20 millárd forintnyi tartozás. A felhasználó – jogosan – azt várná, hogy pl.: "kevesebb, mint 15 milliárd forint"-szer˝u lekérdezések esetén a fenti szöveget tartalmazó dokumentum is szerepeljen a találati listában. Ez sajnos nem fog megtörténni, mivel a modul csak az intervallum fels˝o korlátját tekinti, mint értéket és ezt teszi kereshet˝ové. Egyébként a használt keres˝orendszer ett˝ol sokkal többet nem is enged meg, hiszen egy numerikus mez˝ohöz pontosan egy értéket lehet hozzárendelni. Országgy˝ulési naplók használata során sok olyan mondatba botlottam, mikor egy-egy felszólaló az euróról vagy más pénznemekr˝ol beszél mennyiségi környezet nélkül. Ekkor, a felismer˝o modul az ilyen környezeteket is megjelöli, viszont feldolgozás során ez a megjelölt környezete értelmezhetetlen lesz. Pl.: „az euró”. 5
csak magyar nyelven megfogalmazott
44
4.5.
Szinonimák használata
„A szinonímia, azaz rokonértelm˝uség az a jelenség, amikor egy fogalmat több különféle szóval is kifejezhetünk. Szinonimák, vagyis rokon értelm˝uek azok a szavak, amelyek különböz˝o alakúak, de azonos vagy hasonló dolgot jelentenek.”
4.5.1.
Motiváció
Mint azt mindennapi életünkben is tapasztaljuk, mind írásban, mind pedig beszédben igyekszünk elkerülni a szóismétléseket, ehhez pedig a legkézenfekv˝obb eszköz a rokon értelm˝u szavak használata. Parlamenti felszólalások esetén a képvisel˝ok talán még nagyobb hangsúlyt fektetnek a szabatos fogalmazásra, így feltételezhetem, hogy ezekben a dokumentumokban az átlagosnál több szinonima használat fordul el˝o. Dokumentumok közötti keresések esetén, gyakran találkozhatunk azzal a problémával, hogy ha nem tudunk nagyon pontos keres˝okifejezést összeállítani, a keresett dokumentumokat nem, vagy csak részben találhatjuk meg. Lássuk hogyan kaphatunk pontosabb találati listát csupán az alaprendszer által biztosított eszközök használatával!
4.5.2.
Rokon értelmu˝ szavak használata az Indrivel
A használt keres˝orendszer lekérdez˝onyelve – az IndriQuery Language – lehet˝oséget ad, olyan lekérdezések futtatására, melyben megadhatunk szócsoportokat, melyek elemeinek jelentése egyez˝o vagy hasonló. Ennek használatával úgy érhetünk el jobb találati pontosságot, hogy ha keres˝okifejezésünkbe a nyelv szintaxisával megadjuk, hogy mely szavak hordoznak hasonló jelentéstartalmat. A következ˝o operátorokat használhatjuk: • #syn(...) • {...} • <...> • #wsyn(...) Az els˝o három kifejezés egymással ekvivalens, míg az utolsónál a rokon értelm˝u szavakhoz súlyokat is rendelhetünk. Pl.: {országgy˝ ulés parlament}, #syn(kutya eb), #wsyn(1.0 országgy˝ ulés 0.8 parlament)
45
4.5.3.
Automatikus szinonimahasználat
A MorphoLogictól kapott nyelvi eszközök között szerepelt szinonima szótár is, így adva volt a lehet˝oség hogy ezzel egészítsem ki az Indri funkcionalitását. A szótár alkalmazásprogramozási felülete úgy m˝uködik, hogy egy lekérdezéskor, egy szóra az azzal rokonértelm˝u szavak csoportjával tér vissza. Szerettem volna, hogyha a felhasználónak nem maga kell kitalálnia keres˝okifejezésben egy-egy szóhoz a rokonértelm˝u szavakat, hanem egy speciális karakterrel6 utasíthatja a keres˝ot, hogy egy szó szinonimáit is vegye a találatok közé. Ezt úgy valósítottam, meg, hogy beavatkozva a lekérdezési folyamatba, a lekérdezést el˝o-feldolgozom, és minden egyes jelölt szó helyére beillesztem annak rokon értelm˝u párjait is. Például a ~parlament kifejezés #syn(parlament országgy˝ ulés országház) alakúra transzformálódik.
4.5.4.
A megoldás korlátai
Mivel a fenti átalakítás automatikus, így könnyen bekerülhetnek olyan rokon értelm˝u szavak a keres˝okifejezésbe, amik az eredeti jelentéstartalomtól távol állnak, és az így kapott lekérdezésben nagy lesz a zaj. Továbbá az is igaz, hogy bár ezzel a megoldással könnyítünk a felhasználó dolgán, csökkentjük a döntéshelyzetek számát, ugyanakkor egy fontos ponton vonjuk meg t˝ole a mérlegelés jogát. Egy jól használható megoldás lehetne, hogy ha már a lekérdez˝ofelületen kiválaszthatná a felhasználó a használandó szinonimákat. Ez funkció nem került megvalósításra a fejlesztés során.
6
ez a karakter a jel lett
46
5. fejezet Az elkészült rendszer értékelése Ebben a fejezetben célom, hogy megvizsgáljam a kiegészített keres˝orendszert, és több szempont mentén összehasonlítsam az Indrivel. Nyilvánvalóan nem tudom az összes új modul hatását teljes kör˝uen mérni, mert néhányuk olyan új funkcionalitást ad az eszköznek, melyek nem vagy alig összehasonlíthatóak az eredeti program m˝uködésével.
5.1.
Teljesítmény
Els˝o lépésben azt vizsgáltam meg, hogy a keres˝orendszer teljesítménye hogyan változik az általam készített eszközök hatására. Ez három helyen érhet˝o tetten: • indexelési id˝o változása, • index méretének változása, • keresési id˝o változása.
5.1.1.
Indexelési id˝o
Az indexelési id˝ot úgy mértem, hogy a rendelkezésemre álló dokumentumokat, azok keletkezési éve szerint csoportosítottam, majd ezekre futtattam az alkalmazást. A 5.1 ábrán az látható, hogy egy-egy adathalmaz méretének függvényében, hogyan változott az annak feldolgozásával töltött id˝o. Ezek alapján megállapítható, hogy a szótövezés jelent˝osen lassította az indexelés folyamatát. Viszont az is észrevehet˝o, hogy a tiltólistás szavak sz˝urésével, ez a teljesítménybeli visszaesés mérsékelhet˝o. A fenti tényekre magyarázatot adhat, hogy a szótövezés költséges m˝uvelet és a szöveg majdnem minden szavára végrehajtjuk. Azt is meg kell még említeni, hogy az indexelés 47
5.1. ábra. Indexelési id˝o az adathalmaz méretének függvényében
5.2. ábra. Index mérete az adathalmaz méretének függvényében a keresések el˝okészítéséül szolgál, és egy dokumentumhalmazra csak egyszer kell lefuttatni. Így az itt vesztett id˝o a végfelhasználó számára észrevétlen maradhat.
5.1.2.
Index mérete
Inkrementális indexelést végezve azt vizsgáltam, hogy hogyan változnak a készített indexek méretei, az eszközök használatának, illetve, az adatmennyiség függvényében. Ennek a mérésnek az eredményét szemlélteti a 5.2 ábra. Mint arra számítottam, az index mérete csökkent szótövezés és stopword sz˝urés esetén. Tiltólistás szavak sz˝urésének alkalmazásakor, ez annak az egyszer˝u ténynek a következménye, hogy kevesebb kifejezés kerül az indexbe. Szótövezéskor, pedig egy szó különböz˝o ragozott alakjai ugyanahhoz a kifejezéshez tárolódnak. Az így nyert tárhely-
48
növekedés a program eredeti m˝uködéséhez viszonyítva (átlagosan): • szótövezéssel 22%, • tiltólistás szavak sz˝urésével 6%, • szótövezéssel és tiltólistás szavak sz˝urésével 28%. Látható, hogy e két egyszer˝u eszköz használatával érzékelhet˝oen lehet javítani a keres˝orendszer tárhely gazdálkodásán.
5.1.3.
Lekérdezési id˝o
Azt gondoltam, hogy ahogy csökkent az index mérete, azzal valamilyen arányban csökkenhet egy lekérdezés átlagos ideje. Azzal is számoltam, hogy ez az id˝o valószín˝uleg összefüggésben áll a keres˝okifejezés hosszával. Ezért az irodalomban leggyakoribb keres˝okifejezés hosszakra vizsgáltam azt, hogy hogyan változik a teljesítménye a keres˝orendszernek.
5.3. ábra. Lekérdezési id˝o a keres˝okifejezés hosszának függvényében Mérésem eredményei a 5.3 ábrán látható. Amit ezek alapján biztosan állíthatok az az, hogy a szótövezés nem befolyásolta érzékelhet˝oen a lekérdezési id˝ot. Másrészt a két eszköz együttes használata esetén sem mutatható ki egyértelm˝uen javulás vagy romlás. Fontos még megjegyezni, hogy a kapott értékek milliszekundumos nagyságrend˝uek, így nem zárhatom ki a pontatlanságból fakadó ingadozásokat.
49
5.2.
Relevancia
5.2.1.
Módszer
„A relevancia egész általánosan az információ fontossága, jelent˝osége. Valamivel sz˝ukebb értelemben az adott kérdésre kapott információk meghatározó, lényeges volta. Az adott keres˝okérdés vonatkozásában relevánsak a visszakeresett tételek, amelyek objektív értelemben megfelelnek a feltett kérdésnek.”[12] Nézzük, hogyan alkalmazhatjuk ezt a fogalmat egy keres˝orendszer értékelésénél! A dokumentumtár elemeit, egy lekérdezés eredményére vonatkozóan, négy diszjunkt halmazba oszthatjuk, melyet a 5.1 táblázat szemléltet. 5.1. táblázat. Információ a relevancia szempontjából releváns nem releváns megtalált A B nem megtalált C D
Az egyes csoportokat a következ˝oképpen szokás nevezni: • A (megtalált releváns elemek) – találatok (hits) • B (megtalált nem releváns elemek) – zaj (noise) • C (releváns kihagyott elemek) – veszteség (misses, losses) • D (nem releváns kihagyott elemek) – érdektelen információk 5.1 jelöléseit alkalmazva további fogalmakat definiálhatunk, melyekkel már leírható egy keresés eredményessége. Pontosság 1 Annak számossága, hogy a keresés eredményei között mennyi releváns: |A|/|A ∪ B| Teljesség 2 A megtalált és az összes releváns elem mennyiségének hányadosa: |A|/|A ∪ C| Ezekkel a mutatókkal már sok minden kifejezhet˝o, de mivel egymástól nem függetlenek, önmagukban nem adnak egzakt módszert egy keres˝orendszer eredményességének 1 2
angol nyelv˝u szakirodalomban precision angol nyelv˝u szakirodalomban recall
50
mérésére. Az is nyilvánvaló, hogy a két mennyiség egymással fordított arányban áll: növelve egy rendszer pontosságát, veszíthetünk a teljességéb˝ol, és a teljességet célul t˝uzve a pontossági érték romolhat. Ezek miatt a két mutató valamilyen kombinációját szokás alkalmazni. A legelterjedtebb mérték az ún. F mérték, mely az alábbi képlettel számolható: 2 )·(P ·R) , ahol P a pontosságot, míg R a teljességet jelöli. A β paraméter a P és az Fβ = (1+β (β 2 ·P +R) R értékek súlyát határozza meg a súlyozott harmonikus középértékben, és leggyakrabban értékét 1-nek választják. A fentiek jól alkalmazhatóak olyan keres˝orendszerekre, amik az eredménylistában nem határoznak meg rangokat3 . Más a helyzet viszont az olyan keres˝ok esetén, ahol az eredménylista az elemekhez rendelt rang alapján rendezett halmaz. Ekkor az F mérték, figyelmen kívül hagyja ezt a rangsorolást. Ennek kiküszöbölésére a kutatók több módszert is javasolnak[16, 8], melyekb˝ol az egyik legjobb tulajdonságokkal bíró metrika az ún. P N
(P (r)·rel(r))
, ahol N Mean Average Precision4 . Ezt a követez˝o módon számolhatjuk: r=1 R a találati listában szerepl˝o elemek száma, rel(x) értéke 1, ha az x-edik elem a listában releváns, egyébként 0, P (x) a pontosság a találati lista els˝o x elemére sz˝ukítve, R pedig a tárban található releváns dokumentumok számossága. Már láttuk, hogy egy eredményhalmazt hogyan tudunk értékelni, ha meg tudjuk különböztetni a releváns dokumentumokat a nem relevánsoktól. Arról még nem ejtettem szót, hogy mihez viszonyítva is határozzuk meg egy dokumentum alkalmasságát: a szakirodalomban[8] a relevancia meghatározása mindig az „információ igényeknek” megfelel˝oen történik. Ez a gyakorlatban azt jelenti, hogy nem a keres˝okifejezéshez viszonyítjuk a találatokat, hanem egy el˝ore megfogalmazott kérdéshez (aminek már csak egy reprezentációja a keres˝okifejezés). Mindezek alapján a méréshez szükségem van:
1. természetes nyelven megfogalmazott, egzakt „információ igényekre”, melyek a keres˝o nyelvén is kifejezhet˝oek, 2. az igényeknek megfelel˝o keres˝okifejezésekre, 3. jól körülhatárolt dokumentumhalmazra, melyekben az egyes igényeknek megfelel˝oen osztályozva vannak a releváns és nem releváns dokumentumok, 4. metrikára. 3 4
minden elemet egyformán jónak min˝osítenek a továbbiakban MAP
51
5.2. táblázat. A továbbfejlesztett rendszer és az Indri eredményességének összehasonlítása a MAP metrika segítségével Indri 54% szótövezéssel 69% szinonimákkal 69% mennyiség57% felismeréssel dátumfelismeréssel 59% eszközök együttes 59% használatával
5.2.2.
Mérési eredmények
A keres˝o értékelésének vizsgálatához • elkészítettem egy jól körülhatárolt dokumentumhalmazt, • meghatároztam olyan természetes nyelvi kérdéseket, melyekr˝ol azt gondoltam, hogy parlamenti naplókat olvasva választ találok, • a kérdéseket többféleképpen kifejeztem az Indri Query Language segítségével (ahol a hozzáadott funkcióktól javulás volt várható javítottam az eredeti kifejezésen), • és a kérdéseknek megfelel˝oen osztályoztam a dokumentumokat. A lekérdezésének eredményességét a MAP metrikával vizsgáltam. Lefuttatva és értékelve a kereséseket, majd átlagolva ezek eredményét, a 5.2 táblázatban látható relevancia értékeket kaptam. A mérési eredményeket vizsgálva fontos szem el˝ott tartani, hogy keres˝orendszerek értékelése során – különösen a keres˝okifejezések létrehozásakor – számos olyan döntést hoztam, melyeknél nem állt rendelkezésemre egzakt eszköz a lehet˝oségek vizsgálatára. Így a mérés eredménye – a szubjektivitásból adódóan – megfelel˝o fenntartással kezelend˝o. Ennek ellenére most megpróbálom ezek mentén értékelni munkámat. A számadatokból els˝o pillantásra az olvasható ki, hogy bár nem sokkal, de mindegyik eszköz képes javítani a találati pontosságon. A mérések során a pontossággal és teljességgel kapcsolatban változó tapasztalatokat szereztem. Sokszor fordult el˝o az, hogy például szinonimákat használva az eredménylista zaja n˝ott, a pontosság helyett. Hasonló tapasztalataim voltak a mennyiség és dátumfelismeréssel, míg a szótövezés szinte mindig növelte az eredményességet.
52
Úgy gondolom, hogy ezeket a negatív kilengéseket számos tényez˝o okozhatta. Szinonimák használata esetén azt tapasztaltam, hogy az olyan keres˝oszavak használatánál, melyek amúgy is rontottak a pontosságon, hozzávéve annak rokon értelm˝u párjait katalizáltam ezt a rossz folyamatot. Másrészr˝ol hasznos eszköznek bizonyult akkor, amikor köznapi nyelven megfogalmazott kifejezésre alkalmaztam, ugyanis a parlamenti naplókban gyakran találkoztam hivataloskodó szóhasználattal, amit tartalmazó szövegrészeket így el tudtam érni. A mennyiség és dátumfelismeréskor megélt kudarcokat többségében annak tulajdonítom, hogy egy-egy parlamenti napló a méreténél fogva számos témát ölel fel. A rendszer nem képes elkülöníteni ezeket egymástól, így a bennük található mennyiségekre és dátumformákra keresve sokszor inkább csak a zaj növekszik. Ugyanakkor úgy gondolom az sem véletlen, hogy mégis sikerült kimutatható javulást elérni ezek használatával: dátumokat gyakran használunk, és ha rendelkezünk az információ igényhez kapcsolódó id˝oponthoz köthet˝o kiegészít˝o adatokkal, akkor jelent˝os javulást érhetünk el.
5.3.
Összefoglalás
Összességében elmondható, hogy a készített eszközök mind teljesítményben, mind pedig relevancia szempontjából nem rontottak az eredeti keres˝o m˝uködésén. Mindenképpen sikernek könyvelhet˝o el, hogy új, eddig nem használt funkcionalitásokkal gazdagodott az Indri, melyek javíthatnak a lekérdezések eredményességén. Általánosságban még az is elmondható, hogy a modulok helyes használatához, némi szakértelemre és körültekintésre van szükség. Meggondolatlanul alkalmazva o˝ ket, jelent˝osen romolhat a keres˝orendszer átlagos relevanciája.
53
Köszönetnyilvánítás Szeretném megköszönni Dr. Prószéky Gábornak a munkám során nyújtott támogatását, a kapott hasznos ötleteket, javaslatokat; a MorphoLogic tulajdonát képez˝o nyelvi elemz˝ot és az országgy˝ulési naplók adatbázisát. Köszönettel tartozom még Endrédy Istvánnak, aki a nyelvi eszközök használata során látott el hasznos technikai információkkal. Sokat köszönhetek még David Fishernek, aki a Lemur projekt egyik gazdája, és a keres˝orendszer használatával kapcsolatos kérdéseimre mindig készségesen válaszolt. Hálával tartozom még családomnak a dolgozat elkészítése során tanúsított türelmükért.
54
Függelék Tiltólistás szavak jegyzéke a az abban abból ahhoz ahogy ahol akár aki akik akkor alá alapján alatt által általában amely amelyben amelyek amelyekben amelyeket amelyet amelyik amelynek
ami amíg amikor amir˝ ol amit amolyan annak arra arról át az azért azok azokat azoknak azon azonban azt aztán azután azzal ban bár be
belül ben benne bizony bizonyos biztos csak csupán de e ebben ebb˝ ol eddig egész egészen egy egyéb egyébként egyértelm˝ uen egyes egyet egyetlen egyik egyre
55
egyrészt egységes ehhez ekkor el elé elég ellen ellenére el˝ o el˝ obb el˝ oször el˝ ott el˝ otti els˝ o els˝ osorban emilyen én ennek ennél éppen erre err˝ ol és esetén esetleg ez ezek ezeket ezen ezért ezt ezzel fel felé
fog fognak gyakorlatilag ha hanem hát helyett hiszem hiszen hogy hogyan hogyha hozzá ide igen így ill illet˝ oleg illetve ilyen ilyenkor inkább is ismét itt jelenlegi jó jobban jól kapcsán kapcsolatban kapcsolatos kell kellene kellett
56
képest keresztül ki kicsit kíván kívül korábban korábbi köszönöm követ˝ oen között közül különböz˝ o le legalább legyen lehet lehetett lehetséges lenne lenni lesz lett maga magát majd már más másik meg még megfelel˝ o mégis mellett mely
melyek mert mi miatt miért míg mikor miközben milyen mind minden mindenképpen mindenki mindent mindig minél mint mintegy mintha mit mivel módon most nagy nagyobb nagyon ne néha néhány nekem neki nekünk nélkül nem nemcsak
nincs nyilván oda olyan ott ˝ o ˝ ok ˝ oket ön öné önök össze pedig például persze pontosan rá s sajnos se sem semmi senki sok sokat sokkal során s˝ ot szerint szét szinte szintén szükséges talán te
57
tehát tekintettel teljes tényleg természetesen ti tisztelt tovább továbbá további több túl t˝ unik úgy ugyan ugyanakkor ugyancsak ugyanis új újabb újra után utána utolsó ügy vagy vagyis vagyok vagyunk vajon valaki valamennyi valami valamilyen valamint
való valóban van vannak végre
végül vele viszont vissza volna
volt voltak voltam voltunk
Konfigurációs fájl A konfigurációs fájl DTD specifikációja a következ˝o: A mez˝ok jelentése: • separators – elválasztókarakterek, az egyes sep mez˝ok elemei azok a karakterek, melyek elválasztják a mennyiséget jelöl˝o kifejezés részeit. Az isDecimal attribútum true értéke esetén pedig a mez˝o értékére tizedes elválasztó karakterként tekint a feldolgozó program. • units – felismerend˝o mennyiségek listája • unit – egy felismerend˝o mennyiségi tulajdonság egy mértékegysége, például súlymérték estén kg, g. Attribútumai: – type – a jelölt mennyiségi tulajdonsághoz létrehozandó field neve. Pl.: weight – multiplier – a mennyiségi tulajdonság SI mértékegységéhez viszonyított szorzó. Pl.: kg esetén 1000. 58
• dates – a használandó dátumformák listája. Értékei a 4.3.4-ban leírt dátumnyelv elemei. A mérések futtatásához használt konfigurációs fájl: <separators> <sep isDecimal="true">, <sep isDecimal="false">\s kg km forint euro euró dollár yyyy. month d. yyyy. month dd. yyyy. month d- yyyy. month dd- yyyy. mon. d. yyyy. mon. dd. yyyy. mon. d- yyyy. mon. dd- yyyy. month d. yyyy.mm.dd. yyyy.mm.d. yyyy.mm.dd yyyy.mm.d
59
Felhasználói dokumentáció A készített program célja, hogy lehet˝oséget biztosítson strukturált lekérdezések futtatására, egy tetsz˝olegesen választott magyar nyelv˝u dokumentumhalmazon. A felhasználónak – az Indri képességein túl – lehet˝osége nyílik: • magyar nyelv˝u szövegben való intelligens – szót˝o szerinti – keresésre, • magyar nyelv˝u automatikus szinonima használatra, • magyar nyelvterületeken szokásos dátumok használatára a dokumentumhalmazban, ezek felismerésére, keresésére, • tetsz˝oleges mennyiségi információk használatára a dokumentumhalmazban olyan módon, hogy az a keresés során elérhet˝o összehasonlító operátorokkal is kereshet˝ové váljon. A kiegészített keres˝orendszer több futtatható alprogramból áll, melyekb˝ol a legfontosabbak: dátum és mennyiség jelöl˝o el˝ofeldolgozó program, index készít˝o alkalmazás, webes felület. Az alábbiakban ezek telepítését és használatát tekintem át.
Rendszerkövetelmények A készített alkalmazás futtatásához, az alábbi hardver konfiguráció ajánlott: • >1000 MHz processzor, • >512 RAM, • 300 MB szabad tárhely. A m˝uködéshez szükséges szoftverkörnyezet a következ˝o5 : • 32 bites Linux operációs rendszer • Boost programkönyvtár Regex komponense (1.38<) • Apache Tomcat 6.0.20< • Sun Java Runtime Environment 1.6< 5
A készített programhoz mellékeltem a MorphoLogic tulajdonát képez˝o morfológiai elemz˝o modul id˝okorlátos verzióját, mely 2010. december 31.-ig m˝uködik. Ha az olvasó az alkalmazást ett˝ol tovább szeretné használni, kérem vegye fel a kapcsolatot a készít˝o céggel.
60
Telepítés Az alábbi lépéseket követ˝oen használhatjuk a programot: 1. Az alkalmazás könyvtárstruktúrájában lév˝o lib mappát tegyük elérhet˝ové a PATH rendszerváltozóban. 2. Telepítsük a Tomcat webszervert. 3. A web mappában található war kiterjesztés˝u fájlt adjuk hozzá a Tomcat szerver alkalmazásaihoz. 4. A Tomcat alkalmazás META-INF könyvtárának context.xml fájljában állítsuk be az alábbi paraméterek értékét6 : • index.indri.stemmed – szótövezést használó index elérési útja, • index.indri.plain – eszközöket nélkülöz˝o index elérési útja, • index.indri.stemmedstopped – szótövezést és tiltólistás szavak sz˝urését használó index elérési útja, • index.indri.stopped – csak tiltólistás szavak sz˝urését használó index elérési útja. 5. Helyezzük a conf.xml, conf.dtd fájlt és a lex könyvtárat a Tomcat futtatási könyvtárába!
El˝ofeldolgozó Az el˝ofeldolgozó programot a bin mappa fieldAnnotator alkalmazásával indíthatjuk el. Használat a következ˝o: fieldAnnotator , ahol a fromFile a feldolgozandó fájlt jelöli a toFile pedig a létrehozandó új fájlt. A program futtatásához szükséges, hogy korábban említett conf.xml elérhet˝o legyen a futtató környezetéb˝ol Ebben a konfigurációs fájlban7 adhatjuk meg, hogy milyen dátumformákkal és mennyiség típusokkal szeretnénk a keres˝orendszert használni. Egy minta fájl található az examples mappában. 6 7
A program mellékleteként az env könyvtárban megtalálhatóak az általam használt indexek is. Használatához lásd a Konfigurációs fájl alrészt
61
Indexel˝o alkalmazás Indexel˝o alkalmazásként az Indri BuildIndex alprogramja használandó. Ennek a futtatásához is szükséges a conf.xml fájl elérhet˝osége, és fontos, hogy az el˝ofeldolgozáskor és az indexeléskor a konfigurációs fájl tartalma megegyezzen. Az indexelés indítása a buildindex <parameterFile> paranccsal történik. A paraméter fájl formátuma az eredeti rendszer leírásának8 megfelel˝o. Ahhoz, hogy a magyar nyelvi eszközöket használhassuk, az alábbi sorokkal kell kiegészíteni azt: • magyar nyelv˝u szótövezéshez <stemmer>hunStemmer • dátumfelismeréshez date true <parserName>HunDateFieldAnnotator • mennyiségek felismeréshez a lenti kódsorokat annyiszor ahányféle mennyiséget szeretnénk használni. Az M helyére mindig a mennyiséget jelöl˝o conf.xml-ben is megtalálható kulcsszó írandó. Pl.: Weigl, deviza M true <parserName>UnitFieldAnnotator Egy példa paraméter fájl található az examples könyvtárban.
Keres˝o alkalmazás A Tomcat szerver elindítása és az indexek elérési útjának beállítása után, a localhost:8080/indriWeb9 címre navigálva érhetjük el a webes lekérdez˝o felületet. Ennek formája a 6.1 ábrán látható. 8
http://www.lemurproject.org/doxygen/lemur/html/IndriParameters.html a 8080 a Tomcat által használt alapértelmezett port, de ez persze módosítható, és ezzel együtt a hivatkozás is változik 9
62
6.1. ábra. A keres˝orendszer lekérdez˝o felülete.
A felhasználói interfész négy részb˝ol áll: • keres˝omez˝o • szótövezést választó gomb • stopword sz˝urést választó gomb • eredmények A keres˝omez˝obe begépelve, majd Enter-t ütve indíthatjuk el a keresést. Szinonima használatra a ~ operátorral van lehet˝oség, mégpedig úgy, hogy ezt a kívánt szó elé írjuk. A lekérdezés a választó gombok által meghatározott indexen fog végrehajtódni. A találati lista els˝o tíz eleme a keres˝omez˝o alatt jelenik meg.
Fejleszt˝oi dokumentáció A keres˝orendszer továbbfejlesztéséhez az alábbi eszközöket használtam fel: • GCC 4.4.1 fordító • SWIG 1.3.36 • Boost 1.38 programkönyvtár • Sun JAVA 1.6.15 JDK • Eclipse 3.4 (CDT modullal) • Iconv 2.10.1 programkönyvtár 63
6.2. ábra. A szótövez˝o és a szinonimaszótár integrációja
Munkám során a részfeladatok implementációit – alkalmazkodva az Eclipse fejleszt˝okörnyezet konvencióihoz – projektek keretében valósítottam meg. A készített osztályok a com::sefh névtérbe kerültek, ezen belül is további névtereket alkottam az egy csoportba tartozóknak. A modulokat lefordítva – a fileAnnotator kivételével – egy-egy ún. shared objectet10 kapunk, melyek futási id˝oben kapcsolódnak a futtatható állományokhoz. Most áttekintem, hogy az egyes projektek keretében milyen részfeladat valósult meg, illetve azok statikus felépítését. 10
osztott objektum
64
Az alkalmazások felépítése humor A humor projekt tartalmazza a MorphoLogictól kapott nyelvi eszköz köré készült burkoló osztályt, és az ahhoz szükséges header fájlokat. A HumorCPP osztály a 6.2 ábrán látható, melynek m˝uveleteit és adattagjait a 6.1 táblázat tartalmazza.
65
6.1. táblázat. HumorCPP osztály Muvelet ˝ static void initialize( std::string directory ) static bool isInitialized()
static int close()
static std::vector<std::string> getStem(std::string word) static std::vector<std::string> getSyns(std::string word) HumorCPP()
static iconv_t utc
static iconv_t ctu
static int morphId static int stemOptions static int synOptions static std::vector<std::string> split(std::string str) static iconv_t openCpToUtf()
static void closeDesc (iconv_t conv_desc) static std::string convert (iconv_t desc, std::string fromStr) static iconv_t openUtfToCp ()
66
Láthatóság Leírás public inicializálja a nyelvi és karakterkonverziós eszközöket public igaz értékkel tér vissza, ha az inicializáció sikeres volt public a karakterkonverziós és nyelvi eszközök bezárása public egy szó szótöveinek listáját adja vissza public egy szó szinonimáinak listáját adja vissza private rejtett konstruktor a példányosítás megakadályozására private karakterkonverziós eszköz leírója (UTF-8 → CP-1250) private karakterkonverziós eszköz leírója (CP-1250 → UTF-8) private nyelvi eszköz leírója private szótövezési opciók private szinonimakészítési opciók private vessz˝ovel elválasztott szavakból készíti el azok listáját private CP-1250 → UTF-8 karakterkonverziós eszköz megnyitása private karakterkonverziós eszköz bezárása private karakterkonverzió végrehajtása a kapott leíróval private UTF-8 → CP-1250 karakterkonverziós eszköz megnyitása
6.2. táblázat. HunStemTransformation osztály Muvelet ˝ HunStemtransformation() ~HunStemtransformation() indri::api::ParsedDocument* transform( indri::api::ParsedDocument* document )
Láthatóság public public public
void handle( indri::api::ParsedDocument* document )
public
void setHandler( indri::parse::ObjectHandler< indri::api::ParsedDocument >& handler ) static void printDbg( indri::api::ParsedDocument* doc)
public
indri::parse::ObjectHandler< indri::api::ParsedDocument >* _handler
private
public
Leírás konstruktor destruktor a paraméterként kapott dokumentum termjeit egyenként feldolgozva, meghatározza azok szótöveit a transform m˝uvelet meghívása után, meghívja a feldolgozási lánc következ˝o elemét a feldolgozási láncban a rákövetkez˝o beállítása
fejlesztési célokat szolgáló függvény, mely futási idej˝u információkat ír ki a standard kimenetre a feldolgozási láncban az objektum rákövetkez˝oje
hunStemmer A projekt összesen két osztályt tartalmaz, melyb˝ol a HunStemTransformation az indri::parse::Transformation absztrakt típust valósítja meg, a HunSynonym pedig egy olyan egyke osztály, melynek célja, hogy IndriQuery lekérdezéseket szinonimákkal lásson el. A HunStemTransformation osztály leírása a 6.2, míg a HunSynonym a 6.3 táblázatban találhatóak.
67
6.3. táblázat. HunSynonym osztály Muvelet ˝ static HunSynonym* getInstance() ~HunSynonym() std::string processQuery( std::string& word ) std::string generateSynString(std::string& word) HunSynonym() static HunSynonym* instance
68
Láthatóság Leírás public a típus egyetlen példányával tér vissza public destruktor public a lekérdezés feldolgozása és szinonimákkal kiegészítése protected a paraméterként kapott szóhoz szinonimák generálása és keres˝okifejezéssé alakítása protected konstruktor protected az osztály egyetlen példánya
6.3. ábra. utils projekt osztályai
utils Segédeszközöket tartalmazó osztályok összessége a projekt. Ezek és kapcsolatuk a 6.3 ábrán látható. Az egyes osztályok leírása az 6.4, 6.5 és az 6.6 táblázatokban találhatóak. A felsoroltakon kívül beépítettem még az alkalmazásba egy XML feldolgozó eszközt, amit a http://www.applied-mathematics.net/tools/xmlParser. html címr˝ol szereztem be. A Unit osztály egy példánya egy mértékegység reprezentálásáért felel˝os, a Configuration osztály a konfigurációs fájlból kapott információk tárolásáért és konverziójáért, míg a StringConverter egyéb, stringekhez kapcsolódó m˝uveleteket tartalmaz.
69
6.4. táblázat. Unit osztály Muvelet ˝ Unit(std::string type_, std::string constant_, double multiplier_) std::string type
std::string constant double multiplier
Láthatóság Leírás public konstruktor, paraméterként az adattagok értékeit várja public a mennyiséget jelöl˝o mértékegység metrikája public a mennyiséget jelöl˝o mértékegység public a mennyiséget jelöl˝o mértékegység szorzója az SI párjához képest
6.5. táblázat. StringConverter osztály Muvelet ˝ static char* iToA(int value, char* str, int radix) static bool isPrefix(std::string substr, std::string word) std::wstring toWstring(std::string str) std::string toString(std::wstring str) StringConverter()
70
Láthatóság Leírás public a közismert itoa függvény implementációja public igazzal tér vissza, ha az els˝o paraméter prefixe a másodiknak, ellenben hamissal public string típusú objektumból wstring típusút készít public wstring típusú objektumból string típusút készít private rejtett, üres konstruktor a példányosítás megakadályozására
6.6. táblázat. Configuration osztály Muvelet ˝ static Configuration* getDefault() Configuration() std::vector* getUnits() std::vector<std::string>* getSeparators() std::string getDecimalSeparator() std::vector<std::string>* getDateFormatStrings() Configuration(std::string fileName)
std::vector<std::string>* separators std::string decimalSeparator
std::vector* units std::vector<std::string>* dateFormats void parseFile(std::string fileName)
Láthatóság Leírás public egyke típus egyetlen példányát adja vissza public destruktor public mértékegységeket jelöl˝o objektumokkal tér vissza public elválasztókarakterekkel tér vissza public tizedeselválasztókarakterekkel tér vissza public dátumformák dátumnyelvbeli alakját adja vissza private rejtett konstruktor, paraméterként megkapja a konfigurációs fájl elérési útját private elválasztókarakterek halmaza private tizedeselválasztókarakterek halmaza private mértékegységek halmaza private dátumformák halmaza private
private
static Configuration* defaultInstance
71
a m˝uvelet beolvassa a paraméterként kapott fájlt, és a benne található adatokat az objektum adattagjaiban tárolja egyke Configuration típus egyetlen példánya
6.4. ábra. dateRecognizer projekt kapcsolatai
dateRecognizer A dateRecognizer csomag olyan osztályokat tartalmaz, melyek az indexelési id˝oben történ˝o dátumfelismerést, konverziót végzik. Kapcsolatukat a 6.4 ábrán láthatjuk. A DateFormat típus egy példánya dátumformát tárol, illetve egy dátumforma mez˝oihez nyújt m˝uvelteket (6.8 táblázat), míg a HunDateFieldAnnotator objektumai dátum típusú mez˝ok elemzésére és indexben való tárolására szolgálnak (6.7 táblázat).
72
6.7. táblázat. HunDatefieldAnnotator osztály Muvelet ˝ HunDatefieldAnnotator( std::string field) ~HunDatefieldAnnotator() indri::api::ParsedDocument* transform( indri::api::ParsedDocument* document ) void handle( indri::api::ParsedDocument* document ) void setHandler( indri::parse::ObjectHandler< indri::api::ParsedDocument >& handler ) indri::parse::ObjectHandler< indri::api::ParsedDocument >* _handler int findExtentEnd(int supposedEnd, std::string text)
Láthatóság Leírás public konstruktor, paraméterként a mez˝ot jelöl˝o stringgel public destruktor public a paraméterként kapott dokumentum mez˝oi közül a dátum típusúakat feldolgozza majd tárolja public a transform m˝uvelet meghívása után, meghívja a feldolgozási lánc következ˝o elemét public a feldolgozási láncban a rákövetkez˝o beállítása
private
private
std::string _field
private
std::vector* _dateFormats void _parseDate(const std::string& date, indri::parse::TagExtent *extent) const
private private
73
a feldolgozási láncban az objektum rákövetkez˝oje a mez˝o végét jelz˝o karakter pozíciójának megkeresése dátumokat jelöl˝o mez˝o neve dátumformák halmaza dátum számmá alakítása
6.8. táblázat. DateFormat osztály Muvelet ˝ static std::vector* getInstances() ~DateFormat() boost::regex getRecognizerRegExp() std::string getRecognizerString() std::string getMonth( std::string date) std::string getYear( std::string date) std::string getDay( std::string date) std::string getYearIntegrString( std::string date) std::string getMonthIntegerString( std::string date) std::string getDayIntegerString( std::string date) DateFormat(std::string formatString) int yearPos, monthPos, dayPos
Láthatóság Leírás public a típus példányait adja vissza public destruktor public a dátumformát felismer˝o reg. kif.-t adja vissza public a dátumformát felismer˝o reg. kif.-t adja vissza public a dátum hónap mez˝ojét adja vissza public a dátum év mez˝ojét adja vissza public a dátum nap mez˝ojét adja vissza public a dátum év mez˝ojét adja vissza számként public
a dátum hónap mez˝ojét adja vissza számként
public
a dátum nap mez˝ojét adja vissza számként
private
konstruktor
private
dátumforma mez˝oinek sorrendje dátumformát felismer˝o reg. kif. dátumforma dátumnyelvbeli leírása számokkal írt hónapok esetén igaz dátumnyelvbeli elem beolvasása reguláris kifejezés tárolása mez˝ok sorrendjének tárolása
std::string recognizerRegExp
private
std::string formatString
private
bool isNumericMonth
private
void _parseDateFormat( std::string formatString) void _setRegExpString( std::string formatString) void _setTagsPositions(int yearStart, int monthStart, int dayStart) std::string getStringAtPos(int 74 pos, std::string date)
private private private
private
dátum mez˝oinek elérését szolgáló függvény
6.5. ábra. unitRecognizer projekt kapcsolatai
unitRecognizer Mennyiségek felismerését lehet˝ové tev˝o osztályokat tartalmaz. A UnitRecognizer osztály, egy olyan egyke típust valósít meg, mely mennyiség típusokat reprezentál és biztosít hozzájuk konverziós m˝uveletet. A NumberFormats (6.11 táblázat) típus számformátumokat reprezentál, és lehet˝ové teszi azok egységes alakra hozását, feldolgozását. A UnitRecognizer (6.10 táblázat) osztály egy objektuma, egy-egy mennyiség típus reprezentálásáért és feldolgozásáért felel˝os. A UnitFieldAnnotator (6.9 táblázat) pedig az indri::api::Transformation típust valósítja meg, ezáltal lehet˝ové téve, hogy a feldolgozási láncban elemezze a mennyiségi információnak jelölt szövegrészeket. A projekt osztálydiagramja látható a 6.5 ábrán.
75
6.9. táblázat. UnitFieldAnnotator osztály Muvelet ˝ UnitFieldAnnotator( std::string field) ~UnitFieldAnnotator() indri::api::ParsedDocument* transform( indri::api::ParsedDocument* document ) void handle( indri::api::ParsedDocument* document ) void setHandler( indri::parse::ObjectHandler< indri::api::ParsedDocument >& handler ) indri::parse::ObjectHandler< indri::api::ParsedDocument >* _handler UnitRecognizer* unitRecognizer
Láthatóság Leírás public konstruktor, paraméterként a mez˝ot jelöl˝o stringgel public destruktor public a paraméterként kapott dokumentum mez˝oi közül a mennyiséget jelöl˝oket feldolgozza majd tárolja public a transform m˝uvelet meghívása után, meghívja a feldolgozási lánc következ˝o elemét public a feldolgozási láncban a rákövetkez˝o beállítása
private
private private
std::string fieldName
76
a feldolgozási láncban az objektum rákövetkez˝oje mértékegységet felismer˝o objektum mennyiséget jelöl˝o mez˝onév
6.10. táblázat. UnitRecognizer osztály Láthatóság Muvelet ˝ static UnitRecognizer* public getDefault() std::string public getRecognizingRegExpFromConstants ( std::string )
std::string getRecognizingRegExp()
public
double getSIValue(std::string)
public
std::string getTypeOfMeasure(std::string) std::map<std::string, std::string>* getUnitsRecognizingRegexps() UnitRecognizer() static UnitRecognizer* defaultInstance std::vector* units
public
std::vector<std::string>* separators std::string decSep
private
public
private private private
private
77
Leírás egyke típus egyetlen példányát adja vissza a paraméterként kapott mértékegységhez létrehozott mennyiség felismer˝o reguláris kifejezéssel tér vissza az összes mennyiséget felismer˝o reg. kif.-fel tér vissza a mennyiség SI értékével tér vissza a mennyiség típusával tér vissza a mértékegységeket és a hozzájuk tartozó reg. kif.-eket adja vissza konstruktor egyke típus példánya mennyiség típusok halmaza elválasztókarakterek halmaza tizedeelválasztókarakter
6.11. táblázat. NumberFormats osztály Muvelet ˝ static double writtenNumberToDouble( std::string input ) static double convertToDouble(std::string decimalSep, std::string unit) static NumberFormats* getNumberFormatFromSeparators( std::string ) std::string getRegExpString()
Láthatóság Leírás public bet˝uvel írott szám felismerése
~NumberFormats() static int partOfNumberValue(std::string)
public public
public
public
public
NumberFormats(std::string private separators) void createFormatStr(std::string private sep) static bool isInt(char c)
private
static bool isInt(std::string& str)
private
std::string formatString
private
static char* digits[10] static char* tens[12] static char* hundred, thousand, million, milliard, thousandmilliard
private private private
78
a paraméterként kapott mennyiség értékével tér vissza az elválasztókarakterek alapján készített számformátummal tér vissza számformátumot felismer˝o reguláris kifejezéssel tér vissza destruktor egy bet˝uvel írt szám legfeljebb százas nagyságrend˝u értékét számolja ki konstruktor számformátumhoz tartozó reguláris kifejezés létrehozása megvizsgálja, hogy a karakter egész számot reprezentál-e megvizsgálja, hogy egy string egész számot reprezentál-e számformátumot felismer˝o reguláris kifejezés számjegyek tízes értékek százat, ezret, milliót, stb.-t tartalmazó string konstansok
6.6. ábra. fileAnnotator projekt kapcsolatai
fileAnnotator A projekt ez eddigiekkel ellentétben egy futtatható állomány forrását tartalmazza, mely a mennyiség és dátumfelismeréshez szükséges el˝ofeldolgozás m˝uveletét látja el. A szükséges osztályok kapcsolata látható a 6.6 ábrán. A FieldAnnotator (6.12 táblázat) osztály olyan statikus metódusokat tartalmaz, melyek egy fájlban található dátumok és mennyiségek mez˝okké alakítását végzik el.
79
6.12. táblázat. FieldAnnotator osztály Muvelet ˝ static void doReplace( const std::string fileName, const std::string output)
static std::string doTransformation( const std::string& inputString) static std::string doDateTransformation( const std::string& inputString) static std::string doUnitTransformation( const std::string& inputString) FieldAnnotator() static void writeFile( std::string outFilePath, const std::string& outString) static std::string parseFile( std::string fileName)
80
Láthatóság Leírás public a fileName elérési úton található fájlt feldolgozza, mez˝oket hoz létre, majd az output elérési útú fájlba írja ki public a paraméterként kapott stringben mez˝oket hoz létre public a paraméterként kapott stringben dátummez˝oket hoz létre public a paraméterként kapott stringben mennyiségeket jelöl˝o mez˝oket hoz létre private konstruktor private fájlba írja a kapott stringet private
beolvassa a paraméterként kapott útvonalon elérhet˝o fájlt
indriWeb A projekt egy olyan alkalmazást tartalmaz, mely JSP technológiával készült és webes felületet biztosít lekérdezések futtatásához. A rendelkezésemre álló forráskód hibákat, gyengeséget tartalmazott, melyeket javítani voltam kénytelen: • Latin-1 karakterkódolás helyett UTF-8 használata, • az ún. snippetek generálása során az eredeti alkalmazás többször is végtelen ciklusba futott, vagy hibás eredményt generált. Ezeken kívül úgy módosítottam az alkalmazáson hogy a felhasználó választhasson négy használható index közül, mely lehet egyszer˝u, szótövezett, szótövezett és tiltólistás szavak által sz˝urt, vagy csak tiltólistás szavak által sz˝urt.
Az alkalmazások muködése ˝ A készített új funkciók m˝uködését bemutató szekvenciadiagramok a következ˝ok: • 6.7 ábra – indexelés közben egy dokumentum szavának tövezése • 6.8 ábra – egy lekérdezést követ˝oen a keres˝okifejezés kiegészít˝odik egy szavának szinonimáival • 6.9 ábra – egy fájl el˝ofeldolgozása közben egy dátum és egy mennyiségmez˝o készítése • 6.10 ábra – indexelés közben, a dokumentumban lév˝o egy mennyiséget és egy dátumot jelöl˝o mez˝o feldolgozása, és tárolása az indexben
81
6.7. ábra. Szótövezés indexkészítés közben 82
6.8. ábra. A keres˝okifejezés kiegészítése szinonimákkal
83
6.9. ábra. El˝ofeldolgozás folyamata
84
6.10. ábra. Dátum és mennyiségfelismerés indexelési id˝oben
85
Tesztelés Az alprogramokon, a fejlesztést követ˝oen, egységteszteket végeztem, hogy felderítsem a lehetséges hibákat. Ezt követ˝oen minden új modul integrációja után, a rendszer egészét is újra tesztek alá vetettem. A webes keres˝ofelületet külön is ellen˝oriztem megengedett és nem megengedett bemeneti értékekre.
Ismert hibák Az alkalmazás fejlesztése során felismert hibák, melyeket egyel˝ore nem sikerült kijavítanom: • index készítés közben – bekapcsolt szótövezés mellett – memória szivárgást tapasztaltam, melynek következtében hosszabb futtatás során elfogyhat a virtuális memória, és a program abortálhat, • a webes felület egyes dátumkeres˝o m˝uveleteknél leáll és abortálja a Tomcat szervert. Ez a hiba ritkán bukkan fel, de ha el˝ofordul, akkor olyan esetekben, amikor szótövezett indexr˝ol egyszer˝u indexre váltunk11 .
Továbbfejlesztés Az alábbi területeken látok további fejlesztési lehet˝oséget: • A szinonimák használatát a felhasználó választására lehetne bízni, mégpedig úgy, hogy ne automatikusan kerüljenek be a rokon értelm˝u szavak a keres˝okifejezésbe, hanem a webes felületen a felhasználó választhasson közülük. • Dátumfelismerés javítása: megtalálni a módot nem teljes vagy környezetfügg˝o dátumok tárolására. • Dátumok keresésénél a az IndriQuery Language használata kényelmetlen, helyette a webes felületen dátumválasztókkal lehetne segíteni ezen adatok megadását. • Mennyiségek keresésénél a lekérdez˝onyelv használata kényelmetlen, helyette grafikus felhasználói elemekkel lehetne segíteni ezek megadását. 11
A program webes felületének alapja egy nem stabil JSP technológiával készült alkalmazás. Az Indri 4.11-re való áttéréssel és ezzel a együtt a PHP5–ös felülettel vélhet˝oen megoldódik a probléma.
86
• Mennyisége felismerésénél megtalálni a módot arra, hogy intervallumokat is lehessen tárolni. • Az Indri 4.11-es verzióra való frissítés, ami számos hibajavítást ígér. • PHP5 webes felület használata JSP helyett (Indri 4.11-t˝ol érhet˝o el)
87
Irodalomjegyzék [1] Boost regex library, 2009. október. URL http://www.boost.org/doc/ libs/1_41_0/libs/regex/doc/html/index.html. [2] Thorsten Brants: Natural language processing in information retrieval. In Decadt és mások [3]. [3] Bart Decadt – Véronique Hoste – Guy De Pauw (szerk.). Computational Linguistics in the Netherlands 2003, December 19, Centre for Dutch Language and Speech, University of Antwerp, Antwerp papers in linguistics konferenciasorozat, 111. köt. University of Antwerp, 2003. [4] Emmanuel Eckard – Jean-Cédric Chappelier: Free Software for research in Information Retrieval and Textual Clustering. Jelentés, 2007, Ecole Polytechnique Fédérale de Lausanne. [5] Prószéky Gábor: Számítógépes nyelvészet. Budapest, 1989, SZÁMALK, 605. p. ISBN 9635532016. [6] Prószéky Gábor – Kis Balázs: Számítógéppel emberi nyelven. Bicske, 1999, SZAK Kiadó, 340. p. ISBN 9639131164. [7] The lemur toolkit, 2009. december. URL http://www.lemurproject.org/. [8] Christopher D. Manning – Prabhakar Raghavan – Hinrich Schütze: Introduction to Information Retrieval. 2008, 482. p. ISBN 0521865719. [9] Christian Middleton – Ricardo Baeza-Yates: A comparison of open source search engines. Jelentés, 2007, Universitat Pompeu, Fabra Department of Technologies. [10] I. Ounis – G. Amati – V. Plachouras – B. He – C. Macdonald – C. Lioma: Terrier: A High Performance and Scalable Information Retrieval Platform. In Proceedings of 88
ACM SIGIR’06 Workshop on Open Source Information Retrieval (OSIR 2006) (konferenciaanyag). 2006. [11] Maria Teresa Pazienza (szerk.). Information Extraction: Towards Scalable, Adaptable Systems, Lecture Notes in Computer Science konferenciasorozat, 1714. köt. Springer, 1999. ISBN 3540666257. [12] Ungváry Rudolf – Vajda Erik: Könyvtári információkeresés. Budapest, 2002, Typotex, 169. p. ISBN 9639326291. [13] Search engines history, 2009. október. URL http://www.searchengineshistory.com. [14] Trevor Strohman – Donald Metzler – Howard Turtle – W. Bruce Croft: Indri: A language-model based search engine for complex queries (extended version). 407. IR, 2005, University of Massachusetts. [15] A tutorial on character code issues, 2009. október. URL http://www.cs.tut.fi/~jkorpela/chars.html. [16] C. J Van Rijsbergen: Information Retrieval. London, 1979, Butterworths. [17] Ellen M. Voorhees: Natural language processing and information retrieval. In Pazienza [11], 32–48. p. ISBN 3540666257. .
89