Tolerante und Wildcard-Retrieval

Tolerantes Retrieval ermöglicht es einem Suchsystem, Abfragen trotz Rechtschreibvarianten, Wildcards und phonetischer Unterschiede abzugleichen, sodass Benutzer weiterhin relevante Dokumente finden, auch wenn Abfrage und Text nicht exakt übereinstimmen.

Definition

Tolerantes Retrieval umfasst Techniken auf Wörterbuchebene, die Abfrageterme mit indizierten Termen abgleichen, trotz unvollständiger, falsch geschriebener oder phonetisch variierender Eingaben, einschließlich Wildcard-Expansion, Editierdistanz-basierter Rechtschreibkorrektur und phonetischer Kodierung.

Scope

Dieses Thema behandelt Techniken, die eine exakte Termübereinstimmung auf Wörterbuchebene lockern: Wildcard-Abfrageverarbeitung unter Verwendung von Permuterm- und K-Gramm-Indizes, Rechtschreibkorrektur mittels Editierdistanz und Kontext sowie phonetische Übereinstimmung wie Soundex. Es wird behandelt, wie das Termwörterbuch erweitert wird, um diese approximativen Suchvorgänge zu unterstützen, und wie Kandidatenterme generiert und bewertet werden, was sich von der semantischen Übereinstimmung unterscheidet, die sich eher auf die Bedeutung als auf die Oberflächenform bezieht.

Core questions

• Wie werden Wildcard-Abfragen wie Präfix-, Suffix- und Infixmuster gegen das Wörterbuch ausgewertet?
• Wie unterstützen Permuterm- und K-Gramm-Indizes Wildcard-Suchvorgänge?
• Wie wird der am nächsten liegende korrekt geschriebene Term für einen falsch geschriebenen Abfrageterm gefunden?
• Wie quantifiziert die Editierdistanz (Levenshtein-Distanz) den Unterschied zwischen zwei Zeichenketten?
• Wie gruppiert die phonetische Übereinstimmung wie Soundex Terme, die ähnlich klingen?

Key concepts

• Wildcard-Abfrage
• Permuterm-Index
• K-Gramm-Index
• Editierdistanz (Levenshtein-Distanz)
• Rechtschreibkorrektur
• phonetische Übereinstimmung (Soundex)
• approximative Zeichenkettenübereinstimmung
• Kandidatentermgenerierung

Key theories

Wildcard-Indizierung mit Permuterm- und K-Gramm-Indizes

Durch das Rotieren von Termen, sodass ein Wildcard immer am Ende steht (Permuterm), oder das Indizieren von Termen nach ihren Zeichen-K-Grammen kann das System ein Wildcard-Muster in gewöhnliche Wörterbuchsuchen umwandeln, die Kandidatenterme abrufen.

Rechtschreibkorrektur mittels Editierdistanz

Die minimale Anzahl von Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, die erforderlich sind, um eine Zeichenkette in eine andere umzuwandeln (Editierdistanz), bietet ein prinzipielles Maß zur Vorschlagung korrekt geschriebener Alternativen zu einem Abfrageterm, oft in Kombination mit Termhäufigkeit und Kontext.

Clinical relevance

Tolerantes Retrieval ermöglicht alltägliche Suchfunktionen: Rechtschreibvorschläge wie „Meinten Sie“, Autovervollständigung und Präfixsuche sowie eine fehlertolerante Übereinstimmung von Namen und Produktbegriffen. Es verbessert die Trefferquote und die Benutzerfreundlichkeit erheblich, wenn Abfragen Tippfehler enthalten oder Benutzer die genaue Schreibweise nicht kennen.

History

Approximative Übereinstimmung und Rechtschreibkorrektur haben eine lange Geschichte in der Informatik, wobei Soundex auf die Aufzeichnungsindizierung des frühen 20. Jahrhunderts zurückgeht. Kukichs Übersicht von 1992 konsolidierte automatische Rechtschreibkorrekturtechniken, und Navarros Übersicht von 2001 systematisierte die approximative Zeichenkettenübereinstimmung. Diese Methoden wurden zu Standardkomponenten von Suchwörterbüchern, da die Websuche eine fehlertolerante Abfrageverarbeitung unerlässlich machte.

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

Wie geht eine Suchmaschine mit einem Wildcard wie „comput*“ um?

Sie verwendet eine Hilfswörterbuchstruktur, wie einen Permuterm- oder K-Gramm-Index, um alle Terme zu finden, die dem Muster entsprechen (Computer, Computing, Computation usw.), und wertet dann die ursprüngliche Abfrage so aus, als ob diese Terme explizit aufgelistet worden wären.

Was ist die Editierdistanz und warum wird sie zur Rechtschreibkorrektur verwendet?

Die Editierdistanz zählt die minimale Anzahl von Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, die erforderlich sind, um ein Wort in ein anderes umzuwandeln. Eine geringe Editierdistanz zwischen einem falsch geschriebenen Abfrageterm und einem Wörterbuchterm deutet darauf hin, dass der Wörterbuchterm eine wahrscheinliche beabsichtigte Korrektur ist.