Stängeln

In der linguistischen Morphologie und im Information Retrieval bezeichnet Stemming den Prozess, flektierte (oder manchmal abgeleitete) Wörter auf ihren Wortstamm , ihre Basis oder Wurzel – in der Regel eine geschriebene Wortform – zu reduzieren. Der Stamm muss nicht mit der morphologischen Wurzel des Wortes identisch sein; es genügt meist, dass verwandte Wörter auf denselben Stamm zurückgeführt werden, selbst wenn dieser Stamm selbst keine gültige Wurzel darstellt. Algorithmen für Stemming werden in der Informatik seit den 1960er Jahren erforscht. Viele Suchmaschinen behandeln Wörter mit demselben Stamm als Synonyme im Rahmen einer Suchanfrageerweiterung , einem Prozess, der als Konflation bezeichnet wird.

Ein Computerprogramm oder eine Subroutine, die Wörter auf ihren Wortstamm reduziert, kann als Stemming-Programm , Stemming-Algorithmus oder Stemmer bezeichnet werden .

Ein Stemmer für Englisch, der mit dem Stamm „cat“ arbeitet, sollte Zeichenketten wie „cats“ , „catlike“ und „catty“ erkennen. Ein Stemming-Algorithmus könnte beispielsweise die Wörter „fishing“ , „fished“ und „fisher“ auf den Stamm „fish“ reduzieren . Der Stamm muss kein Wort sein; so reduziert der Porter-Algorithmus beispielsweise „ garegate “ , „argued“ , „ arguates“ , „arguing “ und „argus“ auf den Stamm „argu“ .

Der erste veröffentlichte Stemmer wurde 1968 von Julie Beth Lovins entwickelt. ^{[ 1 ]} Diese Arbeit war aufgrund ihres frühen Erscheinungsdatums bemerkenswert und hatte großen Einfluss auf spätere Forschungen in diesem Bereich. Sie verweist darin auf drei frühere bedeutende Versuche zur Entwicklung von Stemming-Algorithmen: den von Professor John W. Tukey von der Princeton University , den von Michael Lesk an der Harvard University unter der Leitung von Professor Gerard Salton entwickelten Algorithmus und einen dritten Algorithmus von James L. Dolby von R&D Consultants in Los Altos, Kalifornien.

Ein späterer Stemmer wurde von Martin Porter entwickelt und in der Juli-Ausgabe 1980 der Fachzeitschrift „ Program“ veröffentlicht . Dieser Stemmer fand weite Verbreitung und wurde zum De-facto-Standardalgorithmus für das Stemming englischer Wörter. Dr. Porter erhielt im Jahr 2000 den Tony Kent Strix Award für seine Arbeiten zum Stemming und Information Retrieval.

Es wurden zahlreiche Implementierungen des Porter-Stemming-Algorithmus geschrieben und frei verbreitet; viele dieser Implementierungen wiesen jedoch subtile Mängel auf. Daher schöpften diese Stemmer ihr Potenzial nicht aus. Um diese Fehlerquelle zu beseitigen, veröffentlichte Martin Porter um das Jahr 2000 eine offizielle, freie Software -Implementierung (größtenteils unter BSD -Lizenz) ^{[ 2 ]} des Algorithmus. In den folgenden Jahren erweiterte er diese Arbeit durch die Entwicklung von Snowball , einem Framework zum Schreiben von Stemming-Algorithmen, und implementierte einen verbesserten englischen Stemmer sowie Stemmer für mehrere andere Sprachen.

Der Paice-Husk-Stemmer wurde Ende der 1980er Jahre von Chris D. Paice an der Universität Lancaster entwickelt . Er ist ein iterativer Stemmer und verwendet einen extern gespeicherten Satz von Stemming-Regeln. Der Standardregelsatz liefert einen „starken“ Stemmer und kann das Entfernen oder Ersetzen einer Endung festlegen. Die Ersetzungsmethode vermeidet einen separaten Schritt im Prozess, der zum Umkodieren oder für die partielle Übereinstimmung erforderlich ist. Paice entwickelte außerdem ein direktes Messverfahren zum Vergleich von Stemmern, das auf der Zählung von Über- und Unterstemming-Fehlern basiert.

