Die Levenshtein-Distanz in MySQL

13 Feb

Man stelle sich vor, man hat eine größere Menge wissenschaftlicher Publikationen gesammelt. Nehmen wir mal vorsichtig an, es sind zumindest viele Tausend. Und diese Dokumente zitieren und referenzieren sich untereinander. Da kommt es vor, dass sich Tippfehler in Literaturverzeichnissen einschleichen und die Titel eigentlich identischer Dokumente sich nicht mehr vollkommen gleichen. Die Titel eigenen sich aber eigentlich sehr gut, um eine Publikation zu identifizieren. Dementsprechend kommt es bei Analysen der Beziehungen zwischen den Dokumenten zu Folgefehlern.

Um Ungleichheiten in Zeichenketten großzügig zu behandeln, kann man die Levenshtein-Distanz nutzen. Diese vergleicht zwei Zeichenketten und gibt die minimale Anzahl von Operationen (Einfügen, Löschen und Ersetzen) an, die benötigt werden, um die erste Zeichenkette die zweite umzuwandeln. Anstatt Titel auf vollkommene Gleichheit zu überprüfen, ist es hiermit also z.B. möglich, kleinere Ungleichheiten zu tolerieren.

Es gibt eine ganze Reihe von Implementierungen in verschiedenen Sprachen, z.B. in PostgreSQL. Zurzeit arbeite ich allerdings mit MySQL. Hier ist die Funktion nicht von Haus aus installiert, es gibt aber zumindest eine UDF (User Defined Function), die auf der GitHub Seite von Juan Miguel Cejuela zu finden ist. Und da die Einbindung doch ein paar Minuten in Anspruch genommen hat, folgt hier ein kleines HowTo.

Installation

Zunächst lädt man die Datei levenshtein.c runter und folgt den Installationsanweisungen im Kommentar. Bei mir fehlten zusätzliche Codedateien:

$ gcc -o levenshtein.so -shared levenshtein.c
levenshtein.c:33:23: fatal error: my_global.h: No such file or directory
compilation terminated.

Den Sourcecode kann man in Mint/Ubuntu/Debian so beziehen:

$ sudo aptitude install mysql-source-5.5

Als Nächstes wird die benötigte Datei ausfindig gemacht:

$ dpkg -L mysql-source-5.5
/.
/usr
/usr/src
/usr/src/mysql
/usr/src/mysql/mysql-source-5.5.tar.gz
/usr/share
/usr/share/doc
/usr/share/doc/mysql-source-5.5
/usr/share/doc/mysql-source-5.5/copyright
/usr/share/doc/mysql-source-5.5/changelog.Debian.gz

Das Archiv wird entpackt:

$ tar -xzf /usr/src/mysql/mysql-source-5.5.tar.gz

In den extrahierten Dateien wird nach der benötigten Headerdatei gesucht:

$ find ./ -iname "my_global.h"
./source/mysql-5.5/include/my_global.h

Ein erneuter Versuch, zu kompilieren. Dieses Mal mit Angabe des Verzeichnisses der Headerdatei:

$ gcc -o levenshtein.so -shared levenshtein.c -I source/mysql-5.5/include/
In file included from levenshtein.c:33:0:
source/mysql-5.5/include/my_global.h:77:23: fatal error: my_config.h: No such file or directory
compilation terminated.

Suche der zweiten fehlenden Datei:

$ find ./ -iname "my_config.h"
./source/mysql-5.5/builddir/include/my_config.h
./source/mysql-5.5/builddir/packaging/rpm-uln/my_config.h
./source/mysql-5.5/packaging/rpm-uln/my_config.h

Dieses Mal klappt das Kompilieren:

gcc -o levenshtein.so -shared levenshtein.c -I source/mysql-5.5/include/ -I source/mysql-5.5/builddir/include/

Suche nach dem MySQL Plugin Verzeichnis:

$ mysql
mysql> show variables;
+----------------+------------------------+
| Variable_name | Value | |
+----------------+------------------------+
| plugin_dir | /usr/lib/mysql/plugin/ |
+----------------+------------------------+

Kopieren der erstellten Datei ins MySQL Plugin Verzeichnis:

$ sudo cp levenshtein.so /usr/lib/mysql/plugin/

MySQL als root Starten und die Funktion erstellen:

$ mysql -uroot
mysql> CREATE FUNCTION levenshtein RETURNS INT SONAME 'levenshtein.so';
Query OK, 0 rows affected (0.07 sec)
mysql> CREATE FUNCTION levenshtein_k RETURNS INT SONAME 'levenshtein.so';
Query OK, 0 rows affected (0.01 sec)

Test:

mysql> select levenshtein('hello', 'world');
+-------------------------------+
| levenshtein('hello', 'world') |
+-------------------------------+
| 4 |
+-------------------------------+
1 row in set (0.00 sec)

Vladimir Levenshtein (Deutsche Übersetzung) hat den Algorithmus übrigens 1965 veröffentlicht.

Hier ist noch ein Backup der Datei mit dem C Code.

Creative Commons Lizenzvertrag Dieses Werk bzw. Inhalt steht unter einer Creative Commons Namensnennung 3.0 Deutschland Lizenz. Wenn möglich, verwenden Sie doch einen Link zum Originalartikel: Adrian Wilke: Die Levenshtein-Distanz in MySQL.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: