Hatena::ブログ(Diary)

日本 GNU AWK ユーザー会 0.2 このページをアンテナに追加 RSSフィード

2007-11-18

[]Levenshtein 距離

f:id:Rocco:20071005230008p:image:w100:right

以前も書いたものですが、再び登場します。

#! /usr/bin/gawk -f
BEGIN {
    str1 = ARGV[1] "";
    str2 = ARGV[2] "";
    print levenshtein_distance(str1, str2);
}
### 2 つの文字列のレーベンシュタイン距離を返す
### http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2
function levenshtein_distance(s1, s2) {
    len_s1 = length(s1);
    len_s2 = length(s2);
    split(str1, a_str1, "");
    split(str2, a_str2, "");
    for (i = 0; i <= len_s1; i++) {
        distance[i, 0] = i;
    }
    for (j = 0; j <= len_s2; j++) {
        distance[0, j] = j;
    }
    for (i = 1; i <= len_s1; i++) {
        for (j = 1; j <= len_s2; j++) {
            if (a_str1[i] == a_str2[j]) {
                cost = 0;
            } else {
                cost = 1;
            }
            distance[i, j] = min3(distance[i - 1, j    ] + 1,\
                                  distance[i    , j - 1] + 1,\
                                  distance[i - 1, j - 1] + cost);
        }
    }
    return distance[len_s1, len_s2];
}
### 3 つの最小値を返す
function min3(a, b, c,    min) {
    min = a;
    if (b <= min) {
        min = b;
    }
    if (c <= min) {
        min = c;
    }
    return min;
}

飼育しているヘルマンリクガメが口から血を流していたので、急遽、御茶ノ水レプタイルクリニック に連れて行ったのですが、その際に嫁が「高田馬場」と「御茶ノ水」って似てるよねと言ったので思い出しました。

$ gawk -f levenshtein_distance.awk たかたのばば おちゃのみず
5

要するに文字距離が 5 なので、というか要するに「の」しか合っていません。orz

結局ヘルマンリクガメの太郎丸は・・・

ヘルマンリクガメの太郎丸 (後からメスと分かったのですが命名が先でした) 方はかなりひどい口内炎で、注射をしてもらい、しばらく薬で様子を見ることにしました。実は近所の超有名爬虫類病院 (テレビでも紹介されたことあるくらい有名です) に行かないのにはわけがあります。

違いは「愛」なのですが、約 6 年前に目から泡を吹いていて、最初に近所で診てもらったときに「もうこりゃダメだね。すぐ死ぬよ」と言われたのに対し、「レプタイルクリニック」では「大丈夫でしょう。ひととおり検査しておきますね」と言って、診察が終わった後にすーっと「かわいいねぇ」を連呼しているあたりに愛の差があるんだと思います。(実際に「レプタイルクリニック」が正しい診断をしているわけですが、人間で前者のような診察をされたら大問題になると思います)

これは仕事も同じで、「ダメ」でスタートしたらダメなのです。何も見ないで判断したらダメだと思います。

そんな中、来週末は法事で田舎に戻らなければならず不安です。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/Rocco/20071118/p2