möglichkeit für warscheinlichstes Suchergebnis

[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.

[Damaskus]

Also ich hab gestern mal mit SOUNDEX rumgespielt und die Ergebnisse waren schonmal nicht schlecht. Dazu jetzt noch ein paar Verknüpfungen und Filter mit einbauen und dann wirds für den Anfang reichen. Wie sich das dann bei Städten mit richtig vielen Straßen verhält muss ich halt mal ausprobieren.

[Mr_Snede]

Kann man nicht einen Spamfilter missbrauchen?
- von denen gibt es genug (auch mit python Anbindung)
- Doku / Beispiele sollten auch genug vorhanden sein

Ich hatte die Idee Bogofilter für ein (Web)Recherchetool zu verwenden.

cu Sebastian

[modelnine]

Du sprichst jetzt sicherlich von einem bayesschen Filter, oder nicht? Bayes-Filter "erkennen" Kontext, kein Wort was falsch geschrieben ist. Die Anwendungsgebiete sind völlig andere (zumindest im Normalfall).

[Damaskus]

Da der Link zu dem Soundex Modul nicht mehr aktuell ist gibts hier einen Link zu einer compilierten Win32 Version.

www.python-forum.de/downloads/Levenshtein.pyd

Gruß
Damaskus

[HWK]

Warum dann nicht get_close_matches aus dem Standardmodul difflib?
MfG
HWK

[rayo]

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

Wie nicht mit Strassen versehen?
Also Strassenname sind drin und Routen planen ist doch auch möglich oder?

Gruss

PS: map.google.com hab ich nur in der Schweiz gebraucht, nicht Deutschland.

[Trundle]

Wie nicht mit Strassen versehen?
Also Strassenname sind drin und Routen planen ist doch auch möglich oder?

Manchmal ist es recht hilfreich, sich einmal näher anzuschauen, wann der Beitrag erstellt wurde.

[rayo]

Ach immer das doofe ausgraben tja dann wars wohl nichts

Gruss

[Kai Borrmann]

Da der Link zu dem Soundex Modul nicht mehr aktuell ist gibts hier einen Link zu einer compilierten Win32 Version.

www.python-forum.de/downloads/Levenshtein.pyd

Gruß
Damaskus

Danke für den Tipp.

Nun habe ich sie in das Verzeichnis C:\Python25\Lib\site-packages runtergeladen.

Wie bekomme ich diese Datei dann zum Laufen?

Wenn ich draufklicke, kommt nur Buchstabensalat, es wird also wohl anders zu machen sein?

[Leonidas]

``import Levenshtein``

[OldBoy]

Hier 2 Loesungen in Standard-Python:

Code: Alles auswählen

def dist_lev(a, b):
    """
    Calculates the Levenshtein distance between a and b.
    Written by Magnus Lie Hetland (hetland.org)
    """
    n, m = len(a), len(b)
    if n > m:
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    dummy = [n] * (n+1)
    for i in range(1,m+1):
        previous =  current
        current = dummy[:]
        current[0] = i
        for j in range(1, n+1):
            add = previous[j]+1
            delete = current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]: change += 1
            current[j] = min(add, delete, change)
            
    return current[n]

def dist_ratio(a, b):
    s = difflib.SequenceMatcher(None, a, b)
    return s.ratio()

z.B.

Code: Alles auswählen

>>> a = 'Meier'
>>> b = 'Mayer'
>>> dist_lev(a,b)
2
>>> dist_ratio(a,b)
0.59999999999999998
>>> dist_lev(a,a)
0
>>> dist_ratio(a,a)
1.0

Noch ein paar Tipps:

• - vor dem Vergleich die Texte normalisieren
  (Gross-/Kleinschreibung, Sonderzeichen, Vereinheitlichung ( St/Str/Strasse))
  - bei langen Namen duerfen auch die Abweichungen groesser sein
  - anwendungsspezifische Sonderfaelle pruefen
  (z.B: Alleestr./Allerstr. in Essen, Iran/Irak bei Laendern)

Wer konkrete Hilfe braucht, kann sich gerne per PN an mich wenden. Ich habe dies Aufgabenstellung in den letzten Jahren intensiv im Bereich Laenderangabe/Region/Telefongesellschaft bearbeitet.

Gruss

OldBoy