Stemming - Stemming

Lyžařskou techniku ​​najdete v představci (lyžování) . O lezecké technice viz Glosář lezeckých pojmů § kmen .

V jazykové morfologii a vyhledávání informací , vyplývající je proces snižování ohýbána (nebo někdy získány) slova, jejich slova stonku , báze nebo kořenové tvarovým obecně písemné slovního tvaru. Stonek nemusí být totožný s morfologickým kořenem slova; obvykle stačí, když se příbuzná slova mapují na stejný kmen, i když tento kmen sám o sobě není platným kořenem. Algoritmy pro zastavení jsou v informatice studovány od 60. let minulého století. Mnoho vyhledávačů považuje slova se stejným kmenem za synonyma jako druh rozšíření dotazu , což je proces nazývaný konflace.

Počítačový program nebo podprogram , který pochází slovo může být nazýván vyplývající programu , vyplývající algoritmus nebo Stemmer .

Příklady

Stemmer pro angličtinu operující na kmenové kočce by měl identifikovat takové řetězce jako kočky , kočičí a kočičí . Pramenící algoritmus by mohla také snížit slova rybaření , loven , a rybář na stonku ryby . Stonek nemusí být slovo, například Porter algoritmus snižuje, argumentovat , argumentovali , tvrdí , argumentovat , a argus na stonku Argu .

Dějiny

První publikovanou stopku napsala Julie Beth Lovins v roce 1968. Tento dokument byl pozoruhodný svým raným datem a měl velký vliv na pozdější práci v této oblasti. Její dokument odkazuje na tři dřívější hlavních pokusů vyplývají algoritmů, profesor John W. Tukey z Princeton University , algoritmus vyvinutý na Harvard University od Michaela Lesk , pod vedením profesora Gerarda Salton a třetí algoritmus vyvinutý Jamesem L. Dolby R and D Consultants, Los Altos, Kalifornie.

Pozdější stemmer napsal Martin Porter a byl publikován v červenci 1980 v časopise Program . Tento stemmer byl velmi široce používán a stal se de facto standardním algoritmem používaným pro anglické pochodování. Dr. Porter obdržel v roce 2000 cenu Tonyho Kenta Strixe za práci na zastavení a získávání informací.

Mnoho implementací Porterova generačního algoritmu bylo napsáno a volně distribuováno; mnoho z těchto implementací však obsahovalo jemné nedostatky. V důsledku toho tyto stmívače neodpovídaly jejich potenciálu. Aby byl tento zdroj chyb odstraněn, vydal Martin Porter oficiální implementaci algoritmu zdarma (většinou s licencí BSD ) kolem roku 2000. Tuto práci v příštích několika letech rozšířil vybudováním Snowball , rámce pro psaní algoritmů pro odvodnění a implementoval vylepšený anglický stemmer spolu s stemmers pro několik dalších jazyků.

Paice-Husk Stemmer byl vyvinut Chrisem D Paiceem na Lancasterově univerzitě na konci 80. let minulého století, jedná se o iterativní pramen a obsahuje externě uloženou sadu pravidel pro odstopování. Standardní sada pravidel poskytuje „silný“ kmen a může určit odstranění nebo nahrazení koncovky. Náhradní technika eliminuje potřebu oddělené fáze v procesu překódovat nebo poskytnout částečné přizpůsobení. Paice také vyvinul přímé měření pro porovnávání stmívačů založených na počítání chyb nadměrného a nedostatečného vyrovnání.

Algoritmy

Nevyřešený problém v informatice :

Existuje v angličtině nějaký dokonalý algoritmus pro odvodnění?

(více nevyřešených problémů v informatice)

Existuje několik typů algoritmů zastavení, které se liší výkonem a přesností a způsobem, jakým jsou překonávány určité překážky.

Jednoduchý stonek vyhledává skloňovanou formu ve vyhledávací tabulce . Výhodou tohoto přístupu je, že je jednoduchý, rychlý a snadno zpracovává výjimky. Nevýhody spočívají v tom, že všechny skloňované tvary musí být v tabulce výslovně uvedeny: nová nebo neznámá slova nejsou zpracovávána, i když jsou zcela pravidelná (např. Kočky ~ kočka), a tabulka může být velká. U jazyků s jednoduchou morfologií, jako je angličtina, jsou velikosti tabulek skromné, ale velmi skloňované jazyky jako turečtina mohou mít pro každý kořen stovky potenciálních skloňovaných forem.

Vyhledávací přístup může použít předběžné označování části řeči, aby se předešlo přetížení.

Výrobní technika

Vyhledávací tabulka, kterou používá stemmer, se obvykle vyrábí poloautomaticky. Pokud je například slovo „spuštěno“, převrácený algoritmus může automaticky generovat formuláře „spuštěno“, „běží“, „spuštěno“ a „běží“. Poslední dvě formy jsou platné konstrukce, ale jsou nepravděpodobné.

