続・上限付きLevenshtein距離を高速に計算する

作者: 藤本誠二 <fujimoto@ceptord.net>
更新: 2017年12月09日

この記事は「上限付きLevenshtein距離を高速に計算する」の続きです。

先の解説記事では、測定上限 k=2 についてのみ速度検証を行いました。 そして、確かにこのケースではWagner-Fischer法より速いことは確認できたのですが、 ここで疑問を覚えるのは、 それ以外のパラメータについても、速度上の優位性が保たれるか? という点です (平たく言えば「さっきの検証では都合のよいパラメータを選んだだけでは?」という疑問です)。

この疑問はかなりポイントをついています。 というのも、先の記事の手法を k > 2 に拡張しようとすると、測定上限 k に対して、 検証すべきパターンが指数的に爆発することが分かるからです。 したがって、一定以上の k については、 Wagner-Fischer法の方が効率的になることが容易に予想されます。

本記事のゴールは、具体的にどの k において [先の記事の手法の速度] > [Wagner-Fischer法の速度] となるかを確かめることです。

性能試験

辞書データは前記事と同様に SCOWL から取得したものを用います (99,171語)。 与えられた入力語に対して、 編集距離が k 以下になる単語を辞書からすべて抽出し、 この処理に要する時間を測定します。

入力語の選び方によって結果に偏りが生じるのを避けるため、 10個のワードを辞書からランダムに抽出し、平均をとることにします。

本試験に用いた実装はこちらからダウンロードできます。

試験環境

試験結果

ランダム抽出された入力語

試験結果

kmblevenWagner-Fischer
10.09秒1.69秒
20.20秒3.59秒
30.60秒5.66秒
41.99秒7.64秒
56.74秒9.38秒
622.55秒10.83秒

試験結果のグラフ

考察

以上の結果をまとめると、(少なくとも今回の試験に用いた条件では) おおむね k = 5 まではmblevenに速度の優位性があり、 それを上回る場合はWagner-Fischer法の方が効率的になる、 という結論になりそうです。

この k = 5 という境界そのものは、実装や処理系に依存する値ですが、 グラフから見て取れるように、測定上限の変化に対して、 Wagner-Fischerはたかだか線形にしか遅くならないのに、 mblevenの場合は指数関数的に処理時間が伸びているので、 どこかの地点で効率性の逆転が必ず生じるというのは、まず間違いないようです。

未解決の課題


Top