Fehlertolerante Suche
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
abgleich
akzent
algorithmus
buchstabe
eigene funktionen
einsatz
entfernen
erfinden
funktion
http
internet
manko
match
rad
riesige datenbank
suche
text
umlaut
url
wort
-
Seit geraumer Zeit durchforste ich das Internet nach einer Lösung zur fehlertoleranten Suche in deutschen Datensätzen. Geplant ist ein Einsatz unter PHP und MySQL, allerdings gebe ich mich auch mit einem Algorithmus zufrieden, den ich dann selbst dorthin portiere. PHP-eigene Funktionen wie soundex, metaphone oder Ähnlichkeitsberechnungen nach Levenshtein sind unzureichend, da nur Wortdifferenzen oder v. a. anglophile Worte geprüft werden.
Bislang beschränken sich meine Ansätze auf das Entfernen von Umlauten oder Akzenten, die eigentliche "Fuzz-Logic" fehlt. Ich muß das Rad nicht neu erfinden, gerne greife ich auf vorhandene Codes zurück, nur möchte ich keine Funktion kaufen. Erstrebenswert ist eine Lösung, die keine riesige Datenbank mit Grundbegriffen zum Abgleich benötigt, wobei ein solches Manko noch verschmerzlich wäre. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Naja wenn jemand eine gut funktionierende Möglichkeit gefunden hat wird die nicht so einfach irgendwo stehen. Levenshtein und auch die späteren Ergänzungen sind einfach der Grundsatz nach dem fast alles funktioniert. Ich kenne keine Fuzzylogik ohne große Datenbank, die auf einer anderen Sache fußt.
Damerau-Levenstein ist noch etwas genauer, aber ich weiß nicht auf welcher Basis du das sonst machen willst. Das ist wie der Name schon sagt eine unscharfe Suche, dass heißt Fehlmeldungen oder aber nicht gemeldete, aber richtige Ergebnisse sind unumgänglich und man kann nur den optimalen Weg finden, indem man an größeren Datensätzen die Parameter anpasst und dann per Hand den Algorithmus trainiert. -
althaus schrieb:
Seit geraumer Zeit durchforste ich das Internet nach einer Lösung zur fehlertoleranten Suche in deutschen Datensätzen. Geplant ist ein Einsatz unter PHP und MySQL, allerdings gebe ich mich auch mit einem Algorithmus zufrieden, den ich dann selbst dorthin portiere.
Ein funktionierender (allerdings etwas aufweniger) Ansatz ist die Suche nach n-grammen (Wortteilen mit maximal n Buchstaben). Am häufigsten werden Trigramme verwendet:
http://www.google.de/search?num=20&hl=de&safe=off&q=unscharfe+suche+fuzzy+trigramm&btnG=Suche
Die c't hatte vor längerer Zeit einen interessanten Artikel dazu (mit Quellcode in C):
http://www.heise.de/kiosk/archiv/ct/1997/4/386_kiosk
Etwas Theorie dazu gibts kostenfrei bspw. hier:
http://www.fask.uni-mainz.de/user/rapp/papers/disshtml/main/node76.html
PHP-eigene Funktionen wie soundex, metaphone oder Ähnlichkeitsberechnungen nach Levenshtein sind unzureichend, da nur Wortdifferenzen oder v. a. anglophile Worte geprüft werden.
Bislang beschränken sich meine Ansätze auf das Entfernen von Umlauten oder Akzenten, die eigentliche "Fuzz-Logic" fehlt. Ich muß das Rad nicht neu erfinden, gerne greife ich auf vorhandene Codes zurück, nur möchte ich keine Funktion kaufen. Erstrebenswert ist eine Lösung, die keine riesige Datenbank mit Grundbegriffen zum Abgleich benötigt, wobei ein solches Manko noch verschmerzlich wäre.
Suchmaschinen greifen auf diverse Mechanismen wie Stemming zurück, um ähnliche Worte anzugleichen. Die sind aber komplizierter zu implementieren als die Trigramm-Suche und sind darüber hinaus oft von der verwendeten Sprache abhängig.
Ein Beispiel (da ist auch 'ne PHP-Implementierung dabei):
http://tartarus.org/~martin/PorterStemmer/
Was das Eindampfen der Buchstaben aufs lateinische Alphabet angeht, habe ich (für meine Zwecke) gute Erfahrungen mit dem Perl-Modul Text::Unidecode gemacht, welches ich nach PHP "portiert" habe. Die Hauptarbeit steckt dort nicht im Code sondern in den Dekodiertabellen. Das Ergebnis kann man hier bewundern:
http://execbase.de/yano.php?name=%E5%87%AF%E5%85%B0&name=Kai-lan&q=match+names
Das klappt auch bei der Verwendung von zwei nichtlateinischen Kodierungen:
http://execbase.de/yano.php?name=%E5%8C%97%E4%BA%AC&name=%D0%91%D1%8D%D0%B9%D1%86%D0%B7%D0%B8%D0%BD&q=match+names
Erschreckend -- aber ist ja auch nicht auf meinem Mist gewachsen.
Beitrag zuletzt geändert: 25.10.2010 23:38:40 von alopex -
Danke für die (bisherigen) Antworten. Grundsätzlich habe ich nichts gegen eine größere Datenbank, ggf. eine, die sich selbst erweitert, z.B. Zuordnungen von verwendeten Suchbegriffen, die (teil-) automatisch auch bei Rechtschreibfehlern hinterlegt werden.
Verständlich ist, daß Firmen, die eben solche Technologien anbieten, dafür bezahlt werden wollen. Dennoch stellt sich mir die Frage, ob jemand ein Open Source-/Freeware-Projekt kennt, welches zumindest schon die grundlegende Implementation erleichtert und von Beteiligungen lebt. Trotz meines deutlichen Augenmerks auf dieses Thema scheue ich nämlich den Aufwand, eine eigene (Insel-) Lösung aufzustellen.
VG -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
