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

möglichkeit für warscheinlichstes Suchergebnis

Beitragvon Damaskus » Dienstag 28. Februar 2006, 22:13

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

Beitragvon modelnine » Dienstag 28. Februar 2006, 22:55

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.
--- Heiko.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Re: möglichkeit für warscheinlichstes Suchergebnis

Beitragvon gerold » Dienstag 28. Februar 2006, 23:03

Damaskus hat geschrieben: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
:-)
Zuletzt geändert von gerold am Dienstag 28. Februar 2006, 23:20, insgesamt 2-mal geändert.
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Dienstag 28. Februar 2006, 23:04

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

Beitragvon modelnine » Dienstag 28. Februar 2006, 23:07

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

Beitragvon Damaskus » Dienstag 28. Februar 2006, 23:14

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
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Mittwoch 1. März 2006, 10:31

Damaskus hat geschrieben: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)

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
N317V
User
Beiträge: 504
Registriert: Freitag 8. April 2005, 13:23
Wohnort: München

Beitragvon N317V » Mittwoch 1. März 2006, 11:43

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

Wie man Fragen richtig stellt
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Mittwoch 1. März 2006, 11:54

N317V hat geschrieben: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?

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Beitragvon mawe » Mittwoch 1. März 2006, 11:58

jens hat geschrieben:Wie implementiert man den nun in Python?

Gar nicht, man besorgt sich den Code und verwendet ihn :)
Benutzeravatar
Damaskus
Administrator
Beiträge: 890
Registriert: Sonntag 6. März 2005, 20:08
Wohnort: Schwabenländle

Beitragvon Damaskus » Mittwoch 1. März 2006, 12:08

mawe hat geschrieben:
jens hat geschrieben: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
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Mittwoch 1. März 2006, 12:12

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 :(

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Benutzeravatar
Damaskus
Administrator
Beiträge: 890
Registriert: Sonntag 6. März 2005, 20:08
Wohnort: Schwabenländle

Beitragvon Damaskus » Mittwoch 1. März 2006, 12:19

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.
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Mittwoch 1. März 2006, 12:27

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 :P

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

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Benutzeravatar
Damaskus
Administrator
Beiträge: 890
Registriert: Sonntag 6. März 2005, 20:08
Wohnort: Schwabenländle

Beitragvon Damaskus » Mittwoch 1. März 2006, 12:39

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

Wer ist online?

Mitglieder in diesem Forum: /me, Bing [Bot]