アルゴリズム・データ構造図鑑 · 基礎から応用へ

編集距離の動的計画法:接頭辞同士の最小編集を積み上げる

挿入・削除・置換の漸化式を使い、距離だけの計算と編集列の復元、文字単位の違いを整理する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. どの編集操作を一回と数えるか
  2. 接頭辞の表へ分解する
  3. kittenからsittingへ変える
  4. 領域削減と文字の仕様
  5. この記事をロゲイアに質問する理解を確かめる

どの編集操作を一回と数えるか

ここでは文字の挿入、削除、置換をそれぞれ費用1とするLevenshtein距離を考えます。同じ文字を対応させる費用は0です。隣接二文字の交換を一回とする操作は含めず、それを許す距離とは区別します。文字列の類似度を測る方法はほかにもありますが、許した操作と費用が変われば答えも変わります。例えばabからbaへは置換二回で費用2であり、交換一回の費用1ではありません。最短の編集回数が小さいことと、意味が近いことは同じではありません。

接頭辞の表へ分解する

D[i][j]を先頭i文字から先頭j文字へ変える最小費用とします。空文字列との境界はD[i][0]=i、D[0][j]=jです。内部では、削除D[i−1][j]+1、挿入D[i][j−1]+1、対応D[i−1][j−1]+cの最小を取り、cは二文字が同じなら0、違えば1です。各候補は最後に行った操作の違いなので、可能な編集列を漏らさず短い接頭辞の答えへ結びつけられます。表を埋める順番では、参照する上、左、左上のセルが既に計算済みである必要があります。

kittenからsittingへ変える

kittenの先頭kをsへ置換してsitten、eをiへ置換してsittin、末尾へgを挿入してsittingとすれば費用3です。動的計画法でもこの最小値を求められます。末尾だけを眺めて差を数えるのではなく、一文字の挿入で以後の対応位置がずれる可能性を表で扱います。実際の編集列が必要なら、各セルで選んだ前のセルへ最終位置から戻ります。同じ最小値を与える候補が複数ある場合には、複数の最適な編集列が存在することもあります。

領域削減と文字の仕様

長さmとnの全表は時間O(mn)、領域O(mn)です。距離の値だけなら直前行と現在行を保持してO(min(m,n))領域へ減らせますが、そのままでは全編集列の復元情報は残りません。費用の対称性を仮定して行と列を交換する場合も、操作費用が異なる版へ安易に広げないでください。Unicodeではコードポイントが同じ見た目の文字単位とは限らず、正規化の有無でも距離は変わります。空文字列、同一文字列、挿入だけの例、交換を一回と誤認しやすい例で仕様を検証します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