Edit Distance für Listen

Lange Listen und zu große Dateien!

Bei der Recherche zu einem Thema passiert eigentlich routinemäßig mindestens eins der beiden Dinge und bringt den Prozess unnötig, durch rein technisch schwer verarbeitbare Informationen, ins stocken.

Um der Flut an Daten Herr zu werden, schreibe ich schon geraume Zeit meine eigenen Tools, da im konkreten Fall meist gerade nicht das passende Tool zur Verfügung steht.

So hatte ich vor kurzem wieder den Fall, dass ich in zwei lange Listen von Unternehmensnamen prüfen wollte, ob Unternehmen aus Liste A in Liste B vorkommen. Natürlich schreibt im Internet jeder wie er will. Das ist nichts neues.

Das heißt dann aber, dass z.B. Unternehmensname GmbH nicht mit einem einfachen Abgleich mit Unternehmensname G.m.b.H oder sogar nur Unternehmensname gematcht würde, was aber eigentlich gewünscht ist.

Zum Glück gibt es allerdings einen bekannten Algorithmus, mit dem man Listen auch auf Ähnlichkeit basierend überprüfen kann. Der Editierabstand oder Edit Distance oder auch Levenshtein Distanz genannt. Verschiedene Implementationen im Internet stehen zur Verfügung, aber nicht genau mit der Ausrichtung in der ich sie benötigt habe. Von Online-Tool nehme ich in solch einem Fall eh eher Abstand , da ich nicht sicher sein kann, was im Hintergrund genau mit den Daten passiert.

Genau für meinen Fall habe ich als so ein kleines Kommandozeilentool geschrieben, dass ich hier gerne teilen.

Levenshtein für den Listenvergleich

Das Tool macht nichts anderes als zwei Listen, die in Form einer CSV-Datei übergeben werden, gegeneinander mittels der Levenshtein-Distanz zu überprüfen und die Ähnlichkeit von Listeneinträgen aus A zu Einträgen aus B in strukturierte Form wieder auszugeben.

Das Tool könnt ihr am Ende der Seite herunterladen.

Ihr braucht nur eine CSV-Datei anlegen. Die ersten beiden Spalten beinhalten die beiden Listen, die ihr gegeneinander prüfen wollt. In der dritten Spalte stehen Zeichenketten, die beim Vergleich ignoriert werden sollen. Diese Liste kann auch leer sein.

Wenn ihr diese Datei in z.B. Excel nun als CSV-Datei speichert, sollte das Resultat im Texteditor ungefähr so aussehen. Zu beachten ist, dass das Programm als Trennzeichen der Spalten ein Semikolon “;” erwartet

Nun könnt ihr das Programm mit den folgenden Parametern starten:

 EditDistanceListen.exe PFAD_ZUR_CSV_DATEI MAXIMALER_EDITIERABSTAND 

>EditDistanceListen.exe test_ignore.csv 4

Neben dem Output auf der Konsole produziert das Programm zugleich eine CSV-Datei result.csv (s.u.) im gleichen Ordner wie das Programm (Achtung! wird momentan noch überschrieben) und versucht diese auch gleich zu öffnen.

Hier könnt ihr das kleine Tool herunterladen (Prüfsummen am Ende!)

Algorithm : SHA256
Hash      : 3562D83FC191F10AD6BDDCFEBEE7DD2687400B031A76A981423C20F26802B9A2
File      : EditDistanceListen.exe

Algorithm : SHA256
Hash      : 56ABE877593448D3F60BBADF917824AA2FA1636635A91A782708D1743F9CE65F
File      : EditDistanceListen.zip