Es gibt verschiedene Arten von Stemming-Algorithmen, die sich hinsichtlich Leistung und Genauigkeit sowie der Überwindung bestimmter Stemming-Hindernisse unterscheiden.

Ein einfacher Stemmer sucht die flektierte Form in einer Nachschlagetabelle . Die Vorteile dieses Ansatzes liegen in seiner Einfachheit, Schnelligkeit und der problemlosen Behandlung von Ausnahmen. Zu den Nachteilen zählt, dass alle flektierten Formen explizit in der Tabelle aufgeführt werden müssen: Neue oder unbekannte Wörter werden nicht berücksichtigt, selbst wenn sie vollkommen regelmäßig sind (z. B. cats ~ cat), und die Tabelle kann sehr groß werden. Bei Sprachen mit einfacher Morphologie, wie Englisch, sind die Tabellengrößen überschaubar, aber stark flektierte Sprachen wie Türkisch können Hunderte von potenziellen flektierten Formen für jede Wurzel aufweisen.

Ein Lookup-Ansatz kann eine vorläufige Wortartenbestimmung nutzen , um Überstemmung zu vermeiden. ^{[ 3 ]}

Die vom Stemmer verwendete Nachschlagetabelle wird in der Regel halbautomatisch erstellt. Wenn das Wort beispielsweise „run“ lautet, könnte der invertierte Algorithmus automatisch die Formen „running“, „runs“, „runned“ und „runly“ generieren. Die letzten beiden Formen sind zwar gültig, aber unwahrscheinlich.

Algorithmen zur Suffixentfernung verwenden keine Nachschlagetabelle mit flektierten Formen und Stammformbeziehungen. Stattdessen wird eine typischerweise kürzere Liste von „Regeln“ gespeichert, die dem Algorithmus anhand einer gegebenen Wortform den Weg zur Stammform aufzeigt. Beispiele für solche Regeln sind:

• Endet das Wort auf 'ed', entfernen Sie das 'ed'.
• Endet das Wort auf 'ing', entfernen Sie das 'ing'.
• Endet das Wort auf 'ly', entferne das 'ly'.

Verfahren zur Suffixentfernung sind deutlich einfacher zu warten als Brute-Force-Algorithmen, vorausgesetzt, der Entwickler verfügt über ausreichendes Wissen in Linguistik, Morphologie und der Kodierung von Suffixentfernungsregeln. Suffixentfernungsalgorithmen gelten aufgrund ihrer ungenauen Leistung bei Ausnahmefällen (wie „ran“ und „run“) mitunter als ungenau. Die von ihnen erzeugten Lösungen beschränken sich auf Wortarten mit wenigen Ausnahmen, die über gut definierte Suffixe verfügen. Dies stellt jedoch ein Problem dar, da nicht alle Wortarten über ein so gut formuliertes Regelwerk verfügen. Die Lemmatisierung versucht, diese Herausforderung zu bewältigen.

Das Entfernen von Präfixen kann ebenfalls implementiert werden. Selbstverständlich verwenden nicht alle Sprachen Präfixe oder Suffixe.

Die Ergebnisse von Suffixentfernungsalgorithmen können aus verschiedenen Gründen variieren. Ein Grund ist, ob der Algorithmus voraussetzt, dass das Ausgabewort ein existierendes Wort der jeweiligen Sprache ist. Manche Ansätze benötigen das Wort nicht im Lexikon (der Gesamtheit aller Wörter der Sprache). Andere Ansätze hingegen verwalten eine Datenbank (eine umfangreiche Liste) aller bekannten morphologischen Wortstämme, die als Wörter existieren. Diese Ansätze prüfen die Liste auf das Vorhandensein des gesuchten Begriffs, bevor sie eine Entscheidung treffen. Existiert der Begriff nicht, wird üblicherweise eine alternative Vorgehensweise gewählt. Diese kann verschiedene Kriterien berücksichtigen. Das Nichtvorhandensein eines Ausgabeworts kann dazu führen, dass der Algorithmus alternative Regeln zur Suffixentfernung anwendet.

