たつをの ChangeLog

4 件 見つかりました。

Dynamic Programming による類似文字列マッチの実装例

2007-01-22-4 [Programming][Algorithm]

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



DP はいわゆる「類似文字列検索（あいまい検索）」に使うと
便利なアルゴリズム。
実は、大学院でも前の会社でも、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が何文字違いかを表すもの（と、とりあえず
考えておこう）。

surgery
00000000
s10111111
u21012222
r32101223
v43211233
e54322123
y65433222

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

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

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

surgery
0
s 0
u 0
r 0
v 1
e 12
y 2

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

foosurgerybar
00000000000000
s11110111111111
u22221012222222
r33332101223332
v44443211233443
e55554322123454
y66665433222345

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

foosurgerybar
0
s 0
u 0
r 0
v 1
e 12
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: 説明不足だったので「定義みたいなの」を追加。

この記事に言及しているこのブログ内の記事

無印良品の足なり直角靴下は快適だ！

2007-01-22-3 [Life]

一昨日の話。
くつしたに穴が開いてしまったので、無印良品で新しいのを物色。
直角に編んであって、かかとにもフィットするという触れ込みの
「足なり直角靴下」を買ってみました。

くつ下くつした

で、さっそく履いて過ごしているのですが、これが快適！
ずれたり、下がってくることもあまりなく、安心できるフィット感です。
500円だし、ちょっと試してみることをオススメ。

■足なりボーダー柄直角靴下


ref.
- [を] 足なり直角で五本指の靴下[2007-07-12-4]

この記事に言及しているこのブログ内の記事

Google AdSense の規約改定の話題

2007-01-22-2 [Affiliate]

メモ。秋元さんのブログのGoogle AdSense規約関連記事。
- Google AdSenseの規約がさらに窮屈に
  http://labs.cybozu.co.jp/blog/akky/archives/2007/01/
  google-adsense-new-rule.html
- Google AdSense規約改訂に関する続報
  http://labs.cybozu.co.jp/blog/akky/archives/2007/01/
  google-adsense-new-rule2.html

Amazon アソシエイトのレポートの更新が遅れている

2007-01-22-1 [Affiliate]

アソシエイト・セントラル　レポート更新遅延のお知らせ
http://affiliate-blog.amazon.co.jp/2007/01/post_5.html

現在アソシエイト・セントラルのレポートの更新が遅れており、
1月18日からのデータをご利用いただけない状態となっております。


毎日更新の売り上げレポートが一週間近く更新なしになっています。
今回は今までになく長いですよね。
まあ、のんびりと復旧待ち。

追記070123: 復旧しましたね。

たつをの ChangeLog

Powered by chalow