| 

.NET C# Java Javascript Exception

7
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?
22.10.2009
ermin 1,3k 2 7
1
Hatte nen ähnlichen Anwendungsfall und habs dort mit Normalisierung gelößt. Eine Alternative würde mich aber auch interessieren.
Floyd 22.10.2009
4 Antworten
5
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:
mysql> SELECT SOUNDEX('Hello');
-> 'H400'
mysql> SELECT SOUNDEX('Quadratically');
-> 'Q36324'


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)
22.10.2009
DaSpors 4,1k 2 8
5
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, ...).
23.10.2009
fenchurch 611 5
4
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.
22.10.2009
gfoidl 9,4k 3 5
gfoidl 9,4k 3 5
4
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.
FalkP 23.10.2009
1
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 ;)
gfoidl 23.10.2009
1
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.
23.10.2009
tomahlak 237 1 2

Stelle deine .net-Frage jetzt!