CreateField Blog

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

2016-01-01から1ヶ月間の記事一覧

MySQLで編集距離を求めるUDF

先日、Groongaでビットパラレルで高速な編集距離の実装を検証してました。 ビットパラレルを使ってGroongaで高速な編集距離関数の検証 - CreateField Blog 編集距離とは挿入、置換、削除、並び替えの編集操作によって一方の文字列をもう一方の文字列に変形す…

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

Groongaではサジェスト機能のためにedit_distance関数が実装されています。 これはO(nm)の計算量が必要な動的計画法で文字数が多くなると結構遅くなります。 そこで、高速化するためにビットパラレル法をGroongaの関数で実装してみて比較してみました。 naoa…