Suche nach ähnlichen Datensätzen

[darton]

Hallo!
Ich hab folgendes Problem: Ich lasse von einem Programm mehrere Textdateien einlesen und davon sollen dann die einzelnen Datensätze in einer Datenbank gespeichert werden. Vorher soll allerdings überprüft werden, ob man quasi alles richtig geschrieben hat. Also, wenn irgendwo in der Datenbank ein Ort namens "Osnabrück" drinne steht, aber "Osnabrueck" als neuer Datensatz eingetragen werden soll, dann soll nachgefragt werden, ob man nicht "Osnabrück" gemeint hat (ähnlich wie bei Google). Wie macht man sowas? Mich interessiert jetzt erstmal nur der Algorithmus, unabhängig von einer Programmiersprache. Ich habe schon erst an den Hamming-Abstand gedacht, allerdings funktioniert der ja glaube ich nur, wenn die beiden Wörter gleich lang sind. Also wer weiß das?

 

[Madman1209]

Hi,

du kannst ja prüfen, ob ein Wert "LIKE" ein anderer bereits in der Datenbank bestehender Wert ist. Meine Glaskugel sagt, du nutzt MySQL. Lies dir die Beiträge einfach mal durch.

Reihenfolge:
1. Daten vorbereiten
2. Daten prüfen, ob "LIKE" einen Treffer hat
3. Wenn Treffer, dann nachfragen
3.1 Wenn bereits in DB, tue nichts
3.2 Wenn neu, füge hinzu

VG,
Mad

 

[darton]

OK, aber dann müsste ich ja eigentlich vorher wissen, mit welchen Wörtern ich vergleiche. Was ist denn, wenn weder "Osnabrück" noch "Osnabrueck" in der Datenbank vorhanden sind? Und wenn Osnabrück dann eingetragen wird, sieht der dann, dass noch nichts ähnliches drinne ist. Aber wenn "Osnabrueck" dann eingetragen werden soll, müsste der meckern. Genauso müsste der z.B. meckern bei "Ossnabrück" oder "Osnabrük". Man kann ja vorher nicht wissen, wo die Fehler sind.

 

[Madman1209]

Hi,

du hattest geschrieben es geht nur um den Algorithmus, also die Logik. Die habe ich dir aufgezeichnet.

1. Du hast den Datensatz, den du einfügen willst. Dieser hat von mir aus ein Feld "Stadt" mit dem Wert "Osnabrück".
2. Du lässt die "LIKE"-Abfrage über deine DB laufen. Wenn du mehr als 0 Datensätze zurückbekommst, gibts es bereits ähnliche Werte in der Datenbank. Diese kannst du dem Nutzer zur Auswahl geben. Wenn sich der Nutzer trotzdem entscheidet, den Datensatz einzufügen wird er eben neu dazugeschrieben. Wenn nicht dann eben nicht.
3. Hast du keine Ergebnisse bei der "LIKE"-Abfrage kannst du den Datensatz schreiben, da es keine Ähnlichekeiten in der Datenbank gibt.

VG,
Mad

 

[Revolution]

Für kleine Anwendungen wird das denke ich zu aufwändig. Selbst Google macht oft genug mist bei der Korrektur.

Ich würde dir empfehlen alles über die PLZ einzulesen und dann den Ortsnamen hinzuzufügen.

 

[ice-breaker]

sprachliche Ähnlichkeit:

• Kölner Phonetik
• Soundex (engl.)

Stringähnlichkeit:

• Dammerau-Levenshtein-Distanz

 

[darton]

Leider ist das Feld Ort nicht das einzige Feld, wo eine Funktionalität gebraucht wird, die Strings auf Ähnlichkeit überprüft. Ich hab mich nochmal ein bisschen schlau gemacht und herausgefunden, dass es die Levenshtein-Distanz gibt. Ich denke, ich werde es mal damit ausprobieren.

Edit: ice-breaker war schneller Aber besten Dank, werde mir auch mal die Kölner Phonetik und Soundex angucken.

 

[ice-breaker]

Du solltest auch die Dammerau-Levenshtein-Distanz statt der Dammerau-Distanz verwenden, denn bei der Dammerau-Levenshtein-Distanz ist ein Buchstabendreher nur eine Operation, bei der normalen Dammerau-Distanz sind es 2, für Buchstabendreher (Vertipper) hast du also eine höhere Wahrscheinlichkeit dies zu erkennen.