Stanislav Balocký - Slovenský Stemmer

    Table of contents
    No headers

    Úvod

    Stemming je proces redukovania ohýbaných slov do ich kmeňového resp. základného tvaru. V podstate sa jedná o hľadanie morfologického koreňa jednotlivých slov. Proces získavania koreňov slov sa často nazýva aj „zjednotenie“, je významný pri indexovaní, vyhľadávacích nástrojov a iných problémoch týkajúcich sa prirodzeného jazyka.

    Základné typy algoritmov

    • Brute force

    Brute force stemmery používajú relačnú tabuľku medzi koreňom hľadaného slova a jeho ohýbaným tvarom. Pre nájdenie koreňa sa v tabuľke vyhľadá ohýbané slovo a k nemu prislúchajúci koreň. Brute Force metóda vyžaduje z dôvodu veľkosti relačnej tabuľky taktiež veľké množstvo pamäte. V globále je nereálne pokryť úplne celú slovnú zásobu daného jazyka, a preto nemožno očakávať sto percentný výsledok.

    • Oddeľovanie sufixov 

    Pri tomto type algoritmov nedochádza k vytváraniu tabuľky relácií koreňov slov a ich ohybov, ale vytvára sa zoznam pravidiel, ktoré je potrebné vykonať. Oddeľovanie sufixov je v podstate oveľa jednoduchšou technikou, či už na hardvér alebo zložitosť implementácie. Jadrom algoritmu je odsekávanie prípon slova, ktoré sú vopred zadefinované (‘surfing’ -> ‘surf’). Nevýhodou je, že pre niektoré typy slov nie možné jednoznačne nájsť jeho koreň (‘ran’ -> ‘run’).

    • Lematizácia

    Viac komplexnejším prístupom pri získavaní základu slov je lematizácia. Tento proces zahŕňa v prvom rade rozpoznanie slovného druhu a neskôr aplikovanie rozličných normalizačných metód na každý slovný druh. Stemmovacie pravidlá sa takto menia na základe slovného druhu.

     Úloha

     a. Vytvorenie slovenského stemmera pre slovenské priezviská a  názvy ulíc. Úlohou je zadefinovanie základných pravidiel  v skriptovacom jazyku Snowball, ktorého výstupom je C - kód. Výsledný kód bude slúžiť ako modul do existujúceho C stemmera a bude rozšírený o grafické rozhranie.

     

    stemmer_state_diagram.bmp

     b. Nájsť možnosti vytvorenia stemmovacieho modulu pre textový vyhľadávací systém Lucene.

    Snowball
    Snowball je špeciálny programovací jazyk, ktorý bol vytvorení na jednoduchú reprezentáciu stemovacích algoritmov. Kompilátor snowball-a z vstupného Snowball skriptu (sbl súbor) vygeneruje buď ANSI C kompatibilný program alebo Java program. Pre ANSI C, z každého vstupného sbl súboru vznikne c súbor s odpovedajúcim hlavičkovým súborom ( subor.c a subor.h ). Podobne je to pre verziu Javy, kde pri skompilovaní sbl súboru je vygenerovaný Java súbor (subor.java).

    Definované pravidlá
    V prvom kroku je potrebné zadefinovať zoznam sufixov, ktoré budeme odsekávať:


    {a, á, i, ová, ova, ov, ého, ému, ská, ovo, iho ... } 


    Je teda potrebné zadefinovať všetky známe slovenské prípony, ktoré je potrebné odseknúť.
    Ďalšie pravidlo sa týka priezvisk končiacich na ovec, nek – Kopolovec, Szimanek. Základom priezviska Kopolovec je Kopolovc (Kopolovcov -> Kopolovc), preto je potrebné od slov končiacich na ‘ovec’ odstrániť samohlásku ‚e’. Podobné pravidlo sa týka priezviska typu Szimanek, kde je základom Szimank. (Szimánkovi -> Szimánk).

    Modul do .NetLuce

    Lucene je open source engine, ktorý poskytuje fulltext vyhľadávacie a indexačne funkcie. Pôvodne implementovaný v Jave, ale dnes dostupný v rôznych verziách pre Perl, C#, C++, Python, Ruby a PHP, ponúka otvorené a plne prispôsobiteľné riešenie.Verzia Lucene v C# verzii je dostupná tu.

    Okrem iného ponúka .Net Lucene aj knižnicu Snowball.Net. Táto knižnica slúži ako stemmer pre svetové jazyky ako (angličtina, nemčina, taliančina, španielčina, atď.), slovenskú verziu impilicitne neobsahuje. Úlohou teda je rozširiť knižnicu Snowball.Net o slovenský jazyk. Knižnicu Snowball.net.dll je nasledne možné referencovať vo vlastných projektoch a pre zvolený jazyk využiť stemmovacie funckie.

    Opis modulu

    Zadefinované pravidlá sbl súbore boli prekladačom Snowball-u vyexportovoané do Java súboru. Tento Java súbor bol následne manuálne prepísaný do jazyka C#. Takto upravený súbor bol vložený do projektu Snowbal.Net pod novým slovenským jazykom. Výsledná knižnica už teda podporovala aj slovenský jazyk.


    Testovacie dáta
     Oba programy boli testované na týchto vstupoch. Vstupné dáta boli získané z webových stránok. Tieto dáta predstavujú priezviská a ulice v rôznych skloňovaných tvaroch slovenského jazyka.

    Návod na spustenie

    Pre spustenie oboch aplikácii je potrebné mať nainštalovaný MS .Net Framework 3.5.

    • spustenie prvého riešenia

    Jedná sa o klasickú Windows Forms aplikáciu, spustiteľnú pod MS Windows. Po spustení je potrebné otvoriť súbor so vstupmi, následne sa v okne zobrazia načítané vstupy a k ním prislúchajúce korene slov.

    gui.bmp

    • spustenie modlu pre .Net Lucene

    Modul do .Net Lucene je možné otestovať nasledovným spôsobom: spustením konzolovej aplikácie Snowball.net.exe.

    Parametrom programu je jazyk (napr. slovak, german, atd.) a cesta ku vstupnému súboru. Výstupom je vypísanie koreňov slov na obrazovku konzoly.

    Zhodnotenie

    V konečnej fáze sa podarilo vytvoriť aplikácie, ktoré na testovanej množine podali pomerne slušné výsledky. Výsledky tvorili korene slov z testovacej množiny. Aplikácia podporuje taktiež  viacslovné vstupy, ktoré sú typické pre názvy ulíc resp. mena a priezviska. Aplikácie sú teda použíteľné, no pre reálne použitie v praxi by bolo potrebné rozšíriť aplikácie o nové pravidlá pre ďalšie slovné druhy ako napr. slovesá, či skloňovanie čísloviek.

    Výsledky

    Súbor výsledkov je dostupný tu. Programy boli tesotvané na vzorke 70 vstupov. Z celkového počtu vstupov bol jeden výstup nesprávny (Sepei -> Sepe). Jedná sa však o meno s cudzím významom. Konečnú úspešnosť by sme mohli vyyrátať ako pomer správnych výsledkov ku počtu celej vstupnej možiny. 

    i = (C / U).100 (C = korektné výstupy, U = početosť vstupnej množiny dát), v našom prípade: i = (69/70).100 = 98,5%. Z výsledkov vyplýva, že navrhnutý stemmer má na testovacíh dátach veľmi slušnú úspešnosť.

    Tag page (Edit tags)
    • No tags
    You must login to post a comment.
    Powered by MindTouch Core