Es kann vorkommen, dass zwei oder mehr Regeln zum Entfernen von Suffixen auf denselben Eingabeterm zutreffen, was zu einer Mehrdeutigkeit hinsichtlich der anzuwendenden Regel führt. Der Algorithmus kann (manuell oder stochastisch) einer der Regeln eine Priorität zuweisen. Alternativ kann er die Anwendung einer Regel ablehnen, da diese zu einem nicht existierenden Term führt, während die andere, sich überschneidende Regel dies nicht tut. Beispielsweise könnte der Algorithmus beim englischen Begriff „ friendlies“ das Suffix „-ies“ erkennen , die entsprechende Regel anwenden und das Ergebnis „ friendl“ erhalten . „Friendl“ ist wahrscheinlich nicht im Lexikon vorhanden, weshalb die Regel verworfen wird.

Eine Verbesserung gegenüber dem einfachen Entfernen von Suffixen ist die Verwendung von Suffixsubstitutionen. Ähnlich wie eine Entfernungsregel ersetzt eine Substitutionsregel ein Suffix durch ein alternatives. Beispielsweise könnte es eine Regel geben, die „ies“ durch „y“ ersetzt . Wie sich dies auf den Algorithmus auswirkt, hängt von dessen Design ab. Der Algorithmus kann beispielsweise feststellen, dass sowohl die Entfernungsregel für das Suffix „ies“ als auch die Substitutionsregel anwendbar sind. Da die Entfernungsregel zu einem nicht existierenden Begriff im Lexikon führt, die Substitutionsregel jedoch nicht, wird stattdessen die Substitutionsregel angewendet. In diesem Beispiel wird aus „friendlies“ „friendly“ anstatt „friendl'“ .

Um das genauer zu betrachten: Eine gängige Technik besteht darin, Regeln zyklisch (rekursiv, wie Informatiker sagen würden) anzuwenden. Nach Anwendung der Suffix-Ersetzungsregel in diesem Beispiel wird in einem zweiten Durchlauf nach passenden Regeln für den Begriff „ friendly“ gesucht , wobei die Regel zum Entfernen von „ly“ wahrscheinlich erkannt und angewendet wird. Zusammenfassend lässt sich sagen: „friendlylies“ wird (durch Ersetzung) zu „friendly“ , welches wiederum (durch Entfernen von „ly“) zu „friend“ wird .

Dieses Beispiel verdeutlicht den Unterschied zwischen einem regelbasierten und einem Brute-Force-Ansatz. Bei einem Brute-Force-Ansatz sucht der Algorithmus in Hunderttausenden flektierten Wortformen nach passenden Wörtern und findet idealerweise die entsprechende Grundform „friend“ . Beim regelbasierten Ansatz werden die drei oben genannten Regeln nacheinander angewendet, um zur selben Lösung zu gelangen. Wahrscheinlich ist der Brute-Force-Ansatz langsamer, da Suchalgorithmen direkten Zugriff auf die Lösung haben, während regelbasierte Ansätze verschiedene Optionen und Kombinationen ausprobieren und dann das beste Ergebnis auswählen.

Ein komplexerer Ansatz zur Bestimmung des Wortstamms ist die Lemmatisierung . Dabei wird zunächst die Wortart ermittelt und anschließend für jede Wortart unterschiedliche Normalisierungsregeln angewendet. Die Wortart wird vor der Wurzelsuche bestimmt, da sich die Stammbildungsregeln in manchen Sprachen je nach Wortart ändern.

