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

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