STEMMING ALGORITHMS

1. Table Lookup
2. Successor Variety
3. n-gramm Stemmers
4. Affix Removal Stemmers
• Porter Algorithm

• Die Rolle des Stemmings beim Komprimieren von Index-Dateien

EINFÜHRUNG

Um die Suche nach relevanten Informationen zu verbessern, muss man Möglichkeiten finden, wie man unterschiedliche morphologische Varianten eines Suchbegriffs findet. Es liegt nahe, dass jemand, der an Dokumenten interessiert ist, die das Wort "engeneer" enthalten, wahrscheinlich auch solche Dokumente interessant finden wird, in denen die Wörter "engeneering" oder "engeneered" vorkommen. Dies kann man unter Anderem durch Konflation von Wörtern erreichen.

Unter der Konflation versteht man Kürzen, Kombinieren oder auch Zusammenfügen von Wörtern (Buchstabenfolgen!) und/oder "Wortelementen", um unterschiedliche morphologische Varianten eines Wortes zu matchen. Die Konflation kann auf zweierlei Weisen vorgenommen werden: manuell, indem man die regulären Ausdrücke benutzt, oder automatisch, mit Hilfe von geeigneten Programmen, sogenannten Stemmern.

Es liegt nahe, dass, außer dass durch das Stemming die Suche nach relevanten Dokumenten verbessert wird, als ein positives Begleiteffekt die Index-Dateien reduziert werden können, da in der Regel mehrere vollständige Terme ein und dasselbe Stem haben. Einigen Berichten zufolge werden die Index-Dateien manchmal um bis über 50% reduziert.

Stemming von Termen kann man entweder während der Indexierung, oder während der Suche vornehmen. Beide Ansätze haben sowohl ihre Vorteile als auch ihre Nachteile. Ein wichtiger Vorteil des Stemming während der Indexierung ist einerseits die Effizienz des Verfahrens - die Terme müssen dann nicht mehr während der Suche gestemmt werden - und andererseits eine Komprimierung der Index-Datei (was man beim Stemming während der Suche nicht hat!). Der Nachteil ist, dass die Information über den vollständigen Begriff verlorengeht, oder man braucht zusätzlichen Speicherplatz, wo sowohl der Begriff selbst als auch das entsprechende Stem gespeichert werden. Unter diesem Aspekt wäre das Stemming während der Suche geeigneter.

Nach der Methode der Konflation können Algorithmen bzw. Stemmer in mehrere Gruppen eingeteilt werden:

1. Affix removal algorithms - entfernen die Präfixe und/oder die Suffixe und hinterlassen ein - manchmal auch etwas transformiertes - Stem.
2. Successor variety stemmer - verwenden als Basis für Stemming Frequenzen von Buchstabensequenzen im Text.
3. Stemmer nach der n-gramm Methode - konflatieren die Terme aufgrund ihrer gemeinsamen Digrammen oder n-grammen.
4. Table lookup stemmer - die Terme und ihre entsprechenden Stems sind alle in einer Tabelle gespeichert.

Später werden diese Gruppen auch näher vorgestellt.

Es gibt mehrere Kriterien, die bei der Beurteilung der Stemmer in Betracht gezogen werden müssen. Das sind vor Allem:

• Korrektheit - also weder overstemming (wenn zu viel von dem Term entfernt wurde - führt dazu, dass auch nicht verwandte Begriffe das gleiche Stem haben, weswegen dann bei der Suche auch nichtrelevante Dokumente durchsucht werden und in der Antwortmenge enthalten sind)), noch understemming (wenn zu wenig von dem Term entfernt wurde - führt dazu, dass verwandte Begriffe nicht konflatiert werden, weswegen relevante Dokumente vielleicht nicht durchsucht werden und nicht in die Antwortmenge kommen);
• Retrieval-Effizienz - gemessen nach Recall und Präzision, nach der Schnellichkeit… und
• Kompressionsrate

TYPEN VON STEMMING ALGORITHMEN

1. Table Lookup

Alle Indexterme und ihre Stems sind in einer Tabelle gespeichert.

Das Problem bei solchen Tabellen ist einerseits ein relativ großer Pflegeaufwand,weil sie ständig aktualisiert werden müssen; andererseits brauchen solche Tabellen auch viel Speicherplatz.

2. Successor Variety (die Nachfolger-Verschiedenheit)

Diese Stemmer basieren auf den Arbeiten aus dem Bereich der strukturalen Linguistik, die versucht, Wort- und Morphemgrenzen aufgrund der Distribution der Phoneme in einem großen Korpus zu determinieren; nur arbeitet ein Stemmer statt mit Phonemen mit Buchstaben und statt mit phonologisch transkribierten Ausdrücken mit dem Korpus.

