「Modern Information Retrieval」(8.6.1 p.216) での
Dynamic Programming (DP) の解説のところのアルゴリズムを
素直に Perl で実装したみた。
さらにマッチ箇所取り出しロジックも実装してみた。

#


DP はいわゆる「類似文字列検索（あいまい検索）」に使うと
便利なalgorithm。
実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。
単純ながら使い勝手もよく、まさに現場向きかと。
grep 式に頭から見ていくので計算量的にはイマイチなのだが、
転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。

■定義みたいなの

Q1. 二つの文字列 "home" と "ahoge" はどれだけ類似しているか？
A1. こう考えてみる。
home の m を g に置き換えて、先頭に a と追加すると ahoge になる。
つまり「置き換え」と「追加・挿入」とで操作を計 2 回行ったわけだ。
てなわけで、この二つの文字列の「距離」を 2 と定義し、
どれだけ類似しているかの尺度として用いる。

Q2. "hemi" と "gome" はどちらがより "home" と似ているか？
A2. home の o を e に、 e を i に置き換えると hemi になるので
操作は 2 回（距離 = 2）。
home の h を g に置き換えると gome になるので操作は 1 回（距離 = 1）。
よって、"gome" の方が "hemi" よりも "home" に似ていると言える。

で、こういう類似文字列マッチをやるのが DP。

■説明

まずは、スコアテーブル C[i,j] を作成する。
Modern Information Retrieval での説明を一部改変して引用。
P[i]はパターン（キーワード）、T[j]は検索・マッチ対象のテキスト。

C[0,j] = 0
C[i,0] = i
C[i,j] = if (P[i] = T[j]) then C[i-1,j-1]
         else 1 + min(C[i-1,j],C[i,j-1],C[i-1,j-1])	        

P = "survey", T = "surgery" で作ったテーブルはこんな感じになる。
右下のマスの数字は、PとTが何文字違いかを表すもの（と、とりあえず
考えておこう）。

		s	u	r	g	e	r	y
	0	0	0	0	0	0	0	0
s	1	0	1	1	1	1	1	1
u	2	1	0	1	2	2	2	2
r	3	2	1	0	1	2	2	3
v	4	3	2	1	1	2	3	3
e	5	4	3	2	2	1	2	3
y	6	5	4	3	3	2	2	2

テーブルができてしまえばあとは簡単。
右下からスタートし、上・左・左上の中から最小スコアのマスを選んで
左上までたどっていけば、キーとテキストがどうマッチしたかが分かる。
上への移動はキー側の一文字を削除することを意味する。
左への移動はキー側へ一文字挿入することを意味する。
左上への移動は同じ文字か文字の置き換えを意味する。
コードでは関数 traverse の再帰呼び出しで実現している。

テーブルを見ながら確認してもらいたいのだが、
survey を surgery にするには、
(1) r を e と y の間に「挿入」し
  （または y を末尾に挿入し、その前の y を r に「置き換え」る）、
(2) v を g に「置き換え」る、
という操作をすればよいことが分かる。

通り道を図で表すとこんな感じ。

		s	u	r	g	e	r	y
	0
s		0
u			0
r				0
v					1
e						1	2
y								2

T が長い場合はスタート位置を工夫して、無駄な再帰が避けるとよいかと。
コード中で $start を設定している箇所と、
P = "survey", T = "foosurgerybar" でのテーブル（下記）を見ながら
考えてみよう！

		f	o	o	s	u	r	g	e	r	y	b	a	r
	0	0	0	0	0	0	0	0	0	0	0	0	0	0
s	1	1	1	1	0	1	1	1	1	1	1	1	1	1
u	2	2	2	2	1	0	1	2	2	2	2	2	2	2
r	3	3	3	3	2	1	0	1	2	2	3	3	3	2
v	4	4	4	4	3	2	1	1	2	3	3	4	4	3
e	5	5	5	5	4	3	2	2	1	2	3	4	5	4
y	6	6	6	6	5	4	3	3	2	2	2	3	4	5

はい、一番下の行の中で一番小さい数字のマスからスタートすればOK。
こんな感じに。

f

o

o

s

u

r

g

e

r

y

b

a

r

0

s

0

u

0

r

0

v

1

e

1

2

y

2

■コード

#!/usr/bin/perl
use strict;
use warnings;

my @key = qw/ s u r v e y /;
my @text = qw/ f o o s u r g e r y b a r /;
unshift @key, "";  # BK
unshift @text, ""; # BK

# スコアテーブルの作成
my @C;
for (my $j = 0; $j < @text; $j++) {
    $C[0][$j] = 0;
}
for (my $i = 0; $i < @key; $i++) {
    $C[$i][0] = $i;
}
for (my $i = 1; $i < @key; $i++) {
    for (my $j = 1; $j < @text; $j++) {
        my ($u, $l, $d) = ($C[$i-1][$j], $C[$i][$j-1], $C[$i-1][$j-1]);
        if ($key[$i] eq $text[$j]) {
            $C[$i][$j] = $d;
        } else {
            my $min = (sort {$a <=> $b} ($u, $l, $d))[0];
            $C[$i][$j] = 1 + $min;
        }
    }
}

# スコアテーブルの表示
print "      ".join("   ", @text),"\n";
for (my $i = 0; $i < @key; $i++) {
    printf " %1s  ", $key[$i];
    for (my $j = 0; $j < @text; $j++) {
        printf " %-3d", $C[$i][$j];
    }
    print "\n";
}

# マッチ箇所取り出し処理のスタート位置決定
my $start = $#text;
for (my $j = $#text; $j > 0; $j--) {
    if ($C[$#key][$j] < $C[$#key][$start]) {
         $start = $j;
    }
}

# マッチ箇所取り出し
my @results = traverse($#key, $start);

sub traverse {
    my ($i, $j) = @_;
    return if ($i == 0 or $j == 0);

    my ($u, $l, $d) = ($C[$i-1][$j], $C[$i][$j-1], $C[$i-1][$j-1]);
    my $min = (sort {$a <=> $b} ($u, $l, $d))[0];

    if ($min == $d) {
        my @rv = traverse($i-1, $j-1);
        return @rv, {token => $text[$j],
                     tag => ($d == $C[$i][$j]) ? "match" : "replace"};
    } elsif ($min == $l) {
        my @rv = traverse($i, $j-1);
        return @rv, {token => $text[$j], tag => "insert"};
    } else {
        my @rv = traverse($i-1, $j);
        return @rv, {token => "", tag => "delete"};
    }
}

# 結果表示
print join("", map {$_->{token}} @results),"\n";
print join(", ", map {"$_->{token}:$_->{tag}"} @results),"\n";

■実行例

% ./dp.pl
         f   o   o   s   u   r   g   e   r   y   b   a   r
     0   0   0   0   0   0   0   0   0   0   0   0   0   0
 s   1   1   1   1   0   1   1   1   1   1   1   1   1   1
 u   2   2   2   2   1   0   1   2   2   2   2   2   2   2
 r   3   3   3   3   2   1   0   1   2   2   3   3   3   2
 v   4   4   4   4   3   2   1   1   2   3   3   4   4   3
 e   5   5   5   5   4   3   2   2   1   2   3   4   5   4
 y   6   6   6   6   5   4   3   3   2   2   2   3   4   5
surgery
s:match, u:match, r:match, g:replace, e:match, r:insert, y:match

追記070123: 説明不足だったので「定義みたいなの」を追加。