Stemming är processen att hitta stammen till ett ord för ett givet källord. Ett ords stam är inte nödvändigtvis densamma som den morfologiska roten till ordet .
Uppgiften att hitta ett ords stam har varit ett långvarigt problem inom datavetenskap . Den första publikationen om detta nummer går tillbaka till 1968 . Stemming används i sökmotorer för att utöka användarens sökfråga , är en del av textnormaliseringsprocessen .
Ett specifikt sätt att lösa problemet med att hitta grunden för ord kallas stemmingsalgoritm , och en specifik implementering är stemmer .
Den första publicerade stemmer skrevs av Julie Beth Lovins 1968 [1] . Denna artikel är känd för sitt tidiga publiceringsdatum och har haft ett stort inflytande på senare arbete på området.
Stemmern skrevs senare av Martin Porter och publicerades 1980. Denna stämmer har använts mycket och har blivit de facto standardalgoritmen för texter på engelska. Dr. Porter fick Strix Award 2000 för sitt arbete med stemming och informationssökning.
Många implementeringar av Porters stamalgoritm har skrivits och distribuerats fritt; Men många av dessa implementeringar innehåller svåra att hitta brister. Som ett resultat av detta fungerade inte dessa algoritmer till sin fulla potential. För att eliminera denna typ av fel släppte Martin Porter en officiell gratis implementering av algoritmen runt 2000. Han fortsatte detta arbete under de närmaste åren och utvecklade Snowball , ett ramverk för att skapa utgångsalgoritmer, och förbättrade engelska stämmers, såväl som stämmare för flera andra språk.
Det finns flera typer av härdningsalgoritmer som skiljer sig åt när det gäller prestanda, noggrannhet och hur vissa härdningsproblem övervinns.
En enkel stemmer slår upp en böjningsform i en uppslagstabell . Fördelarna med detta tillvägagångssätt är dess enkelhet, snabbhet och enkla undantagshantering. Nackdelarna är bland annat att alla böjningsformer måste anges uttryckligen i tabellen: nya eller okända ord kommer inte att behandlas även om de är korrekta (t.ex. iPads ~ iPad) och även problemet är att uppslagstabellen kan vara väldigt stor. För språk med enkel morfologi som engelska är tabellstorlekarna små, men för högböjningsspråk (som turkiska) kan en tabell ha hundratals möjliga böjningsformer för varje rot.
Uppslagstabeller som används i avstämmare genereras vanligtvis halvautomatiskt. Till exempel, för det engelska ordet "run", kommer formerna "running", "runs", "runned" och "runly" att genereras automatiskt. De två sista formerna är giltiga konstruktioner, men det är osannolikt att de förekommer i vanlig engelsk text.
Sökalgoritmen kan använda prepartitionsuppmärkning för att undvika denna typ av lemmatiseringsfel , när olika ord tilldelas samma lemma (överstamming) [2] .
Algoritmer för termineringstrunkering använder inte en uppslagstabell, som består av böjningsformer och rotformrelationer. Istället lagras vanligtvis en mindre lista med "regler", som används av algoritmer, givet ordets form, för att hitta dess stam [3] . Några exempelregler ser ut så här:
Algoritmer för terminering av trunkering är mycket effektivare än brute force-algoritmer . För att utveckla sådana algoritmer behöver man en programmerare som är ganska väl insatt i lingvistik , i synnerhet morfologi , och som även kan koda "trunkeringsregler". Termineringsavkortningsalgoritmer är ineffektiva för undantag (t.ex. 'kör' och 'kör'). Lösningarna som erhålls genom att avsluta trunkeringsalgoritmer är begränsade till de delar av tal som har välkända ändelser och suffix, med några undantag. Detta är en allvarlig begränsning, eftersom inte alla delar av tal har en väldefinierad uppsättning regler. Lemmatisering försöker ta bort denna begränsning.
Prefix trunkeringsalgoritmer kan också implementeras. Men inte alla språk har prefix och suffix.
Ytterligare kriterier för algoritmerAlgoritmer för termineringstrunkering kan variera i resultat av en mängd olika anledningar. En av dessa anledningar är algoritmens egenhet: om ordet vid utgången av algoritmen måste vara ett riktigt ord på det givna språket. Vissa metoder kräver inte närvaron av ordet i motsvarande språklexikon . Dessutom upprätthåller vissa algoritmer en databas med alla kända morfologiska rötter som existerar som riktiga ord. Dessa algoritmer kontrollerar förekomsten av en term i databasen för att fatta ett beslut. Om termen inte hittas, vidtas i regel alternativa åtgärder. Dessa alternativa åtgärder kan använda lite olika kriterier för att fatta ett beslut. En term som inte finns kan fungera som en alternativ trunkeringsregel.
Det kan vara så att två eller flera trunkeringsregler gäller för samma indataterm, vilket skapar oklarheter om vilken regel som ska tillämpas. Algoritmen kan bestämma prioritet för utförandet av sådana regler (med hjälp av en person eller på ett stokastiskt sätt). Eller så kan algoritmen förkasta en av reglerna om den resulterar i en icke-existerande term, medan den andra inte gör det. Till exempel, för den engelska termen "friendlies", kan algoritmen bestämma suffixet "ies", tillämpa lämplig regel och returnera resultatet "friendl". Termen "vän" kommer sannolikt inte att finnas i lexikonet och därför kommer denna regel att förkastas.
En av förbättringarna i algoritmer för trunkering av suffix är användningen av suffix- och suffixsubstitution. Liksom trunkeringsregeln ersätter substitutionsregeln ett suffix eller slutar med ett alternativt. Till exempel kan det finnas en regel som ersätter "ies" med "y". Eftersom trunkeringsreglerna leder till en obefintlig term i lexikonet löser substitutionsreglerna detta problem. I det här exemplet konverteras "vänskapsmatcher" till "vänlig" istället för "vän".
Vanligtvis är tillämpningen av dessa regler cyklisk eller rekursiv. Efter den första tillämpningen av substitutionsregeln för detta exempel väljer algoritmen nästa regel för den "vänliga" termen, som ett resultat av vilken "ly"-suffixtrunkeringsregeln kommer att identifieras och kännas igen. Termen "vänskap" blir alltså termen "vänlig" genom substitutionsregeln, som efter tillämpning av trunkeringsregeln blir termen "vän".
Detta exempel hjälper till att visa skillnaden mellan en regelbaserad metod och en brute force-metod . Med hjälp av en uttömmande sökning kommer algoritmen att leta efter termen "vänskap" i en uppsättning av hundratusentals böjningsordformer och helst hitta motsvarande stam "vän". I en regelbaserad metod exekveras reglerna sekventiellt, vilket resulterar i samma lösning. Troligtvis kommer den regelbaserade metoden att vara snabbare.
Inom lingvistik är de vanligaste termerna för affix suffix och prefix. Förutom tillvägagångssätt som hanterar suffix eller ändelser, hanterar vissa av dem även prefix. Till exempel, för ett engelskt ord indefinitely , kommer denna metod att avgöra att "in"-konstruktionen i början av ordet är ett prefix och kan tas bort för att få ordstammen. Många av metoderna som nämns ovan använder också detta tillvägagångssätt. Till exempel kan slutstympningsalgoritmen hantera både suffix och ändelser samt prefix, i vilket fall den kommer att anropas annorlunda och följa detta tillvägagångssätt. Forskning om affixstemrar för flera europeiska språk finns i en publikation ( Jongejan et al 2009 ).
Ett mer komplext tillvägagångssätt för att lösa problemet med att bestämma ett ords stam är lemmatisering . För att förstå hur lemmatisering fungerar behöver du veta hur de olika formerna av ett ord skapas. De flesta ord förändras när de används i olika grammatiska former . Slutet på ordet ersätts av en grammatisk ändelse, och detta leder till en ny form av det ursprungliga ordet. Lemmatisering utför den omvända omvandlingen: den ersätter den grammatiska ändelsen med ett suffix eller ändelsen på initialformen [4] .
Lemmatisering innefattar också att bestämma orddelen av ett ord och tillämpa olika normaliseringsregler för varje orddel. Definitionen av orddelen sker innan man försöker hitta stammen, eftersom reglerna för härkomst för vissa språk beror på orddelen för ett givet ord.
Detta tillvägagångssätt är starkt beroende av den exakta definitionen av den lexikaliska kategorin (ordsform). Även om det finns överlappning mellan normaliseringsreglerna för vissa lexikaliska kategorier, förnekar en angivande av fel kategori eller att inte bestämma den korrekta kategorin fördelen med detta tillvägagångssätt jämfört med trunkeringsalgoritmen. Huvudtanken är att om röstaren kan få mer information om ordet som bearbetas, så kan den tillämpa mer exakta normaliseringsregler.
Ripple-down regler tillvägagångssättRipple-down-regler designades ursprungligen för att få kunskap och underhålla regelbaserade system. I detta tillvägagångssätt förvärvas kunskap baserat på det aktuella sammanhanget och läggs till stegvis. Regler skapas för att klassificera fall som passar ett visst sammanhang.
Till skillnad från standardklassificeringsregler använder Ripple-down-regler undantag från befintliga regler, så ändringar är bara relaterade till regelns sammanhang och påverkar inte andra. Verktyg för kunskapsinhämtning hjälper dig att hitta och ändra motstridiga regler. Här är ett enkelt exempel på en Ripple-down- regel :
if a ^ b then c except if d then e else if f ^ g then h
Denna regel kan tolkas på följande sätt: "om a och b är sanna, så bestämmer vi c , förutom när d inte är sant. Om d är sant (undantag), så fattar vi ett beslut e . Om a och b inte är sanna, så går vi till en annan regel och avgör h om f och g är sanna." Denna form av regler löser problemet med lemmatisering mycket väl [5] .
För att skapa ett undantag från en regel måste algoritmen först bestämma ordet som inducerade det givna undantaget. Därefter bestäms skillnaderna mellan de två orden. Regelns undantagsvillkor kommer att matcha dessa skillnader.
Stokastiska algoritmer är förknippade med den probabilistiska bestämningen av ett ords rotform. Dessa algoritmer bygger en probabilistisk modell och tränas med hjälp av en tabell över överensstämmelse mellan rot- och böjningsformer. Denna modell presenteras vanligtvis i form av komplexa språkliga regler, liknande reglerna som används i trunkerings- och lemmatiseringsalgoritmer. Stemming görs genom att införa modifierade former för att träna modellen och generera en rotform enligt modellens interna regeluppsättning, förutom att besluten relaterade till tillämpningen av den mest lämpliga regeln eller sekvensen av regler, såväl som valet av ordets stam, tillämpas på grundval av att det resulterande korrekta ordet kommer att ha högst sannolikhet (fel ord har lägst sannolikhet).
Vissa lemmatiseringsalgoritmer är stokastiska i den meningen att ett ord kan tillhöra flera orddelar med olika sannolikheter. Dessa algoritmer kan också ta hänsyn till omgivande ord, så kallade sammanhang. Kontextfria grammatiker tar inte hänsyn till någon ytterligare information. I båda fallen, efter att ha tilldelats en sannolikhet till varje möjlig del av tal, väljs den del av tal med högst sannolikhet, såväl som motsvarande regler för att erhålla en normaliserad form.
Vissa härdningsalgoritmer använder N-gram- analys för att välja en lämplig stam för ett ord [6] .
Stemming baserat på en korpus av texterEn av de största nackdelarna med klassiska stemmers (som Porters stemmer) är att de ofta inte skiljer på ord med liknande syntax men helt olika betydelser. Till exempel kommer "nyheter" och "nya" att reduceras till stammen "ny" som ett resultat av stemming, även om dessa ord tillhör olika lexikaliska kategorier. Ett annat problem är att vissa stamalgoritmer kan vara lämpliga för en korpus och orsaka för många fel i en annan. Till exempel kommer orden "aktier", "aktier", "strumpa" etc. ha en speciell betydelse i texterna i tidningen The Wall Street Journal . Huvudidén med korpusbaserad härkomst är att skapa ekvivalensklasser för orden från klassiska röstare, och sedan "bryta" några ord kombinerade baserat på deras förekomst i korpusen. Det hjälper också till att förhindra de välkända kollisioner av Porters algoritm, såsom "policy/polis", eftersom chansen att dessa ord inträffar tillsammans är ganska låg [7] .
Sådana algoritmer använder en databas med stammar (till exempel en uppsättning dokument som innehåller stammar av ord). Dessa stammar motsvarar inte nödvändigtvis vanliga ord, i de flesta fall är stammen en delsträng (till exempel för engelska är "brows" en delsträng i orden "browse" och "browsing"). För att bestämma roten till ett ord försöker algoritmen matcha det med stammarna från databasen och tillämpar olika begränsningar, till exempel på längden på den sökta stammen i ordet i förhållande till längden på själva ordet (till exempel Exempelvis skulle det korta prefixet "vara", som är grunden för sådana ord, som "vara", "var" och "vara" inte utgöra grunden för "bredvid").
Hybridmetoder använder två eller flera av metoderna som beskrivs ovan. Ett enkelt exempel är suffixträdsalgoritmen , som i början av sitt arbete använder uppslagstabeller för att erhålla initial data med hjälp av uttömmande sökning. Men istället för att lagra hela komplexet av relationer mellan ord för ett visst språk, används en uppslagstabell för att lagra ett litet antal "frequent undantag" (till exempel för det engelska språket "run => run"). Om ordet inte finns i uteslutningslistan används algoritmer för slutavkortning eller lemmatisering för att få resultatet.
Medan det mesta av den tidiga vetenskapliga verksamheten inom detta område var fokuserad på engelska (mestadels med hjälp av Porters stemmingsalgoritm), har efterföljande arbete ägnats åt många andra språk [8] [9] [10] [11] [12] .
Hebreiska och arabiska anses fortfarande vara svåra språk att lära sig när det gäller härkomst. Engelska stemmingsalgoritmer är ganska triviala (endast enstaka problem uppstår, till exempel är ordet "torkar" tredje person singular presensform av verbet "torka", eller ordet "axlar" är plural av "axe" och " axel"); men stemmers blir svårare att designa när ett mer komplext målspråk väljs, nämligen ett språk med mer komplex morfologi och stavning. Till exempel är stemmers för det italienska språket mer komplexa än stemmers för engelska (på grund av det stora antalet böjningsformer av verb), implementeringar för det ryska språket är ännu svårare (ett stort antal deklinationer av substantiv), för hebreiska de är ännu mer komplexa (på grund av icke-konkatenativ morfologi). , skrivning utan vokaler och behovet av prefixavkortningsalgoritmer: hebreiska ordstammar kan vara två, tre eller fyra tecken långa, men inte längre) och så vidare.
Flerspråkiga härkomstalgoritmer tillämpar de morfologiska reglerna för två eller flera språk samtidigt.
Det ryska språket tillhör gruppen av syntetiska böjningsspråk, det vill säga språk där ordbildningen dominerar med affix som kombinerar flera grammatiska betydelser samtidigt (till exempel typ - ändelsen й indikerar samtidigt singular, maskulina kön och nominativa kasus), därför tillåter detta språk användning av stemmingsalgoritmer. Det ryska språket har en komplex morfologisk förändring av ord, vilket är en källa till fel när man använder stemming. Som en lösning på detta problem, tillsammans med de klassiska härkomstalgoritmerna, kan lemmatiseringsalgoritmer användas som för ord till den initiala grundformen.
Låt oss överväga de mest populära implementeringarna av stemmers baserat på olika principer och tillåter bearbetning av icke-existerande ord för det ryska språket.
Stemmer PorterHuvudidén med Porters stemmer är att det finns ett begränsat antal ordbildande suffix, och ordstamming sker utan att använda några stambaser: endast en uppsättning befintliga suffix och manuellt inställda regler.
Algoritmen består av fem steg. Vid varje steg skärs ett ordbildande suffix av och den återstående delen kontrolleras för överensstämmelse med reglerna (till exempel för ryska ord måste stammen innehålla minst en vokal). Om det resulterande ordet uppfyller reglerna sker övergången till nästa steg. Om inte, väljer algoritmen ett annat suffix för klippning. I det första steget skärs det maximala formbildande suffixet av, vid det andra - bokstaven "i", vid det tredje - det ordbildande suffixet, vid det fjärde - suffixen för superlativformer, "ь" och en av de två "n" [13] .
Denna algoritm trunkerar ofta ordet mer än nödvändigt, vilket gör det svårt att få rätt stam på ordet, till exempel säng-> tak (i det här fallet är den egentligen oförändrade delen säng , men röstaren väljer det längsta morfemet för radering). Porters stemmer klarar inte heller av alla möjliga förändringar i ordet rot (till exempel bortfall och flytande vokaler).
StemkaDenna stemmingsalgoritm (analysator) utvecklades av Andrey Kovalenko 2002. Den är baserad på en probabilistisk modell: ord från träningstexten tolkas av analysatorn i par "de två sista bokstäverna i stammen" + "suffix", och om ett sådant par redan finns i modellen, ökar dess vikt , annars läggs den till i modellen. Därefter rangordnas den resulterande datamatrisen i fallande viktordning och modellerna, vars sannolikhet är mindre än 1/10000, skärs av. Resultatet - en uppsättning potentiella ändelser med villkor på de föregående tecknen - inverteras för bekvämligheten av att skanna ordformer "från höger till vänster" och presenteras som en övergångstabell för en finit automat. Vid tolkning skannas ordet enligt de konstruerade övergångstabellerna. En specialregel lades också till algoritmen, som säger att den oföränderliga stammen måste innehålla minst en vokal [14] .
Den presenterade analysatorn finns tillgänglig i källtexter och kan användas i fri form med villkoret referens till källan [15] [16] .
MyStemMyStem-avstämmaren utvecklades av Ilya Segalovich 1998. Den tillhör nu Yandex [17] . I det första steget, med hjälp av suffixträdet i inmatningsordet, bestäms de möjliga gränserna mellan stammen och suffixet, varefter, för varje potentiell stam (som börjar med den längsta), kontrollerar binär sökning i stamträdet dess närvaro i ordboken eller hitta stammarna närmast den (med ett mått på närhet är längden på den vanliga "svansen"). Om ordet är ett ordboksord avslutas algoritmen, annars fortsätter den till nästa partition.
Om stamvarianten inte stämmer överens med någon av de ”närmaste” ordboksstammarna betyder det att det analyserade ordet med denna stamvariant inte finns i ordboken. Sedan, baserat på den befintliga stammen, suffixet och modellen för den "närmaste" vokabulärstammen, genereras en hypotetisk modell för att ändra det givna ordet. Hypotesen kommer ihåg, och om den redan har byggts tidigare ökar den sin vikt. Om ordet aldrig hittades i ordboken reduceras längden på den nödvändiga allmänna stamändelsen med ett, trädet skannas efter nya hypoteser. När längden på den gemensamma "svansen" når 2, stannar sökningen och hypoteserna rangordnas efter produktivitet: om hypotesens vikt är fem eller fler gånger mindre än den största vikten, elimineras en sådan hypotes. Resultatet av röstarens arbete är den resulterande uppsättningen hypoteser för ett icke-existerande ord eller en hypotes för ett ordboksord [18] .
Röstaren kan användas för kommersiella ändamål; undantag är: skapande och distribution av spam, sökmotoroptimering av webbplatser och utveckling av produkter och tjänster som liknar tjänsterna och produkterna från Yandex [17] . Källkoder distribueras inte [19] . För att installera, ladda bara ner och packa upp arkivet [20] .
Det finns två typer av fel i stemmingsalgoritmer: overstemming' och understemming . Överstämning är ett fel av det första slaget , när böjningsord felaktigt hänförs till ett lemma. Understemming är ett fel av det andra slaget , när morfologiska former av ett ord tillskrivs olika lemman. Stamalgoritmer försöker minimera båda dessa fel, även om en minskning av en typ av fel kan öka den andra [21] .
Låt oss överväga dessa typer av fel i arbetet med Porters stemmingsalgoritm. fall för överstammande fel : denna algoritm kommer att matcha orden "universal", "universitet" och "universum" med stammen "universum"; även om dessa ord är etymologiskt olika, hänvisar deras moderna betydelser till olika områden, så det är inte korrekt att behandla dem som synonymer. Fall av understemmingsfel : Porters algoritm kommer att matcha ord som härrör från samma lemma med olika stammar och kommer därför att tillskriva dem till olika lemman - "alumn" → "alumn", "alumni" → "alumni", "alumn" / " alumnae" → "alumna" (dessa ord bibehöll latinska drag i sin morfologi, men dessa nästan synonymer kombinerades inte av en röst).
Stemming används som en ungefärlig metod för att gruppera ord med liknande grundläggande betydelser. Till exempel är text som nämner "påskliljor" förmodligen nära besläktad med text som nämner "påsklilja" (utan "s"). Men i vissa fall har ord med samma stam idiomatiska betydelser som nästan inte är relaterade: en användares sökning efter dokument som innehåller "marknadsföring" kommer också att returnera dokument som nämner "marknader" men inte innehåller "marknadsföring" (vilket med största sannolikhet inte gör det tillgodose användarens informationsbehov ).
Stemming är ganska vanligt i sökmotorer . Men relativt snart erkändes effektiviteten av stemming i sökmotorer för det engelska språket som mycket begränsad, och detta ledde till att unga forskare inom området för informationssökning förstod att stemming inte är allmänt tillämpligt [22] [23] . I sökmotorer, i stället för stemming, kan ett tillvägagångssätt som bygger på att söka efter N-gram snarare än stammar användas. Dessutom har nyare studier visat stora fördelar med N-gram-sökning efter andra språk än engelska [24] [25] .
När man analyserar ämnesområden med hjälp av stemming, skapas ordböcker över dessa områden [26] .
Många kommersiella företag har använt stemming sedan åtminstone 1980-talet och har utvecklat algoritmiska och lexikaliska stämmer för många språk [27] [28] .
Snöbollsstämmare jämfördes med kommersiella. Resultaten har varit blandade [29] [30] .
Googles sökmotor har använt stemming sedan 2003 [31] . Tidigare gav en sökning på "fish" inte resultat som innehöll "fishing".
| naturlig språkbehandling | |
|---|---|
| Allmänna definitioner | |
| Textanalys |
|
| Refererar |
|
| Maskinöversätta |
|
| Identifiering och datainsamling | |
| Tematisk modell | |
| Peer review |
|
| Naturligt språkgränssnitt | |