Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
HHU Düsseldorf, WS 2008/09 Information Retrieval 272
Kapitel 18
Fehlertolerantes Retrieval
HHU Düsseldorf, WS 2008/09 Information Retrieval 273
18. Fehlertolerantes Retrieval
• Eingabefehler– in den Dokumenten– in den Suchanfragen
• Formen– Leerzeichenfehler ("...ofthe..."; "th_ebook")– Fehler an Worten, die isoliert erkannt werden
• typographische Fehler ("teh" statt "the")• orthographische Fehler ("recieve" statt "receive")• phonetische Fehler ("4u" statt "for you")
– Fehler an Worten, die erst im Kontext erkannt werden• syntaktische Fehler ("the study was conducted be XY")• semantische Fehler ("they are leaving in about 15 minuets to
go ...")Kukich K. (1992): Techniques for automatically correcting words in texts. –
In: ACM Computing Surveys 24, S. 377-439.
HHU Düsseldorf, WS 2008/09 Information Retrieval 274
18. Fehlertolerantes Retrieval
Fehler an Worten, die isoliert erkannt werden
Zusätzlicher Buchstabe
10%
Ausgelassener Buchstabe
16%
Multiple Error13%
Falscher Buchstabe
59%
Buchstaben-dreher
2%
Damerau, F.J. (1964): A technique for computer detection and correction of spelling errors. –In: Communications of the ACM 7, S. 171-176.
HHU Düsseldorf, WS 2008/09 Information Retrieval 275
18. Fehlertolerantes Retrieval
Fehlertolerantes Retrieval. Ansatz 1: Phonetik(1a) Der Soundex-Algorithmus
– Verschmelzung von Wortformen anhand ihres Klanges– Vorgehen:
• erster Buchstabe bleibt erhalten• Vokale a, e, i, o, u, y 1• labiale und labiodentale Laute b, f, p, v 2• Kehl- und Zischlaute c, g (übergehen: gh), k ,q, x, s, z (ohne
Schluss-s und -z) 3• Dentallaute d, t 4• palataler Reibelaut l 5• labionasaler Laut: m 6• dento- oder linguanasaler Laut n 7• dentaler Reibelaut r 8
Russell, R.C. (1917): Index. – Patent-Nr. US 1.261.167. – Erteilt am: 2.4.1918. – (Eingereicht am 25.10.1917).
HHU Düsseldorf, WS 2008/09 Information Retrieval 276
18. Fehlertolerantes Retrieval
Fehlertolerantes Retrieval. Ansatz 1: PhonetikDer Soundex-Algorithmus
– Regeln:• aufeinander folgende Buchstaben derselben Lautklasse:
nur den ersten berücksichtigen("Ball" wird zu "Bal")
• mehrere Vokale im Wort:nur den ersten berücksichtigen("Carter" wird zu "Catr")
– Heutiger Stand:• H ist Vokal• m und n: nur eine Klasse
Jacobs, J.R. (1982): Finding words that sound alike. The SOUNDEX algorithm. – In: Byte 7, S. 473-474.
HHU Düsseldorf, WS 2008/09 Information Retrieval 277
18. Fehlertolerantes Retrieval
Fehlertolerantes Retrieval. Ansatz 1: PhonetikDer Soundex-Algorithmus
HoppaH oppaH opa (doppelte Belegung)H op (nur 1 Vokal)H 12
HighfieldH ighfieldH ifield (gh wird übergangen)H ifld (nur 1 Vokal)H 1254
HHU Düsseldorf, WS 2008/09 Information Retrieval 278
18. Fehlertolerantes Retrieval
Fehlertolerantes Retrieval. Ansatz 1: Phonetik(1b): Phonix
– Verfeinerungen von Soundex• phonetische Regeln werden auch auf den 1. Buchstaben
angewandt (night - knight)• "phonetische Ersetzung":
– gleiche Buchstabenfolgen (z.B. "ough") klingen in unterschiedlichen Worten unterschiedlich ("plough" -"cough")
– Regeln beziehen sich auf die Stellung der Zeichenfolge im Wort: am Anfang (z.B. "kn" zu "n"), in der Mitte und am Ende (dort "kn" nicht ändern)
Gadd, T.N. (1988): 'Fisching fore werds': Phonetic retrieval of written text in information systems. –In: Program 22, S. 222-237.
Gadd, T.N. (1990): PHONIX: The algorithm. – In: Program 24, S. 363-366.
HHU Düsseldorf, WS 2008/09 Information Retrieval 279
18. Fehlertoleranz
phonetische Ersetzung
HHU Düsseldorf, WS 2008/09 Information Retrieval 280
18. Fehlertolerantes Retrieval
Fehlertolerantes Retrieval. Ansatz 2: Damerau-Methode
– benötigt Wörterbuch– Schritt 1: Fehleridentifikation (Vergleich: Wort -
Wörterbuch)– Schritt 2: Identifikation des Fehlertyps (die Damerau-
Methode bearbeitet nur Einzelfehler, keine multiple errors)
– Schritt 3: Fehlerkorrektur
Damerau, F.J. (1964): A technique for computer detection and correction of spelling errors. –In: Communications of the ACM 7, S. 171-176.
HHU Düsseldorf, WS 2008/09 Information Retrieval 281
18. Fehlertolerantes Retrieval
Fehlerkorrektur nach Damerau-Methode
FALSCHER BUCHSTABE:
12345678
Eingabe: ALPHIBET
Lexikon: ALPHABET
einzige Differenz bei Stelle 5
Ergebnis Korrigiere Alphibet zu Alphabet!
HHU Düsseldorf, WS 2008/09 Information Retrieval 282
18. Fehlertolerantes Retrieval
Fehlerkorrektur nach Damerau-Methode
BUCHSTABENDREHER:
12345678
Eingabe: ALHPABET
Lexikon: ALPHABET
Differenzen bei Stellen 3 und 4. HP in der Eingabe entspricht umgekehrter Reihenfolge PH im Lexikon
Ergebnis Korrigiere Alhpabet zu Alphabet!
HHU Düsseldorf, WS 2008/09 Information Retrieval 283
18. Fehlertolerantes Retrieval
Fehlerkorrektur nach Damerau-Methode
ZUSÄTZLICHER BUCHSTABE
123456789
Eingabe: ALLPHABET
Lexikon: ALPHABET
Erste Differenz bei Stelle 3 –Löschen des L bei Eingabe
Ergebnis ALPHABET Übereinstimmung mit Lexikon: Korrigiere Allphabet zu Alphabet!
HHU Düsseldorf, WS 2008/09 Information Retrieval 284
18. Fehlertolerantes Retrieval
Fehlerkorrektur nach Damerau-Methode
AUSGELASSENER BUCHSTABE
12345678
Eingabe: ALPABET
Lexikon: ALPHABET
Erste Differenz bei Stelle 4 –Löschen des H bei Lexikon
Ergebnis ALPABET Übereinstimmung mit Eingabe: Korrigiere Alpabet zu Alphabet!
HHU Düsseldorf, WS 2008/09 Information Retrieval 285
18. Fehlertolerantes Retrieval
Fehlertolerantes Retrieval. Ansatz 3: n-Gramme
– benötigt Wörterbuch; Zerlegung der Lexeme in n-Gramme– Schritt 1: Fehleridentifikation (wenn Wort ein n-Gramm
enthält, das nicht im Wörterbuch vorkommt)– Schritt 2: Fehlerkorrektur (Ähnlichkeit nach Dice) (m, m':
Anzahl der Buchstaben):• # n-Gramme des Wortes: m' + n - 1• # n-Gramme des Lexems: m + n - 1• # gemeinsamer n-Gramme: g• Ähnlichkeit(Wort-Lexem) = 2g / (m + n -1 + m' + n - 1)
Angell, R.C.; Freund, G.E.; Willett, P. (1983): Automatic spelling correction using a trigram similarity measure. –In: Information Processing & Management 19, S. 255-261.
HHU Düsseldorf, WS 2008/09 Information Retrieval 286
18. Fehlertolerantes Retrieval
Eingabewort: CONSUMMING; Lexem: CONSUMING; N=3
CONSUMMING hat zehn Buchstaben und wird demnach durch zwölf Trigramme(m'+n-1 = 12) ausgedrückt:
**C, *CO, CON, ONS, NSU, SUM, UMM, MMI, MIN, ING, NG*, G**.
Die Zerlegung von CONSUMING ergibt elf Trigramme (m+n-1 = 11):**C, *CO, CON, ONS, NSU, SUM, UMI, MIN, ING, NG*, G**.
Gemeinsam haben die beiden Zeichenketten zehn Trigramme (g = 10):**C, *CO, CON, ONS, NSU, SUM, MIN, ING, NG*, G**.
Die Ähnlichkeit von CONSUMMING und CONSUMING beträgt also:2 * 10 / (12 + 11)= 20 / 23 = 0,87.