Algoritmy odstraňování přípon

Algoritmy oddělování přípony nespoléhají na vyhledávací tabulku, která se skládá ze skloňovaných forem a vztahů kořenových formulářů. Místo toho je uložen typicky menší seznam „pravidel“, který poskytuje cestu pro algoritmus, vzhledem k formě vstupního slova, k nalezení jeho kořenové podoby. Některé příklady pravidel zahrnují:

  • pokud slovo končí na „ed“, odstraňte „ed“
  • pokud slovo končí na „ing“, odstraňte „ing“
  • pokud slovo končí na „ly“, odstraňte „ly“

Přístupy k odizolování přípon mají výhodu, že jsou mnohem jednodušší na údržbu než algoritmy hrubé síly, za předpokladu, že správce je dostatečně dobře informován o výzvách lingvistiky a morfologie a o pravidlech odstraňování přípon. Algoritmy odstraňování přípon jsou někdy považovány za hrubé vzhledem ke špatnému výkonu při řešení výjimečných vztahů (jako „běžel“ a „běžel“). Řešení vytvořená algoritmy odstraňování přípon jsou omezena na ty lexikální kategorie, které mají až na výjimky dobře známé přípony. To je však problém, protože ne všechny části řeči mají tak dobře formulovaný soubor pravidel. Lemmatizace se pokouší tuto výzvu zlepšit.

Může být také implementováno odstraňování předpon. Samozřejmě ne všechny jazyky používají předponu nebo příponu.

Další kritéria algoritmu

Algoritmy odstraňování přípon mohou mít různé výsledky z různých důvodů. Jedním z takových důvodů je, zda algoritmus omezuje, zda výstupní slovo musí být skutečným slovem v daném jazyce. Některé přístupy nevyžadují, aby slovo skutečně existovalo v jazykovém lexikonu (množině všech slov v jazyce). Alternativně některé přístupy k odstraňování přípon udržují databázi (velký seznam) všech známých morfologických kořenů slov, která existují jako skutečná slova. Tyto přístupy před přijetím rozhodnutí zkontrolují existenci výrazu v seznamu. Pokud výraz neexistuje, obvykle se provede alternativní akce. Tato alternativní akce může zahrnovat několik dalších kritérií. Neexistence výstupního výrazu může sloužit k tomu, že algoritmus vyzkouší alternativní pravidla svlékání přípon.

Může se stát, že se na stejný vstupní výraz použijí dvě nebo více pravidel odstraňování přípon, což vytvoří nejednoznačnost ohledně toho, které pravidlo použít. Algoritmus může přiřadit (lidskou rukou nebo stochasticky) prioritu jednomu nebo druhému pravidlu. Nebo může algoritmus odmítnout jednu aplikaci pravidla, protože má za následek neexistující termín, zatímco druhé překrývající se pravidlo nikoli. Vzhledem k anglickému výrazu friendlies může například algoritmus identifikovat příponu ies a použít příslušné pravidlo a dosáhnout výsledku friendl . Friendl se v lexikonu pravděpodobně nenachází, a proto je pravidlo odmítnuto.

Jedním zlepšením při odstraňování základních přípon je použití náhrady přípon. Podobně jako u pravidla pro svlékání nahrazuje pravidlo pro nahrazení příponu alternativní příponou. Například by mohlo existovat pravidlo, které nahradí IES s y . Jak to ovlivní algoritmus, se liší v návrhu algoritmu. Pro ilustraci, algoritmus může zjistit, že obě y přípona stripování pravidlo, jakož i uplatnit pravidlo substituce přípona. Protože pravidlo odizolování má za následek neexistenci výrazu ve slovníku, ale pravidlo nahrazení nikoli, je místo toho použito pravidlo nahrazení. V tomto příkladu, přátelské stává přátelské místo friendl‘ .

Ponořením se dále do detailů je běžnou technikou cyklická aplikace pravidel (rekurzivně, jak by řekli počítačoví vědci). Po použití pravidla nahrazování přípon v tomto příkladu se provede druhý průchod k identifikaci pravidel shody u výrazu přátelský , kde je pravděpodobně identifikováno a přijato pravidlo odizolování ly . Stručně řečeno, přátelští se stanou (prostřednictvím substituce) přátelskými, kteří se stanou (prostřednictvím svlékání) přáteli .

Tento příklad také pomáhá ilustrovat rozdíl mezi přístupem založeným na pravidlech a přístupem hrubou silou. Při přístupu hrubou silou by algoritmus hledal přátelské přátele v sadě stovek tisíc skloňovaných slovních tvarů a ideálně by našel odpovídající kořenovou formu přítele . V přístupu založeném na pravidlech by byla použita tři výše uvedená pravidla za sebou, aby se sblížila na stejném řešení. Je pravděpodobné, že přístup hrubou silou by byl pomalejší, protože vyhledávací algoritmy mají přímý přístup k řešení, zatímco pravidla založená na pravidlech by měla vyzkoušet několik možností a jejich kombinací a poté zvolit, který výsledek se zdá být nejlepší.

Lemmatizační algoritmy

Složitějším přístupem k problému určování kmene slova je lemmatizace . Tento proces zahrnuje nejprve určení části řeči slova a použití různých normalizačních pravidel pro každou část řeči. Část řeči je nejprve detekována před pokusem o nalezení kořene, protože u některých jazyků se pravidla odvozování mění v závislosti na části řeči slova.

Tento přístup je velmi podmíněn získáním správné lexikální kategorie (části řeči). Přestože se pravidla normalizace pro určité kategorie překrývají, identifikace nesprávné kategorie nebo neschopnost vytvořit správnou kategorii omezuje další výhodu tohoto přístupu oproti algoritmům odstraňování přípon. Základní myšlenkou je, že pokud je stopař schopen pochopit více informací o slově, které pochází, pak může použít přesnější normalizační pravidla (která na rozdíl od pravidel odstraňování přípon mohou také upravit kmen).

Stochastické algoritmy

Stochastické algoritmy zahrnují použití pravděpodobnosti k identifikaci kořenové podoby slova. Stochastické algoritmy jsou školeny („učí se“) v tabulce kořenových forem k ohýbaným relacím forem, aby se vytvořil pravděpodobnostní model. Tento model je obvykle vyjádřen ve formě komplexních lingvistických pravidel, která jsou svou povahou podobná těm, která se vyskytují v oddělování přípon nebo lemmatizaci. Stemming se provádí tak, že se do natrénovaného modelu vloží skloňovaný tvar a model vytvoří kořenový tvar podle svého vnitřního souboru pravidel, který je opět podobný svlékání a lemmatizaci přípon, kromě toho, že rozhodnutí spojená s aplikací nejvhodnějšího pravidla, nebo zda nebo nezastavit slovo a pouze vrátit stejné slovo, nebo zda použít dvě různá pravidla postupně, jsou aplikovány na základě toho, že výstupní slovo bude mít nejvyšší pravděpodobnost správnosti (to znamená nejmenší pravděpodobnost, že bude nesprávné, což je způsob, jakým se obvykle měří).

Některé algoritmy lemmatizace jsou stochastické v tom, že vzhledem ke slovu, které může patřit do více částí řeči, je každé možné části přiřazena pravděpodobnost. To může vzít v úvahu okolní slova, nazývaná kontext, nebo ne. Gramatiky bez kontextu neberou v úvahu žádné další informace. V obou případech se po přiřazení pravděpodobností každé možné části řeči vybere nejpravděpodobnější část řeči a odtud se na vstupní slovo použijí příslušná normalizační pravidla pro vytvoření normalizované (kořenové) podoby.

n -gramová analýza

Některé techniky odvozování používají pro výběr správného kmene slova n-gramový kontext slova.

Hybridní přístupy

Hybridní přístupy používají souběžně dva nebo více přístupů popsaných výše. Jednoduchým příkladem je algoritmus stromu přípon, který nejprve pomocí hrubé síly konzultuje vyhledávací tabulku. Místo toho, aby se pokusila uložit celou sadu vztahů mezi slovy v daném jazyce, je vyhledávací tabulka malá a slouží pouze k uložení nepatrného množství „častých výjimek“ jako „ran => run“. Pokud slovo není v seznamu výjimek, použijte svlékání přípon nebo lemmatizaci a vytvořte výsledek.

Připojte stonky

V lingvistice , termín přípona odkazuje buď předpona nebo přípona . Kromě řešení přípon se několik přístupů také pokouší odstranit běžné předpony. Například vzhledem ke slovu na dobu neurčitou určete, že úvodní „in“ je předpona, kterou lze odstranit. Mnoho ze stejných přístupů zmíněných dříve platí, ale jdou pod názvem přípona stripping . Studii afixu vyplývajícího z několika evropských jazyků naleznete zde.

Algoritmy shody

Takové algoritmy používají kmenovou databázi (například sadu dokumentů, které obsahují kmenová slova). Tyto stonky, jak je uvedeno výše, nejsou nutně platnými slovy (ale spíše běžnými podřetězci, jako „obočí“ v „procházení“ a v „procházení“). Aby bylo možné určit slovo, pokusí se ho algoritmus spojit se stonky z databáze, přičemž aplikuje různá omezení, například na relativní délku kandidátského kmene ve slově (aby například krátká předpona „být“, která je kmen takových slov jako „být“, „byl“ a „být“, nebude považován za kmen slova „vedle“) ..

