SEMINARARBEIT
Vergleich der Levenshtein-Distanz und des Bloomfilter-Algorithmus zur
Objektidentifizierung im Kontext des Forschungsprojekts MPI
(Massively Adhoc Processing in the Internet) Aktuelle Forschungsprojekte der
Wirtschaftsinformatik
vorgelegt von
Tobias Lindner www.tobiaslindner.eu
Mnchen, den 31. Mrz 2015
Hochschule fr angewandte Wissenschaften Mnchen Fakultt fr Informatik und Mathematik Masterstudiengang Wirtschaftsinformatik Erstprfer: Prof. Dr. Peter Mandl Betreuer: Dr. Nikolai Bauer
Alexander Dschl
Vergleich der Levenshtein-Distanz und des Bloomfilter-Algorithmus zur
Objektidentifizierung im Kontext des Forschungsprojekts MPI
Inhaltsverzeichnis
Seite II
Inhaltsverzeichnis
1 EINFHRUNG .......................................................................................................................... 1
1.1 EINLEITUNG UND MOTIVATION .................................................................................................... 1
1.2 DUPLIKATE UND DUPLIKATERKENNUNG ......................................................................................... 1
1.3 ERKENNUNGS- UND KONSOLIDIERUNGSPROZESS .............................................................................. 2
1.4 KLASSIFIZIERUNG VON DUPLIKATERKENNUNGSALGORITHMEN ............................................................. 2
2 AUFGABENSTELLUNG .............................................................................................................. 3
2.1 AUFGABENSTELLUNG UND ZIELSETZUNG ........................................................................................ 3
2.2 IMPLEMENTIERUNGS- UND TESTSZENARIO ...................................................................................... 3
3 LEVENSHTEIN-DISTANZ ........................................................................................................... 4
3.1 FUNKTIONSWEISE ..................................................................................................................... 4
3.2 EINFACHES BEISPIEL .................................................................................................................. 5
3.3 VARIANTEN DER IMPLEMENTIERUNG ............................................................................................. 5
4 BLOOMFILTER ......................................................................................................................... 6
4.1 FUNKTIONSWEISE ..................................................................................................................... 6
4.2 EINFACHES BEISPIEL .................................................................................................................. 7
4.3 VARIANTEN DER IMPLEMENTIERUNG ............................................................................................. 7
5 IMPLEMENTIERUNG ................................................................................................................ 8
5.1 LEVENSHTEIN-DISTANCE ............................................................................................................ 8
5.2 BLOOMFILTER ......................................................................................................................... 9
6 AUSWERTUNG ...................................................................................................................... 10
6.1 INFRASTRUKTUR UND KONFIGURATION ....................................................................................... 10
6.2 AUSFHRUNGSZEITEN ............................................................................................................. 10
6.3 TREFFERGENAUIGKEIT ............................................................................................................. 11
7 ZUSAMMENFASSUNG ........................................................................................................... 12
8 LITERATURVERZEICHNIS ........................................................................................................ 13
Vergleich der Levenshtein-Distanz und des Bloomfilter-Algorithmus zur
Objektidentifizierung im Kontext des Forschungsprojekts MPI
Einfhrung
Seite 1
1 Einfhrung
1.1 Einleitung und Motivation Die Zusammenfhrung von Daten aus unterschiedlichen Datenquellen (auch Deduplizierung genannt)
sowie die Bereinigung von inkonsistenten, redundanten, inkorrekten oder falsch formatierten Daten
wird immer hufiger zentraler Bestandteil von wissenschaftlichen und wirtschaftlichen IT-Projekten
(Bethlehem 2008; Schnell et al. 2009; Schnell 2010). Anwendungsszenarien sind beispielsweise die
Korrektur von Eingabefehlern, die Umformatierung von verschiedenen Schreibweisen, das Erkennen
und Auflsen von Abkrzungen, das Finden eines bestimmten Objekts in einer Objektmenge oder der
Abgleich und die anschlieende Zusammenfhrung von zwei bestehenden Datenbestnden. Die
meist automatisch ausgefhrten Verfahren, die dabei angewandt werden, werden als
Duplikaterkennung oder Objektidentifizierung bezeichnet.
Auch in der Musikbranche ist die Zuordnung einer musikalischen Nutzung (z.B. in Form von Musik-
Streaming-Diensten, Downloads, CD-Kufen, etc.) zu eindeutig identifizierbaren musikalischen
Werken und seinen Urhebern ein zentrales Problem. Dabei besteht die Herausforderung zum einen
darin, mglichst effizient und automatisch aus Nutzungen die betroffenen Werke eindeutig zu
identifizieren sowie zum anderen darin, den Datenbestand bekannter Werke laufend zu
aktualisieren. Vor diesem Hintergrund soll das konkrete Matching-Problem kurz nher spezifiziert
werden. Zudem sollen einfache Matching-Algorithmen auf Basis der Levenshtein-Distanz und des
Bloomfilters beispielhaft implementiert sowie deren Vor- und Nachteile, Ausfhrungs-
geschwindigkeiten und Treffergenauigkeiten verglichen werden.
1.2 Duplikate und Duplikaterkennung Mehrere verschiedene Datenstze, die dasselbe Objekt in der realen Welt reprsentieren, werden als
Dubletten oder Duplikate bezeichnet. Beispiele hierfr sind mehrfach gefhrte Kunden oder
Lieferanten in einem Managementsystem, verschiedene Reprsentationen eines Materials oder
Produkts oder aufgrund unterschiedlicher Schreibweisen doppelt aufgenommene Adressen in einer
Adressdatenbank. Unter Duplikaterkennung oder Objektidentifizierung werden die verschiedenen
Verfahren verstanden, um diese Duplikate innerhalb eines Datenbestandes zu identifizieren. Die
verschiedenen hierfr angewandten hnlichkeitsmae werden im Kapitel 1.4 Klassifizierung von
Duplikaterkennungsalgorithmen nher erlutert.
Generell muss laut (Apel et al. 2010, S. 166) zwischen zwei Arten von Duplikaten unterschieden
werden: identische Duplikate und nichtidentische Duplikate. Whrend bei identischen Duplikaten alle
Attribute bereinstimmen, weichen bei nichtidentischen Duplikaten ein oder mehrere Attributwerte
voneinander ab. Da im ersten Fall eine Konsolidierung nicht notwendig ist, ist sowohl die Erkennung
als auch die Bereinigung (einfache Lschung der berzhligen Datenstze ohne Informationsverlust)
trivial. Im zweiten Fall ist der Erkennungs- und Bereinigungsprozess weitaus komplexer, da zum einen
ein einfacher Ist-Gleich-Vergleich ber alle Attribute nicht ausreicht und zum anderen die
berzhligen Datenstze nicht einfach gelscht, sondern aufwndig konsolidiert werden mssen.
Vergleich der Levenshtein-Distanz und des Bloomfilter-Algorithmus zur
Objektidentifizierung im Kontext des Forschungsprojekts MPI
Einfhrung
Seite 2
1.3 Erkennungs- und Konsolidierungsprozess Nach (Apel et al. 2010, S. 166) verfolgen alle zur Duplikaterkennung eingesetzten Methoden zwei
Ziele: Effektivitt und Effizienz. Zum einen sollte das Ergebnis hochqualitativ sein die Menge an
richtig gefundenen Duplikaten sollte mglichst hoch sein. Zum anderen muss gleichzeitig die Anzahl
der verwendeten Vergleichsoperationen mglichst klein gehalten werden, um die Laufzeit auch bei
sehr groen Datenmengen niedrig zu halten.
Um den beiden Zielen Effektivitt und Effizienz gerecht zu werden, sollte der Prozess laut (Apel et al.
2010, S. 167 ff.) folgende vier Schritte umfassen:
1. Vorverarbeitung der Daten
2. Partitionierung der Datenstze
3. Erkennung von Duplikaten
4. Konsolidierung zu einem Datensatz
Eine detaillierte Beschreibung der einzelnen Prozessschritte wrde den Rahmen dieser Studienarbeit
bei weitem sprengen. Daher wird an dieser Stelle auf die ausfhrliche Literatur von (Apel et al. 2010)
verwiesen. Der Fokus der vorliegenden Arbeit liegt vielmehr in der Untersuchung bzw. im Vergleich
zweier Algorithmen zur Duplikaterkennung und lsst sich vor allem im 3. Schritt einordnen.
1.4 Klassifizierung von Duplikaterkennungsalgorithmen Vergleichsfunktionen bercksichtigen neben der quivalenz (also der semantischen Gleichheit) auch
die hnlichkeit (Grad der lexikalischen und syntaktischen Gleichheit) zweier Datenstze. Diese
Funktionen werden auch als hnlichkeitsmetrik bezeichnet und liefern als Ergebnis meistens eine
reelle Zahl zwischen 0 (keine hnlichkeit) und 1 (absolute Gleichheit). Meist werden zur Berechnung
der hnlichkeitsmetrik mehrere Attribute der zu vergleichenden Datenstze verwendet. Hierbei
muss vor allem auf den Datentyp (unterschiedliche Metriken fr Zeichen, Zahlen oder Datumswerte)
sowie die zugr
