möglichkeit für warscheinlichstes Suchergebnis

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Mittwoch 1. März 2006, 12:52

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/ :lol:

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Mittwoch 1. März 2006, 23:34

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.
--- Heiko.
N317V
User
Beiträge: 504
Registriert: Freitag 8. April 2005, 13:23
Wohnort: München

Donnerstag 2. März 2006, 08:27

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.
Es gibt für alles eine rationale Erklärung.
Außerdem gibt es eine irrationale.

Wie man Fragen richtig stellt
Benutzeravatar
Damaskus
Administrator
Beiträge: 919
Registriert: Sonntag 6. März 2005, 20:08
Wohnort: Schwabenländle

Samstag 4. März 2006, 18:42

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
User
Beiträge: 317
Registriert: Mittwoch 18. Januar 2006, 19:46

Sonntag 5. März 2006, 10:06

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.
Benutzeravatar
Damaskus
Administrator
Beiträge: 919
Registriert: Sonntag 6. März 2005, 20:08
Wohnort: Schwabenländle

Sonntag 5. März 2006, 10:15

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.
Benutzeravatar
Mr_Snede
User
Beiträge: 387
Registriert: Sonntag 8. Februar 2004, 16:02
Wohnort: D-Dorf, Bo

Sonntag 5. März 2006, 14:48

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
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Sonntag 5. März 2006, 15:24

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).
--- Heiko.
Benutzeravatar
Damaskus
Administrator
Beiträge: 919
Registriert: Sonntag 6. März 2005, 20:08
Wohnort: Schwabenländle

Donnerstag 20. März 2008, 14:55

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
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Donnerstag 20. März 2008, 18:41

Warum dann nicht get_close_matches aus dem Standardmodul difflib?
MfG
HWK
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Donnerstag 20. März 2008, 19:03

jens hat geschrieben: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.
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Donnerstag 20. März 2008, 19:11

rayo hat geschrieben: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
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Donnerstag 20. März 2008, 19:15

Ach immer das doofe ausgraben :) tja dann wars wohl nichts

Gruss
Benutzeravatar
Kai Borrmann
User
Beiträge: 29
Registriert: Sonntag 7. Januar 2007, 09:11
Wohnort: Berlin

Dienstag 13. Mai 2008, 03:45

Damaskus hat geschrieben: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?
Dr. Kai Borrmann
Sperlingsgasse 1
10178 Berlin
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 13. Mai 2008, 05:26

``import Levenshtein``
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten