編集距離 (Levenshtein Distance)

昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。

編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。

例えば

という具合です。

編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。

編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが良く知られています。その考え方は LCS長の計算と非常に良く似ています。二つの系列 X, Y の LCS長を求めるには X の長さ i までの部分系列 Xi, Y の長さ j までの部分系列 Yj の LCS長を LCS(i, j) としたとき、一つ前の要素までの LCS長 LCS(i - 1, j - 1), LCS(i - 1, j), LCS(i, j - 1) を使って求めることができたのでした。編集距離も同じように、二つの文字列のそれぞれ i 番目と j 番目の編集距離 LD(i, j) を求めるのに一つ前の文字までの編集距離 LD(i - 1, j - 1), LD(i - 1, j), LD(i, j - 1) を使って算出することができます。

LCS長は"最長"共通部分系列の計算、編集距離は"最小"の手順回数の計算です。いずれも最大もしくは最小つまり最適解を求める問題で、ある問題がその部分問題の最適解によって計算できるという点で共通しています。このような特性を部分問題最適性と言います。部分問題最適性を持つ問題はその部分問題の重複度合いが高い、つまり何度も同じ部分問題の最適化を参照するような場合に DP が有効です。(同時に部分問題最適性は貪欲アルゴリズム (Greedy Algorithm) を適用できる可能性も示唆します。)

編集距離計算の考え方

編集距離の計算の考え方については レーベンシュタイン距離の求め方について教えてください - Yahoo!知恵袋 での質問への回答が非常に分かりやすかったです。是非併せてご一読ください。以下、この回答例を参考にさせていただきます。

という二つの単語の編集距離 LD("apple", "play") を求めます。

