Pavol Humay - Stemmer slovenského jazyka (5)

     

    Úvod

    Problém vyhľadávania základných tvarov slov má motiváciu napr. v prehľadávacích nástrojoch. Spravidla ak používateľ chce nájsť slovo „autami“ najskôr ho bude zaujímať aj výsledok hľadania pre slovo „auto“, prípadne pre iné tvary tohto slova. Rozšírením prehľadávania aj o iné tvary slova sa množstvo relevantných výsledkov hľadania zväčší a zvyšuje šance na nájdenie správneho výsledku pre používateľa.

    Ďalšou motiváciou pre úpravu slov na ich základný tvar je oblasť komunikácie medzi strojom a človekom. Napr. algoritmy na konverziu prirodzeného jazyka na formálny jazyk prevedú vety prirodzeného jazyka do formálnejšej reprezentácie. Prípadne algoritmy na konverziu formálneho jazyka do prirodzeného transformujú

    Pojem Stemovanie

    Stemovanie je proces úpravy slov na ich základny (koreňový) tvar. Napr. koreňom slova „autá“ je slovo „auto“. Existujú rôzne prístupy na hľadanie základných tvarov slov. Niektoré využívajú slovníky, podľa ktorých identifikujú slovo alebo úpravu ktorá sa má vykonať, iné využívajú úpravy ktoré sa aplikujú podľa aktuálneho tvaru slova alebo umiestnenia slova vo vete.

    Prehľad existujúcich algoritmov

    Slovníkový algoritmus

    Tento algoritmus vychádza z predpokladu, že máme k dispozícii slovník rozvinutých tvarov a k nim prislúchajúcich základných tvarov. Samotný algoritmus iba vyhľadáva v tomto slovníku slová a nahrádza ich základným tvarom. Nevýhodou tejto metódy je pomerne veľká pamäťová a časová náročnosť na vyhľadanie slov v slovníku. Tiež je problémom takýto slovník vytvoriť. Na druhej strane poskytuje výhodu oproti iným, sofistikovanejším algoritmom. Pri veľa slovách a pravidlách existujú výnimky. Slovníkový algoritmus práve tieto výnimky dokáže správne spracovať (ak sa v jeho slovníku nachádzajú), zatiaľ čo iné algoritmy ich nemusia správne identifikovať.

    Porovnávací algoritmus

    Ide o obdobu slovníkového algoritmu. Je tu však jeden rozhodujúci rozdiel. A to ten, že na miesto udržiavania všetkých rozvinutých tvarov slov, udržujeme iba „jadro“ slov, ktoré je identické pre všetky jeho rozvinuté tvary. Napr. Majme slovo „auto“ jeho rozvinuté tvary „autom“, „autá“, „autami“... Jeho jadrom sa zdá byť teda slovo „aut“ ktoré samo o sebe nie je ani slovom, ale nachádza sa v každom rozvinutom tvare. Samozrejme existujú slová v ktorých by sa toto jadro nachádzalo tiež, napr. slovo „automat“. Preto musí byť zabezpečené aby ku každému jadru boli dodatočné pravidlá na určenie správneho slova. Výhodou tohto algoritmu je skoro rovnaká sila určovania základných slov ako pri slovníkovom algoritmu, ale využívaný slovník je podstatne menší. Z toho vyplýva aj väčšia rýchlosť a menšia pamäťová náročnosť algoritmu.

    Algoritmus odstraňovania sufixov

    Zakladá sa na odstraňovaní sufixov zo slov. V slovenskom jazyku je skor potreba odstránenie sufixu doplniť o nahradenie základného sufixu. Napr. pri slove „autami“ dosiahneme základný tvar odstránením sufixu „ami“ a pridaním nového sufixu „o“. Spôsob hľadania sufixov musí vychádzať z gramatiky jazyka. Keďže sa zaoberáme slovenským jazykom, vychádzame z gramatiky pre slovenský jazyk.

    Algoritmus odstraňovania prefixov a sufixov (affix)

    Podobne ako u algoritmu odstraňovania sufixov postupuje aj tento algoritmus. Umožňuje však silnejšie úpravy odstraňovaním nie len sufixov ale aj prefixov. Napr. slovo „nemali“ dokáže odstránením prefixu „ne“ a nahradením sufixu „ali“ za „ať“ upraviť na tvar „mať“. Nevýhodou algoritmov tohto typu je správne určenie ktoré ktorý sufix akým nahradiť. Na toto je vhodné slová identifikovať a vedieť ako ktoré sufixy a prefixy spracovávať.

    Lemmatizačný algoritmus

    Proces tohto algoritmu je založený na identifikovaní významu slova z kontextu. Pravidlá normalizácie slova sa potom určujú podľa toho v akej pozícii vo vete sa nachádza. Pravidlá normalizácie predstavujú zväčša odstraňovanie sufixov alebo prefixov.

    Stochasticky algoritmus

    Základným princípom tohto algoritmu je využívanie trénovania na množine rozvinutých slov a ich základných tvarov a následné aplikovanie natrénovaných pravidiel na slová u ktorých hladáme základný tvar. Výsledkom trénovania je model pravdepodobností, podľa ktorého sa následne vyberajú pravidlá normalizácie slov. Tu je nevýhodou, že nájdené základné tvary majú podľa natrénovaného modelu najvyššiu pravdepodobnosť byť správnymi. Ale nie vždy to musí platiť. Pre tento algoritmus je veľmi dôležitý proces učenia. Ako bude následne pracovať zaleží od trénovacej množiny.

    Hybridné prístupy

    Ide o kombináciu rôznych prístupov. Cieľom je vhodnou kombináciou docieliť najlepšie výsledky. Napr. pri odstraňovaní sufixov použijeme slovníkový prístup na identifikovanie typu slova (určíme aké pravidlá pre toto slovo platia).

    Prehľad existujúcich nástrojov

    Porter Stemming Algorithm

    Webové rozhranie poskytuje možnosť transformácie anglického textu na text v základnom tvare. Ide o webové rozhranie ktoré slúži výhradne na testovacie účely.

    http://utilitymill.com/utility/Porter_Stemming_Algorithm

    The Lancaster Stemming Algorithm

    Nástroj ktorý slúži na testovanie použitého algoritmu. Je implementovaný v jave a poskytuje grafické rozhranie. Používa odstraňovanie affixov.

    http://www.comp.lancs.ac.uk/computing/research/stemming/index.htm

    [ANN] Ruby-Stemmer

    Ide o knižnicu naprogramovanú v SnowBall API programovaný v jazyku RUBY. Podporuje viacero jazykov a aj algoritmov (používa vlastné označenie algoritmov bez ich popisu).

    http://www.locknet.ro/projects/ann-ruby-stemmer

    Implementácia zadania

    Na začiatku som sa snažil vytvoriť slovníkový algoritmus. Problém bol však nájsť vyhovujúci slovník ktorý by som na tento účel použil. Preto som použil iný prístup. Popis ako by sa dal takýto slovník vytvoriť som popísal v zhodnotení (posledná kapitola). Jeho overenie by však nebolo možné ak by som nemal alternatívny prístup k stemovaniu zvoleného textu.

    Algoritmus

    V mojom zadaní boli implementované dva algoritmy na spracovanie vstupov. Prvým je odstraňovanie sufixov, druhy je slovníkový algoritmus.

    Odstraňovanie sufixov

    U tohto algoritmu nebol implementovaný žiaden ďalší prístup na identifikovanie aké sufixy sa majú pre konkrétne slova odstraňovať. Určovanie pravidiel na odstraňovanie sufixov vychádza z gramatických pravidiel slovenského jazyka. V prípade že by sa dané pravidlo dalo aplikovať na rôzne slová, nebolo implementované. Jeho použitie by prinieslo správny výsledok iba v niektorých prípadoch.

    Slovníkový algoritmus

    Tento algoritmus bol už rozoberaný v predchádzajúcich kapitolách. Preto sa nebudem venovať priamo jemu ale samotnému slovníku. Keďže sa mi nepodarilo nájsť vhodný slovník pomocou ktorého by som dokázal transformovať zvolené slovo na slovo v základnom tvare. Preto som použil existujúci slovník slov ktorý som mal k dispozícii a z neho sa pokúsil vytvoriť prekladový slovník. Slovník som tvoril nasledovne: ku každému slovu som skúmal nasledujúce slová. Ak boli aspoň na 60% podobné, považoval som ich za rozvinutú formu prvého slova. Takto som postupne vytváral páry rozvinutého tvaru a základného. Pomocou tohto slovníka sa dá tiež hľadať základný tvar. Keďže nie je možné overiť jeho správnosť pomocou nejakého algoritmu, je možnosť po spracovaní manuále označiť, ktoré slová majú správny základný tvar a ktoré nie. Táto možnosť sa týka aj predchádzajúceho algoritmu keďže porovnávanie so slovníkom vytvára iba možnosť overiť či ide o slovo ale nie o slovo v základnom tvare (potrebovali by sme slovník základných tvarov na správne overenie čo nás znova stavia pred úlohu tvorby takého slovníku a otázku jeho správnosti.

    Vypracovanie

    Nástroj bol implementovaný v jazyku PHP a za použitia databázového systému MySQL. Nástroj umožňuje načítavať existujúce linky z internetu, spracovať ich a uložiť získané informácie o stránke do databázy. V spracovaných stránkach je možné vykonávať vyhľadávanie. Pri následnom zobrazení prehľadávaných stránok sú hľadané slová zvýraznené. Po načítaní a spracovaní stránky sa zobrazia identifikované slova a štatistika spracovania. Slová ktoré bolí upravené stemovacím algoritmom sú farebne odlíšené.

    Zhodnotenie výsledkov

    Vyhodnotenie testovacieho vstupu ktorý je priložený na wiki stránke projektu.

    Metóda odstraňovania sufixov bola úspešný v 52,8% prípadoch, slovníková metóda v 32.3% prípadoch. Automatické overenie voči slovníku ukázalo správnosť v 49,5% prípadoch. Overovanie voči slovníku poskytuje menšiu úspešnosť pretože slovník neobsahuje všetky slová ktoré sa na testovanej stránke vyskytovali. Prípady keď upravené slovo nebolo v základnom tvare ale bolo to správne slovo som na tejto testovanej stránke nezaznamenal. To by výslednú správnosť naopak zvyšovalo aj keď by vlastne šlo o nesprávny údaj.

    Inštalácia

    Na fungovanie nástroj potrebuje webový server ktorý poskytuje PHP a MySQL služby. Najskôr je potrebné vytvoriť databázu a do nej pomocou obsahu súboru database.sql vložiť potrebné tabuľky. Pred používaním je potrebné vložiť do databázy slovník, ktorý je zahrnutý v súboroch dict.sql a transDict.sql. Tento je dosť veľký preto odporúčam vkladanie cez konzolu databázy. Tu je dôležité kódovanie. V databáze je pri vytváraní tabuliek nastavené UTF-8 kódovanie textových polí. Preto je potrebné pri práci v konzole mať tiež nastavené rovnaké kódovanie. Inak by sa mohlo stať, že vložené údaje budú nepoužiteľné. Nastavenia prístupu k databáze sa nastavujú v hlavičke zdrojového súboru.

    Zhodnotenie

    Výsledná práca algoritmu sa ukázala ako veľmi nepresná. Toto je spôsobené neinformovanosťou pri výbere pravidla na úpravu slova. Taktiež neboli pri tvorbe pravidiel zvážené výnimky gramatiky. To má za následok ďalšiu redukciu kvality algoritmu. Zlepšenie práce algoritmu by sa dalo dosiahnuť vytvorením slovníka, ktorý by upresňoval výber pravidla. Podobne ako u algoritmu ktorý používa prekladový slovník, by sme mali slovník ktorý by neuvádzal základný tvar slova, ale aké úpravy sa s týmto slovom dajú vykonávať. Týmto by sme dosť stratili na výkone algoritmu (lebo by sme museli vykonávať porovnávanie voči veľkému slovníku) ale získali na efektivite aj keď by bola menšia ako u slovníkového algoritmu. Preto by bolo lepším riešením zohľadňovať pozíciu slova vo vete a takto sa snažiť odhadnúť aké pravidlá používať. Algoritmus by stále nebol úplne presný, ale bol by časovo menej náročný ako slovníkový algoritmus a súčasne efektívnejší ako implementovaný algoritmus. Ale už by sme nemohli hovoriť o stemovaní ale o lematizácii.


     

    Tag page (Edit tags)
    • No tags

    Files 6

    FileSizeDateAttached by 
     clanok_sme.zip
    Testovacie Data
    112.97 kB12:29, 6 Jan 2009pavol.humayActions
     database.zip
    skript na vytvorenie databazy
    464 bytes12:40, 6 Jan 2009pavol.humayActions
     prezentacia.pdf
    Prezentacia projektu
    47.13 kB00:33, 12 Dec 2008pavol.humayActions
     projekt (1).zip
    samotny projekt
    5.93 kB12:43, 6 Jan 2009pavol.humayActions
     skript.zip
    skript na generovanie slovnikov zo zakladneho slovnika (aj prekladoveho)
    557.63 kB12:43, 6 Jan 2009pavol.humayActions
     slovniky_data.zip
    slovniky
    1561.86 kB12:40, 6 Jan 2009pavol.humayActions
    You must login to post a comment.
    Powered by MindTouch Core