文字列間補正問題

文字列間補正問題とは、一方の文字列を他方の文字列に変換するために必要な最小コストの「編集操作」の連続によって測定される、二つの文字列間の距離を決定する問題である。検討される編集操作には、文字列の1つの記号を他の単一記号に変える操作、文字列から1つの記号を削除する操作、または文字列に単一記号を挿入する操作が含まれる。本稿では、この問題を二つの文字列の長さの積に比例した時間で解くアルゴリズムを提示する。応用としては、自動スペル訂正問題や二つの文字列に共通する最長部分文字列を決定する問題などが考えられる。