このとき、apple, play それぞれの一文字前までの編集距離として以下の3通りが考えられます

  • LD("appl", "play")
  • LD("apple, "pla")
  • LD("appl", "pla")

これらの値が既に既知であったとしましょう。LD("apple", "play") を求めるのに、うまくこの 3 つの値を使うことを考えます。つまり、既に分かっている直前の部分問題の最適解に {挿入, 削除, 置換} いずれかの操作を加えて LD("apple", "play") の最適解を求めるのです。

  • LD("appl", "play") に "e" を挿入(+1)で LD("apple", "play") になる → LD("apple", "play") = LD("appl", "play") + 1
  • LD("apple, "play") から "y" を削除で LD("apple", "pla") になる、すなわち LD("apple", "pla") は削除操作一回(+1)で LD("apple", "play") と同じ → LD("apple", "play") = LD("apple", "pla") + 1
  • LD("appl", "pla") の次の文字を置換 (+1) で LD("apple", "play") になる → LD("apple", "play") = LD("appl", "pla") + 1
    • ただし、次の文字が等しい場合は置換の必要がない → 例 LD("apple", "plane") = LD("appl", "plan") + 0

これらの関係から、LCS長の時同様、再帰的な漸化式が得られそうなのは直感的に分かります。上記3パターンを i 番目, j 番目までの編集距離 LD(i, j) で一般化してみます。

  • LD(i, j) = LD(i - 1, j) + 1
  • LD(i, j) = LD(i, j - 1) + 1
  • LD(i, j) = LD(i - 1, j - 1) + α, ただし α = 0 または 1 (i, j 番目の文字が等しい場合は 0)

となります。編集距離は最小手順ですから、最適解はこの3つの値のうち最小のものになります。結局 LD(i, j) を求めるには LD(i - 1, j -1), LD(i - 1, j), LD(i, j -1) が分かっていれば良いことが分かります。予想通り、再帰的な漸化式になっています。DP 的には、ここまで来ればあとは簡単です。

i, j は任意ですので LD(i - 1, j -1), LD(i - 1, j), LD(i, j -1) もまたより小さな LD(i', j') から求まります。つまり編集距離 LD(i, j) を求めるには部分問題の最適解を再帰的に求めていくことで計算できるわけです。なお、LD(0, 0) = 0, LD(i, 0) = i, LD(0, j) = j なのは自明です。

ここはLCS長のときの

LCS(i, j) の i, j は任意ですから、LCS(i - 1, j - 1) や LCS(i, j -1), LCS(i - 1, j) もまたより小さな LCS(i', j') から求まります、つまり LCS 長を求める問題は部分問題の最適解を再帰的に求めていくことで計算できるわけです。なお LCS(0, 0), LCS(i, 0), LCS(0, j) はいずれかの系列の要素が空なのでいずれもLCS長が 0 です。

と全く同じです。

これらの考え方により、結果として DP のよくあるパターン、

  • i行j列の2次元の表を用意して
  • 自明な既知の値 (今回は LD(0, 0) = 0, LD(i, 0) = i, LD(0, j) = j) を基点に
  • i, j の昇順に既知の値だけを使って最適解 (編集距離では最小値) を計算していく
    • 最適解 … 2次元の表の min{左 + 1, 上 + 1, 左上 + if (i番目j番目の文字が等しい) then 0 else 1 }

で編集距離が求まることが分かります。

Python による実装

参考までに DP による編集距離の実装を Python で書いてみました。

#!/usr/bin/env python

def levenshtein_distance(a, b):
    m = [ [0] * (len(b) + 1) for i in range(len(a) + 1) ]

    for i in xrange(len(a) + 1):
        m[i][0] = i

    for j in xrange(len(b) + 1):
        m[0][j] = j

    for i in xrange(1, len(a) + 1):
        for j in xrange(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                x = 0
            else:
                x = 1
            m[i][j] = min(m[i - 1][j] + 1, m[i][ j - 1] + 1, m[i - 1][j - 1] + x)
    # print m
    return m[-1][-1]

import sys

s1 = sys.argv[1]
s2 = sys.argv[2]

print levenshtein_distance(s1, s2)

説明は長いのに実装するとあっけないというのは DP でよくあることです。実行結果は以下のようになります。

% python levenshtein.py apple play
4
% python levenshtein.py perl pearl
1

Perl による実装

Perl での実装も紹介しておきます。こちらは日本語 (Unicode) も対応です。

use List::Util qw/min/;
use Params::Validate qw/validate_pos/;

sub levenshtein_distance {
    my ($s1, $s2) = validate_pos(@_, 1, 1);
    my $m = [];

    my @s1 = split //, $s1;
    my @s2 = split //, $s2;

    for (my $i = 0; $i <= @s1; $i++) {
        $m->[$i]->[0] = $i;
    }

    for (my $j = 0; $j <= @s2; $j++) {
        $m->[0]->[$j] = $j;
    }

    for (my $i = 1; $i <= @s1; $i++) {
        for (my $j = 1; $j <= @s2; $j++) {
            my $diff = ($s1[ $i - 1 ] eq $s2[ $j - 1]) ? 0 : 1;
            $m->[$i]->[$j] = min(
                $m->[$i - 1]->[$j - 1] + $diff,
                $m->[$i - 1]->[$j] + 1,
                $m->[$i]->[$j - 1] + 1
            );
        }
    }

    return $m->[-1]->[-1];
}

なお CPAN には Text::Levenshtein や Text::LevenshteinXS など編集距離を算出するモジュールがあります。

Kansai.pm#11 での編集距離の話題

先日の Kansai.pm#11 では編集距離を用いたスペルミス修正プログラムのアルゴリズムについて発表しました (こちらでは Jaro-Winkler 距離の話題も扱っています) ので興味のある方は併せてご覧ください。

また、編集距離計算のアルゴリズムチューニングについては同じく Kansai.pm#11 での PFI の吉田さんによる発表 Cell Challenge 2009 参加記 が面白いです。マルチコアプロセッサの Cell での計算速度を競う Cell Challenge 2009 のテーマは編集距離計算だったそうで、ビット並列化によるアルゴリズムの改善とマルチコア向け最適化を行い大幅な速度向上を達成された様子が解説されています。気になる大会の結果は、吉田さんのチームが優勝だったそうです。おめでとうございます。

参考文献