perlで行うDPマッチング

はじめまして。
現在、DPマッチングを行うプログラムを作りたいと思っています。
http://chalow.net/2007-01-22-4.html
上記のサイトを参考にしていたのですが、
掲載されているプログラムを実行すると、先頭と末尾のマッチしていない部分が
省略されて結果が出力されてしまいます。
先頭・末尾の不一致部分も出力するには、どのように改変すれば良いのでしょうか。
教えていただけると嬉しいです。
是非ともご教授のほどよろしくお願い申し上げます。

＜追記＞
argiusさん、説明不足で申し訳ありません。
上記サイトのDPマッチングは、二つの文字列を比較し、
この文字は一致していて、この文字は置換されており、この文字は削除されている、この文字は追加されている…という結果を出力します。
例えば、「survey」と「surgey」を比較すれば、「vとgが置換されている」、と結果として出力されます。
しかし、上記サイトのプログラムのままでは、「survey」と「foosurgeybar」を比較しても、
先頭・末尾の挿入部分が無視され、「vとgが置換されている」、と結果として出力されます。
これを、「fooが挿入されている」「barが挿入されている」という結果も出力するようにしたいです。
わかりづらくて大変申し訳ありません。

argius

2015/09/13 10:58

私はDPマッチングは詳しくないのですが... 「先頭と末尾のマッチしていない部分」の箇所の意味が良く分からないので、もう少し詳しく教えてください。

行動規範の内容に同意します

回答1件

ベストアンサー

あまりスマートなやり方では無いかもしれませんが、こんな感じでどうでしょう。

ポイントは、下記です。

traverse関数にテキストの文字数($#text)を探索開始位置($k)として渡し、関数内でそれとテキスト開始位置($j)を比較して、スタート位置より前なら末尾の不一致なので、そこから$jの位置までを全て"insert"にする。$kが未定義の場合は無視する。
同じくtraverse関数にて、パターンの開始位置($i)がゼロになった箇所より前は先頭の不一致なので、そこから$jがゼロになるまでを全てinsertにする。

※順番は後ろから前へ

以下、書き換えたコードを示します。

lang
1# (前半省略)
2# ここまではそのまま
3
4# マッチ箇所取り出し
5# my @results = traverse($#key, $start);
6my @results = traverse($#key, $start, $#text);
7
8sub traverse {
9#    my ($i, $j) = @_;
10#    return if ($i == 0 or $j == 0);
11    my ($i, $j, $k) = @_;
12    return if ($j == 0);
13
14    if ($i == 0) { # 範囲外(先頭)
15        my @rv = traverse(0, $j-1, 0);
16        return @rv, {token => $text[$j], tag => "insert"};
17    }
18    elsif (defined $k && $j < $k) { # 範囲外(末尾)
19        my @rv = traverse($i, $j, $k-1);
20        return @rv, {token => $text[$k], tag => "insert"};
21    }
22
23# ここからはそのまま
24    my ($u, $l, $d) = ($C[$i-1][$j], $C[$i][$j-1], $C[$i-1][$j-1]);
25
26# (後半省略)