Um die Methode entwickeln zu können, haben Hafer und Weis zunächst einige Begriffe definiert:

Die successor variety (die Nachfolger-Verschiedenheit) eines Strings haben sie definiert als die Zahl der unterschiedlichen Buchstaben, die diesem String in den Wörtern eines Textkorpus folgen.

Beispiel:

Innerhalb des Textkorpus

In einem großen Korpus (cca. 2000 Terme) wird sich mit jedem Buchstaben, der einem "Teilstring" hinzugefügt wird, die Nachfolger-Verschiedenheit erhöhen, bis die Grenze eines Segments erreicht wird; in dem Moment fällt sie wieder stark zurück. Diese Information wird benutzt, um die Stems zu identifizieren.

Aufgrund von so gewonnenen Nachfolger-Verschiedenheiten wird das gegebene Wort segmentiert; hier gibt es wieder mehrere Methoden:

• Cutoff method: es wird einfach ein Grenzwert für die Nachfolger-Verschiedenheit selektiert; wenn die Grenze erreicht wird, wird der Rest abgeschnitten.
  Das Problem: wie soll man den richtigen cutoff-Wert bestimmen?

• Complete word method: der Bruch kommt nach dem Segment, das als ein vollständiges Wort im Korpus vorkommt.

• Peak and plateau method: der Sequenzbruch kommt nach demjenigen Buchstaben, dessen Nachfolger-Verschiedenheit höher ist als die Nachfolger-Verschiedenheit des ihm vorangehenden und ihm nachfolgenden Buchstaben; es muss also kein cutoff-Wert explizit genannt werden. Anhand eines Beispiels kann man die Methode besser Verstehen:

Prefix		Successor Variety	Letters
	R	3	E, I, O
	RE	2	A, D
	REA	1	D
	READ	3	A, I, S
	READA	1	B
	READAB	1	L
	READABL	1	E
	READABLE	1	BLANK

Also: in diesem Fall kommt der Bruch nach dem String mit dem successor variety-Wert 3, nämlich nach dem String "READ".

Hafer und Weis haben die obigen Methoden experimentell evaluiert; ihre Schlussfolgerung war, dass keine von ihnen perfekte Resultate liefert, aber man kann sie kombinieren. Im obigen Beispiel wäre das Wort nach beiden Methoden - also nach complete word method und peak and plateau method - in "READ" und "ABLE" segmentiert.

Danach muss ein Segment als Stem selektiert werden. Dies geschieht nach folgendem Algorithmus:

Zur Erklärung des Algorithmus soll hinzugefügt werden, dass Hafer und Weis eine interessante Regelmäßigkeit festgestellt haben: nämlich, wenn ein Segment in mehr als 12 Wörtern im Korpus vorkommt, dann ist es ein Präfix; andererseits sind im Englischen mehrfache Präfixe äußerst selten - daher kann man nach einem Präfix das zweite Segment als Stem nehmen.

3. n-gramm Stemmers

Diese Stemmer funktionieren nach der shared-digramm(n-gramm)-Methode; einer Methode, die Adamson und Boreham entwickelt haben. Es werden Paare von Wörtern gebildet aufgrund ihrer gmeinsamen Digrammen. Zum Beispiel: die Wörter statistics und statistical haben sechs gemeinsame Digramme):

Der Ahnlichkeitsmaß S zwischen den beiden Begriffen wird berechnet nach der Formel:

Dabei ist:

A --> die Zahl der einzelnen Digrammen aus dem ersten Wort;
B --> die Zahl der einzelnen Digrammen aus dem zweiten Wort;
C --> die Zahl der gemeinsamen Digrammen.

Aus diesen Daten wird eine Ähnlichkeitsmatrix erstellt:

Im Realfall werden die meisten Wörter paarweise verglichen einen Ähnlichkeitsmaß gleich null haben, also die positiven Werte in der Matrix sind zestreut.

4. Affix Removal Stemmers

Diese Stemmers entfernen das Präfix/Suffix vom Term und hinterlassen das - manchmal transformierte - Stem. Ein ganz einfaches Beispiel eines solchen Stemmer wäre folgender Algorithmus:

Meistens werden sogenannte iterative longest match stemmers verwendet; dabei wird immer nach bestimmten Regeln die längste mögliche Sequenz entfernt, und das Verfahren wird wiederholt bis keine Charaktere mehr entfernt werden können. Manchmal ist aber das Stem am Ende nicht korrekt konflatiert. Es gibt zwei Methoden, um das zu korrigieren.

• RECODING: hier handelt es sich um eine Kontext-sensitive Transformation der Form AxC -> AyC (z.B. wenn das Stem mit "i" endet und von "k" gefolgt wird, dann i -> k, z.B. skies/sky);
• PARTIAL MATCHING: beim Vergleichen werden nur n Anfangscharaktere des Stems betrachtet; zwei Stems sind gleich wenn sie sich in allem entsprechen außer in ihren letzten Charakteren.

