Jaro-Winkler 距離の計算

ナイツ関数（ボケの方）を解いてみるではレーベンシュタイン距離を用いて解きましたが、同じように文字列の近さを調べるものに Jaro-Winkler distance (英語) というものがあります。

何が違うかというと、Jaro-Winkler distance はある範囲にあるものが交換可能かどうかを見ていくため、文字のタイプミスのようなものを発見する際に用いられることが多いようです。 一方、レーベンシュタイン距離は 2 つの文字列全体を探索するのが特徴で、これらの特徴はコードにも現れます。

#! /usr/bin/gawk -f
# jaro-winkler.awk
# Ref.: http://en.wikipedia.org/wiki/Jaro-Winkler_distance
# Ref.: http://www.iugrina.com/files/JaroWinkler/JaroWinkler.php.IUGRINA

BEGIN {
    print JaroWinkler("MARTHA", "MARHTA");
    print JaroWinkler("DWAYNE", "DUANE");
    print JaroWinkler("DIXON", "DICKSONX");
}

function getCommonCharacters(string1, string2, allowedDistance, \
                             str1_len, str2_len) {
    str1_len = split(string1, a_string1, "");
    str2_len = split(string2, a_string2, "");
    temp_string2 = string2;
    split(temp_string2, a_temp_string2, "");
    commonCharacters = "";
    for (i = 1; i <= str1_len; i++){
        noMatch = 1;
        for(j = max(1, i - allowedDistance); noMatch == 1 && \
            j <= min(i + allowedDistance, str2_len); j++) {
            if(a_temp_string2[j] == a_string1[i]) {
                noMatch = 0;
                commonCharacters = commonCharacters a_string1[i];
                a_temp_string2[j] = "";
            }
        }
    }
    return commonCharacters;
}

function Jaro(string1, string2,         str1_len, str2_len) {
    str1_len = split(string1, a_string1, "");
    str2_len = split(string2, a_string2, "");
    distance = int(min(str1_len, str2_len) / 2);
    commons1 = getCommonCharacters(string1, string2, distance);
    commons2 = getCommonCharacters(string2, string1, distance);
    split(commons1, a_commons1, "");
    split(commons2, a_commons2, "");
    if ((commons1_len = length(commons1)) == 0) {
        return 0;
    }
    if ((commons2_len = length(commons2)) == 0) {
        return 0;
    }
    transpositions = 0;
    upperBound = min(commons1_len, commons2_len);
    for (i = 1; i <= upperBound; i++) {
        if (a_commons1[i] != a_commons2[i]) {
            transpositions++;
        }
    }
    transpositions /= 2.0;
    print string1, string2 ":";
    printf("%s", "Jaro Score = (" commons1_len " / " str1_len " + " \
            commons2_len " / " str2_len " + (" commons1_len " - " \
            transpositions ") / " commons1_len ") / 3 = ");
    JaroScore =  (commons1_len / str1_len + commons2_len / str2_len + \
            (commons1_len - transpositions) / commons1_len) /3;
    print JaroScore;
    return JaroScore;
}

function getPrefixLength(string1, string2,      n) {
    MINPREFIXLENGTH = 4;
    n = min(MINPREFIXLENGTH, min(split(string1, a_string1, ""), \
        split(string2, a_string2, "")));
    for (i = 1; i <= n; i++) {
        if (a_string1[i] != a_string2[i]) {
            return i - 1;
        }
    }
    return n;
}

function JaroWinkler(string1, string2, JaroDistance, prefixLength) {
    PREFIXSCALE = 0.1;
    JaroDistance = Jaro(string1, string2);
    prefixLength = getPrefixLength(string1, string2);
    printf("%s", "Jaro Distance = " JaroDistance " + " prefixLength " * " \
           PREFIXSCALE " * (1 - " JaroDistance ") = ");
    return JaroDistance + prefixLength * PREFIXSCALE * (1.0 - JaroDistance);
}

function max(n, m) {
    if (n >= m) {
        return n;
    } else {
        return m;
    }
}

function min(n, m) {
    if (n <= m) {
        return n;
    } else {
        return m;
    }
}

ここでは例として、Jaro-Winkler distance に掲載されているものでテストしています。 また、コードは上記ページからのリンクにある PHP のコード (GPL) からの移植です。 実行してみましょう。

$ nawk -f jaro-winkler.awk
MARTHA MARHTA:
Jaro Score = (6 / 6 + 6 / 6 + (6 - 1) / 6) / 3 = 0.944444
Jaro Distance = 0.944444 + 3 * 0.1 * (1 - 0.944444) = 0.961111
DWAYNE DUANE:
Jaro Score = (4 / 6 + 4 / 5 + (4 - 0) / 4) / 3 = 0.822222
Jaro Distance = 0.822222 + 1 * 0.1 * (1 - 0.822222) = 0.84
DIXON DICKSONX:
Jaro Score = (4 / 5 + 4 / 8 + (4 - 0) / 4) / 3 = 0.766667
Jaro Distance = 0.766667 + 2 * 0.1 * (1 - 0.766667) = 0.813333

ここではスコアと距離の 2 つを表示するようにしてみました。 また、理解を深めるために式も表示してあります。

プログラムに解かせるのも面白いのですが、実際に紙と鉛筆でも求めることができます。