Über die Ähnlichkeit von Strings

Ein Problem beim Migrieren von Datenbanken ist das Sicherstellen, dass kein Element doppelt vorkommt. Wenn a) verschiedene Datenbank-Systeme beteiligt sind und b) eine Vielzahl von Personen, die die Daten eingeben, verspricht dies, ein interessantes Problem zu werden.

Konkretisieren wir das mal an einem Beispiel: In einer Bibliothek arbeiten Frau A und Herr B. Frau A verwaltet eine Liste von Schallplatten in Excel, Herr B nutzt eine kleine Access Anwendung. Da die beiden Listen auf eine einheitliche Datenbank migriert werden sollen, gilt es jetzt die beiden Listen, die jeweils nur den Namen der Schallplatte als Schlüssel nutzen, abzugleichen. Weder die Liste von Frau A noch die Liste von Herrn B ist vollständig, jede Schallplatte ist jedoch nur einmal vorhanden, rein manuelle Kontrolle scheidet aus da a) zuviele Schallplatten vorhanden sind und b) bei der Kontrolle selbst Fehler gemacht werden können. Ziel ist daher, zusätzlich zur manuellen Kontrolle eine Unterstützung zu suchen, die die wahrscheinlich identischen Einträge hervorhebt.

Mein erster Ansatz war, die beiden Listen zusammen in einem Excel-Sheet zu speichern und jeweils zu speichern, ob der Eintrag aus der Liste von Frau A oder Herrn B stammt. Dann wurde die Liste aufsteigend sortiert, das Ergebnis war, dass von zwei Einträgen, die sich nur am Ende unterscheiden, der kürzere Eintrag vor dem längeren steht.

  • Sinead O’Connor – I Do Not Want What I Haven’t Got
  • Sinead O’Connor – I Do Not Want What I Haven’t Got (Single)

Der nächste Schritt war dann für jede Zelle zu entscheiden, ob der Zellinhalt Teil der darauffolgenden Zelle war. Dazu wurde die Finden() Funktion von Excel genutzt.

  • Sinead O’Connor – I Do Not Want What I Haven’t Got
  • Sinead O’Connor – I Do Not Want What I Haven’t Got (Single)

Einen Großteil der doppelten Einträge kann man auf diese Weise abdecken, doch versagt er bei geringsten Schreibfehlern, wie dem folgenden:

  • Sinead O’Connor – I Do Not Want What I Haven’t Got
  • Sinead OConnor – I Do Not Want What I Haven’t Got (Single)

Diese lassen sich per zeichenweisem Vergleich ermitteln. Sauber wäre eine Lösung die nur die tatsächlichen Längen berücksichtigt, als ersten Wurf habe ich jedoch einfach die Zeichen 1 bis 15 miteinander verglichen (Formel wird nachgeliefert).

Dann zählt man einfach die Anzahl der Zeichen, die unterschiedlich sind, bei geringen Abweichungen ist die Wahrscheinlichkeit hoch, einen identischen Eintrag zu haben. Eine Erweiterung dieses Konzept ist die sogenannte Levenshtein-Distanz, die ich über ein R Skript berechnen lasse.

Der Wert der Levenshtein-Distanz gibt dabei an, wieviele Zeichen man minimal ändern muss, um von String A auf String B zu kommen. Für die beiden Zeichenketten „Hello“ und „Hallo“ ist der Wert daher 1.

Über ein kurzes R-Skript lese ich die Plattennamen ein und mache jeweils einen paarweisen Vergleich, der R-Code für die Levenshtein Distanz entstammt dem R-Wiki http://wiki.r-project.org/rwiki/doku.php?id=tips:data-strings:levenshtein

data<-readLines("c:/music_names.dat")
y<-length(data)
result<-1:y
 
for(i in 2:y){
	result[i]<-levenshtein(data[i],data[i-1],case=FALSE) 
}
write.table(result, "C:/result.dat")

Den result-Vektor können wir dann in das Excel-Sheet einfügen.

Uwe

Uwe Ziegenhagen likes LaTeX and Python, sometimes even combined. Do you like my content and would like to thank me for it? Consider making a small donation to my local fablab, the Dingfabrik Köln. Details on how to donate can be found here Spenden für die Dingfabrik.

More Posts - Website