Levenshtein mit MySQL, ähnliche Begriffe finden

Die Levenshtein-Distanz berechnet die Anzahl an Zeichen die nötig sind, um 2 Wörter durch Ergänzen oder Löschen  aneinander anzugleichen (identisch machen).

Die aus PHP bekannte Funktion levenshtein() ist in MySQL nicht implementiert. Es gibt aber Möglichkeiten sie nachträglich zu integrieren. Entweder durch die in C geschrieben UDF Plugins oder eben durch direkte Eingabe von SQL Anweisungen. Letztere, die Stored Procedures haben den Vorteil, dass sie ohne Zugang zum Server bei entsprechender Berechtigung z.B. über phpMyAdmin installiert werden können. Nachteilig ist unter anderem die schlechte Geschwindigkeit.

Ich zeige hier die SQL Anweisung und muss leider ernüchternd sagen, dass die Geschwindigkeit echt miserable ist. Also dient die Funktion lediglich zu Testzewcken.

Der Aufruf:

SELECT `column`, LEVENSHTEIN('baum', `column`) AS `dist`
FROM `table`
HAVING `dist` BETWEEN 1 AND 
ORDER BY `dist` ASC
LIMIT 10;

Funktion:

Die LEVENSHTEIN-Funktion liefert einen Integer Wert zurück, der bei identischen Wörtern 0 ist. Wenn sehr ähnliche Wörter gefunden werden sollen, sollte die Distanz zwischen 1 und 5 liegen. Im Beispiel werden als ähnlich Wörter zu 'baum' gesucht.

Der Funktionscode: Quelle: http://kristiannissen.wordpress.com/2010/07/08/mysql-levenshtein/

Der erste Befehl kann natürlich weg gelassen werden und dient nur zum Testen. Er entfernt zuvor schon deklarierte Funktionen.

DROP FUNCTION IF EXISTS levenshtein;

delimiter //
CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) ) RETURNS INT
	DETERMINISTIC
	BEGIN
		DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
		DECLARE s1_char CHAR;
		DECLARE cv0, cv1 VARBINARY(256);
		SET s1_len = CHAR_LENGTH(s1), 
			s2_len = CHAR_LENGTH(s2), 
			cv1 = 0x00, 
			j = 1, 
			i = 1, 
			c = 0;
		
		IF s1 = s2 THEN
			RETURN 0;
		ELSEIF s1_len = 0 THEN
			RETURN s2_len;
		ELSEIF s2_len = 0 THEN
			RETURN s1_len;
		ELSE
			WHILE j <= s2_len DO
				SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
			END WHILE;
			WHILE i <= s1_len DO
				SET s1_char = SUBSTRING(s1, i, 1), 
					c = i, 
					cv0 = UNHEX(HEX(i)), 
					j = 1;
				WHILE j <= s2_len DO
					SET c = c + 1;
					
					IF s1_char = SUBSTRING(s2, j, 1) THEN
						SET cost = 0; 
					ELSE 
						SET cost = 1;
					END IF;
					
					SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) 
						+ cost;
					IF c > c_temp 
						THEN SET c = c_temp; 
					END IF;
					
					SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10)
						 + 1;
					
					IF c > c_temp THEN
						SET c = c_temp;
					END IF;
					SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
				END WHILE;
				SET cv1 = cv0, i = i + 1;
					
			END WHILE;
		END IF;
	RETURN c;
END //
delimiter ;