Vergleich der Levenshtein-Distanz und des Bloomfilter … · 2019-10-30 · Vergleich der Levenshtein-Distanz und des Bloomfilter-Algorithmus zur Objektidentifizierung im Kontext

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

München, den 31. März 2015

Hochschule für angewandte Wissenschaften München Fakultät für Informatik und Mathematik Masterstudiengang Wirtschaftsinformatik Erstprüfer: Prof. Dr. Peter Mandl Betreuer: Dr. Nikolai Bauer

Alexander Döschl



Inhaltsverzeichnis

Seite II

Inhaltsverzeichnis

1 EINFÜHRUNG .......................................................................................................................... 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 AUSFÜHRUNGSZEITEN ............................................................................................................. 10

6.3 TREFFERGENAUIGKEIT ............................................................................................................. 11

7 ZUSAMMENFASSUNG ........................................................................................................... 12

8 LITERATURVERZEICHNIS ........................................................................................................ 13



Einführung

Seite 1

1 Einführung

1.1 Einleitung und Motivation Die Zusammenführung von Daten aus unterschiedlichen Datenquellen (auch Deduplizierung genannt)

sowie die Bereinigung von inkonsistenten, redundanten, inkorrekten oder falsch formatierten Daten

wird immer häufiger 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 Auflösen von Abkürzungen, das Finden eines bestimmten Objekts in einer Objektmenge oder der

Abgleich und die anschließende Zusammenführung von zwei bestehenden Datenbeständen. Die

meist automatisch ausgeführten 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-Käufen, etc.) zu eindeutig identifizierbaren musikalischen

Werken und seinen Urhebern ein zentrales Problem. Dabei besteht die Herausforderung zum einen

darin, möglichst 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 näher spezifiziert

werden. Zudem sollen einfache Matching-Algorithmen auf Basis der Levenshtein-Distanz und des

Bloomfilters beispielhaft implementiert sowie deren Vor- und Nachteile, Ausführungs-

geschwindigkeiten und Treffergenauigkeiten verglichen werden.

1.2 Duplikate und Duplikaterkennung Mehrere verschiedene Datensätze, die dasselbe Objekt in der realen Welt repräsentieren, werden als

Dubletten oder Duplikate bezeichnet. Beispiele hierfür sind mehrfach geführte Kunden oder

Lieferanten in einem Managementsystem, verschiedene Repräsentationen 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 hierfür angewandten Ähnlichkeitsmaße werden im Kapitel 1.4 Klassifizierung von

Duplikaterkennungsalgorithmen näher erläutert.

Generell muss laut (Apel et al. 2010, S. 166) zwischen zwei Arten von Duplikaten unterschieden

werden: identische Duplikate und nichtidentische Duplikate. Während 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 Löschung der überzähligen Datensätze 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

überzähligen Datensätze nicht einfach gelöscht, sondern aufwändig konsolidiert werden müssen.



Einführung

Seite 2

1.3 Erkennungs- und Konsolidierungsprozess Nach (Apel et al. 2010, S. 166) verfolgen alle zur Duplikaterkennung eingesetzten Methoden zwei

Ziele: Effektivität und Effizienz. Zum einen sollte das Ergebnis hochqualitativ sein – die Menge an

richtig gefundenen Duplikaten sollte möglichst hoch sein. Zum anderen muss gleichzeitig die Anzahl

der verwendeten Vergleichsoperationen möglichst klein gehalten werden, um die Laufzeit auch bei

sehr großen Datenmengen niedrig zu halten.

Um den beiden Zielen Effektivität 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 Datensätze

3. Erkennung von Duplikaten

4. Konsolidierung zu einem Datensatz

Eine detaillierte Beschreibung der einzelnen Prozessschritte würde den Rahmen dieser Studienarbeit

bei weitem sprengen. Daher wird an dieser Stelle auf die ausführliche 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 lässt sich vor allem im 3. Schritt einordnen.

1.4 Klassifizierung von Duplikaterkennungsalgorithmen Vergleichsfunktionen berücksichtigen neben der Äquivalenz (also der semantischen Gleichheit) auch

die Ähnlichkeit (Grad der lexikalischen und syntaktischen Gleichheit) zweier Datensätze. 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 Datensätze verwendet. Hierbei

muss vor allem auf den Datentyp (unterschiedliche Metriken für Zeichen, Zahlen oder Datumswerte)

sowie die zugrundeliegende Sprache (länder- und sprachspezifische Eigenschaften) der einzelnen

Attribute geachtet werden. Nachfolgend werden einige Ansätze zur Ähnlichkeitsbestimmung kurz

dargestellt. Eine detaillierte Übersicht ist in den Vorlesungsunterlagen von Felix Naumann vom

Hasso Plattner Institut der Universität Potsdam (Naumann, S. 28 ff.) zu finden. Für eine ausführliche

Beschreibungen der einzelnen Metriken wird auf (Apel et al. 2010, S. 175 ff.) sowie auf (Naumann,

Herschel 2010, S. 23 ff.) verwiesen.

Phonetische Metriken. Die Ähnlichkeit wird über die Distanz bei der Aussprache des Textes bestimmt

und eignet sich daher vor allem für über das Gehör aufgenommene und anschließend eingegebene

Attribute. Eine Bewertung von Tippfehlern ist jedoch nicht möglich. Weit verbreitet sind der

Soundex-Algorithmus1 und die besser auf die deutsche Sprache abgestimmte Kölner Phonetik2.

Filter-basierte/Hash-basierte Metriken. Bloomfilter3 in den verschiedensten Varianten und

Erweiterungen fallen beispielsweise in diese Kategorie.

Domänenspezifische Metriken. Hierzu zählen Algorithmen zur Ähnlichkeitsbestimmung von

regelbasierten und numerischen Werten sowie Datumswerten.

