ナイツ関数（ボケの方）を解いてみる

ナイツ関数（ボケの方）を解いてみます。 今から 10 年以上前に月刊「アスキー」で awk (jgawk) の MS-DOS 版のバイナリーがフロッピーでおまけで付いてきていた時代がありました。 その中に jgawk を使ったプログラムで似たようなものが掲載されていました。

個人的な話ですが、その際に東大文学部の友人が「これは凄いよ」と言っていた記憶がありますが、当時の私にはそのアルゴリズムを理解できなかった記憶があります。 そういう意味では十数年目のリベンジになります。

解き方としては「レーベンシュタイン距離 (Levenshtein Distance)」を用います。 これは文字の入れ替え (置換、追加、削除など) の手順を何度行えば同じになるかという手順数を表すもので、知っておくと便利なものです。

ここでは同じ文字数でレーベンシュタイン距離が 2 以下のものに置換を行うのですが、そのまま置換すると元の文書が分からなくなるので、故意に「元の文字列(置換後の文字列)」というフォーマットにして出力させています。

また、単語リストは一旦配列に格納するため、メモリを大幅に消費しますので、非力なマシンでの実行は注意してください。

#! /usr/bin/gawk -f
# nights_function.awk

BEGIN {
    # 以下のようにしてワードリストファイルを用意したものを使う
    #   $ nkf -w --overwrite fam*txt
    #   $ dos2unix fam*txt
    #   $ $ awk -v OFS='\n' -v ORS='\n' '$1=$1' fam*.txt > fam.txt
    word_list_file = "fam.txt";

    dist = 2;

    while (getline < word_list_file > 0) {
        word_list[i++] = $0;
    }
    close(word_list_file);
}

{
    for (i = 1; i <= NF; i++) {
        for (idx in word_list) {
            if (levenshtein_distance($i, word_list[idx]) <= dist &&\
                length($i) == length(word_list[idx])) {
                $i = $i "(" word_list[idx] ")";
                ## $i = word_list[idx];
                break;
            }
        }
        printf("%s ", $i);
    }

    print "";
}

# 2 つの文字列のレーベンシュタイン距離を返す
# http://tinyurl.com/5mnwo2
function levenshtein_distance(s1, s2,   a_str1, a_str2, i, j) {
    len_s1 = length(s1);
    len_s2 = length(s2);
    split(s1, a_str1, "");
    split(s2, 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;
}

さて、実際に実行してみましょう。 出力例とは若干異なるのですが、気にしないでください。

$ cat input.txt
ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
 プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス

$ time gawk -f nights_function.awk input.txt
ドウカク(ドクヤク) org ヘ ヨウコソ(ヨワミソ)
コノ サイト ハ ダサレタ(ヤサガタ) オダイ ヲ イカニ トクカ キソイアウ
プログラマ ノ タメノ コロシアム デス
トウコウ(トウミン) ヲ タメシテ(タイシツ) ミタイ カタ ハ テスト
トリアエズ ナガメテ(ハナガメ) ミタイ カタ ハ ゲンゴ ノ イチラン(イチハツ) ガ オススメ(エビスメ) デス
gawk -f nights_function.awk input.txt  5.39s user 0.01s system 99% cpu 5.441 total

こんな感じに出力されます。

どうしても配列 (awk の場合には連想配列) の呼び出しに時間がかかってしまうため、処理時間は他の言語よりも長くなります。

tag_gawk.pngtag_gawk.png