möglichkeit für warscheinlichstes Suchergebnis

[Damaskus]

Hi,
gibt es eine möglichkeit ein "warscheinliches" Suchergebnis zu bekommen.
Also wenn ein Suchbegriff nicht 100% übereinstimmt dann bräucht ich zumindest das nächstliegendste Ergebnis.
Zum Einsatz können SQLite oder Dict. kommen, Mysql und andere DB´s scheiden leider aus.

Hat da jemand eine Idee dazu oder muss ich mir da selbst was ausdenken?

Gruß
Damaskus

[modelnine]

Selber was ausdenken. Fuzzy searching ist alles andere als einfach. Soweit ich weiß hat MySQL einen Aufsatz mit dem sowas ähnliches geht, aber das ist super rechenintensiv. Am einfachsten dürfte es sein wenn Du nicht nach den ähnlichen Treffern für ein bestimmtes Wort suchst, sondern dem Benutzer anbietest auf ein anderes Suchwort zu schalten was ähnlich ist (genau wie Google es macht), und halt eine Liste von möglichen Suchwörtern vorhälst so dass nur noch in dieser Liste nach einem "Fuzzy-match" gesucht werden muß.

Siehe hierzu am besten (z.B. für Namen) sowas wie Soundex, oder ähnliche Dinge.

[gerold]

zumindest das nächstliegendste Ergebnis.
Zum Einsatz können SQLite

Hi Damaskus!

Ich kenne nur MS-SQL, mit dem ich so etwas öfter mache, aber ob SQLite damit klar kommt, das weiß ich noch nicht. Bei dem microsoftschen Datenbanksystem läuft das mit "soundex".

Ich habe im Cheese Shop etwas zu Levenshtein gefunden:

Gefunden:
http://www.sqlite.org/lang_expr.html
Suche nach "soundex".

Soundex vergleicht den Klang eines Wortes "Mair" und "Meier" klingen gleich, deshalb ist das Ergebnis beim Aufruf mit "soundex" gleich. Du musst also so arbeiten:
...
Where (soundex(nachname) = soundex("Mair"))

lg
Gerold

[modelnine]

Hab gerade mal im Netz ein bissel geschaut, und hab ein Tutorial für MySQL und PHP gefunden die genau den Weg gehen den ich vorgeschlagen habe:

http://codewalkers.com/tutorials/46/1.html

Vielleicht hilft Dir das weiter.

[modelnine]

Ich kenne nur MS-SQL, mit dem ich so etwas öfter mache, aber ob SQLite damit klar kommt, das weiß ich noch nicht. Bei dem microsoftschen Datenbanksystem läuft das mit "soundex".

Nur noch mal als kleine Anmerkung zu Soundex/Levenshtein (besonders Soundex): Beide Algorithmen in Ihrer normalen Anwendungsform (Levenshtein ist verallgemeinerbar, aber das mußt Du selbst rausfinden) sind auf englische Namen (also Personen-Nachnamen) ausgelegt, und werden in Amerika dazu benutzt um möglicherweise falsch geschriebene Daten für die Sozialversicherung ausfindig zu machen. Es sind keine Allround-Fuzzy-Searching Algorithmen, sondern um es noch mal zu wiederholen: sie sind auf eine sehr spezifische Domäne von Daten ausgelegt!

Bitte sie nicht allgemein benutzen (außer Du willst tatsächlich nur in Namen suchen), weil nämlich ganz und gar keine Ergebnisse rauskommen die Du haben willst wenn Du's auf andere Wörtern anwendest.

Update: Aus der vorher verlinkten Seite hab ich folgendes Zitat was das auch noch mal bekräftigt: "One alternative is the levenshtein() function which is much better performance wise when compared to the similar_text() function. The drawback is that levenshtein() produces results that are not quite as accurate as similar_text()."

Im Endeffekt ist similar_text sehr ähnlich wie das was difflib.get_close_matches aus der stdlib intern macht...

[Damaskus]

hmm....
ich wills für Straßennamen verwenden.
Ich werd mir mal Soundex bzw. den PHP weg anschauen.

Thx für die Antworten

Gruß
Damaskus

[jens]

hmm....
ich wills für Straßennamen verwenden.
Ich werd mir mal Soundex bzw. den PHP weg anschauen.

Thx für die Antworten

Gruß
Damaskus

Hm. Dann müßte man wahrscheinlich erstmal eine Datenbank aufbauen, die überhaupt den Sound von Buchstabenkombinationen festhält. Das ganze müßte man dann wohl für jede Sprache (deutsch, englisch ect.) haben... Ist schon recht aufwendig.

