MySQLで編集距離を求めるUDF

先日、Groongaでビットパラレルで高速な編集距離の実装を検証してました。

ビットパラレルを使ってGroongaで高速な編集距離関数の検証 - CreateField Blog

編集距離とは挿入、置換、削除、並び替えの編集操作によって一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数です。ちょこっとだけ表記ゆれしている文字列を抽出したりできます。

ちょっとMySQLでもカジュアルに使いたいなぁと思って編集距離を求めるUDFをさくっと作りました。

１バイト文字であればビットパラレル法でそこそこ高速に編集距離を求めることができます。

10万レコードの比較

文字数x文字数	動的計画法	ビットパラレル固定長
62x62	11.6524 sec	0.1811 sec

とりあえず、英語で使いたかっただけということもあってビットパラレルオプションは日本語に対応していません。ビットパラレルを使わない方であれば、日本語も対応しています。

使用例

CREATE TABLE IF NOT EXISTS `test` (
  `name` varchar(64) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

INSERT INTO test VALUES("MySQL");
INSERT INTO test VALUES("MySQL2");
INSERT INTO test VALUES("MySQM");
INSERT INTO test VALUES("MySQ");
INSERT INTO test VALUES("MySLQ");
INSERT INTO test VALUES("MySOM");
INSERT INTO test VALUES("PostgreSQL");
INSERT INTO test VALUES("Oracle");

SELECT name, edit_distance(name, "MySQL") FROM test
WHERE edit_distance(name, "MySQL") < 3
ORDER BY edit_distance(name, "MySQL") ASC;

+--------+------------------------------+
| name   | edit_distance(name, "MySQL") |
+--------+------------------------------+
| MySQL  | 0                            |
| MySQL2 | 1                            |
| MySQ   | 1                            |
| MySQM  | 1                            |
| MySLQ  | 1                            |
| MySOM  | 2                            |
+--------+------------------------------+
6 rows in set (0.00 sec)

SELECT edit_distance("abc", "abd", 1);
+--------------------------------+
| edit_distance("abc", "abd", 1) |
+--------------------------------+
| 1                              |
+--------------------------------+
1 row in set (0.00 sec)

第３引数に1を指定するとビットパラレル法になります。