1 http://de.wikipedia.org/wiki/Soundex, Zugriff: 12.02.2015

2 http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik, Zugriff: 12.02.2015

3 http://de.wikipedia.org/wiki/Bloomfilter, Zugriff: 12.02.2015



Aufgabenstellung

Seite 3

Distanz-basierte Metriken. Bei Distanz-basierten Metriken erfolgt die Ermittlung der Ähnlichkeit

durch den buchstabenweisen Vergleich zweier Zeichenketten. Da unterschiedliche Wortreihenfolgen

zu sehr unrealistischen Werten führen können, eignen sich diese Metriken vor allem zum Vergleich

von einzelnen Wörtern. Eingesetzt werden häufig die Levenshtein-Distanz4 oder der Jaro-Winkler-

Algorithmus5.

Token-basierte Metriken. Token-basierte Metriken sind mit den Distanz-basierten Metriken

verwandt, eignen sich jedoch vor allem für den Vergleich von Zeichenketten mit mehreren Wörtern.

Hierbei wird die Zeichenkette zunächst in einzelne Token aufgeteilt und anschließend verglichen, wie

viele Token die zu vergleichenden Zeichenketten gemeinsam haben. Die Aufteilung kann dabei nach

vorgegebenen Trennzeichen (z.B. Leerzeichen oder Satzzeichen) oder nach festen Intervallen (z.B.

Bildung von Buchstaben-Pärchen) erfolgen. Häufig eingesetzt werden n-Gramme6 bzw. die

Erweiterung q-Gramme.

2 Aufgabenstellung

2.1 Aufgabenstellung und Zielsetzung Wie bereits in der Einleitung kurz erläutert, besteht die zentrale Herausforderung in der

Musikbranche darin, musikalische Nutzungen möglichst effizient und automatisch eindeutig

identifizierbaren Werken und seinen Urhebern zuzuordnen.

Vor diesem Hintergrund sollen die Ansätze der beiden Matching-Verfahren „Levenshtein-Distanz“

und „Bloomfilter“ zunächst näher untersucht und anschließend prototypisch implementiert werden.

Dadurch sollen sowohl die verschiedenen Funktionsweisen und Einsatzmöglichkeiten als auch

Potenziale und Herausforderungen der Algorithmen kurz aufgezeigt werden.

Darüber hinaus sollen die Messergebnisse bzgl. der Ausführungsgeschwindigkeiten und

Treffergenauigkeiten erste Erkenntnisse darüber liefern, ob die Implementierung eines Bloomfilters

eine sinnvolle Ergänzung oder Alternative für den derzeit von der GEMA eingesetzten Levenshtein-

Distanz-Algorithmus darstellt.

2.2 Implementierungs- und Testszenario Um die Ausführungsgeschwindigkeiten und Treffergenauigkeiten der beiden oben genannten

Verfahren vergleichen zu können, werden für diese zwei einfache Prototypen im Oracle-Umfeld als

Funktionen in PL/SQL implementiert und anschließend Messungen bei der Nutzung der Algorithmen

durchgeführt.

Um ein möglichst authentisches Test-Umfeld sowie möglichst aussagekräftige Messergebnisse zu

erhalten, wird zunächst ein kleiner, 10.000 Datensätze umfassender Referenzdatenbestand über

musikalische Werke und seine Urheber aufgebaut. Hierzu werden aus einer originalen DDEX-Datei

von Spotify Premium aus dem Jahre 2013 die notwendigen Informationen (Artisten und Titel des

Liedes) extrahiert und in einer Oracle-Datenbank gespeichert.

4 http://de.wikipedia.org/wiki/Levenshtein-Distanz, Zugriff: 12.02.2015

5 http://en.wikipedia.org/wiki/Jaro-Winkler_distance, Zugriff: 12.02.2015

6 http://de.wikipedia.org/wiki/N-Gramm, Zugriff: 12.02.2015



Levenshtein-Distanz

Seite 4

Um die Ausführungsgeschwindigkeiten und Treffergenauigkeiten der beiden implementierten

Algorithmen messen zu können, wird zusätzlich ein 100 Datensätze umfassender Testdatenbestand

aufgebaut. Dieser besteht aus 100 zufällig ausgewählten Datensätzen des Referenzdatenbestandes.

Um Abweichungen zu generieren, wird jeder Datensatz des Testdatenbestands manuell um eine oder

mehrere der nachfolgend genannten Eigenschaften verändert:

Einbau von Schreibfehlern/Buchstabendrehern/etc.

Hinzufügen oder Entfernen einzelner Wörter bei Artisten oder Liedtitel

z.B.: „(Live)“, „(Digital Remaster)“ oder „(Radio Edition)“

Vertauschen des Vor- und Nachnamens des Artisten

Vertauschen der Reihenfolge bei mehreren Artisten

Vertauschen von Artist und Liedtitel

z.B.: „ABBA - Dancing Queen“ wird zu „Dancing Queen by ABBA“

Suchen des Liedtitels bei YouTube und Übernahme der Schreibweise des hochgeladenen

Videos (dadurch authentischere Testdaten)

3 Levenshtein-Distanz

3.1 Funktionsweise Der Levenshtein-Algorithmus berechnet die Mindestanzahl von Einfüge-, Lösch- und Ersetz-

Operationen, um eine bestimmte gegebene Zeichenkette in eine zweite, ebenfalls gegebene

Zeichenkette umzuwandeln. Die Anzahl der notwendigen Editieroperationen wird dabei als

Levenshtein-Distanz oder auch als Editierdistanz bezeichnet. Benannt wurde die Levenshtein-Distanz

nach dem russischen Mathematiker und Wissenschaftler Wladimir Lewenstein, der diese 1965 erfand

und hierfür 2006 die Richard-W.-Hamming-Medaille für außergewöhnliche Leistungen in der

Informationstechnik des IEEE erhielt (Hamming). Anwendung findet die Levenshtein-Distanz

hauptsächlich zur Ähnlichkeitsbestimmung von Zeichenketten, u.a. bei der Duplikaterkennung oder

zur Rechtschreibprüfung. Im Original-Artikel (Levenshtein, 1965) wird zwar die Funktionsweise der

Levenshtein-Distanz auf theoretischer und mathematischer Basis definiert, jedoch kein Algorithmus

für die Distanz-Berechnung angegeben. Die Implementierung des Algorithmus erfolgt meist nach

dem Prinzip der dynamischen Programmierung (Bellman, 1957), einer Methode zum algorithmischen

Lösen von Optimierungsproblemen:

Zunächst wird eine zweidimensionale Matrix erstellt. Anschließend wird für jede (m,n)-Zelle die

Levenshtein-Distanz zwischen dem m-ten Buchstaben des ersten Wortes und dem n-ten Buchstaben

des zweiten Wortes errechnet. Meist wird diese Matrix bzw. Tabelle von der oberen linken zur

unteren rechten Ecke gefüllt. Jeder horizontale, vertikale oder diagonale Sprung von einer Zelle zur

nächsten entspricht dabei einer Editieroperation und wird mit virtuellen Kosten versehen.

Horizontale und vertikale Sprünge entsprechen Einfüge- oder Löschoperationen, für die

normalerweise Kosten von „1“ angesetzt werden. Ein diagonaler Sprung wird für den Fall, dass der

m-te und n-te Buchstabe übereinstimmt mit „0“, andernfalls mit „1“ berechnet. Da jede Zelle jeweils

den lokalen Aufwand minimiert, entspricht die Zahl in der rechten unteren Ecke der Levenshtein-

Distanz der beiden Wörter. Im nachfolgenden Kapitel wird dieses Vorgehen mit einem einfachen

Beispiel visuell verdeutlicht.



Levenshtein-Distanz

Seite 5

3.2 Einfaches Beispiel Die nachfolgende Matrix zeigt die Berechnung der Levenshtein-Distanz mit den beiden Wörtern

„Meilenstein“ und „Levenshtein“:

M e i l e n s t e i n

0 1 2 3 4 5 6 7 8 9 10 11

L 1 1 2 3 3 4 5 6 7 8 9 10

e 2 2 1 2 3 3 4 5 6 7 8 9

v 3 3 2 2 3 4 4 5 6 7 8 9

e 4 4 3 3 3 3 4 5 6 6 7 8

n 5 5 4 4 4 4 3 4 5 6 7 7

s 6 6 5 5 5 5 4 3 4 5 6 7

h 7 7 6 6 6 6 5 4 4 5 6 7

t 8 8 7 7 7 7 6 5 4 5 6 7

e 9 9 8 8 8 7 7 6 5 4 5 6

i 10 10 9 8 9 8 8 7 6 5 4 5

n 11 11 10 9 9 9 8 8 7 6 5 4

Durch die Tabelle gibt es zwei mögliche Wege, die den niedrigsten Aufwand produzieren:

M e i l e n s t e i n M e i l e n s t e i n L e v e n s h t e i n L e v e n s h t e i n ~ = + ~ = = = - = = = = ~ = ~ + = = = - = = = =

= Übereinstimmung; ~ Ersetzen; + Einfügen; - Löschen

3.3 Varianten der Implementierung Nachfolgend werden zwei häufig eingesetzte Varianten der Levenshtein-Distanz kurz dargestellt.

Gewichtete Levenshtein-Distanz. Im Gegensatz zur einfachen Levenshtein-Distanz werden bei der

gewichteten Levenshtein-Distanz die verschiedenen Operationen (Ersetzen, Einfügen, Löschen)

unterschiedlich gewichtet. Sollen beispielsweise gleich lange Zeichenketten beim Vergleich besser

bewertet werden als Zeichenketten mit unterschiedlicher Länge, könnten höhere Kosten für Einfüge-

und Löschoperationen angesetzt werden. Darüber hinaus können einzelne Zeichen mit variablen

Kosten gewichtet werden. Dieses Verfahren wird beispielsweise bei der Schreibmaschinendistanz7

eingesetzt und berücksichtigt die Entfernung der Zeichen auf einer QWERTZ- bzw. QWERTY-Tastatur.

Damerau-Levenshtein-Distanz. Bei der Damerau-Levenshtein-Distanz wird die einfache Levenshtein-

Distanz um die in (Damerau, 1964) eingeführte Eigenschaft – die Identifikation von zwei vertauschten

Zeichen – erweitert. Soll beispielsweise das durch einen Tippfehler falsch geschriebene Wort

„Levensthein“ mit den richtigen Wort „Levenshtein“ verglichen werden, ist beim Einsatz der

Damerau-Levenshtein-Distanz nur eine statt zwei Operationen notwendig, um die erste Zeichenfolge

in die zweite zu überführen.

7 http://de.wikipedia.org/wiki/Schreibmaschinendistanz, Zugriff: 16.02.2015



Bloomfilter

Seite 6

4 Bloomfilter

4.1 Funktionsweise Der Bloomfilter ist eine erstmals von Burton Bloom (Bloom, 1970) vorgestellte Datenstruktur, mit der

sowohl sehr zeit- als auch platzsparend festgestellt werden kann, ob ein Datensatz in einer

Datenmenge vorhanden ist. Ursprünglich wurde der Algorithmus für die Rechtschreibkontrolle und

Worttrennung entwickelt und wird heute hauptsächlich bei der Verwaltung von Datenbanken, beim

Caching und beim effizienten Routing von Paketen in Netzwerken eingesetzt. Darüber hinaus

kommen Bloomfilter häufig zum Einsatz, wenn nach sensiblen Daten gefiltert wird, die nicht im

Klartext vorhanden sein sollen. Es werden lediglich zwei Operationen bereitgestellt: Eine Operation

