« 起きたら夜続き | メイン | 皆さん忙しいみたい »
2008年11月08日
編集距離（レーベンシュタイン距離）の計算
文字列間の類似度を求める方法の一つとして、編集距離が挙げられます。編集距離は、考案者にちなみレーベンシュタイン距離とも呼ばれますが、具体的には、挿入や削除、置換によって、一方の文字列から他方の文字列に変換するために必要な作業の最小回数です。
use List::Util;
sub levenshtein_distance {
my ($list_1, $list_2) = @_;
my $len_1 = scalar(@{$list_1});
my $len_2 = scalar(@{$list_2});
my @d;
foreach my $i (0 .. $len_1) {
$d[$i][0] = $i;
}
foreach my $j (0 .. $len_2) {
$d[0][$j] = $j;
}
foreach my $i (1 .. $len_1) {
foreach my $j (1 .. $len_2) {
$d[$i][$j] = List::Util::min(
$d[$i - 1][$j] + 1,
$d[$i][$j - 1] + 1,
$d[$i - 1][$j - 1] + (($list_1->[$i - 1] eq $list_2->[$j - 1]) ? 0 : 1),
);
}
}
return $d[$len_1][$len_2];
}
Perl で書いてみるとこんな感じかな（Perl 5.8 標準ライブラリの List::Util が必要です）。配列のリファレンスで文字列を表現し、引数として受け取ります。文字列をスカラーで渡さないのは、文字列以外にも何らかの順序配列の編集距離を計算するのに利用するためです。
my $list_1 = [ 't', 's', 'u', 'k', 'u', 'b', 'a', ]; my $list_2 = [ 't', 'o', 'k', 'y', 'o', ]; print levenshtein_distance( $list_1, $list_2);
実際の利用例はこんな感じ。単純にテキスト間の編集距離を求めたいのであれば、Text::Levenshteinを利用するのが良いと思います。
この関数は、ウェブページを HTML 構造に基づきクラスタリングするために作成しました。HTML は DOM Tree と呼ばれる木構造で表現できますが、この木からブロック要素部分を後順走査で探索し（実際は HTML タグを上部から探索するので結果的に後順走査になるだけ）、その結果を配列として表現します（タグ名の配列を作る）。その配列同士の編集距離にを求めることは、HTML 構造に基づく類似度を求めることであり、結果的に HTML 構造に基づくクラスタリングが出来るのでは無いかと考えています。まぁ。ブラウザのレンダリングに大きな影響を与えないような部分木が存在する可能性もあり、要検討なのですがね。
木の編集距離の文字列の編集距離による近似という論文を見つけ、調査中。日本語論文だと思っていたら、英語論文だったので涙目（発表者が日本人で日本語タイトルなのに）。
【関連記事】
・コサイン尺度（コサイン類似度）の計算 （2008年11月04日）
【関連情報】
・レーベンシュタイン距離 - Wikipedia
http://ja.wikipedia.org/wiki/レーベンシュタイン距離
2008年11月08日 22:14 | Programming