Es gibt mehrere Stemmers nach dieser Methode: Lovins (1968), Salton (1968), Dawson (1974), Porter (1980) and Paice (1990). Der wohl bekannteste ist der Porter's Stemmer, und der wird hier auch näher dargestellt.

Porter algorithm

Porter algorithm besteht aus einer Reihe von Regeln, die die Konditionen und die Aktionen bestimmen:

1. Das Maß m eines Stems bezeichnet die Zahl seiner alternierenden Vokal-Konsonant-Sequenzen. Unter Vokale gehören a, e, i, o, u und y wenn es nach einen Konsonant kommt. Das Maß m ist definiert als:

   [C](VC)^m[V]

   Bemerkung: Die eckigen Klammern bedeuten die Optionalität.

   Das unten stehende Beispiel sollte das verdeutlichen.

Measure	Examples
m=0	TR, EE, TREE, Y, BY
m=1	TROUBLE, OATS, TREES, IVY
m=2	TROUBLES, PRIVATE, OATEN




2. *< X > -- Das Stem endet mit dem gegebenen Buchstaben.

3. *v* -- Das Stem enthält einen Vokal.

4. *d -- Das Stem endet mit einem Doppelkonsonant.

5. *o -- Das Stem endet mit einer Sequenz Konsonant-Vokal-Konsonant, wobei der letzte Konsonant w, x oder y ist.

Die Regeln sind in Schritte eingeteilt. Die Regeln in einem Schritt werden immer reihenweise geprüft und es kann immer nur eine Regel angewendet werden; sie sind nämlich so formuliert und geordnet, dass immer das längste mögliche Suffix entfernt wird.

Im Folgenden werden der Porters Algorithm sowie die in einzelne Schritte eingeteilte Regeln dargestellt.

EVALUIERUNG

Es wurden mehrere Studien durchgeführt, in denen versucht wurde, die einzelnen Stemmer zu beurteilen; allerdings sind die Resultate manchmal: fraglich, weil die Berichte über die statistischen Ergebnissen fehlen, oder wegen der spezifischen Eigenschaften der Korpora. Im Algemeinen konnte man keine großen Unterschiede zwischen unterschiedlichen Verfahren feststellen. Tatsache ist, dass das Stemming fast immer die Effizienz des IR mehr oder weniger verbessert.

1987 haben z.B. Walker und Jones eine Studie über das Porter's Stemmer durchgeführt. Sie haben herausgefunden, dass ein schwaches Stemming das Recall erhöht, wobei die Präzision darunter nicht leidet (wie das bei starkem Stemming der Fall ist). Daher empfehlen sie eine automatische Benutzung von schwachem Stemming; nach dem starkem Stemming sollte man greifen erst wenn das schwache keine befriedigenden Resultate ergibt.

Außerdem hängen die Resultate manchmal auch von dem Wortschatz ab: der Stemmer angewandt auf einem spezifischen und homogenen Vokabular kann die Terme anders konflatieren als bei anderen Typen vom Vokabular.

Die Rolle des Stemmings beim Komprimieren von Index-Dateien

Nach experimentellen Untersuchungen wurden die Dateien meistens, je nach dem Stemmer und nach dem Korpus, um 30-40 % komprimiert, manchmal aber auch bis über 50%. In der Realität sind aber die Platzeinsparungen doch etwas niedriger; mit der Größe einer Datei sinkt nämlich auch die tatsächliche Reduktion, so wie wenn die Datei viele Zahlen oder Eigennamen enthält, oder auch viele Tippfehler.

Andererseits steigt die Kommpressionsrate - insbesondere bei den Affix removal Stemmer - wenn die Datei viele Terme mit Suffixen enthält.

Einige interessante Links:

http://rayuela.ieec.uned.es/cgi-bin/ircourse/stem2.perl (demo/Perl - Text-Eingabe)
http://ils.unc.edu/keyes/java/porter/index.html (demo/Java - 1-Wort-Eingabe)
http://www.pitt.edu/~steffi/porter.html (demo/Perl - 1-Wort-Eingabe)
http://maya.cs.depaul.edu/~mobasher/classes/ds575/software/stem.c (implementiert in C)
http://www.sims.berkeley.edu/courses/is202/f98/Lecture15/sld022.htm (einige fehlerhafte Konflationen des Porter Stemmer)

Literatur für diesen Teil des Referats:

W. Frakes and R. Baeza-Yates, editors: Information Retrieval: Data Structures and Algorithms. Prentice-Hall, 1992. (Kapitel 8)