Hana Pifková - Slovenský stemmer

    Úvod

    Cieľom projektu bolo vytvoriť slovenský stemmer podstatných mien. Ide o program, ktorý vyskloňované podstatné mená prevedie na základný tvar bez prípon. Takýto tvar sa využíva napríklad vo vyhľadávačoch, prípadne pri indexovaní a následnom prehľadávaní textových dokumentov.

    Zadanie

    Vytvoriť slovenský stemmer pre podstatné mená, zistiť jeho úspešnosť porovnaním ručne prevedených slov a slov prevedených programom. Následne sa pokúsiť o integráciu slovenského stemmera do vyhľadávacieho systému Lucene a experimentálne dokázať jeho funkčnosť.

    Motivácia

    Ako už bolo spomenuté, stemmery sa využívajú vo vyhľadávačoch. Vývoj slovenských riešení je však ešte len na začiatku. Google síce má vlastný slovenský stemmer, tento však tiež nie je úplne stopercentne funkčný. Voľne dostupný (prípadne dokonca open-source) slovenský stemmer zatiaľ neexistuje. Je to aj tým, že slovenčina je slovanský jazyk s piatimi ohybnými slovnými druhmi a gramatickými pravidlami, z ktorých každé je potvrdené nejakou výnimkou. Preto je vytvorenie slovenského stemmera náročnejšie ako napríklad anglického.

    Existujúce riešenia

    Existuje niekoľko komerčných stemmerov pre slovenčinu. Voľne dostupné sú však stemmery pre iné slovanské jazyky. My sme sa konkrétne inšpirovali pravidlami pre ruský stemmer naprogramovaný v jazyku Snowball (viac informácií a samotný algoritmus nájdete tu).

    Riešenie

    Riešením je čisto aplikácia v programovacom jazyku Java. Hlavnou triedou je Stemmer.java, obsahuje samotný algoritmus stemovania (k jednotlivým pravidlám sa ešte dostaneme). Na stiahnutie je aplikácia pripravená ako zrarovaný Eclipse projekt. Obsahuje všetky potrebné triedy, ako aj príklady testovacích vstupov a výstupov k nim prináležiacich.

    Vstupy a výstupy

    Ako vstup prijíma program textový súbor, v ktorom sú slovenské podstatné mená v rôznych tvaroch (musia byť oddelené whitespace-mi).

    Príklad vstupného súboru:

    práca prácou chodby umenie umením
    sladkosti
    vznášadlami balónikom
    hrdinami holúbätami
    srdieèko sviatku
    rasistom fľaškou hrochom hroch vrchoch
    dlane kosti krov krvi
    prstoch
    prstom
    Peter Petra
    svetrík sveter svetrom
    hrachom hrach strach

    Príklad výstupného súboru:

    práca         prác
    prácou        prác
    chodby        chodb
    umenie        umeň
    umením        umeň
    sladkosti     sladkosť
    vznášadlami   vznášadl
    balónikom     balónik
    hrdinami      hrdin
    holúbätami    holúb
    srdiečko      srdiečk
    sviatku       sviatk
    rasistom      rasist
    fľaškou       fľašk
    hrochom       hroch
    hroch         hroch
    vrchoch       vrch
    dlane         dlaň
    kosti         kosť
    krov          krov
    krvi          krv
    prstoch       prst
    prstom        prst
    Peter         Petr
    Petra         Petr
    svetrík       svetrik
    sveter        svetr
    svetrom       svetr
    hrachom       hrach
    hrach         hrach
    strach        strach

    Algoritmus

    1. Zo súboru sa načíta vstup (výsledkom je ArrayList<String>, čiže vstup je rozdelený na jednotlivé slová).
    2. Pre každé slovo zo vstupu sa spustí stemovací proces (aplikujú sa pravidlá). Výsledkom tohto procesu je výstupné slovo, respektíve koreň slova.
    3. Do výstupného súboru sa vypíšu tieto dvojice (slovo na vstupe - jeho koreň).

    Pravidlá

    Samotný stemmer funguje tak, že slovo, ktoré dostane, zbaví prípon. Pre podstatné mená je to opodstatnené, pretože predpony vždy menia význam slova (výlet vs. odlet, kdežto napríklad pre slovesá občas tento rozdiel nie je až taký badateľný). Prípon sa zbavuje postupne podľa nasledovného kľúča.

    Vytvorenie skupín prípon. Aby sme predišli tomu, že sa nám odstráni najprv kratšia prípona (napríklad v slove dievčatami chceme odstrániť "ami" a nie len "i"), rozdelíme si zoznam prípon (získaný z tabuľky skloňovania podľa vzorov) na isté levely tak, že na najvyššej úrovni sú prípony, ktoré nie sú obsiahnuté v iných. V nižších úrovniach sú potom prípony, ktoré v nich sú obsiahnuté, ale tak, že ak je nejaká prípona obsiahnuta v inej, musí byť na úrovni pod ňou. Takto sme vytvorili takýto graf prípon:

     pripony.gif

    Samotné pravidlá. Pre vstupné slovo sa potom prípony odstraňujú taktýmto spôsobom:

    1. Postupne (po leveloch) prechádzame graf prípon (od najvyššej po najnižšiu úroveň). Ak dané slovo končí danou príponou, pokračujeme krokom 2. Inak pokračujeme v prehľadávaní prípon. Ak sa slovo nekončí žiadnou príponou, pokračujeme krokom 7.
    2. Ak prípona začína na e alebo i a pred ňou sa nachádza d, t, n alebo l, ostránime príponu, posledné písmeno zvyšku nahradíme jeho mäkkým variantom (ď, ť, ň alebo ľ) a výsledok vrátime ako cieľový tvar (koreň). Inak pokračujeme krokom 3.
    3. Ak prípona patrí medzi prípony začínajúce na i, ktoré sú typické pre cudzie slová (napríklad situácia) a zvyšok slova končí na c, g, z alebo s (väčšina cudzích slov tohto typu končí na tieto písmená), odstránime príponu a k zvyšku pripojíme písmeno i a tento výsledný tvar vrátime ako cieľový tvar (koreň). Inak pokračujeme krokom 4.
    4. Overíme, či nepríde k overstemmingu ("prestemovaniu"). To by sa stalo, keby sme odstránili ako príponu niečo, čo príponou nie je. (Napríklad pre slovo hrach a príponu ach príde k overstemmingu.) Vo väčšine prípadov platí, že ak slovo po odstránení prípony obsahuje ešte nejaké samohlásky, respektíve v strede slova l, ĺ, r alebo ŕ, neprichádza k oversemmingu. Preto ak zvyšok slova obsahuje samohlásku, pokračujeme krokom 6. Ak obsahuje l, ĺ, r alebo ŕ, pokračujeme krokom 5. Inak vrátime ako výsledný tvar pôvodné slovo.
    5. Ak sa l, ĺ, r alebo ŕ nachádzajú na konci slova, prišlo k overstemmingu - vrátime pôvodné slovo ako výsledok. Inak pokračujeme krokom 6.
    6. Odstránime príponu. Pokračujeme krokom 7.
    7. Vyriešime niektoré výnimky. Ide hlavne o prípady, keď je lepšie mať koreň slova iný ako genitív singuláru. Napríklad slová sveter (svetra), sviatok (sviatku), bieliz (bielizňou), kotol (kotlom), tanec (tanca), keď odstránime poslednú samohlásku. Taktiež odstránime príponu um pre cudzie slová ako štúdium a podobne. Ak slovo končí na ic, je pravdepodobné, že k tomu prišlo ostemovaním pôvodného slova podobného slovu hubobníci - preto odstránime c a nahradíme ho písmenom k. (Mohlo by sa zdať, že by sme celú príponu ic mali nahradiť príponou ík, ale nie je tomu tak, pretože tento problém vyrieši krok 8.) Pokračujeme krokom 8.
    8. Najväčšie nepravidelnosti v skloňovaní podstatných mien vytvára genitív plurálu podstatných mien ženského a stredného rodu. Príklady: lampa - lámp, koza - kôz, mesto - miest, vlna - vĺn. Vbežnej reči platí, že prevažná väčšina podstatných mien, v ktorých je posledná slabika dlhá, je genitívom plurálu ženského alebo stredného rodu a základný tvar, ktorý hľadáme, má túto slabiku krátku. Preto, ak je posledná slabika dlhá, nahradíme dlhú hlásku alebo dvojhlásku jej krátkym variantom a výsledné slovo vrátime ako hľadaný základný tvar. Inak už nič nemeníme a vrátime slovo ako základný tvar.

    Problémy

    Ako už bolo spomenuté, slovenčina má veľa pravidiel a ešte viac výnimiek. Preto sme sa potýkali s istými ťažkosťami.

    Niektoré podstatné mená majú nepravidelné tvorenie množného čísla. Príklad: človek - ľudia, dieťa - deti. Tento problém sme neriešili - je možné vyriešiť ho, ale iba vytvorením tabuľky, resp. nejakého slovníka.

    Ďalším problémom boli pravidlá, ktoré sa navzájom "bili". Napríklad slovo lám je genitív plurálu od slova lama, kdežto slovo pán je nominatív singuláru a tým pádom by sme ho nemali meniť. Preto, ak sme narazili na takéto slová (typy slov), experimentálne sme určili približný pomer každého prípadu v bežnom článku a podľa toho upravili pravidlo, ktoré ich obhospodaruje. Tým sme minimalizovali počet nesprávne ostemovaných slov.

    Keďže náš stemmer bol vytvorený iba pre podstatné mená, je pracné a náročné pripravovať mu vhodné vstupy. Tento problém je ale v našom prípade riešitaľný iba naimplementovaním slovenského POS tagging-u  a to je dosť zložitý problém sám osebe, preto sme ho vrámci nášho projektu neriešili.

    Testovacie dáta

    Stemmer sme testovali na všetkých tvaroch všetkých vzorov podstatných mien (vzory.in), na problematických slovách (1.in a 2.in) a na dvoch článkoch zo stránky sme.sk (romovia.in a elektrina.in).

    Výsledky

    Na zhodnotenie úspešnosti sme vybrali dva články zo sme.sk, pretože sa tam nachádzajú slová, aké sa bežne vyskytujú v slovenských článkoch, v správnom pomere. Slová sme ostemovali ručne a potom porovnali s výsledkami stemmera. Tieto porovnania sa nachádzajú v súboroch elektrina1.xls a romovia1.xls.

    Úspešnosť stemmera s sme vyrátali ako pomer správne určených k celkovému počtu slov. Pre porovnanie sme vyrátali podobný pomer sn aj pre neopakujúce sa slová (tj že každé slovo sa započíta iba raz). Pre porovnávacie súbory nám vyšli výsledky takéto:

    s1 = 181 / 200 = 0,905

    sn1 = 124 / 138 = 0,898551

    s2 = 231 / 250 = 0,924

    sn2 = 195 / 213 = 0,915493

    Vidíme, že úspešnosť je pre neopakujúce sa slová nižšia než pre všetky. Z toho sa dá odvodiť, že pre často používané slová stemmer pracuje lepšie ako pre niektoré málo používané tvary. Celkovo sa úspešnosť pohybuje okolo 90 a viac percent, čo je vcelku úspech, keď vezmeme do úvahy, že sme nepoužili žiaden slovník s výnimkami a že slová ako ľudia a deti sú dosť často používané.

    Integrácia do Lucene

    Integráciu do Lucene sme vyriešili vytvorením vlastných podtried tried Analyzer (SlovakAnalyzer) a TokenFilter (SlovakFilter). Následne sme vytvorili jednoduchú konzolovú aplikáciu vhodnú na experimentovanie a debugovanie.

    Rozhodli sme sa experimentovať trošku aj so zoznamom stopwords - slov, ktoré sa nestemujú a hneď na začiatku stemovania tento proces zastavia. Príklad takéhoto zoznamu (značne okliešteného a neúplného, treba samozrejme rátať aj s tým, že keďže náš stemmer je použiteľný len na podstatné mená, niektoré slová v tomto zozname sú aj iným stemmerom stemovateľné (napríklad slovesá)) si môžete pozrieť tu.

    PRiebeh programu je nasledovný.

    Aplikácia najprv zaidexuje 5 predpripravených textových súborov (v každom sa kvôli prehľadnosti nachádzajú len dve slová, ale rožšírenie je úplne jednoduché - stačí zmeniť obsah súborov v priečinku files1).

    Následne si od používateľa vypýta query (používateľ zadá jednotlivé hľadané výrazy do konzoly) a prejde indexom dokumentov. Ak nájde v niektorom dokumente jeden/viac hľadaných výrazov (resp. výrazov s rovnakým koreňom, ako majú hľadané výrazy), vypíše na obrazovku názov súboru a skóre zhodnosti (ktoré mu pridelila ohodnocovacia funkcia vrámci Lucene).

    Program pracuje bez problémov, až na to, že skóre nadobúda podivné hodnoty. To je však vec Lucene a s našou aplikáciou to má spoločné len toľko, že to vyzerá zle pri zobrazení. Vyššie skóre znamená bližšiu podobnosť query a zaindexovaného súboru.

    Inštalácia a spustenie

    V oboch prípadoch ide  oprojekt v Jave, je potrebné mať nainštalovanú minimálne Javu 5. Potom treba zrarovaný projekt rozbaliť, v prípade integrácie do Lucene je potrebné mať stiahnutý aj balík Lucene. Následne treba projekty skompilovať a spustiť triedu Experiment (pre integráciu do Lucene) alebo triedu Zadanie (pre pôvodné zadanie).

    Tag page (Edit tags)
    • No tags

    Files 16

    FileSizeDateAttached by 
     1.in
    No description
    245 bytes21:07, 15 Jan 2009Hana.PifkovaActions
     1.out
    No description
    422 bytes21:08, 15 Jan 2009Hana.PifkovaActions
     2.in
    No description
    158 bytes21:07, 15 Jan 2009Hana.PifkovaActions
     elektrina.in
    No description
    1823 bytes21:07, 15 Jan 2009Hana.PifkovaActions
     elektrina1.xls
    výsledky 2
    33.5 kB21:06, 15 Jan 2009Hana.PifkovaActions
     lucene-core-2.4.0.jar
    lucene knižnice (potrebné pre spustenie projektu lucene_slovak_stemmer)
    799.77 kB21:06, 15 Jan 2009Hana.PifkovaActions
     lucene_slovak_stemmer.rar
    integrácia do Lucene (Eclipse projekt)
    17.08 kB21:04, 15 Jan 2009Hana.PifkovaActions
     pripony.gif
    No description
    69.65 kB00:25, 16 Jan 2009Hana.PifkovaActions
     romovia.in
    No description
    3.54 kB21:07, 15 Jan 2009Hana.PifkovaActions
     romovia1.xls
    výsledky 1
    50 kB21:06, 15 Jan 2009Hana.PifkovaActions
     SlovakAnalyzer.java
    No description
    1930 bytes21:22, 15 Jan 2009Hana.PifkovaActions
     SlovakFilter.java
    No description
    1581 bytes21:22, 15 Jan 2009Hana.PifkovaActions
     Stemmer.java
    trieda obsahujúca samotný stemovací algoritmus
    7.37 kB21:04, 15 Jan 2009Hana.PifkovaActions
     stemmer.rar
    slovenský stemmer (Eclipse projekt)
    15.68 kB21:04, 15 Jan 2009Hana.PifkovaActions
     stopwords_file.txt
    príklad zoznamu stop-slov
    527 bytes21:33, 15 Jan 2009Hana.PifkovaActions
     vzory.in
    No description
    2.69 kB21:07, 15 Jan 2009Hana.PifkovaActions
    You must login to post a comment.
    Powered by MindTouch Core