ermöglicht das Hinzufügen eines Datensatzes zu einem Bloomfilter, die zweite Operation bietet die

Möglichkeit, abzufragen, ob ein bestimmter Datensatz im Bloomfilter enthalten ist. Die nachträgliche

Entfernung eines bestimmten Datensatzes aus einem Bloomfilter ist bei der klassischen

Implementierung nicht möglich. Da es sich um eine probabilistische und verlustbehaftete

Datenstruktur handelt, können Abfragen zu falsch-positiven Ergebnissen führen. Dies bedeutet:

Liefert der Bloomfilter bei einer Abfrage ein positives Ergebnis, befindet sich der gesuchte Datensatz

mit einer sehr hohen Wahrscheinlichkeit in der Datenmenge. Liefert eine Abfrage hingegen ein

negatives Ergebnis, war der gesuchte Datensatz definitiv nicht in der Datenmenge enthalten.

Ein Bloomfilter besteht aus einem Bit-Array A mit einer festgelegten Länge m und wird zu Beginn mit

Nullen gefüllt. Zudem werden k unterschiedlichen Hashfunktionen benötigt. Zu beachten ist hierbei,

dass die gelieferten Hashwerte gleichverteilt sein müssen. Da die Hashwerte keine kryptografischen

Eigenschaften aufweisen müssen, können anstatt rechenintensiver kryptografischer Hashverfahren

(z.B. MD58, SHA9, …) einfache und schnelle Hashverfahren, wie beispielsweise Murmur10 oder FNV11,

eingesetzt werden. Das Risiko eines falsch-positiv Ergebnisses kann bei gegebenem m und n

(Höchstzahl der zu speichernden Werte) durch die geeignete Wahl von k minimiert werden. Die

Ermittlung des geeigneten k erfolgt dabei durch folgende Formel (Broder, Mitzenmacher, 2002):

Soll ein Datensatz zum Bloomfilter hinzugefügt werden, werden von dem zu speichernden Wert mit

Hilfe der k Hashfunktionen h Hashwerte ermittelt. Jeder der Hashwerte stellt dabei eine Position im

Bit-Array dar, die unabhängig vom vorherigen Wert („0“ oder „1“) auf „1“ gesetzt wird. Dies wird für

beliebig viele Datensätze wiederholt.

Um zu überprüfen, ob ein bestimmter Datensatz im Bloomfilter vorhanden ist, müssen von dem zu

überprüfenden Wert mit Hilfe der k Hashfunktionen h Hashwerte ermittelt werden. Steht im Bit-

Array nun an einer oder mehreren der h Stellen eine „0“, so ist der gesuchte Datensatz mit absoluter

Sicherheit nicht in der Datenmenge enthalten. Steht im Bit-Array an jeder der h Stellen eine „1“ ist

der gesuchte Datensatz mit sehr hoher Wahrscheinlichkeit, jedoch nicht mit absoluter Gewissheit in

der Datenmenge enthalten.

8 http://de.wikipedia.org/wiki/Message-Digest_Algorithm_5, Zugriff: 18.02.2015

9 http://de.wikipedia.org/wiki/Secure_Hash_Algorithm, Zugriff: 18.02.2015

10 http://en.wikipedia.org/wiki/MurmurHash, Zugriff: 18.02.2015

11 http://de.wikipedia.org/wiki/FNV_%28Informatik%29, Zugriff: 18.02.2015



Bloomfilter

Seite 7

4.2 Einfaches Beispiel Die im vorherigen Kapitel beschriebene Funktionsweise des klassischen Bloomfilters soll nachfolgend

durch ein einfaches Beispiel visualisiert werden. Dabei werden folgende Annahmen getroffen:

Länge des Bit-Arrays: m = 10

Anzahl der Hashfunktionen: k = 3

Wörter: „Bloom“, „Hochschule“, „München“

Vorgang Bloomfilter

Zu Beginn sind alle Elemente des Bit-Arrays auf „0“ gesetzt. 0 0 0 0 0 0 0 0 0 0

Nun werden die einzelnen Wörter nacheinander zum Bloomfilter hinzugefügt. Hierzu werden für jedes Wort die drei Hashwerte der drei unterschiedlichen Hashfunktionen ermittelt und anschließend die entsprechenden Positionen im Bit-Array auf „1“ gesetzt. Alle Hashwerte sind für dieses Beispiel frei konstruiert.

„Bloom“ Hashwerte: „8“, „2“, „4“ 0 1 0 1 0 0 0 1 0 0

„Hochschule“ Hashwerte: „7“, „4“, „1“ 1 1 0 1 0 0 1 1 0 0

„München“ Hashwerte: „9“, „2“, „8“ 1 1 0 1 0 0 1 1 1 0

Finaler Bloomfilter 1 1 0 1 0 0 1 1 1 0

Nachdem alle Wörter zum Bloomfilter hinzugefügt wurden, sollen nun mit einigen Wörtern überprüft werden, ob diese enthalten sind. Hierfür werden ebenfalls für jedes Wort die drei Hashwerte der drei unterschiedlichen Hashfunktionen ermittelt und anschließend überprüft, ob alle Positionen im Bit-Array auf „1“ gesetzt sind.

„Filter“ Hashwerte: „10“, „1“, „3“ Nur die Position „1“ ist im Bit-Array gesetzt, die Positionen „3“ und „10“ nicht. Somit ist das Wort „Filter“ definitiv nicht enthalten, was korrekt ist.

„Hochschule“ Hashwerte: „7“, „4“, „1“ Alle drei Positionen sind im Bit-Array gesetzt. Das Wort „Hochschule“ könnte mit einer hohen Wahrscheinlichkeit enthalten sein. Dies ist auch der Fall.

