Stemming je proces hledání kmene slova pro dané zdrojové slovo. Kmen slova nemusí být nutně stejný jako morfologický kořen slova .
Úkol najít kmen slova je dlouhodobý problém v informatice . První publikace na toto téma pochází z roku 1968 . Stemming se používá ve vyhledávačích k rozšíření vyhledávacího dotazu uživatele , je součástí procesu normalizace textu .
Specifický způsob řešení problému hledání základu slov se nazývá stemming algorithm a specifickou implementací je stemmer .
První publikovaný stemmer napsala Julie Beth Lovins v roce 1968 [1] . Tento dokument je pozoruhodný svým raným datem vydání a měl velký vliv na pozdější práci v oboru.
Stemmer později napsal Martin Porter a publikoval v roce 1980. Tento stemmer byl velmi široce používán a stal se de facto standardním algoritmem pro texty v angličtině. Dr. Porter obdržel cenu Strix v roce 2000 za svou práci na stopování a získávání informací.
Mnoho implementací Porterova stemming algoritmu bylo napsáno a volně distribuováno; mnoho z těchto implementací však obsahuje těžko zjistitelné nedostatky. V důsledku toho tyto algoritmy nefungovaly naplno. K odstranění tohoto typu chyb vydal Martin Porter kolem roku 2000 oficiální bezplatnou implementaci algoritmu. V této práci pokračoval během několika příštích let vývojem Snowball , rámce pro vytváření stemmingových algoritmů a vylepšených anglických stemmerů, stejně jako stemmerů pro několik dalších jazyků.
Existuje několik typů stemmingových algoritmů, které se liší z hlediska výkonu, přesnosti a způsobu, jakým jsou překonány určité steming problémy.
Jednoduchý stemmer vyhledá ve vyhledávací tabulce flektivní formu . Výhodou tohoto přístupu je jeho jednoduchost, rychlost a snadné zpracování výjimek. Mezi nevýhody patří, že všechny tvary skloňování musí být v tabulce výslovně uvedeny: nová nebo neznámá slova nebudou zpracována, i když jsou správná (např. iPady ~ iPad) a problém je také v tom, že vyhledávací tabulka může být velmi velká. U jazyků s jednoduchou morfologií, jako je angličtina, jsou velikosti tabulek malé, ale pro jazyky s vysokou flektivitou (jako je turečtina) může mít tabulka stovky možných forem skloňování pro každý kořen.
Vyhledávací tabulky používané v stemmerech jsou obvykle generovány poloautomaticky. Například pro anglické slovo „run“ se automaticky vygenerují tvary „running“, „runs“, „runned“ a „runly“. Poslední dva formuláře jsou platnými konstrukcemi, ale je nepravděpodobné, že se objeví v běžném anglickém textu.
Algoritmus hledání může použít předrozdělovací značku , aby se vyhnul tomuto druhu chyby lemmatizace , když jsou ke stejnému lemmatu přiřazena různá slova (přecenění) [2] .
Algoritmy zkracování zakončení nepoužívají vyhledávací tabulku, která se skládá z inflexních forem a vztahů kořen-forma. Místo toho je obvykle uložen menší seznam „pravidel“, který využívají algoritmy, daný tvar slova, k nalezení jeho kmene [3] . Některé příklady pravidel vypadají takto:
Algoritmy zkrácení ukončení jsou mnohem účinnější než algoritmy hrubé síly . K vývoji takových algoritmů je zapotřebí programátor, který se poměrně dobře orientuje v lingvistice , zejména morfologii , a je také schopen kódovat „pravidla zkrácení“. Algoritmy zkracování ukončení jsou neefektivní pro výjimky (např. 'ran' a 'run'). Řešení získaná ukončovacími algoritmy zkracování jsou omezena na ty části řeči , které mají dobře známé koncovky a přípony, až na některé výjimky. To je vážné omezení, protože ne všechny slovní druhy mají dobře definovaný soubor pravidel. Lemmatizace se pokouší toto omezení odstranit.
Mohou být také implementovány algoritmy zkracování prefixů. Ne všechny jazyky však mají předpony a přípony.
Další kritéria pro algoritmyAlgoritmy zkracování ukončení se mohou ve výsledcích lišit z různých důvodů. Jedním z těchto důvodů je zvláštnost algoritmu: zda slovo na výstupu algoritmu musí být skutečné slovo v daném jazyce. Některé přístupy nevyžadují přítomnost slova v odpovídajícím jazykovém lexikonu . Některé algoritmy navíc udržují databázi všech známých morfologických kořenů, které existují jako skutečná slova. Tyto algoritmy kontrolují přítomnost termínu v databázi a rozhodují se. Pokud termín není nalezen, jsou zpravidla podniknuty alternativní kroky. Tyto alternativní akce mohou k rozhodování používat mírně odlišná kritéria. Termín, který neexistuje, může sloužit jako alternativní pravidlo zkrácení.
Může se stát, že na stejný vstupní výraz platí dvě nebo více pravidel zkrácení, což vytváří nejednoznačnost, které pravidlo se má použít. Algoritmus může určit prioritu provádění takových pravidel (s pomocí osoby nebo stochastickým způsobem). Nebo může algoritmus odmítnout jedno z pravidel, pokud má za následek neexistující termín, zatímco druhé nikoli. Například pro anglický výraz "friendly" může algoritmus určit příponu "ies", použít příslušné pravidlo a vrátit výsledek "přátelský". Výraz "přátelský" s největší pravděpodobností v lexikonu nenajdete, a proto bude toto pravidlo odmítnuto.
Jedním z vylepšení algoritmů zkracování přípon je použití přípon a substituce přípon. Stejně jako pravidlo zkrácení nahrazuje pravidlo náhrady příponu nebo koncovku alternativní. Může například existovat pravidlo, které nahradí „ies“ „y“. Protože pravidla zkrácení vedou k neexistujícímu termínu v lexikonu, pravidla substituce tento problém řeší. V tomto příkladu je „přátelský“ převeden na „přátelský“ namísto „přátelský“.
Aplikace těchto pravidel je obvykle cyklická nebo rekurzivní. Po první aplikaci substitučního pravidla pro tento příklad algoritmus vybere další pravidlo pro „přátelský“ výraz, v důsledku čehož bude identifikováno a rozpoznáno pravidlo zkrácení přípony „ly“. Z pojmu „přátelský“ se tak prostřednictvím substitučního pravidla stává výraz „přátelský“, který se po aplikaci pravidla o zkrácení stává pojmem „přítel“.
Tento příklad pomáhá demonstrovat rozdíl mezi metodou založenou na pravidlech a metodou hrubé síly . Pomocí vyčerpávajícího vyhledávání bude algoritmus hledat výraz „přátelské“ v množině stovek tisíc skloňovaných slovních tvarů a v ideálním případě najde odpovídající kmen „přítel“. V metodě založené na pravidlech se pravidla provádějí postupně, což vede ke stejnému řešení. S největší pravděpodobností bude metoda založená na pravidlech rychlejší.
V lingvistice jsou nejběžnějšími termíny pro afixy přípona a předpona. Kromě přístupů, které zpracovávají přípony nebo koncovky, některé z nich zpracovávají také předpony. Například pro anglické slovo neurčitě tato metoda určí, že konstrukce "in" na začátku slova je předpona a lze ji odstranit, aby se získal kmen slova. Mnoho z výše uvedených metod také používá tento přístup. Algoritmus zkrácení konce například zvládne jak přípony, tak koncovky, stejně jako předpony, v takovém případě se bude nazývat jinak a bude se řídit tímto přístupem. Výzkum afixových stemmerů pro několik evropských jazyků lze nalézt v publikaci ( Jongejan et al 2009 ).
Složitějším přístupem k řešení problému určování kmene slova je lemmatizace . Abyste pochopili, jak lemmatizace funguje, musíte vědět, jak se vytvářejí různé formy slova. Většina slov se mění, když jsou použita v různých gramatických tvarech . Konec slova je nahrazen gramatickou koncovkou, což vede k novému tvaru původního slova. Lemmatizace provádí obrácenou transformaci: gramatickou koncovku nahradí sufixem nebo koncovkou počátečního tvaru [4] .
Lemmatizace také zahrnuje určování slovního druhu slova a aplikaci různých normalizačních pravidel pro každý slovní druh. Definice slovního druhu nastává před pokusem o nalezení kmene, protože u některých jazyků pravidla odvození závisí na slovním druhu daného slova.
Tento přístup je velmi závislý na přesné definici lexikální kategorie (slovního druhu). Přestože se normalizační pravidla pro některé lexikální kategorie překrývají, specifikování nesprávné kategorie nebo neschopnost určit správnou kategorii neguje výhodu tohoto přístupu oproti algoritmu zkracování. Hlavní myšlenkou je, že pokud je stemmer schopen získat více informací o zpracovávaném slově, pak může aplikovat přesnější pravidla normalizace.
Přístup k pravidlům zvlněníRipple-down pravidla byla původně navržena k získání znalostí a udržování systémů založených na pravidlech. V tomto přístupu jsou znalosti získávány na základě aktuálního kontextu a postupně přidávány. Pravidla jsou vytvořena pro klasifikaci případů, které odpovídají konkrétnímu kontextu.
Na rozdíl od standardních klasifikačních pravidel pravidla Ripple-down používají výjimky ze stávajících pravidel, takže změny souvisejí pouze s kontextem pravidla a neovlivňují ostatní. Nástroje pro získávání znalostí vám pomohou najít a upravit konfliktní pravidla. Zde je jednoduchý příklad pravidla Ripple-down :
if a ^ b then c except if d then e else if f ^ g then h
Toto pravidlo lze interpretovat následovně: „jestliže a a b jsou pravdivé, pak rozhodneme c , kromě případů, kdy d neplatí. Je-li d pravdivé (výjimka), pak učiníme rozhodnutí e . Pokud a a b neplatí, přejdeme k jinému pravidlu a rozhodneme h , pokud jsou f a g pravdivé." Tato forma pravidel velmi dobře řeší problém lemmatizace [5] .
K vytvoření výjimky z pravidla musí algoritmus nejprve určit slovo, které vyvolalo danou výjimku. Poté se určí rozdíly mezi těmito dvěma slovy. Výjimečná podmínka pravidla bude odpovídat těmto rozdílům.
Stochastické algoritmy jsou spojeny s pravděpodobnostním určením kořenové formy slova. Tyto algoritmy vytvářejí pravděpodobnostní model a jsou trénovány pomocí tabulky korespondence mezi kořenovými a inflexními formami. Tento model je obvykle prezentován ve formě komplexních lingvistických pravidel, která jsou svou povahou podobná pravidlům používaným v algoritmech zkracování a lemmatizace. Stemming se provádí zavedením upravených formulářů pro trénování modelu a generováním kořenového formuláře podle vnitřní sady pravidel modelu, kromě toho, že rozhodnutí související s aplikací nejvhodnějšího pravidla nebo sekvence pravidel, stejně jako s volbou kmene slova, jsou aplikovány na základě toho, že výsledné správné slovo bude mít největší pravděpodobnost (chybná slova mají nejmenší pravděpodobnost).
Některé lemmatizační algoritmy jsou stochastické v tom smyslu, že slovo může patřit do několika slovních druhů s různou pravděpodobností. Tyto algoritmy mohou také brát v úvahu okolní slova, nazývaná kontext. Bezkontextové gramatiky neberou v úvahu žádné další informace. V obou případech se po přiřazení pravděpodobnosti každému možnému slovnímu druhu vybere slovní druh s nejvyšší pravděpodobností a také odpovídající pravidla pro získání normalizovaného tvaru.
Některé stemmingové algoritmy používají N-gram analýzu k výběru vhodného kmene pro slovo [6] .
Vycházet z korpusu textůJednou z hlavních nevýhod klasických stemmerů (jako Porterova stemmer) je, že často nerozlišují mezi slovy s podobnou syntaxí, ale zcela odlišným významem. Například „novinky“ a „nový“ budou v důsledku odvození redukovány na kmen „nový“, ačkoli tato slova patří do různých lexikálních kategorií. Dalším problémem je, že některé stemming algoritmy mohou být vhodné pro jeden korpus a způsobit příliš mnoho chyb v jiném. Například slova „stock“, „stocks“, „stocking“ atd. budou mít v textech deníku The Wall Street Journal zvláštní význam . Hlavní myšlenkou korpusu založeného stemmeru je vytvořit třídy ekvivalence pro slova klasických stemmerů a poté „rozbít“ některá slova kombinovaná na základě jejich výskytu v korpusu. Pomáhá také předcházet známým kolizím Porterova algoritmu, jako je „politika/policie“, protože pravděpodobnost, že se tato slova vyskytnou společně, je poměrně nízká [7] .
Takové algoritmy používají databázi kmenů (například soubor dokumentů obsahujících kmeny slov). Tyto kmeny nemusí nutně odpovídat běžným slovům, ve většině případů je kmen podřetězec (např. pro angličtinu je „brows“ podřetězec ve slovech „browse“ a „browsing“). Aby bylo možné určit kořen slova, algoritmus se jej snaží porovnat s kmeny z databáze, přičemž uplatňuje různá omezení, například na délku hledaného kmene ve slově vzhledem k délce samotného slova (např. například krátká předpona „být“, která je základem takových slov, jako „být“, „být“ a „být“ by netvořila základ výrazu „vedle“).
Hybridní přístupy využívají dvě nebo více metod popsaných výše. Jednoduchým příkladem je algoritmus sufixového stromu , který na začátku své práce používá vyhledávací tabulky k získání počátečních dat pomocí vyčerpávajícího vyhledávání. Místo uložení celého komplexu vztahů mezi slovy pro konkrétní jazyk se však používá vyhledávací tabulka pro uložení malého počtu „častých výjimek“ (například pro anglický jazyk „ran => run“). Pokud slovo není v seznamu vyloučení, použijí se k získání výsledku ukončovací algoritmy zkrácení nebo lemmatizace.
Zatímco většina raných vědeckých aktivit v této oblasti byla zaměřena na angličtinu (většinou pomocí algoritmu Porter stemming), následné práce byly věnovány mnoha dalším jazykům [8] [9] [10] [11] [12] .
Hebrejština a arabština jsou stále považovány za obtížné jazyky, které se lze naučit z hlediska pramenitosti. Anglické odvozené algoritmy jsou poměrně triviální (vyskytují se pouze občasné problémy, například slovo „dries“ je ve třetí osobě jednotného čísla přítomného času slovesa „dry“ nebo slovo „axes“ je množné číslo od „axe“ a „ osa"); ale stemmery se stávají obtížnějšími, když je vybrán složitější cílový jazyk, jmenovitě jazyk se složitější morfologií a pravopisem. Například stemmery pro italský jazyk jsou složitější než stemmery pro angličtinu (vzhledem k velkému množství flektivních tvarů sloves), implementace pro ruský jazyk jsou ještě obtížnější (velké množství deklinací podstatných jmen), pro hebrejštinu jsou ještě složitější (kvůli nezřetězené morfologii). , psaní bez samohlásek a potřeba algoritmů pro zkracování předpon: kmeny hebrejských slov mohou být dlouhé dva, tři nebo čtyři znaky, ale ne déle) a tak dále.
Vícejazyčné algoritmy stemming aplikují morfologická pravidla dvou nebo více jazyků současně.
Ruský jazyk patří do skupiny flektivních syntetických jazyků, to znamená jazyků, ve kterých převládá tvoření slov pomocí přípon kombinující několik gramatických významů najednou (například druh - koncovka й označuje současně jednotné číslo, mužský rod a nominativní případ), proto tento jazyk umožňuje použití stemming algoritmů. Ruský jazyk má složitou morfologickou změnu slov, která je zdrojem chyb při používání kmenování. Jako řešení tohoto problému lze spolu s klasickými stemming algoritmy použít lemmatizační algoritmy, které přivádějí slova do výchozího základního tvaru.
Uvažujme o nejoblíbenějších implementacích stemmerů založených na různých principech a umožňujících zpracování neexistujících slov pro ruský jazyk.
Stemmer PorterHlavní myšlenkou Porterova stemmeru je, že existuje omezený počet slovotvorných přípon a ke tvoření slov dochází bez použití jakýchkoli kmenových základů: pouze sada existujících přípon a ručně nastavená pravidla.
Algoritmus se skládá z pěti kroků. V každém kroku je odříznuta slovotvorná přípona a zbývající část je zkontrolována z hlediska souladu s pravidly (například u ruských slov musí kmen obsahovat alespoň jednu samohlásku). Pokud výsledné slovo splňuje pravidla, dojde k přechodu na další krok. Pokud ne, algoritmus zvolí pro oříznutí jinou příponu. V prvním kroku je maximální tvarotvorná přípona odříznuta, ve druhém - písmeno "i", ve třetím - slovotvorná přípona, ve čtvrtém - přípony superlativů, "ь" a jedno ze dvou "n" [13] .
Tento algoritmus často zkracuje slovo více, než je nutné, což ztěžuje získání správného kmene slova, například postel-> střecha (v tomto případě je skutečně nezměněná část postel , ale kmen volí nejdelší morfém pro vymazání). Také Porterův stemmer nezvládá nejrůznější změny v kořenu slova (například vypadávání a plynulé samohlásky).
StemkaTento stemming algoritmus (analyzátor) vyvinul Andrey Kovalenko v roce 2002. Je založen na pravděpodobnostním modelu: slova z cvičného textu jsou analyzátorem analyzována do dvojic „poslední dvě písmena kmene“ + „přípona“, a pokud se taková dvojice již v modelu vyskytuje, její váha se zvýší. , jinak se přidá do modelu. Poté je výsledné pole dat seřazeno v sestupném pořadí podle hmotnosti a modely, jejichž pravděpodobnost je menší než 1/10000, jsou oříznuty. Výsledek – sada potenciálních koncovek s podmínkami na předchozích znacích – je invertován pro usnadnění skenování slovních forem „zprava doleva“ a je prezentován jako přechodová tabulka konečného automatu. Při analýze je slovo skenováno podle vytvořených přechodových tabulek. Do algoritmu bylo také přidáno speciální pravidlo, které stanoví, že neměnný kmen musí obsahovat alespoň jednu samohlásku [14] .
Prezentovaný analyzátor je dostupný ve zdrojových textech a lze jej používat ve volné formě s podmínkou odkazu na zdroj [15] [16] .
MyStemStemmer MyStem vyvinul Ilya Segalovich v roce 1998. Nyní je majetkem společnosti Yandex [17] . V prvním kroku se pomocí příponového stromu ve vstupním slově určí možné hranice mezi kmenem a příponou, načež se pro každý potenciální kmen (počínaje nejdelším) binárním vyhledáváním ve kmenovém stromu ověří jeho přítomnost v slovník nebo nalezení stopek nejblíže k němu (mírou blízkosti je délka společného "ocasu"). Je-li slovo slovem ze slovníku, algoritmus se ukončí, jinak pokračuje do dalšího oddílu.
Pokud kmenová varianta neodpovídá žádnému z „nejbližších“ slovníkových kmenů, znamená to, že analyzované slovo s touto kmenovou variantou není ve slovníku. Poté se na základě existujícího kmene, sufixu a modelu „nejbližšího“ kmene slovní zásoby vygeneruje hypotetický model pro změnu daného slova. Hypotéza je zapamatována, a pokud již byla postavena dříve, zvyšuje její váhu. Pokud slovo nebylo ve slovníku nikdy nalezeno, délka požadované obecné koncovky kmene se zkrátí o jednu, strom se hledá pro nové hypotézy. Když délka společného „ocasu“ dosáhne 2, hledání se zastaví a hypotézy se seřadí podle produktivity: pokud je váha hypotézy pětkrát nebo vícekrát menší než největší váha, taková hypotéza je vyloučena. Výsledkem stemmerovy práce je výsledný soubor hypotéz pro neexistující slovo nebo jedna hypotéza pro slovo ze slovníku [18] .
Stemmer lze použít pro komerční účely; výjimkou jsou: tvorba a distribuce spamu, optimalizace stránek pro vyhledávače a vývoj produktů a služeb podobných službám a produktům Yandexu [17] . Zdrojové kódy nejsou distribuovány [19] . Pro instalaci stačí stáhnout a rozbalit archiv [20] .
V algoritmech stemmingu existují dva typy chyb: overstemming' a understemming . Overstemming je chyba prvního druhu , kdy jsou flektivní slova mylně připisována jednomu lemmatu. Poddruh je chyba druhého druhu , kdy morfologické tvary jednoho slova jsou připisovány různým lemmatům. Stemming algoritmy se snaží minimalizovat obě tyto chyby, ačkoli snížení jednoho typu chyby může zvýšit druhý [21] .
Podívejme se na tyto typy chyb v práci Porterova stemmingového algoritmu. overstemming error case : tento algoritmus porovná slova "universal", "university" a "universe" s kmenem "univers"; ačkoli jsou tato slova etymologicky odlišná, jejich moderní významy odkazují na různé oblasti, takže není správné je považovat za synonyma. Případ chyby podřazení : Porterův algoritmus porovná slova, která jsou odvozena ze stejného lemmatu s různými kmeny, a proto je přiřadí různým lemmatům - "absolvent" → "absolvent", "absolvent" → "absolvent", "absolvent" / " alumnae" → "alumna" (tato slova si zachovala latinské rysy ve své morfologii, ale tato téměř synonyma nebyla spojena stopkou).
Stemming se používá jako přibližná metoda pro seskupování slov s podobným základním významem. Například text, který zmiňuje „narcisy“, pravděpodobně úzce souvisí s textem, který zmiňuje „narcis“ (bez „s“). V některých případech však slova se stejným kmenem mají idiomatické významy, které spolu téměř nesouvisejí: uživatel vyhledá dokumenty obsahující „marketing“ také vrátí dokumenty, které zmiňují „trhy“, ale neobsahují „marketing“ (což s největší pravděpodobností není uspokojit informační potřeby uživatele).
Stemming je ve vyhledávačích docela běžný . Poměrně brzy však byla účinnost stemmingu ve vyhledávačích pro anglický jazyk uznána jako velmi omezená, a to vedlo mladé výzkumníky v oblasti vyhledávání informací k pochopení, že stemming není obecně použitelný [22] [23] . Ve vyhledávačích lze místo stemmingu použít přístup založený na hledání N-gramů , spíše než stems. Nedávné studie navíc ukázaly velké výhody při hledání N-gramů pro jiné jazyky než angličtinu [24] [25] .
Při analýze oborů pomocí stemmingu se budují slovníky těchto oblastí [26] .
Mnoho komerčních společností používá stemming minimálně od 80. let 20. století a vyvinulo algoritmické a lexikální stemmery pro mnoho jazyků [27] [28] .
Sněhové koule byly porovnány s komerčními. Výsledky byly smíšené [29] [30] .
Vyhledávač Google používá stemming od roku 2003 [31] . Dříve vyhledávání „ryby“ nevrátilo výsledky obsahující „rybaření“.
| zpracování přirozeného jazyka | |
|---|---|
| Obecné definice | |
| Analýza textu |
|
| Odkazování |
|
| Strojový překlad |
|
| Identifikace a sběr dat | |
| Tematický model | |
| Peer review |
|
| Rozhraní přirozeného jazyka | |