Vielleicht recht ja doch ehr eine SQL-LIKE Suche, wie ich gerade bei http://www.python-forum.de/viewtopic.php?p=32084#32084 geschrieben hab.
Man könnte es vielleicht auch so machen, das man die Suchwörter erst in Silben aufteilt und dann nach diesen Silben sucht. Um so mehr Silben gefunden wurde und um so näher diese zusammen hängen, um so mehr Punkte bekommt der Treffer. So könnte man eine Gewichtung erstellen... (War jetzt nur mal so ein Gedanke)

[N317V]

Nur noch mal als kleine Anmerkung zu Soundex/Levenshtein (besonders Soundex): Beide Algorithmen in Ihrer normalen Anwendungsform (Levenshtein ist verallgemeinerbar, aber das mußt Du selbst rausfinden) sind auf englische Namen (also Personen-Nachnamen) ausgelegt"

Kann ich nicht ganz nachvollziehen. In der PHP-Doku steht:

Die Levenshtein-Differenz ist definiert als die minimale Anzahl an Zeichen, die ersetzt, eingefügt oder gelöscht werden müssen um den str1 nach str2 umzusetzen.

Das ist doch vollkommen sprachunabhängig.

[jens]

Das ist doch vollkommen sprachunabhängig.

Das stimmt für die Levenshtein-Differenz schon, nicht jedoch für Soundex siehe: http://de.wikipedia.org/wiki/Soundex

Ist schon sehr Interessant. Aber auch vorstellbar, das ein Levenshtein-Differenz recht rechenaufwändig sein dürfte. Man müßte die Differenz von Suchbegriff zu jedem vorhandenen Wort bildern und das mit der gerinnsten Differenz wäre dann der beste Treffer...

Müßte man mal testen wie lange sowas dauern kann... Auf http://de.wikipedia.org/wiki/Levenshtein-Distanz ist auch der Algorithmus im Pseudocode:

Code: Alles auswählen

int LevenshteinDistance(char s[1..n], char t[1..m])
   declare int d[0..n,0..m]
   declare int i, j, cost
   for i := 0 to n
       d[i,0] := i
   for j := 0 to m
       d[0,j] := j
   for i := 1 to n
       for j := 1 to m
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i,j] := minimum(d[i-1,j  ] + 1,    // insertion
                             d[i,  j-1] + 1,    // deletion
                             d[i-1,j-1] + cost) // substitution
   return d[n,m]

Wie implementiert man den nun in Python?

[mawe]

Wie implementiert man den nun in Python?

Gar nicht, man besorgt sich den Code und verwendet ihn

[Damaskus]

Wie implementiert man den nun in Python?

Gar nicht, man besorgt sich den Code und verwendet ihn

Na das sieht doch richtig gut aus!
Ich werd mal die Performance und vorallem die Treffgenauigkeit testen und dann mal schauen obs was für mein Vorhaben taugt. Ich hab halt leider nur 30 Sekunden für die Ausführung des Programms Zeit. Danach sollte das Ergebnis feststehen.

Gruß
Damaskus

[jens]

Naja, 30Sek sind ja schon eine halbe Ewigkeit!
Wird es eine Web-Geschichte?

EDIT: Leider ist ja http://cheeseshop.python.org/pypi/python-Levenshtein eigentlich in C geschrieben

[Damaskus]

Nö.
Es soll Anfahrtspläne für Feuerwehren und DRK erstellen.
Der Straßenname + Hausnummer wird aus einer Funkmeldung entnommen (deshalb auch das Problem mit der Suche) und dann über ein Koordinaten System in einer Landkarte eingetragen. Und ab damit zum Drucker. Maximale Zeitspanne inkl. ausdruck sind 60 Sekunden. Ansonsten ist das gesamte Programm relativ nutzlos.

[jens]

Hm. Dann sind Straßenname und Hausnummer aber nicht wirklich eindeutig. Oft gibt es einen Namen in mehreren Stadteilen... Aber das hast du sicherlich bedacht

Dennoch interessant... Wäre es da aber nicht besser, wenn man ein Formular mit automatischer vervollständigung hat? Ähnlich die die Browser-URL-Zeile wenn man dort sachen eintippt...

[Damaskus]

