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

Groongaではサジェスト機能のためにedit_distance関数が実装されています。

これはO(nm)の計算量が必要な動的計画法で文字数が多くなると結構遅くなります。

そこで、高速化するためにビットパラレル法をGroongaの関数で実装してみて比較してみました。

naoa/groonga-edit-distance · GitHub

ビットパラレル法

これのFigure 3.と4.のMyersの方の実装をしてみました。

A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances Included in the proceedings of the Prague Stringology Conference 2002 (PSC 2002). http://www.sis.uta.fi/~hh56766/pubs/psc02.pdf

ビット演算で並列に演算して高速化します。計算量はO(n/w m)のようです。 これ長い方を左にするとお得ぽいので長い方が左になるように選択しています。 64文字以下だとO(m)です。mは短い方の文字数。

とりあえず64文字までしか対応していません。64を超えると動的計画法が利用されます。

マルチバイト用の関数では文字をハッシュテーブルで整数値にマッピングしています。文字が増えれば増えるほどマッピングのコストがかかります。マッピングのコストを抑えるために1回のコマンド実行中ハッシュテーブルと左側の文字列のマッピング結果はキャッシュしています。

実験結果

100万件のレコードのscorerに実装したdamerau_edit_distance, edit_distance_bp, edit_distance_bp_varを使ってスコアを求めます。結果出力とスコア代入自体のコストもあるため、score代入のみのケースも示します。なお、全部transposition入りです(たいして差はなかったので)。

文字数x文字数	score代入のみ	動的計画法	ビットパラレル固定長	ビットパラレル可変長
62x62	0.31589 sec	74.16554 sec	1.38189 sec	6.19149 sec
3x62	0.31312 sec	5.26055 sec	0.91457 sec	5.87688 sec
62x3	0.31560 sec	5.73797 sec	0.93845 sec	1.81229 sec
15x15	0.31624 sec	5.40047 sec	0.93917 sec	2.79704 sec
3x3	0.31591 sec	1.19619 sec	0.79177 sec	1.37829 sec

ビットパラレルの方は文字が長くなってもあまり遅くなっていません。ビットパラレル可変長は文字をハッシュテーブルでマッピングしているため、文字数が3文字と非常に少ない場合は効果が低くむしろ時間がかかっています。

3x62の可変長は62x3に比べ結構遅くなっています。可変長の場合、左側の文字列とハッシュテーブルをキャッシュ*1しているのですが、右側はしていません。都度右側の長い文字列をマッピングするのに時間がかかっています(100万レコードの比較なので100万×62)。62x3の場合はキャッシュされる左側が長く、右側が3文字のマッピングだからその分速いです。固定長の方はマッピングがいらないので変わりません。

カラムの文字列をあらかじめマッピングした結果の整数ベクターカラムにしておけば、都度マッピングはいらなくなり、マッピングコストはほとんどなくなるかもしれません。ただ、それは事前に作る必要があって使いづらそうです。

感想

英語の64文字までの特に文字が長いケースで大きく速度の向上が期待できそうです。 日本語でも文字数がある程度あれば、向上が期待できますが、ハッシュテーブルにマッピングするのがめんどくさいです。

ただ、この方法では２つの文字列の比較の計算量がO(m)になったとしても100万レコードとの比較の場合、O(m)×100万が必要になっていまいます。

他の高速な編集距離の実装方法として、levenshtein automataというO(max edit distance) versionってのがあるらしく、O(n/w m)よりも大分はやそうですね。あいまい検索用途ならせいぜい１文字や２文字程度しかいらないのでよさそうです。

Levenshtein automata can be simple and fast

Luceneではこれが実装されているみたいです。

http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html

さきにこっちにきづけばよかった。。今度levenshtein automataを実装できそうだったら実装してみたいです。

このpatlの実装参考になるかな。

https://code.google.com/p/patl/source/browse/trunk/uxn/patl/levenshtein.hpp

*1:１回のselectコマンド実行中、すなわち100万レコードの比較中