ハミング距離

AWK Users JP :: グレイコードでグレイコードを計算しましたが、グレイコードはグレイコード - Wikipedia にもあるようにハミング距離が 1 のものです。 そこで今回はハミング距離そのものを出力するプログラムを作ります。

以前、AWK Users JP :: ナイツ関数（ボケの方）を解いてみるなどでレーベンシュタイン距離を使いましたが、ハミング距離とはレーベンシュタイン距離の一部であり、置換だけの距離ですから、プログラムも簡単になっています。

#! /usr/local/bin/nawk -f
# hamming_distance.awk
# ハミング距離を計算する
# usage: nawk -f hamming_distance.awk str1 str2

BEGIN {
    str1 = ARGV[1];
    str2 = ARGV[2];

    num_str1 = split(str1, arr_str1, "");
    num_str2 = split(str2, arr_str2, "");

    if (num_str1 != num_str2) {
        print "Please use Levenshtein distance." > "/dev/null";
        exit;
    }

    for (i = 1; i <= num_str1; i++) {
        if (arr_str1[i] != arr_str2[i]) {
            hamming_distance++;
        }
    }

    print hamming_distance;
}

実際にハミング距離の例を解いてみます。

$ nawk -f hamming_distance.awk 1011101 1001001
2

$ nawk -f hamming_distance.awk 2143896 2233796
3

$ nawk -f hamming_distance.awk toned roses
3

特に関数化していませんが、比較的簡単に関数化することも可能です。