Ich muss aus einer Datenbank Koordinaten von Haltestellen holen. Das Problem sind die Namen der Haltestellen. So beziehen sich "Berlin Hauptbahnhof", "Berlin Hbf", "Hbf Berlin",... alle auf die selbe Haltestelle, und verschiedene Systeme benutzen verschidenen dieser Namen.
Das Problem könnte man doch am einfachsten mit einem String-Ähnlichkeits-Vergleich lösen. Alson einfach die zu 5 ähnlichsten Strings zu "Berlin Hauptbahnhof" auswählen, und die mit der geringsten Entferung zur Position des Nutzers wählen.
Welchen Algorithmus zur Berechnung der Ähnlichkeit der Strings könnte ich nehmen?
In Deinem Fall ist es mit einem Ähnlichkeits-Vergleich leider nicht getan, da ja auch Abkürzungen erkannt werden sollen. Es gibt für MySQL die Möglichkeit SOUNDEX zu verwenden, aber das liefert nicht soo dolle Ergebnisse. Aus der MySQL Doku:
Wenn Du von SQL absiehst, dann müsstest Du die Ergebnisse nachfiltern. Da gibt es verschiedene Algorithmen. Vielleicht klappt bei Dir ja das mit dern Levenshtein-Distanz. Du solltest aber auf jeden Fall darüber nachdenken, den Suchalgorithmus 'lernfähig' zu machen, damit er mit der Zeit erkennt, dass 'Hbf' == 'Hauptbahnhof' ist. Dazu auch noch ein Link: Duplikaterkennung
Folgender Vorschlag:
text1 = 'Berlin Hbf' text2 = 'Berlin Hautbahnhof' Wenn GleichheitSchonmalBestätigt(text1,text2) dann Fertig()
token1 = Token aus text1 token2 = Token aus text2 fast = 0 Für alle t1 in token 1 Für alle t2 in token2 Wenn IstAehnlich(t1,t2) dann fast = 1
Wenn fast = 1 dann Wenn FrageUserObGleich(text1,text2) dann MerkeDassGleich(text1,text2)
Mein Lieblingsähnlichkeitsalgorithmus ist die Trigramm-Methode. Sie ist für ein Trigramm-Perlmodul hier beschrieben. Ob es entsprechende Libraries für Java gibt, weiß ich nicht, das ganze wäre aber auch nicht besonders schwer zu programmieren.
Wenn du deine Datenbasis über Lucene zugänglich machst, bekommst du eine Fuzzysuche schon mitgeliefert. Die basiert glaube ich auf Levenshtein, da Lucene aber gut erweiterbar ist, könnte man auch andere Algorithmen implementieren.
Welchen Algorithmus man auch immer nimmt, eine vorherige Normalisierung empfiehlt sich auf jeden Fall (alles in Kleinbuchstaben umwandeln, Umlaute etc. normalisieren, evtl. Leerzeichen entfernen, ...).
Wie bereits von DaSpors erwähnt wäre die Levenshtein-Distanz eine Lösung. Dies kann dann als Fuzzy-Suche implementiert werden. Eine Implementierung dessen in C# gibt hier.
Ein komplett anderer Ansatz der mir einfällt wäre einen Assoziativspeicher mittels neuronalem Netz zu erstellen. Habs nicht probiert kann mir aber gut vorstellen dass das geht - ähnlich wie Kohonen's WebSOM. Dadurch sollte es bei korrekter Implementierung auch möglich sein Berlin Hbf und Hbf Berlin dem selben Ausgangsmerkmal zuzuordnen.
Um "Berlin Hbf" und "Hbf Berlin" als gleich zu erkennen muss man kein neuronales Netz bemühen. Hier genügt es den String jeweils anhand bestimmter Trenner (Leerzeichen, Bindestrich, Komma, ...) in Teilstrings zu zerlegen und diese Teilstrings dann in eine eindeutige und nachvollziehbare (z.B. alphabetische) Reihenfolge zu bringen, wieder zu verketten und dann erst zu vergleichen. Das Ganze noch mit Levenshtein kombiniert sollte schon ganz brauchbare Ergebnisse bringen.
Sicherlich wäre es praktischer diese Transformation im Zuge des Normalisierens durchzuführen wie von dir beschrieben.
Das ANN stellt eine Alternative dar mit der in diesem Zuge auch eine "kontextbasierte" Suche ermöglicht wird. Das wird in diesem Fall vermutlich nicht nötig sein, aber es ist möglich ;)
Wenn die Anzahl der eingabefähigen Haltestellen bekannt ist und auch die Strings die tatsächlich verwendet werden, ist es vielleicht performanter eine Thesaurus-Tabelle in der Datenbank zu basteln, deinen Eingabestring auf lowercase und ohne leer- und sonderzeichen zu formatieren und das mit einem SQL-Statement abzufackeln. Der Thesaurus mappt dann auf die korrekte Bezeichnung.
Der Aufwand besteht dann aber in der Thesauruspflege. GGf. hat deine Datenbank aber schon eine Thesaurierungsfunktion dabei. Dann eben diese.
Würde ich aber nur machen, wenn ich keine freien Benutzereingaben verarbeiten muss, sondern quasi statische Strings.