„Ingolstadt“ Hashwerte: „9“, „1“, „4“ Alle drei Positionen sind im Bit-Array gesetzt. Das Wort „Ingolstadt“ könnte mit einer hohen Wahrscheinlichkeit enthalten sein. Da das Wort jedoch oben nicht zum Bloomfilter hinzugefügt wurde, handelt es sich um ein falsch-positives Ergebnis.

4.3 Varianten der Implementierung Im Laufe der Zeit wurden zahlreiche Varianten und Erweiterungen von Bloomfiltern vorgeschlagen

und entwickelt. Der Artikel (Broder, Mitzenmacher, 2002) von Andrei Broder und Michael

Mitzenmacher gibt hierüber einen ersten guten Überblick. Der Counting Bloomfilter (Bonomi et al.

2006) erlaubt beispielsweise auf Kosten eines höheren Platzbedarfs das nachträgliche Entfernen von

Elementen aus dem Filter. Der Stable Bloomfilter (Deng, Rafiei, 2006) ermöglicht es, einen

Bloomfilter auf Stream-Daten anzuwenden und der Bloomier Filter (Chazelle et al. 2004) bietet

Optionen für probabilistische Multiplizitätsabschätzungen von eingefügten Elementen. Spektrale

Bloomfilter (Eisenhardt et al. 2004) wiederum ermöglichen die Repräsentation von Multimengen im

Filter und der Compressed Bloomfilter (Mitzenmacher, 2002) reduziert den Platzbedarf eines Filters.



Implementierung

Seite 8

5 Implementierung

5.1 Levenshtein-Distance Das von Oracle bereitgestellte Package UTL_MATCH enthält eine Reihe hilfreicher Funktionen, um

die Ähnlichkeit bzw. den Unterschied zwischen zwei gegebenen Zeichenketten einfach und schnell zu

bestimmen. Bereitgestellt werden u.a. Funktionen zur Berechnung der Levenshtein-Distanz sowie der

Jaro-Winkler-Algorithmus. Beide Algorithmen wurden neben der klassischen Variante, die

beispielsweise bei der Levenshtein-Distanz die Anzahl der notwendigen Änderungsoperationen

liefert, in einer weiteren Variante implementiert, die das Ergebnis auf einer normierten

Ähnlichkeitsskala von 0 (keine Übereinstimmung) bis 100 (volle Übereinstimmung) zurückgibt. Eine

genaue Beschreibung kann in der offiziellen Dokumentation von Oracle (OracleUtlMatch) eingesehen

werden. Das Package wurde laut (OracleBase) mit der Version Oracle 10g Release 2 eingeführt und

mit der Version Oracle 11g Release 2 erstmals dokumentiert und somit offiziell unterstützt.

Da die von Oracle bereitgestellten Funktionen vermutlich hardwarenah entwickelt (z.B. in C/C++)

und hochoptimiert sind, wurde der Algorithmus zur Berechnung der Levenshtein-Distanz zusätzlich

als PL/SQL-Funktion implementiert. Dadurch werden die gemessenen Verarbeitungszeiten der

verschiedenen Algorithmen und Implementierungen vergleichbarer. Der nachfolgende Code-Auszug

zeigt die Berechnung der Levenshtein-Distanz in PL/SQL. Da die Funktionsweise bereits im Kapitel 3.1

detailliert beschrieben wurde, wird an dieser Stelle nicht näher darauf eingegangen.

... IF input_1_length = 0 THEN RETURN input_2_length; END IF; IF input_2_length = 0 THEN RETURN input_1_length; END IF; levenshtein_grid (0) (0) := 0; FOR i IN 1..input_1_length LOOP str1(i) := SUBSTR(input_1, i, 1); levenshtein_grid (i) (0) := i; FOR j IN 1..input_2_length LOOP str2(j) := SUBSTR(input_2, j, 1); levenshtein_grid (0) (j) := j; IF str1(i) = str2(j) THEN cost := 0; ELSE cost := 1; END IF; levenshtein_grid (i) (j) := LEAST (levenshtein_grid (i-1)(j) + 1, levenshtein_grid (i)(j-1) + 1, levenshtein_grid (i-1)(j-1) + cost); END LOOP; END LOOP; RETURN levenshtein_grid (input_1_length) (input_2_length); ...



Implementierung

Seite 9

5.2 Bloomfilter Die klassische/ursprüngliche Variante des Bloomfilters erlaubt eine zeit- und platzsparende

Möglichkeit zur Bestimmung, ob sich ein gesuchter Datensatz in einer großen Datenmenge befindet.

Das objektgenaue Identifizieren eines Datensatzes in einer Datenmenge ist jedoch nicht möglich.

Daher muss für die, in dieser Arbeit genannten Aufgabenstellung bei der Implementierung und

anschließenden Nutzung des Bloomfilter-Algorithmus an einigen Stellen von der klassischen Variante

abgewichen werden. Die Entwicklung orientiert sich vor allem an der Veröffentlichung (Schnell et al.

2009) zum SAFELINK-Projekt der Universität Duisburg-Essen. Das Projekt befasst sich mit der

Entwicklung von fehlertoleranten Methoden zur Verknüpfung von personenbezogenen Daten unter

Berücksichtigung des Datenschutzes. Aus Gründen der leichteren Lesbarkeit wird auf eine

wiederholte Nennung der Veröffentlichung in den nachfolgenden Abschnitten teilweise verzichtet.

Um für jeden Datensatz des Referenzdaten- bzw. Testdatenbestandes einen eigenen Bloomfilter zu

erzeugen, wird aus den Elementen des Datensatzes (in diesem Fall Namen der Artisten und Titel des

Liedes) zunächst eine Zeichenkette gebildet. Diese Zeichenkette wird anschließend am Anfang und

Ende um ein Leerzeichen ergänzt und in N-Gramme (z.B.: N=2 Bi-Gramme oder N=3 Tri-

Gramme) unterteilt. Aus der Zeichenkette „Bloom“ ergibt sich beispielsweise die Bi-Gramm-Menge

