Stemming er processen med at finde stammen af et ord for et givet kildeord. Et ords stamme er ikke nødvendigvis det samme som ordets morfologiske rod .
Opgaven med at finde stammen af et ord har været et langvarigt problem inden for datalogi . Den første publikation om dette nummer går tilbage til 1968 . Stemming bruges i søgemaskiner til at udvide brugerens søgeforespørgsel , er en del af tekstnormaliseringsprocessen .
En specifik måde at løse problemet med at finde grundlaget for ord på kaldes stammealgoritme , og en specifik implementering er stemmer .
Den første udgivne stemmer blev skrevet af Julie Beth Lovins i 1968 [1] . Dette papir er kendt for sin tidlige udgivelsesdato og har haft stor indflydelse på senere arbejde på området.
Stemmeren blev senere skrevet af Martin Porter og udgivet i 1980. Denne stemmer er blevet meget udbredt og er blevet de facto standardalgoritmen for tekster på engelsk. Dr. Porter modtog Strix-prisen i 2000 for sit arbejde med stemming og informationssøgning.
Mange implementeringer af Porters stammealgoritme er blevet skrevet og frit distribueret; dog indeholder mange af disse implementeringer svære at finde fejl. Som følge heraf fungerede disse algoritmer ikke til deres fulde potentiale. For at eliminere denne type fejl udgav Martin Porter en officiel gratis implementering af algoritmen omkring 2000. Han fortsatte dette arbejde i løbet af de næste par år, udviklede Snowball , en ramme til at skabe stammende algoritmer, og forbedrede engelske stemmere såvel som stemmere til flere andre sprog.
Der er flere typer stammende algoritmer, der adskiller sig med hensyn til ydeevne, nøjagtighed og hvordan visse stammeproblemer overvindes.
En simpel stemmer slår en bøjningsform op i en opslagstabel . Fordelene ved denne tilgang er dens enkelhed, hastighed og lette håndtering af undtagelser. Ulemperne er blandt andet, at alle bøjningsformer skal angives eksplicit i tabellen: nye eller ukendte ord vil ikke blive behandlet, selvom de er korrekte (f.eks. iPads ~ iPad) og også problemet er, at opslagstabellen kan være meget stor. For sprog med simpel morfologi som engelsk er tabelstørrelser små, men for sprog med høj bøjning (som tyrkisk) kan en tabel have hundredvis af mulige bøjningsformer for hver rod.
Opslagstabeller, der bruges i stemmers, genereres normalt semi-automatisk. For eksempel for det engelske ord "løbe", vil formerne "løbende", "løber", "løbe" og "løbende" blive genereret automatisk. De sidste to former er gyldige konstruktioner, men det er usandsynligt, at de optræder i almindelig engelsk tekst.
Søgealgoritmen kan bruge præpartitionsmarkering for at undgå denne form for lemmatiseringsfejl , når forskellige ord tildeles det samme lemma (overstamming) [2] .
Termineringstrunkeringsalgoritmer bruger ikke en opslagstabel, som består af bøjningsformer og rodformrelationer. I stedet lagres normalt en mindre liste af "regler", som bruges af algoritmer, givet ordets form, til at finde dets stamme [3] . Nogle eksempler på regler ser således ud:
Terminering trunkeringsalgoritmer er meget mere effektive end brute force algoritmer . For at udvikle sådanne algoritmer har man brug for en programmør, som er ret velbevandret i lingvistik , især morfologi , og som også er i stand til at kode "trunkeringsregler". Terminering trunkeringsalgoritmer er ineffektive for undtagelser (f.eks. 'løb' og 'løb'). Løsningerne opnået ved at afslutte trunkeringsalgoritmer er begrænset til de dele af tale , der har velkendte endelser og suffikser, med nogle undtagelser. Dette er en alvorlig begrænsning, da ikke alle dele af tale har et veldefineret sæt regler. Lemmatisering forsøger at fjerne denne begrænsning.
Præfikset trunkeringsalgoritmer kan også implementeres. Det er dog ikke alle sprog, der har præfikser og suffikser.
Yderligere kriterier for algoritmerAfskæringsalgoritmer kan variere i resultater af en række forskellige årsager. En af disse grunde er algoritmens ejendommelighed: om ordet ved outputtet af algoritmen skal være et rigtigt ord på det givne sprog. Nogle tilgange kræver ikke tilstedeværelsen af ordet i det tilsvarende sprogleksikon . Derudover vedligeholder nogle algoritmer en database over alle kendte morfologiske rødder, der eksisterer som rigtige ord. Disse algoritmer kontrollerer tilstedeværelsen af et udtryk i databasen for at træffe en beslutning. Hvis udtrykket ikke findes, tages der som regel alternative handlinger. Disse alternative handlinger kan bruge lidt forskellige kriterier til at træffe en beslutning. Et udtryk, der ikke eksisterer, kan tjene som en alternativ trunkeringsregel.
Det kan være, at to eller flere trunkeringsregler gælder for det samme inputled, hvilket skaber uklarhed om, hvilken regel der skal anvendes. Algoritmen kan bestemme prioriteringen af udførelsen af sådanne regler (ved hjælp af en person eller på en stokastisk måde). Eller algoritmen kan afvise en af reglerne, hvis den resulterer i et ikke-eksisterende udtryk, mens den anden ikke gør. For det engelske udtryk "friendlies" kan algoritmen f.eks. bestemme suffikset "ies", anvende den relevante regel og returnere resultatet "friendl". Udtrykket "ven" vil højst sandsynligt ikke blive fundet i leksikonet, og derfor vil denne regel blive afvist.
En af forbedringerne af suffiks trunkeringsalgoritmer er brugen af suffiks og suffikssubstitution. Ligesom trunkeringsreglen erstatter substitutionsreglen et suffiks eller ender med et alternativt. For eksempel kan der være en regel, der erstatter "ies" med "y". Da trunkeringsreglerne fører til en ikke-eksisterende term i leksikonet, løser substitutionsreglerne dette problem. I dette eksempel er "venskaber" konverteret til "venlige" i stedet for "venner".
Anvendelsen af disse regler er typisk cyklisk eller rekursiv. Efter den første anvendelse af substitutionsreglen for dette eksempel, vælger algoritmen den næste regel for det "venlige" udtryk, som et resultat af hvilket "ly" suffikset trunkeringsreglen vil blive identificeret og genkendt. Begrebet "venskaber" bliver således begrebet "venligt" gennem substitutionsreglen, som efter anvendelse af trunkeringsreglen bliver til begrebet "ven".
Dette eksempel hjælper med at demonstrere forskellen mellem en regelbaseret metode og en brute force-metode . Ved at bruge udtømmende søgning vil algoritmen lede efter udtrykket "venskaber" i et sæt af hundredtusindvis af bøjningsordformer og ideelt set finde den tilsvarende stamme "ven". I en regelbaseret metode udføres reglerne sekventielt, hvilket resulterer i den samme løsning. Mest sandsynligt vil den regelbaserede metode være hurtigere.
I lingvistik er de mest almindelige udtryk for affikser suffiks og præfiks. Ud over tilgange, der håndterer suffikser eller endelser, håndterer nogle af dem også præfikser. For eksempel, for et engelsk ord indefinitely , vil denne metode bestemme, at "in"-konstruktionen i begyndelsen af ordet er et præfiks og kan fjernes for at få ordstammen. Mange af de ovennævnte metoder bruger også denne tilgang. For eksempel kan ending trunkeringsalgoritmen håndtere både suffikser og endelser samt præfikser, i hvilket tilfælde den vil blive kaldt anderledes og følge denne tilgang. Forskning om affix stemmers for flere europæiske sprog kan findes i en publikation ( Jongejan et al 2009 ).
En mere kompleks tilgang til at løse problemet med at bestemme stammen af et ord er lemmatisering . For at forstå, hvordan lemmatisering fungerer, skal du vide, hvordan de forskellige former af et ord er skabt. De fleste ord ændrer sig, når de bruges i forskellige grammatiske former . Ordets slutning erstattes af en grammatisk slutning, og dette fører til en ny form af det oprindelige ord. Lemmatisering udfører den omvendte transformation: den erstatter den grammatiske slutning med et suffiks eller slutningen af begyndelsesformen [4] .
Lemmatisering omfatter også at bestemme ordleddet og anvende forskellige normaliseringsregler for hver orddel. Definitionen af ordstemmen opstår før man forsøger at finde stammen, fordi for nogle sprog afhænger reglerne for stemming af orddelen af et givet ord.
Denne tilgang er meget afhængig af den nøjagtige definition af den leksikalske kategori (ordeord). Selvom der er overlap mellem normaliseringsreglerne for nogle leksikalske kategorier, ophæver angivelse af den forkerte kategori eller undladelse af at bestemme den korrekte kategori fordelen ved denne fremgangsmåde i forhold til trunkeringsalgoritmen. Hovedtanken er, at hvis stemmeren er i stand til at få mere information om det ord, der behandles, så kan den anvende mere præcise normaliseringsregler.
Ripple-down regler tilgangRipple-down-regler blev oprindeligt designet til at opnå viden og vedligeholde regelbaserede systemer. I denne tilgang erhverves viden baseret på den aktuelle kontekst og tilføjes gradvist. Regler oprettes for at klassificere sager, der passer til en bestemt kontekst.
I modsætning til standard klassifikationsregler bruger Ripple-down-regler undtagelser til eksisterende regler, så ændringer er kun relateret til reglens kontekst og påvirker ikke andre. Videnindhentningsværktøjer hjælper dig med at finde og ændre modstridende regler. Her er et simpelt eksempel på en Ripple-down- regel :
if a ^ b then c except if d then e else if f ^ g then h
Denne regel kan fortolkes som følger: "hvis a og b er sande, så beslutter vi c , undtagen når d ikke er sandt. Hvis d er sand (undtagelse), så træffer vi en beslutning e . Hvis a og b ikke er sande, så går vi til en anden regel og beslutter h , hvis f og g er sande." Denne form for regler løser problemet med lemmatisering meget godt [5] .
For at skabe en undtagelse til en regel skal algoritmen først bestemme det ord, der inducerede den givne undtagelse. Derefter bestemmes forskellene mellem de to ord. Undtagelsesbetingelsen for reglen vil matche disse forskelle.
Stokastiske algoritmer er forbundet med den probabilistiske bestemmelse af et ords rodform. Disse algoritmer bygger en sandsynlighedsmodel og trænes ved hjælp af en overensstemmelsestabel mellem rod- og bøjningsformer. Denne model præsenteres sædvanligvis i form af komplekse sproglige regler, der ligner de regler, der bruges i trunkerings- og lemmatiseringsalgoritmer. Stemming sker ved at introducere modificerede former for at træne modellen og generere en rodform i henhold til modellens interne regelsæt, bortset fra at beslutningerne var relateret til anvendelsen af den mest passende regel eller rækkefølge af regler, såvel som valget af ordets stamme, anvendes på grundlag af, at det resulterende korrekte ord vil have den højeste sandsynlighed (forkerte ord har den laveste sandsynlighed).
Nogle lemmatiseringsalgoritmer er stokastiske i den forstand, at et ord kan høre til flere dele af tale med forskellige sandsynligheder. Disse algoritmer kan også tage hensyn til omgivende ord, kaldet kontekst. Kontekstfrie grammatikker tager ikke højde for yderligere information. I begge tilfælde, efter at have tildelt en sandsynlighed til hver mulig del af tale, vælges den del af tale med højest sandsynlighed, såvel som de tilsvarende regler for at opnå en normaliseret form.
Nogle stammealgoritmer bruger N-gram analyse til at vælge en passende stamme til et ord [6] .
Stemming baseret på et korpus af teksterEn af de største ulemper ved klassiske stemmer (som Porters stemmer) er, at de ofte ikke skelner mellem ord med ens syntaks, men helt forskellige betydninger. For eksempel vil "nyheder" og "nye" blive reduceret til stammen "ny" som følge af stammer, selvom disse ord tilhører forskellige leksikalske kategorier. Et andet problem er, at nogle stammende algoritmer kan være egnede til et korpus og forårsage for mange fejl i et andet. For eksempel vil ordene "aktier", "aktier", "strømpe" osv. have en særlig betydning i avisen The Wall Street Journal . Hovedideen med korpus- baseret stemming er at skabe ækvivalensklasser for ordene fra klassiske stemmer og derefter "bryde" nogle kombinerede ord baseret på deres forekomst i korpuset. Det hjælper også med at forhindre de velkendte kollisioner af Porters algoritme, såsom "politik/politi", da chancen for at disse ord optræder sammen er ret lav [7] .
Sådanne algoritmer bruger en database med stammer (for eksempel et sæt dokumenter, der indeholder ordstammer). Disse stammer svarer ikke nødvendigvis til almindelige ord, i de fleste tilfælde er stammen en understreng (for eksempel på engelsk er "brows" en understreng i ordene "browse" og "browsing"). For at bestemme roden af et ord, forsøger algoritmen at matche det med stammerne fra databasen ved at anvende forskellige begrænsninger, for eksempel på længden af den søgte stamme i ordet i forhold til længden af selve ordet (f. for eksempel vil det korte præfiks "være", som er grundlaget for sådanne ord, som "være", "været" og "være" ikke danne grundlaget for "ved siden af").
Hybride tilgange bruger to eller flere af metoderne beskrevet ovenfor. Et simpelt eksempel er suffikstræ- algoritmen, som i begyndelsen af sit arbejde bruger opslagstabeller til at opnå indledende data ved hjælp af udtømmende søgning. Men i stedet for at gemme hele komplekset af relationer mellem ord for et bestemt sprog, bruges en opslagstabel til at gemme et lille antal "hyppige undtagelser" (f.eks. for det engelske sprog "løb => løb"). Hvis ordet ikke er på ekskluderingslisten, anvendes afslutningsafkortnings- eller lemmatiseringsalgoritmer for at få resultatet.
Mens det meste af den tidlige videnskabelige aktivitet på dette område var fokuseret på engelsk (for det meste ved hjælp af Porter-stammealgoritmen), er efterfølgende arbejde blevet afsat til mange andre sprog [8] [9] [10] [11] [12] .
Hebraisk og arabisk anses stadig for at være svære sprog at lære med hensyn til stemming. Engelske stammealgoritmer er ret trivielle (kun lejlighedsvise problemer opstår, f.eks. er ordet "tørrer" tredje person ental nutid af verbet "tørre", eller ordet "akser" er flertal af "økse" og " akse"); men stemmers bliver sværere at designe, når der vælges et mere komplekst målsprog, nemlig et sprog med mere kompleks morfologi og stavning. For eksempel er stemmers for det italienske sprog mere komplekse end stemmers for engelsk (på grund af det store antal bøjningsformer af verber), implementeringer for det russiske sprog er endnu vanskeligere (et stort antal bøjninger af substantiver), for hebraisk de er endnu mere komplekse (på grund af ikke-konkatenativ morfologi). , skrivning uden vokaler og behovet for præfikset trunkeringsalgoritmer: Hebraiske ordstammer kan være to, tre eller fire tegn lange, men ikke længere), og så videre.
Flersprogede stammealgoritmer anvender de morfologiske regler for to eller flere sprog på samme tid.
Det russiske sprog tilhører gruppen af bøjningssyntetiske sprog, det vil sige sprog, hvor orddannelsen dominerer ved hjælp af affikser , der kombinerer flere grammatiske betydninger på én gang (for eksempel slags - endelsen й angiver samtidig ental, maskuline køn og nominativ kasus), derfor tillader dette sprog brug af stammende algoritmer. Det russiske sprog har en kompleks morfologisk ændring af ord, hvilket er en kilde til fejl ved brug af stemming. Som en løsning på dette problem kan sammen med de klassiske stammealgoritmer bruges lemmatiseringsalgoritmer, der bringer ord til den oprindelige grundform.
Lad os overveje de mest populære implementeringer af stemmer baseret på forskellige principper og tillader behandling af ikke-eksisterende ord til det russiske sprog.
Stemmer PorterHovedideen med Porters stemmer er, at der er et begrænset antal orddannende suffikser, og ordstamming forekommer uden brug af nogen stambaser: kun et sæt eksisterende suffikser og manuelt indstillede regler.
Algoritmen består af fem trin. Ved hvert trin afskæres et orddannende suffiks, og den resterende del kontrolleres for overholdelse af reglerne (for eksempel for russiske ord skal stammen indeholde mindst en vokal). Hvis det resulterende ord opfylder reglerne, sker overgangen til næste trin. Hvis ikke, vælger algoritmen et andet suffiks til klipning. I det første trin afskæres det maksimale formdannende suffiks, ved det andet - bogstavet "i", ved det tredje - det orddannende suffiks, ved det fjerde - suffikserne af superlativformer, "ь" og en af de to "n" [13] .
Denne algoritme afkorter ofte ordet mere end nødvendigt, hvilket gør det vanskeligt at få den korrekte stilk af ordet, for eksempel seng-> tag (i dette tilfælde er den virkelig uændrede del bed , men stemmeren vælger det længste morfem for sletning). Porters stemmer klarer heller ikke alle mulige ændringer i ordroden (f.eks. frafald og flydende vokaler).
StemkaDenne stammealgoritme (analyzer) blev udviklet af Andrey Kovalenko i 2002. Den er baseret på en probabilistisk model: ord fra træningsteksten parses af analysatoren i par "de sidste to bogstaver i stammen" + "suffiks", og hvis et sådant par allerede er til stede i modellen, øges dets vægt , ellers tilføjes det til modellen. Derefter rangeres det resulterende dataarray i faldende rækkefølge efter vægt, og modellerne, hvis sandsynlighed er mindre end 1/10000, afskæres. Resultatet - et sæt potentielle slutninger med betingelser på de foregående tegn - vendes for at lette scanning af ordformer "fra højre til venstre" og præsenteres som en overgangstabel for en endelig automat. Ved parsing scannes ordet i henhold til de konstruerede overgangstabeller. Der blev også tilføjet en særlig regel til algoritmen, som siger, at den ufravigelige stamme skal indeholde mindst én vokal [14] .
Den præsenterede analysator er tilgængelig i kildetekster og kan bruges i fri form med betingelsen om reference til kilden [15] [16] .
MyStemMyStem-stemmeren blev udviklet af Ilya Segalovich i 1998. Den er nu Yandex 's ejendom [17] . Ved det første trin, ved hjælp af suffikstræet i inputordet, bestemmes de mulige grænser mellem stammen og suffikset, hvorefter, for hver potentiel stamme (startende med den længste), binær søgning i stamtræet kontrollerer dens tilstedeværelse i ordbogen eller finde stænglerne tættest på den (ved et mål for nærhed er længden af den fælles "hale"). Hvis ordet er et ordbogsord, afsluttes algoritmen, ellers fortsætter den til næste partition.
Hvis stamvarianten ikke matcher nogen af de "nærmeste" ordbogsstammer, betyder det, at det analyserede ord med denne stamvariant ikke er i ordbogen. Derefter, baseret på den eksisterende stamme, suffiks og model for den "nærmeste" ordforrådsstamme, genereres en hypotetisk model til at ændre det givne ord. Hypotesen huskes, og hvis den allerede er bygget tidligere, øger den sin vægt. Hvis ordet aldrig blev fundet i ordbogen, reduceres længden af den påkrævede generelle stammeslutning med én, træet scannes for nye hypoteser. Når længden af den fælles "hale" når 2, stopper søgningen, og hypoteserne rangeres efter produktivitet: hvis vægten af hypotesen er fem eller flere gange mindre end den største vægt, elimineres en sådan hypotese. Resultatet af stemmerens arbejde er det resulterende sæt af hypoteser for et ikke-eksisterende ord eller en hypotese for et ordbogsord [18] .
Stemmeren kan bruges til kommercielle formål; undtagelser er: oprettelse og distribution af spam, søgemaskineoptimering af websteder og udvikling af produkter og tjenester svarende til tjenester og produkter fra Yandex [17] . Kildekoder distribueres ikke [19] . For at installere skal du blot downloade og udpakke arkivet [20] .
Der er to typer fejl i stammealgoritmer: overstemming' og understemming . Overstamming er en fejl af den første slags , når bøjningsord fejlagtigt tilskrives ét lemma. Understemning er en fejl af den anden art , når morfologiske former af ét ord tilskrives forskellige lemmaer. Stemming-algoritmer forsøger at minimere begge disse fejl, selvom reduktion af en type fejl kan øge den anden [21] .
Lad os overveje disse typer fejl i forbindelse med Porters stemmingsalgoritme. overstamming error case : denne algoritme vil matche ordene "universal", "university" og "universe" med stammen "univers"; selvom disse ord er etymologisk forskellige, henviser deres moderne betydninger til forskellige områder, så det er ikke korrekt at behandle dem som synonymer. Understem - fejlstilfælde : Porters algoritme vil matche ord, der er afledt af det samme lemma med forskellige stammer, og vil derfor tilskrive dem til forskellige lemmaer - "alumnus" → "alumnu", "alumni" → "alumni", "alumna" / " alumnae" → "alumna" (disse ord beholdt latinske træk i deres morfologi, men disse næsten-synonymer blev ikke kombineret af en stemmer).
Stemming bruges som en omtrentlig metode til at gruppere ord med lignende grundlæggende betydninger. For eksempel er tekst, der nævner "påskeliljer" sandsynligvis tæt forbundet med tekst, der nævner "påskelilje" (uden "s"). Men i nogle tilfælde har ord med samme stamme idiomatiske betydninger, der næsten ikke er relaterede: en brugers søgning efter dokumenter, der indeholder "markedsføring", vil også returnere dokumenter, der nævner "markeder", men ikke indeholder "markedsføring" (hvilket højst sandsynligt ikke gør opfylder brugerens informationsbehov ).
Stemming er ret almindeligt i søgemaskiner . Relativt hurtigt blev effektiviteten af stemming i søgemaskiner til det engelske sprog imidlertid erkendt som meget begrænset, og dette fik unge forskere inden for informationssøgning til at forstå, at stemming ikke er generelt anvendelig [22] [23] . I søgemaskiner kan der i stedet for stammer bruges en tilgang baseret på søgning efter N-gram frem for stammer. Derudover har nyere undersøgelser vist store fordele ved N-gram søgning efter andre sprog end engelsk [24] [25] .
Når man analyserer emneområder ved hjælp af stemming, opbygges ordbøger over disse områder [26] .
Mange kommercielle virksomheder har brugt stemming i det mindste siden 1980'erne og har udviklet algoritmiske og leksikale stemmere til mange sprog [27] [28] .
Snowball-stemmere blev sammenlignet med kommercielle. Resultaterne er blevet blandede [29] [30] .
Google-søgemaskinen har brugt stemming siden 2003 [31] . Tidligere ville en søgning efter "fisk" ikke give resultater, der indeholdt "fiskeri".
| naturlig sprogbehandling | |
|---|---|
| Generelle definitioner | |
| Tekstanalyse |
|
| Referencer |
|
| Maskinoversættelse |
|
| Identifikation og dataindsamling | |
| Tematisk model | |
| Peer review |
|
| Naturlig sproggrænseflade [ | |