No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Makefile
README.md
edit_distance.c
install.sql
uninstall.sql

README.md

MySQL edit distance UDF

MySQLに編集距離を求める関数を追加します。

  • edit_distance

edit_distance関数

transposition対応のDamerau Edit distanceで編集距離を返します。

第3引数に1を指定すると、ビットパラレル法で高速に編集距離を求めます。 ビットパラレル法は1バイト文字64個まで対応しています。

ビットパラレル法は日本語に対応していません。 第3引数を指定しなければ動的計画法になり一応日本語に対応しています。

arg description default
1 文字列1 NULL
2 文字列2 NULL
3 ビットパラレルを使うかどうか NULL

使用例

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;

mysql> 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)

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

比較

10万レコードの比較

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

Install

make
make install
mysql -ppassword < install.sql

デフォルトでは/usr/local/mysql/lib/plugin/edit_distance.soにインストールされます。 インストール場所を変更する場合は適宜Makefileを書き換えてください。

Uninstall

mysql -ppassword < uninstall.sql
make uninstall

Author

Naoya Murakami naoya@createfield.com

License

Public domain.