Jazykové výzvy

Zatímco většina raných akademických prací v této oblasti byla zaměřena na angličtinu (s významným využitím algoritmu Porter Stemmer), bylo zkoumáno mnoho dalších jazyků.

Hebrejština a arabština jsou stále považovány za obtížné výzkumné jazyky pro zastavení. Anglické stonky jsou poměrně triviální (pouze s občasnými problémy, jako například „suší“ je současná forma slovesa „suché“ ve třetí osobě, „osy“ jsou množné číslo „sekery“ i „osy“); ale konstrukce kmenů se stává obtížnější, protože morfologie, pravopis a kódování znaků v cílovém jazyce se stávají složitějšími. Například italský kmen je složitější než anglický (kvůli většímu počtu skloňování sloves), ruský je složitější ( skloňování podstatných jmen ), hebrejský je ještě složitější (kvůli nekonkalkativní morfologii , psací systém bez samohlásek a požadavek na svlékání předpon: hebrejské stonky mohou mít dva, tři nebo čtyři znaky, ale ne více) atd.

Vícejazyčné předvádění

Vícejazyčné stonkování používá při interpretaci vyhledávacího dotazu místo pravidel pouze pro jeden jazyk současně morfologická pravidla dvou nebo více jazyků. Komerční systémy využívající vícejazyčný původ existují.

Metriky chyb

V algoritmech odstopkování existují dvě měření chyb, overstemming a understemming. Přeplňování je chyba, při níž jsou dvě oddělená skloňovaná slova odvozena od stejného kořene, ale neměla být - falešně pozitivní . Substemming je chyba, kdy by dvě oddělená skloňovaná slova měla být sledována se stejným kořenem, ale nejsou - falešně negativní . Algoritmy blokování se snaží minimalizovat každý typ chyby, ačkoli snížení jednoho typu může vést ke zvýšení druhého.

Například široce používaný Porterův stonek znamená „univerzální“, „univerzitní“ a „vesmír“ až „vesmír“. Jedná se o případ nadměrného zastoupení: ačkoli jsou tato tři slova etymologicky příbuzná, jejich moderní významy jsou v široce odlišných doménách, takže zacházení s nimi jako se synonymy ve vyhledávači pravděpodobně sníží relevanci výsledků vyhledávání.

Příkladem podtržení v Porterově kmeni je „absolvent“ → „alumnu“, „alumni“ → „alumni“, „alumna“/„alumnae“ → „alumna“. Toto anglické slovo zachovává latinskou morfologii, a proto tato téměř synonyma nejsou spojena.

Aplikace

Stemming se používá jako přibližná metoda pro seskupování slov s podobným základním významem. Například text zmiňující „narcisy“ pravděpodobně úzce souvisí s textem zmiňujícím „narcis“ (bez s). Ale v některých případech mají slova se stejným morfologickým kmenem idiomatické významy, které spolu nijak úzce nesouvisejí: uživatele, který hledá „marketing“, většina dokumentů zmiňujících „trhy“ neuspokojí, ale „marketing“ neuspokojí.

Získávání informací

Stemmery jsou běžnými prvky v dotazovacích systémech, jako jsou webové vyhledávače . Účinnost zastavení v anglických dotazovacích systémech se však brzy zjistila jako poměrně omezená, což vedlo výzkumníky v oblasti raného získávání informací k tomu, že považovali zastavení obecně za irelevantní. Místo toho lze použít alternativní přístup založený na hledání n-gramů spíše než stonků. Také mohou prameny poskytovat větší výhody v jiných jazycích než v angličtině.

Analýza domény

Stemming se používá k určení doménových slovníků v doménové analýze .

Použití v komerčních produktech

Mnoho komerčních společností používá stonkování nejméně od 80. let minulého století a vyrábí algoritmické a lexikální prameny v mnoha jazycích.

The Snowball lemmatizátory byly ve srovnání s komerčními lexikální lemmatizátory s různými výsledky.

Vyhledávání Google přijalo slovo pocházející z roku 2003. Dříve by vyhledávání „ryby“ nevracelo „rybaření“. Jiné algoritmy pro vyhledávání softwaru se liší v používání odvozování slov. Programy, které jednoduše hledají podřetězce, samozřejmě najdou „ryby“ v „rybaření“, ale při hledání „ryb“ nenajdou výskyty slova „ryba“.

Viz také

Reference

Další čtení

externí odkazy

Tento článek vychází z materiálu převzatého z Free On-line Dictionary of Computing před 1. listopadem 2008 a začleněn pod podmínky „relicencování“ GFDL , verze 1.3 nebo novější.