編集距離（Edit Distance）

定義

2つの文字列 X と Y がどの程度異なっているかを示す指標として、編集距離（あるいはLevernshtein距離）がある。編集距離は、2つの文字列を同じにするために必要な操作（挿入，削除，置換）の最小回数として定義される。Levernshtein距離の呼称は、1965年に、2つの文字列の距離の概念を考案したロシアの学者ウラジミール・レーベンシュタインに由来する。

編集距離の応用分野

スペル・チェッカー

入力した文字列と辞書に記憶されている単語の文字列としての類似度（＝距離）に基づいて、あいまい検索を行い、類似した単語の候補を提示する。

表記ゆれ検出

「データベース」、「データ・ベース」「データーベース」といった、表記の違いを検出する。

同類の研究論文の検索や盗用の検知

文章を形態素解析し、形態素の並びの類似度（＝距離）に基づいて類似文章を検索する。距離が極めて近い場合は、盗用の可能性も考えられる。

編集距離の求め方

文字列X[1,…,m] と Y[1,…,n] の編集距離を D(m,n)で表すものとする。

この時、i(0≦i≦m)に対し、D(i,0)=i である。なぜなら、空文字とX[1]との違いは、X[1]という1文字が違う（1文字の挿入で同じになる）からD(1,0)=1である。同様に、X[1] とX[1,2]との違いは、X[2]という1文字が違うからD(2,0)= D(1,0)+1= 2である。

同様に、j(0≦j≦n) に対し D(0,j)=j である。なぜなら、空文字とY[1,…,j]との違いは、j文字が違うのでD(0,j)=j である。

X[1,…,i] と Y[1,…j] の編集距離をD(i,j) の計算方法は、次の場合分けができる。

・X[i]＝Y[j] のとき（同じ文字が、X[1,…,i-1] と Y[1,…,j-1]に挿入された場合）

　同じ文字が追加されたため、編集距離は変わらない。すなわち、D(i,j)= D(i-1,j-1) である。

・X[i]≠Y[j] のとき（異なる文字が、X[1,…,i-1] と Y[1,…,j-1]に挿入された場合）

　X[1,…,i-1] と Y[1,…,j-1]に異なる文字が挿入される場合である。X[1,…,i] とY[1,…j]が得られる過程としては、下記の場合がある。

ü X[1,…,i] とY[1,…,j-1]にY[j] を挿入してX[1,…,i] とY[1,…j]が得られた。この場合の編集距離は、D(i, j-1) に1加えた値。ここで、+1 はY[j] を挿入したコストである。

ü 同様に、Y[1,…,j]とX[1,…,i-1] にX[i]とを挿入してX[1,…,i] とY[1,…j] が得られた。この場合の編集距離は、D(i-1, j) に1加えた値。ここで、+1 はX[i] を挿入したコストである。

ü X[1,…,i-1] とY[1,…j-1] に、それぞれ、X[i]とY[j]を挿入してX[1,…,i] とY[1,…j]が得られた。この場合の編集距離は、D(i-1, j-1) に1加えた値。ここで、+1 はX[i] とY[j] の挿入を一つの操作とみなしたコストである。ただし、このコストを2とする計算法もある（参考：http://www.stanford.edu/class/cs124/lec/med.pdf）。