fixedpoint.jp

Levenshtein Distance の動的計画法によるアルゴリズムの改善 (2009-02-27)

2つの文字列の Levenshtein distance の計算には、よく知られた動的計画法によるアルゴリズムがあります。このアルゴリズムでは、それぞれの文字列の長さを N, M とすると計算量が

• 時間: O(MN)
• 空間: O(M)

まで抑えられます。

今回考えた改善は以下のようなものです: 2つの文字列を S1, S2 とします。

1. S1, S2 の共通先頭列を取り去り、それぞれ T1, T2 とする。
2. T1, T2 の共通末尾列を取り去り、それぞれ U1, U2 とする。
3. U1-U2 の levenshtein distance を計算する。これが元の S1-S2 の levenshtein distance に等しい。

証明は、levenshtein distance の定義の対称性から、「T1-T2 の距離が S1-S2 の距離と等しい」ことを示せば十分です。

この改善は時間/空間ともに共通先頭列と共通末尾列が長ければ長いほど効いてきます。