編集距離の算出

平成26年度秋期基本情報技術者試験に出題された「編集距離の算出」のアルゴリズムを MATLAB で作成してみた。

編集距離とは

二つの文字列の差異を測る指標に編集距離がある。

編集距離の概念は，文書比較や検索キーワードの候補の提示などに用いられている。

編集距離とは，1 文字の追加操作又は削除操作を繰り返し適用し，ある文字列を別の文字列に変換するのに必要な最小の操作回数である。

例えば，文字列 “abcabba” を文字列 “cbabac” に変換する場合，下表に示す操作 1 ～ 5 によって変換が完了する。

下表は，最小の操作回数で変換する一例を示しており，編集距離は 5 となる。

操作 No.	操作後の文字列	操作内容
1	bcabba	1 文字目の a を削除
2	cabba	1 文字目の b を削除
3	cbabba	1 文字目の c の後ろに b を追加
4	cbaba	5 文字目の b を削除
5	cbabac	5 文字目の a の後ろに c を追加

表　文字列 “abcabba” を文字列 “cbabac” に変換する場合の例

MATLAB で作成したプログラム

二つの文字列間の編集距離を返す関数を MATLAB で作成した。

引数の仕様は，次のとおりである。

疑似言語において，各配列の添字は，0 から始まっているが，MATLAB では，各配列の添字は，1 から始めている（MATLAB では配列の添字を 0 とすることはできないため）。

引数名／返却値	データ型	意味
Str1	文字列	変換元の文字列 “abcabba” が格納されている 1 次元配列次元は 1 × 7 である
Str1Len	整数型	変換元の文字列の長さ（1 以上）長さを返却する関数 length により，Str1 の長さを求めている
Str2	文字列	変換先の文字列 “cbabac” が格納されている 1 次元配列次元は 1 × 6 である
Str2Len	整数型	変換先の文字列の長さ（1 以上）長さを返却する関数 length により，Str2 の長さを求めている
返却値 D(Str1Len+1,Str2Len+1)	整数型	編集距離を返却値として返す
返却値 alpha	整数型	α の実行回数を返却値として返す
返却値 beta	整数型	β の実行回数を返却値として返す

作成した MATLAB プログラムを示す。

Str1 = "abcabba";
Str2 = "cbabac";

Str1Len = length(Str1);
Str2Len = length(Str2);

D = zeros(Str1Len + 1, Str2Len + 1);
alpha = 0;
beta = 0;

% Initialize the first row and column
for X = 1:Str1Len + 1
    D(X, 1) = X - 1;
end
for Y = 1:Str2Len + 1
    D(1, Y) = Y - 1;
end

% Fill in the rest of the matrix
for X = 2:Str1Len + 1
    for Y = 2:Str2Len + 1
        if Str1(X - 1) == Str2(Y - 1)
            D(X, Y) = min([D(X - 1, Y - 1), D(X, Y - 1) + 1, D(X - 1, Y) + 1]);
            alpha = alpha + 1;
        else
            D(X, Y) = min([D(X, Y - 1) + 1, D(X - 1, Y) + 1]);
            beta = beta + 1;
        end
    end
end

% Display the results
D(Str1Len + 1, Str2Len + 1)
alpha
beta

上記のコードを実行した結果を示す。