Dieser Ansatz ist stark davon abhängig, die korrekte Wortart zu ermitteln. Zwar gibt es Überschneidungen zwischen den Normalisierungsregeln für bestimmte Kategorien, doch die falsche oder nicht ermittelte Kategorie schränkt den Nutzen dieses Ansatzes gegenüber Suffix-Entfernungsalgorithmen ein. Die Grundidee ist, dass der Stemmer, wenn er mehr Informationen über das zu stammende Wort erfasst, präzisere Normalisierungsregeln anwenden kann (die im Gegensatz zu Suffix-Entfernungsregeln auch den Wortstamm modifizieren können).

Stochastische Algorithmen nutzen Wahrscheinlichkeiten, um die Grundform eines Wortes zu bestimmen. Sie werden anhand einer Tabelle mit Beziehungen zwischen Grundform und flektierter Form trainiert (sie „lernen“), um ein probabilistisches Modell zu entwickeln. Dieses Modell wird typischerweise in Form komplexer linguistischer Regeln ausgedrückt, ähnlich denen bei der Suffixentfernung oder Lemmatisierung. Die Stammformreduktion erfolgt durch Eingabe einer flektierten Form in das trainierte Modell. Dieses erzeugt dann die Grundform gemäß seinem internen Regelsatz. Auch dies ähnelt der Suffixentfernung und Lemmatisierung, mit dem Unterschied, dass die Entscheidungen – die Anwendung der passendsten Regel, die Beibehaltung des Wortstamms und die sequentielle Anwendung zweier verschiedener Regeln – darauf basieren, dass das resultierende Wort die höchste Wahrscheinlichkeit für Korrektheit aufweist (und somit die geringste Wahrscheinlichkeit für Inkorrektheit, wie sie üblicherweise gemessen wird).

Manche Lemmatisierungsalgorithmen arbeiten stochastisch, indem sie jedem Wort, das mehreren Wortarten angehören kann, eine Wahrscheinlichkeit zuweisen. Dabei können die umgebenden Wörter (der Kontext) berücksichtigt werden, müssen es aber nicht. Kontextfreie Grammatiken berücksichtigen keine zusätzlichen Informationen. In beiden Fällen wird nach der Zuweisung der Wahrscheinlichkeiten zu jeder Wortart die wahrscheinlichste Wortart ausgewählt. Anschließend werden die entsprechenden Normalisierungsregeln auf das Eingabewort angewendet, um die normalisierte (Grund-)Form zu erzeugen.

Einige Stemming-Verfahren nutzen den n-Gramm- Kontext eines Wortes, um den korrekten Wortstamm auszuwählen. ^{[ 4 ]}

Hybride Ansätze kombinieren zwei oder mehr der oben beschriebenen Verfahren. Ein einfaches Beispiel ist ein Suffixbaum-Algorithmus, der zunächst eine Nachschlagetabelle per Brute-Force-Methode durchsucht. Anstatt jedoch alle Relationen zwischen Wörtern einer Sprache zu speichern, wird die Nachschlagetabelle klein gehalten und enthält nur wenige häufige Ausnahmen wie „ran => run“. Ist das Wort nicht in der Ausnahmeliste enthalten, werden Suffixe entfernt oder das Ergebnis lemmatisiert und ausgegeben.

In linguistics, the term affix refers to either a prefix or a suffix. In addition to dealing with suffixes, several approaches also attempt to remove common prefixes. For example, given the word indefinitely, identify that the leading "in" is a prefix that can be removed. Many of the same approaches mentioned earlier apply, but go by the name affix stripping. A study of affix stemming for several European languages can be found here.^[5]

Such algorithms use a stem database (for example a set of documents that contain stem words). These stems, as mentioned above, are not necessarily valid words themselves (but rather common sub-strings, as the "brows" in "browse" and in "browsing"). In order to stem a word the algorithm tries to match it with stems from the database, applying various constraints, such as on the relative length of the candidate stem within the word (so that, for example, the short prefix "be", which is the stem of such words as "be", "been" and "being", would not be considered as the stem of the word "beside")..

While much of the early academic work in this area was focused on the English language (with significant use of the Porter Stemmer algorithm), many other languages have been investigated.^{[6][7][8][9][10]}