Ein Formular bringt nichts da das ganze selbständig ablaufen sollte.
Das mit den gleichen Straßennamen hab ich mir auch schon überlegt, ist allerdings recht einfach zu lösen da die meisten in anderen Ortsteilen andere Schleifen alarmieren. Aber das größte Problem ist eh erstmal die realisierung des Koordinaten Systems und dem extrahieren der korrekten Straßennamen.

Wenn dazu noch jemand eine Idee hat... immer her damit

Gruß
Damaskus

[jens]

Da kann man sicherlich irgendwie Datensätze von kommerziellen Straßenkarten-Herstellen bekommen... Tja, oder du scannst verbotener weise Karten ein und makierst die koordinaten der Straßen, was viel arbeite sein dürfte

Theoretisch geht das auch mit Google-Maps, allerdings ist Deutschland noch nicht mit Strassen versehen...

btw.: http://de.wikipedia.org/wiki/Google_Maps und http://moon.google.com/

[modelnine]

Nur noch mal ganz kurz dazu dass der Levenshtein-Algorithmus unabhängig von der Sprache ist:

Ein Algorithmus um die Levenshtein-Distanz zweier Strings zu berechnen ist tatsächlich sprachunabhängig, ist aber nur in gewissem (relativ kleinen) maß ein Maß dafür wie verwandt die beiden Wörter sind in einer natürlichen Sprache.

Normalerweise wird aber nicht direkt eine Levenshtein-Distanz berechnet (bedenke zum Beispiel ä und ae Übereinstimmung, oder ähnliches), sondern wird zuerst eine Art Darstellung des Wortes in einer kondensierten Form gesucht (denn schließlich hat eine Sprache mit lateinischem Alphabet nur ungefähr 2.3 bit Entropie pro Byte), und auf den resultierenden String wird dann die Levenshtein-Distanz angewendet. Das ist sehr viel effektiver, und entspricht ungefähr eben dem Soundex-Algorithmus, und spart vor allen Dingen Rechenzeit, weil das Wort "komprimiert," also auch kürzer wird.

Ich hab bisher den Levenshtein-Algorithmus immer nur im Zusammenhang mit dieser "Komprimierung" gesehen (wenns darum ging Fuzzy-Searching zu machen). Und soweit ich das wußte war es bei PHP ganz genauso implementiert, ist es ja aber anscheinend nicht.

Im Endeffekt: wenn's darum geht sinnvoll einen Vergleich anzustellen wird man auf eine Art von Komprimierung nicht verzichten können, weil zum Beispiel:

Hämming
Hemming
Himming

bei diesen Namen der zweite Aufgrund der Aussprache näher zum ersten verwandt ist, jedoch die Levenshtein-Distanz zwischen zweitem und erstem, und drittem und erstem gleich ist.

Alle Algorithmen die eben so eine komprimierte Form berechnen sind sprachabhängig. Genau darauf wollte ich hinaus. Und erst mit solch einem Algorithmus macht Fuzzy matching Sinn. Und zumindest im meiner Erfahrung ist Levenshtein immer direkt mit so einem Algorithmus verbunden bei ernsthaften Anwendungen.

[N317V]

Hämming
Hemming
Himming

bei diesen Namen der zweite Aufgrund der Aussprache näher zum ersten verwandt ist

Gilt nicht für Niederbayern

Und erst mit solch einem Algorithmus macht Fuzzy matching Sinn.

Mag ja sein, aber ehrlich gesagt sehe ich Levenshtein und Soundex lieber getrennt und kombiniere sie selbst so wie ich es brauch, sofern ich es brauch. In PHP kann man da sehr schön alle Soundex-Matches per Levenshtein mit dem Original-Suchwort vergleichen um das ähnlichste Ergebnis zu bekommen. Da die Levenshtein-Funktion aber auf beliebige Strings anwendbar ist (z.B. "f0w0f47w3fjlkdjx"), macht eine vorgeschaltete Komprimierung auf die Aussprache u.U. aber gar keinen Sinn.

[Damaskus]

Hi,
ich will gerade das Levenshtein Modul ausprobieren, aber leider gibts das nicht für Python 2.4 auf einer Win32 Maschine sondern nur für Python 2.3, wie kann ich es auf 2.4 installieren?

Mfg
Damaskus

[Mad-Marty]

Ich könnte mir vorstellen wenn du die Strassennamen katalogiesierst,
das du da schon ähnliche namen verknüpfst, so das später die suche nach dem richtigen namen nicht mehr so aufwendig ist.

Evtl über den Anfangsbuchstaben eine vorauswahl treffen.