{_B; Bl; lo; oo; om; m_}.

Aus den einzelnen Elementen der Bi-Gramm-Menge werden anschließend Hashwerte errechnet und

im Bloomfilter gesetzt. Bei der Umsetzung der k Hash-Funktionen wird auf die oben genannte

Veröffentlichung Bezug genommen. Diese schlägt vor, die k Hash-Funktionen auf Basis zweier

unabhängiger Hash-Funktionen (h1 und h2) zu realisieren. Für eine detailliertere Beschreibung sei

auf die Veröffentlichung verwiesen. Der nachfolgende Code-Auszug zeigt dieses Vorgehen

beispielhaft in PL/SQL.

Als unabhängige Hash-Funktionen wurden für die Implementierung die kryptografischen Funktionen

SHA1 und MD5 gewählt, da diese bereits von Oracle bereitgestellt werden. Andere, weniger

rechenintensivere und daher empfohlene Hashverfahren, wie Murmur oder FNV, müssten zunächst

zeit- und testaufwändig in PL/SQL entwickelt werden.

Bezüglich der optimalen Konfiguration von m und k werden durch die Veröffentlichung eine

Bloomfilter-Länge von 1.000 Bits sowie 15 Hash-Funktionen empfohlen. Diese Werte wurden

übernommen.

Zur Bestimmung der Ähnlichkeit zweier N-Gramm-Mengen wird häufig der sog. DICE-Koeffizient

eingesetzt. a gibt dabei die Anzahl der N-Gramme in der ersten Zeichenkette, b die Anzahl der N-

Gramme in der zweiten Zeichenkette und c die Anzahl der N-Gramme, die in beiden Zeichenketten

vorkommen, an. Als Ergebnis liefert der DICE-Koeffizient eine Gleitkommazahl zwischen 0 (keine

Übereinstimmung) und 1 (totale Übereinstimmung). Da bei dieser Implementierung des Bloomfilters

... FOR i IN 0..k-1 LOOP e := h1 + i*h2; e := MOD(e, bloom_length); bloomfilter(e+1) := 1; END LOOP; ...



Auswertung

Seite 10

N-Gramme eingesetzt werden, kann der DICE-Koeffizienten zur Ähnlichkeitsbestimmung von zwei

Bloomfiltern verwenden werden. Dies wird auch in der oben genannten Veröffentlichung empfohlen.

Die Variablen a, b und c geben beim Einsatz mit Bloomfiltern jedoch nicht die Anzahl der N-Gramme,

sondern die Anzahl der gesetzten Bits an. Der nachfolgende Code-Auszug zeigt die Implementierung

des DICE-Koeffizienten in PL/SQL.

6 Auswertung

6.1 Infrastruktur und Konfiguration Die Entwicklung der Algorithmen sowie die Messung der Ausführungszeiten und

Treffergenauigkeiten erfolgten unter folgenden Hardware- und Software-Komponenten:

Komponente Eigenschaft

Hardware Prozessor Intel® Core™ i7-2630QM (Quad-Core, 2.00 GHz, 6 MB Cache) Arbeitsspeicher 8 GB Festplatte 750 GB HDD, 7.200 Umdrehungen pro Minute Software Betriebssystem Windows 7 Professional (64 Bit) Oracle-Datenbank 11g Express Edition (in der Standardkonfiguration) Tabelle 1: Die eingesetzten Hardware- und Software-Komponenten

6.2 Ausführungszeiten Um die einzelnen Matching-Verfahren hinsichtlich ihrer Verarbeitungszeiten vergleichen zu können,

wurden jeweils 100 Testdatensätze gegen den gesamten Referenzdatenbestand (10.000 Datensätze)

getestet. Die nachfolgende Tabelle zeigt die gemessenen Ausführungszeiten der verschiedenen

Verfahren und Implementierungsvarianten (in Minuten, Sekunden und Millisekunden).

Verfahren Vorberechnung Abgleich Summe

Levenshtein-Distanz (Oracle-Implementierung) -- 00:16,037 00:16,037 Levenshtein-Distanz (Eigen-Implementierung) -- 35:04,904 35:04,904 Bloomfilter 00:40,384 05:05,895 05:46,279 Tabelle 2: Die Ausführungszeiten der einzelnen Matching-Verfahren

... IF bloom1 = bloom2 THEN dice := 1; ELSE SELECT NVL(LENGTH(REPLACE(UTL_RAW.BIT_AND(bloom1, '1'), '0', '')), 0) INTO a FROM dual; SELECT NVL(LENGTH(REPLACE(UTL_RAW.BIT_AND(bloom2, '1'), '0', '')), 0) INTO b FROM dual; SELECT NVL(LENGTH(REPLACE(UTL_RAW.BIT_AND(bloom1, bloom2), '0', '')), 0) INTO c FROM dual; dice := 2 * c / (a + b); END IF; ...



Auswertung

Seite 11

Die Verarbeitungszeit beim Einsatz der Levenshtein-Distanz ist sehr stark von der Implementierung

abhängig. Während die hochoptimierte Oracle-interne Implementierung für eine Million

Distanzberechnungen (Vergleich von 100 Testdatensätzen mit jeweils 10.000 Referenzdatensätzen)

nur 16 Sekunden benötigt, ist die eigene Implementierung in PL/SQL mit 35 Minuten um den Faktor

130 langsamer. Die Verarbeitungszeit beim Einsatz des Bloomfilters setzt sich aus zwei Komponenten

zusammen: Zum einen die einmalige Berechnung und anschließende Speicherung der Bloomfilter der

10.000 Referenzdatensätze (Vorberechnung). Zum anderen die Berechnung der Bloomfilter der 100

Testdatensätze und der anschließende Abgleich mit den gespeicherten Bloomfiltern des