Hebrew and Arabic are still considered difficult research languages for stemming. English stemmers are fairly trivial (with only occasional problems, such as "dries" being the third-person singular present form of the verb "dry", "axes" being the plural of "axe" as well as "axis"); but stemmers become harder to design as the morphology, orthography, and character encoding of the target language becomes more complex. For example, an Italian stemmer is more complex than an English one (because of a greater number of verb inflections), a Russian one is more complex (more noun declensions), a Hebrew one is even more complex (due to nonconcatenative morphology, a writing system without vowels, and the requirement of prefix stripping: Hebrew stems can be two, three or four characters, but not more), and so on.^[11]

Multilingual stemming applies morphological rules of two or more languages simultaneously instead of rules for only a single language when interpreting a search query. Commercial systems using multilingual stemming exist.

Stemming-Algorithmen unterscheiden zwei Fehlerarten: Überstemming und Unterstemming. Überstemming liegt vor, wenn zwei verschiedene flektierte Wörter fälschlicherweise auf dieselbe Wurzel reduziert werden – ein falsch positives Ergebnis . Unterstemming hingegen bedeutet, dass zwei verschiedene flektierte Wörter fälschlicherweise auf dieselbe Wurzel reduziert werden sollten – ein falsch negatives Ergebnis . Stemming-Algorithmen versuchen, beide Fehlerarten zu minimieren, wobei die Reduzierung einer Fehlerart jedoch die einer anderen erhöhen kann.

Der weit verbreitete Porter-Stemmer reduziert beispielsweise die Wörter „universal“, „university“ und „universe“ auf „universals“. Dies ist ein Fall von Überstammung: Obwohl diese drei Wörter etymologisch verwandt sind, liegen ihre modernen Bedeutungen in völlig unterschiedlichen Bereichen, sodass ihre Behandlung als Synonyme in einer Suchmaschine die Relevanz der Suchergebnisse wahrscheinlich verringert.

Ein Beispiel für Unterstemming im Porter-Stemmer ist „alumnus“ → „alumnu“, „alumni“ → „alumni“, „alumna“/„alumnae“ → „alumna“. Dieses englische Wort behält seine lateinische Morphologie bei, sodass diese beinahe synonymen Wörter nicht verwechselt werden.

Stemming dient als Näherungsverfahren, um Wörter mit ähnlicher Grundbedeutung zusammenzufassen. Beispielsweise ist ein Text, der „Narzissen“ erwähnt, wahrscheinlich eng mit einem Text verwandt, der „Narzisse“ (ohne „s“) erwähnt. In manchen Fällen haben Wörter mit demselben Wortstamm jedoch idiomatische Bedeutungen, die nicht eng miteinander verwandt sind: Ein Nutzer, der nach „Marketing“ sucht, wird mit den meisten Dokumenten, die „Märkte“, aber nicht „Marketing“ erwähnen, nicht zufrieden sein.

Stemmer können als Elemente in Abfragesystemen wie Web- Suchmaschinen verwendet werden . Die Effektivität des Stemmings für englische Abfragesysteme erwies sich jedoch bald als recht begrenzt, was frühe Forscher im Bereich Information Retrieval dazu veranlasste , Stemming generell als irrelevant zu betrachten. ^{[ 12 ]} Alternativ kann ein Ansatz verwendet werden, der auf der Suche nach N-Grammen anstelle von Stämmen basiert. Stemmer können zudem in anderen Sprachen als Englisch größere Vorteile bieten. ^{[ 13 ] [ 14 ]}

Stemming wird verwendet, um Domänenvokabulare in der Domänenanalyse zu bestimmen . ^{[ 15 ]}

Viele kommerzielle Unternehmen nutzen Stemming mindestens seit den 1980er Jahren und haben algorithmische und lexikalische Stemmer in vielen Sprachen entwickelt. ^{[ 16 ] [ 17 ]}

Die Snowball- Stemmer wurden mit kommerziellen lexikalischen Stemmern verglichen, wobei unterschiedliche Ergebnisse erzielt wurden. ^{[ 18 ] [ 19 ]}

Google Search führte 2003 die Wortstammerkennung ein. ^{[ 20 ]} Zuvor hätte eine Suche nach „fish“ nicht „fishing“ ergeben. Andere Suchalgorithmen verwenden die Wortstammerkennung unterschiedlich. Programme, die lediglich nach Teilzeichenketten suchen, finden natürlich „fish“ in „fishing“, aber bei der Suche nach „fishes“ finden sie keine Vorkommen des Wortes „fish“.

Stemming wird als Vorverarbeitungsschritt bei Texten eingesetzt, bevor Text-Mining-Analysen durchgeführt werden.

• Computerlinguistik  – Einsatz computergestützter Werkzeuge zur Erforschung der Linguistik
• Ableitung  – Bildung eines neuen Wortes auf der Grundlage eines bestehenden Wortes Seiten mit Kurzbeschreibungen der Weiterleitungsziele– Wortstammbildung ist eine Form der umgekehrten Ableitung.
• Flexion  – Prozess der Wortbildung durch Veränderung zur Darstellung grammatischer Kategorien
• Lemma (Morphologie)  – Wurzelwort einer Menge von Wortformen
• Lemmatisierung  – Kanonisierung in der natürlichen Sprachverarbeitung
• Lexem  – Einheit lexikalischer Bedeutung
• Morphologie (Linguistik)  – Die Lehre von den Wörtern und ihrer Bildung
• Verarbeitung natürlicher Sprache  – Verarbeitung natürlicher Sprache durch einen Computer – Stemming wird allgemein als eine Form der NLP betrachtet.
• NLTK  – Software-Suite für die Verarbeitung natürlicher Sprache Seiten mit Kurzbeschreibungen der Weiterleitungsziele– implementiert mehrere Stemming-Algorithmen in Python
• Wurzel (Linguistik)  – Lexikalischer Kern eines Wortes ohne Affixe
• Snowball (Programmiersprache)  – Programmiersprache zur Stringverarbeitung – entwickelt zur Erstellung von Stemming-Algorithmen
• Wortstamm (Linguistik)  – Der Teil eines Wortes, der für seine lexikalische Bedeutung verantwortlich istSeiten mit Kurzbeschreibungen der Weiterleitungsziele
• Text Mining  – Prozess der Textanalyse zur Informationsgewinnung aus dem Text

• Apache OpenNLP—includes Porter and Snowball stemmers
• SMILE Stemmer—free online service, includes Porter and Paice/Husk' Lancaster stemmers (Java API)
• Themis—open source IR framework, includes Porter stemmer implementation (PostgreSQL, Java API)
• Snowball—free stemming algorithms for many languages, includes source code, including stemmers for five romance languages
• Snowball on C#—port of Snowball stemmers for C# (14 languages)
• Python bindings to Snowball API
• Ruby-Stemmer—Ruby extension to Snowball API
• PECL—PHP extension to the Snowball API
• Oleander Porter's algorithm—stemming library in C++ released under BSD
• Unofficial home page of the Lovins stemming algorithm—with source code in a couple of languages
• Official home page of the Porter stemming algorithm—including source code in several languages
• Official home page of the Lancaster stemming algorithmArchived 2011-07-22 at the Wayback Machine—Lancaster University, UK
• Official home page of the UEA-Lite Stemmer —University of East Anglia, UK
• Overview of stemming algorithmsArchived 2011-07-02 at the Wayback Machine
• PTStemmer—A Java/Python/.Net stemming toolkit for the Portuguese language
• jsSnowball—open source JavaScript implementation of Snowball stemming algorithms for many languages
• Snowball Stemmer – Implementierung für Java
• hindi_stemmer – Open-Source-Stemmer für Hindi
• czech_stemmer – Open-Source-Stemmer für Tschechisch
• Vergleichende Bewertung von morphologischen Analysatoren und Stemmern der arabischen Sprache.
• Tamil Stemmer