読者です 読者をやめる 読者になる 読者になる

CreateField Blog

オープンソースを使って個人でWebサービスを開発・運営していたブログ

MySQLで編集距離を求めるUDF

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

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

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

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

naoa/mysql-edit-distance · GitHub

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

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)

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