Referenzdatenbestandes (Abgleich). Allerdings besteht beim Bloomfilter ein Optimierungspotenzial:

Die rechenintensiven kryptografischen Hashverfahren können durch einfache und schnelle

Hashverfahren ersetzt werden. Dies würde zu einer Reduzierung der Ausführungszeit führen.

6.3 Treffergenauigkeit Um Bestimmen zu können, ob die Matching-Algorithmen die einzelnen Datensätze korrekt zuordnen,

wird bei der Erstellung der Testdatensätze der Verweis auf den Ursprungsdatensatz des

Referenzdatenbestands gespeichert. Stimmt nach der Durchführung eines Abgleichs die ID des

zugeordneten Datensatzes mit der ID des Verweises überein, gilt die Zuordnung als korrekt,

andernfalls als nicht korrekt.

Verfahren Anzahl

Testdatensätze

Anzahl übereinstimmender

Paare

Anzahl nicht übereinstimmender

Paare Trefferquote

Levenshtein-Distanz 100 75 25 75% Bloomfilter 100 95 5 95% Tabelle 3: Die Treffergenauigkeit der einzelnen Matching-Verfahren

Der Bloomfilter hat im gegebenen Testszenario eine deutlich höhere Trefferquote als die

Levenshtein-Distanz. Dies liegt vor allem an der unterschiedlichen Herangehensweise bei der

Verarbeitung der beiden zu vergleichenden Zeichenketten. Während bei der Levenshtein-Distanz die

Anzahl der Änderungsoperationen sehr stark von der Reihenfolge der Zeichen abhängt, spielt die

Reihenfolge der Zeichen beim Bloomfilter aufgrund der N-Gramme nur eine untergeordnete Rolle.

Am besten lässt sich dies anhand eines Beispiels verdeutlichen:

a) Vergleich von „ABBA - Dancing Queen” mit „ABA - Dancing Queen (live)”

b) Vergleich von „ABBA - Dancing Queen” mit „Dancing Queen (live) by ABBA“

Obwohl in beiden Szenarien der Großteil der Zeichen identisch ist, liefert die Levenshtein-Distanz nur

in Szenario A eine korrekte Zuordnung. Der Bloomfilter hingegen liefert bei beiden Szenarien eine

korrekte Zuordnung.

Szenario A: Es gibt keine Änderungen in der Reihenfolge der Zeichen, da lediglich ein Buchstabe fehlt

und etwas angehängt wird. Die Levenshtein-Distanz beträgt acht (Entfernen des Buchstaben „B“ im

Artisten sowie Hinzufügen von „ (live)“ am Ende) und ist relativ niedrig. Die Wahrscheinlichkeit, mit

acht Änderungen bei einer nicht übereinstimmenden Zeichenkette (z.B.: „ABBA - Happy New Year“,

11 Änderungen notwendig) zur Eingabezeichenkette zu gelangen, ist gering. Die Treffergenauigkeit

ist daher hoch. Die Bits des Bloomfilters sind sehr ähnlich, da nur das Bi-Gramm „BB“ fehlt und neue

Bi-Gramme für „ (live)“ hinzukommen. Alle anderen Bi-Gramme sind identisch. Die Treffergenauigkeit

ist daher hoch.



Zusammenfassung

Seite 12

Szenario B: Artist und Titel werden vertauscht, die Reihenfolge der Zeichen hat sich somit stark

geändert. Die Levenshtein-Distanz beträgt 22. Die Wahrscheinlichkeit, mit 22 Änderungen bei einer

nicht übereinstimmenden Zeichenkette (z.B.: „ABBA - Happy New Year“, 11 Änderungen notwendig)

zur Eingabezeichenkette zu gelangen, ist wesentlich höher als im Szenario A. Die Treffergenauigkeit

ist daher geringer und ein falsch-positive Zuordnung leichter möglich. In diesem Fall würde die nicht

übereinstimmende Zeichenkette fälschlicherweise zugeordnet werden. Die Bits des Bloomfilters sind

hingegen sehr ähnlich, da nur Bi-Gramme für „ (live) by“ hinzugekommen sind. Alle anderen Bi-

Gramme sind identisch. Die Treffergenauigkeit ist daher hoch. Mit dem Bloomfilter erfolgt eine

korrekte Zuordnung.

Die Treffergenauigkeit kann darüber hinaus bei beiden Verfahren verbessert werden, wenn die

beiden zu vergleichenden Zeichenketten zuvor bereinigt werden. Beispiele hierfür sind u.a. das

einheitliche Entfernen oder Ersetzen von Sonderzeichen („&“ zu „und“, etc.) sowie eine einheitliche

Großkleinschreibung, da Groß- und Kleinbuchstaben zu Änderungskosten bei der Levenshtein-Distanz

bzw. zu einem anderen Bit-Muster beim Bloomfilter führen.

7 Zusammenfassung In dieser Arbeit wurden im Grundlagenteil eine kurze Einführung in die umfangreiche Thematik der

Duplikaterkennung/Objektidentifizierung sowie ein erster Überblick über die verschiedenen

Klassifizierungen, Lösungsansätze, Algorithmen und Implementierungsverfahren gegeben. Durch die

prototypische Implementierung der Levenshtein-Distanz und des Bloomfilters konnten sowohl eine

mögliche Umsetzung aufgezeigt als auch mögliche Potenziale und Grenzen der Algorithmen näher

untersucht werden. Ziel der Arbeit war es zudem, durch Messergebnisse bzgl. der Ausführungszeiten

und Treffergenauigkeiten erste Erkenntnisse darüber zu liefern, ob die Implementierung eines

Bloomfilters eine sinnvolle Ergänzung oder Alternative für den derzeit eingesetzten Levenshtein-

Distanz-Algorithmus darstellt. Dies soll nachfolgend nun kurz aufgezeigt werden.

