Levenshtein-Distanz mit MySQL

Für ein Projekt benötigte ich eine Möglichkeit, eine Duplikatsprüfung durchzuführen. Anforderung war, nicht nur identische, sondern auch „ähnliche“ Datenbank-Einträge wiederfinden können. Dabei stieß ich auf den Algorithmus der Levenshtein-Distanz. MySQL kennt von Haus aus keine Funktion hierfür. Nach einigem Suchen bin ich allerdings auf ein kleines Plugin gestoßen, dass diesen Algorithmus als user-defined function nachrüstet.

Um es kurz zu machen – für die Installation auf einem CentOS 5 auf einer 64-Bit-Plattform habe ich folgende Schritte benötigt:

mkdir /usr/local/src/mysql_levenshtein_udf-1.0
cd /usr/local/src/mysql_levenshtein_udf-1.0
wget http://joshdrew.com/mysql_levenshtein_udf-1.0.tar.gz
tar -xzvf mysql_levenshtein_udf-1.0.tar.gz
gcc -I/usr/include/mysql -fPIC -O -pipe -o mysqllevenshtein.so -shared \
  -L/usr/lib64/mysql -lmysqlclient mysqllevenshtein.cc
cp mysqllevenshtein.so /usr/lib64/libmysqllevenshtein.so

Das -fPIC steht nicht in der README, wird aber für die 64-Bit-Plattform benötigt. Interessanterweise sucht mysqld die .so-Datei in /usr/lib64 und nicht in /usr/lib64/mysql, wie ich eigentlich erwartet hätte. Aber sei’s drum.

Auf der mysql-Shell schließlich noch als root:

CREATE FUNCTION levenshtein RETURNS INT SONAME 'libmysqllevenshtein.so';

Und das war’s auch schon. MySQL merkt sich solche vom Benutzer eingefügten Funktionen in der Tabelle mysql.func, so dass sie problemlos einen Restart überdauern. Sehr schick!

Und so wird’s benutzt, hier zum Beispiel vor dem Hinzufügen eines neuen Datensatzes, um zu schauen, ob es schon jemanden gibt, der möglicherweise so in etwa ebenfalls „Jonas Pasche“ heißt – nur dass eben auch „Ionas Paschke“ gefunden würde:

SELECT *
  FROM contact
 WHERE LEVENSHTEIN(n_family, "Pasche") < 2
       AND LEVENSHTEIN(n_given, "Jonas") < 2;