読み方 ： へんしゅうきょり

編集距離とは？

操作の種類は、文字を加える「挿入」、文字を取り除く「削除」、文字を別の文字に書き換える「置換」の三つである。例えば、「さくら」を「さくらんぼ」に変えるには「ん」と「ぼ」の二文字を末尾に挿入するだけでよく、編集距離は2となる。この概念を1965年に考案したソビエトの数学者ウラジーミル・レーベンシュタインの名をとって、「レーベンシュタイン距離」とも呼ばれる。

計算には「動的計画法」（dynamic programming）と呼ばれる手法が使われる。二つの文字列の部分的な変換結果を行列のマス目に順番に記録していき、最終的に右下のマスに編集距離が求まる仕組みである。文字列が長くなるほど処理時間は増えるが、一般的な長さであれば実用上の支障はない。

どの操作も一回につきコスト1として数えるのが基本だが、誤りの起こりやすさや重要度に応じて操作ごとに異なるコストを設定する変種も存在する。隣り合う二文字の入れ替えを操作に加えた「ダメラウ＝レーベンシュタイン距離」のように、用途に合わせて操作の種類を拡張した手法も開発されており、キーボード入力のタイプミスを検出する場面ではこちらが適していることも多い。

身近な応用例として、文書作成ソフトのスペルチェックや検索エンジンの「もしかして」提案（サジェスト機能）がある。利用者が入力した語と辞書内の語との編集距離を計算し、距離の小さい候補を修正案として示す仕組みである。また、文章の盗用検知やソースコードの差分表示ツールにも組み込まれており、どの部分がどの程度変わったかを定量的に示す手段として機能している。

生命科学の分野では、DNAの塩基配列やタンパク質のアミノ酸配列を長い文字列と見なし、配列間の差を編集距離として算出する。塩基の置き換わりや欠失を文字の操作に対応させることで、個体間や種間の類縁関係を数値で評価したり、進化の過程でいつ頃枝分かれしたかを推定する手がかりにしたりすることができる。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。