Die Oracle-interne Implementierung der Levenshtein-Distanz bietet im Gegensatz zu einer eigenen

Implementierung ein hohes Steigerungspotenzial bei den Verarbeitungszeiten. Da die offizielle

Veröffentlichung und Unterstützung der Oracle-internen Implementierung erst mit Version „11g

Release 2“ begann, könnten sich große Optimierungspotenziale durch die Aktualisierung älterer

Programmbestandteile (die mit eigenen Implementierungen arbeiten) ergeben, falls dies bisher noch

nicht geschehen ist.

Auch der Einsatz eines Bloomfilters könnte sich aufgrund der deutlich höheren Treffergenauigkeit in

einigen oder vielleicht sogar allen Bereichen lohnen. Diese bessere Trefferquote muss allerdings

gegebenenfalls mit einer längeren Verarbeitungszeit erkauft werden.

Die große Stärke der klassischen Variante des Bloomfilters ist die zeit- und platzsparende

Bestimmung, ob sich ein gesuchter Datensatz in einer sehr großen Datenmenge befindet. Eine

sinnvolle Ergänzung wäre beispielsweise, einen Teil oder alle Datensätze des Referenzdatenbestands

in einen einzigen mehrere zehn- oder hunderttausend Bit langen Bloomfilter zu packen. Dieser

könnte anschließend zur Vorauswahl verwendet werden und steuert, ob eine detailliertere und somit

rechenintensivere Identifizierung mit einem anderen Matching-Algorithmus, zum Beispiel dem

derzeit eingesetzten Levenshtein-Distanz-Algorithmus, durchgeführt werden soll.



Literaturverzeichnis

Seite 13

8 Literaturverzeichnis Apel, Detlef; Behme, Wolfgang; Eberlein, Rüdiger; Merighi, Christian: Datenqualität erfolgreich steuern – Praxislösungen für Business-Intelligence-Projekte. 2., vollständig überarbeitete und erweiterte Auflage, Carl Hanser Verlag, 2010 Bellman, Richard: Dynamic Programming. Princeton University Press, 1957 Bethlehem, Jelke: Surveys without questions. In: E. D. de Leeuw, J. D. Hox und D. A. Dillman (Hg.): International handbook of survey methodology, New York: Erlbaum, 2008, S. 500-511 Bloom, Burton H.: Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13(7): 422-426, 1970 Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George: An Improved Construction for Counting Bloom Filters. In: Lecture Notes in Computer Science Volume 4168, 2006, S. 684-695 Broder, Andrei; Mitzenmacher, Michael: Network applications of bloom filters: A survey. In: Internet Mathematics. 2002, S. 636-646 Chazelle, Bernard; Kilian, Joe; Rubinfeld, Ronitt; Tal, Ayellet: The Bloomier filter: an efficient data structure for static support lookup tables. In: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 2004, S. 30-39 Damerau, Fred J.: A technique for computer detection and correction of spelling errors. In: Communications of the ACM. 7, Nr. 3, März 1964, S. 171–176 Deng, Fan; Rafiei, Davood: Approximately detecting duplicates for streaming data using stable bloom filters. In: Proceedings of the 2006 ACM SIGMOD international conference on Management of data. 2006, S. 25-36 Eisenhardt, Martin; Müller, Wolfgang; Henrich, Andreas: Spektrale Bloom-Filter für Peer-to-Peer Information Retrieval. Conference: INFORMATIK 2004 - Informatik verbindet, Band 2, Beiträge der 34. Jahrestagung der Gesellschaft für Informatik e.V. (GI), Ulm, 20.-24. September 2004 Levenshtein, Vladimir I.: Binary codes capable of correcting deletions, insertions, and reversals. In: Doklady Akademii Nauk SSSR. 163, Nr. 4, 1965, S. 845–848 (Russisch, Englische Übersetzung in: Soviet Physics Doklady, 10(8) S. 707–710, 1966) Mitzenmacher, Michael: Compressed bloom filters. In: IEEE/ACM Transactions on Networking. 2002, S. 604-612 Naumann, Felix; Herschel, Melanie: An Introduction to Duplicate Detection. Morgan & Claypool, 2010 Schnell, Rainer: Record Linkage from a Technical Point of View. In: German Data Forum (RatSWD) (ed.): Building on progress: Expanding the research infrastructure for the social, economic, and behavioral sciences (Vol. 1), Opladen: Budrich UniPress, pp. 531-545, 2010 Schnell, Rainer; Bachteler, Tobias; Reiher, Jörg: Privacy-preserving record linkage using Bloom filters. In: BMC Medical Informatics and Decision Making 9 (41), 2009



Literaturverzeichnis

Seite 14

Internetquellen für die Recherche:

[Hamming] Richard-W.-Hamming-Medaille des IEEE http://www.ieee.org/about/awards/medals/hamming.html Zugriff am 16.02.2015

[Naumann] Duplikaterkennung (Offizielle Folien von Felix Naumann, 03.07.2012)

http://hpi.de/fileadmin/user_upload/fachgebiete/naumann/ folien/SS12/InfoInt/InfoInt_07_Duplikaterkennung.pdf Zugriff am 12.02.2015

[OracleBase] UTL_MATCH : String Matching by Testing Levels of Similarity/Difference

http://oracle-base.com/articles/11g/utl_match-string-matching-in-oracle.php Zugriff am 18.03.2015

[OracleUtlMatch] Offizielle Dokumentation des UTL_MATCH-Packages von Oracle

http://docs.oracle.com/database/121/ARPLS/u_match.htm Zugriff am 18.03.2015

Documents

Vergleich der Levenshtein-Distanz und des Bloomfilter … · 2019-10-30 · Vergleich der Levenshtein-Distanz und des Bloomfilter-Algorithmus zur Objektidentifizierung im Kontext