ubuntuusers.de

Hallo,

ich muß eine Adressuche implementieren und mich stört es, dass ich z.b. den Strassennamen korrekt schreiben muß und bei einer Suche nach "Hafenstraße" nicht "Hafenstrasse" gefunden wird. Kennt ihr vernünftige Algorithmen, die man dafür benutzen kann? Ich bin nach einiger Recherche bei http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik gelandet, ein auf den deutschen Sprachraum abgestimmer http://de.wikipedia.org/wiki/Soundex-Algorithmus.

Ich hab das getestet, aber die Ergebnisse sind noch nicht zufriedenstellend. Gibt es da noch etwas besser geeignetes? Zumal ich mit diesem Algortihmus nicht die Möglichkeit habe, nur nach Teilstrings zu suchen.

Ich kenne bloß das hier: http://norvig.com/spell-correct.html

Kenne mich leider auch nicht detailliert aus, aber da gibt es sicherlich eine Menge.

Einstiegspunkte

• Google Suche "fuzzy string search"

• Approximate string matching

Eine relativ einfache Variante wäre diese: Du nutzt eine Suche nach regulären Ausdrücken. Dafür bearbeitest Du die Eingabe so, dass z.B. "ss", "ß" und "s" durch den regulären Teilausdruck "(s{1,2}|ß) ersetzt werden. Ähnliches machst Du mit "ä", "Ö" usw.

Ciao

robert

Benutz einfach eine Normalisierung. Sämtliche Varianten von Straße, also Strasse, str. etc pp werden beim Einleisen auf eine einzige Variante gemappt. Sowohl beim Einlesen der Datenbank, als auch des Queries. Zum Mapping, kannste einfach reguläre Ausdrücke benutzen.

Kinch schrieb:

Benutz einfach eine Normalisierung. Sämtliche Varianten von Straße, also Strasse, str. etc pp werden beim Einleisen auf eine einzige Variante gemappt. Sowohl beim Einlesen der Datenbank, als auch des Queries. Zum Mapping, kannste einfach reguläre Ausdrücke benutzen.

Man kann das machen, sollte dann aber den ursprünglichen Text behalten. Mit anderen Worten: ein zusätzliches Feld einführen, das den normalisierten Suchtext enthält. Das wäre dann auch die Spalte, auf die man den Index setzt.

Ciao

robert

Hallo,

danke für die Antworten, sie scheinen darauf hinzudeuten, daß es "den" Algorithmus nicht gibt, da hab ich also nichts übersehen. Die Idee einer zusätzlichen Spalte hatten wir auch schon bei Kölner Phonetik, aber dort waren, wir ich schon schrieb, die Ergebnisse nicht zufriedenstellend. Ich probier nochmal den Levenshtein-Algorithmus aus den Wikipedia-Links aus, wenn der Aufwand zum Testen nicht besonders hoch ist. Und ansonsten wird es zumindest eine Suche nach regulären Ausdrücken, um zumindest "Strasse" wie auch "Straße" finden zu können.

Grüße, Jörg

dr.gonzo schrieb:

... Und ansonsten wird es zumindest eine Suche nach regulären Ausdrücken, um zumindest "Strasse" wie auch "Straße" finden zu können.

Das ließe sich ja auch automatisch aufspalten, so dass Du direkt nach allen möglichen Varianten suchst:

Süße  ->  Süße / Sueße
    Süße  ->  Süße / Süsse
    Sueße  ->  / Sueße / Suesse

indem Du alle fraglichen Buchstaben(kombinationen) automatisch in ihre Varianten expandierst.

Obwohl, wenn Du direkt mit Regulären Ausdrücken suchst, wäre das sehr viel einfacher. Nur wie ? - vielleicht so, allerdings etwas unscharf ? :

Süße  ->  S[uü]e?[sß][sz]?e

track