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

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

Levenshtein距離は、一般に動的計画法によって計算することができます。 この手法では、文字列の長さに対応するマトリックスを用意して、 各マスを一定の規則によって埋めていくことで距離を算出します(Wagner-Fischer法)

この手法は非常に汎用的ですが、 他方で、現実の用途では、 すべてのケースで正確な距離を求める必要がないことも多々あります。 たとえば、スペルチェックの分野では、 入力語に近い単語を辞書から抽出するにあたって、 たかだか 1〜2 までの距離を考慮すれば十分であることが少なくありません。 このような事情から、測定できる編集距離に上限を組み込む事で、 計算コストを圧縮する工夫がいくつも考案されてきました。

この記事では、Wagner-Fischer法とは異なる編集距離の計算モデルを解説します。 このモデルを利用することで、編集距離に上限のあるケースでは、 動的計画法よりも効率的に解を求めることができます。

より効率的な計算モデル

「文字列 s・t の間のLevenshtein距離が1である」 という命題について考えます。 この文の真偽を確かめるひとつの方法は、 Levenshtein距離の定義を使って、次のように命題を展開することです:

  1. s に新しく1文字を挿入すると t になる、
  2. もしくは、s の既存の1文字を削除すると t になる、
  3. もしくは、s の既存の1文字を置換すると t になる

三つの式が「もしくは」(OR)で結ばれている事に注目してください。 つまり、この三つの式を個別に検証して、 ひとつでも成り立つ(あるいはすべて成り立たない)ことが分かれば、 もとの命題の真偽を判定できることになります。

問題となるのは、この個々の式の真偽を評価する具体的な方法です。

式を効率的に評価するテクニック

ここで、編集操作と文字列の長さの関係に注目しましょう。 文字列 s,t の長さをそれぞれ n,m (n ≧ m) とおきます。

文字列 s に、任意の一文字を「挿入」したとすると、 操作後の文字列の長さは n+1 になります。 同様に s から一文字「削除」すれば、長さは n-1 となります。 「置換」操作の場合は、長さは n のままです。 このように、編集操作によって、文字列の長さに与える影響は異なります。

この観察を踏まえると、文字列 s・t の長さを見れば、 前節の式の真偽をおおまかに判定できることが分かります。 例えば、ふたつの文字列の長さが等しいとすると、 「挿入」と「削除」は選択肢からすぐに除外できます。 どのように操作を適用しても n ≠ m となるからです。 したがって、三つの式のうち「置換」の条件だけを評価すれば、 もとの命題の真偽を判定できます。

同様の理屈で、s が t よりも一文字だけ長いとすると、 「挿入」と「置換」について見る必要はなく、 「削除」についてのみ検討を加えれば十分になります。 さらに、s が t よりも二文字以上長いとすると、それ以上の検証は必要なく、 もとの命題は即座に偽と判定できます。

以上の観察を表の形に整理すると、次のようになります:

文字列の長さ検証が必要な操作パターン
n - m > 1(なし)
n - m = 1削除
n - m = 0置換

ここまでの議論を「文字列 s・t の間のLevenshtein距離が2である」 というケースに拡張してみましょう。 この命題を定義に従って展開すると、 組み合わせの計算により(OR条件で結ばれた)6つの式が生じます。 ここに先ほどの文字列長による論法を適用すると、次の表が得られます:

文字列の長さ検証が必要な操作パターン
n - m > 2(なし)
n - m = 2(削除 + 削除)
n - m = 1(削除 + 置換)
n - m = 0(置換 + 置換) or (挿入 + 削除)

この作業を繰り返せば、同様の表を任意の編集距離 k に対して作成できます。

厳密に式を評価する

検証領域を絞り込むことができたので、 あとは「表の操作パターンのどれかで s を t に変換できるか?」 を判定できればよいわけです。 編集距離 k の表を前提とすると、 この判定処理は次のアルゴリズムで実現できます:

このアルゴリズムを、表から導き出されるすべての選択肢に適用して、 結果値 d の最小値 dmin が k 以下であれば、 もとの命題が真だと判定できます。 ちなみに、このアルゴリズムの一回あたりの計算コストは、たかだか O(n+m) です。

このアルゴリズムは実務的に有用な性質を備えています:

  1. dmin ≦ k である時、 dmin は s・t 間のLevenshtein距離となります。 たとえば k=2 の表を使って計算を行い、 dmin=1 が得られた場合、 その結果をもって、入力文字列の編集距離は 1 と判定できます。
  2. dmin > k である時、 dmin は s・t 間のLevenshtein距離とは限りません。 たとえば k=2 の表に対して、dmin=3 が得られたとしても、 入力文字列の編集距離が正確に 3 かは分かりません。 この場合は、少なくとも 2 を上回る距離にあると判断できるのみです。

すなわち、k を上限として編集距離を測定したい場合、 1 から k までの個別の命題を立てる必要はないわけです。 上限 k の表について計算を行えば、(1) の性質より、 それ以下の編集距離については一括して測定できるからです。

速度測定

本節では、この記事で紹介した計算モデルの簡単な性能試験を行います。

SCOWL から取得した英単語辞書 (99,171語) を利用し、ランダムに選んだ入力語に対して、 編集距離が 2 以下となるすべての単語を辞書から抽出します。 この抽出処理にかかった時間を、Wagner-Fischer法を用いた場合と比較します。

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

試験環境

試験結果

試験結果表

入力語本記事のアルゴリズムWagner-Fischer法
meteorites0.22秒5.03秒
triplet0.25秒3.94秒
expands0.25秒3.89秒
deputizing0.22秒4.97秒
horizontally0.13秒3.35秒
gecko0.16秒1.68秒
iffy0.11秒0.85秒
平均値0.19秒3.38秒

試験結果のグラフ

実装案内

polylevenライブラリに本記事で紹介したアルゴリズムが導入されています:

https://github.com/fujimotos/polyleven

また、distanceパッケージにも本アルゴリズムの実装が収録されてます (fast_comp関数):

https://github.com/doukremt/distance

リファレンス実装としては、以下のPython実装があります (こちらの実装はDamerau-Levenshtein距離に対応しています):

https://github.com/fujimotos/mbleven


Top