levenshtein-distance - ダメラウ・レーベンシュタイン php

Question

PHP 用のDamerau-Levenshteinアルゴリズムの実装を探していますが、友人の Google では何も見つからないようです。これまでのところ、PHP で実装されたレーベンシュタイン (Damerau 転置なし、これは非常に重要です) を使用するか、元のソース コード (C、C++、C#、Perl) を入手して、それを PHP に書き込む (翻訳する) 必要があります。

PHP の実装に関する知識を持っている人はいますか?

私は社内イントラネットの "もしかして:" 拡張機能に soundex と double metaphone を使用しており、Damerau-Levenshtein アルゴリズムを実装して、結果をより適切に分類できるようにしたいと考えています。このアイデアに似たもの: http://www.briandrought.com/blog/?p=66、私の実装は最初の 5 つのステップに似ています。

Answer 1

私は戻ってきたときに再帰的な解決策を突き刺しました。

/*
 * Naïve implementation of Damerau-Levenshtein distance
 * (Does not work when there are neighbouring transpositions)!
 */
function DamerauLevenshtein($S1, $S2)
{
    $L1 = strlen($S1);
    $L2 = strlen($S2);
    if ($L1==0 || $L2==0) {
        // Trivial case: one string is 0-length
        return max($L1, $L2);
    }
    else {
        // The cost of substituting the last character
        $substitutionCost = ($S1[$L1-1] != $S2[$L2-1])? 1 : 0;
        // {H1,H2} are {L1,L2} with the last character chopped off
        $H1 = substr($S1, 0, $L1-1);
        $H2 = substr($S2, 0, $L2-1);
        if ($L1>1 && $L2>1 && $S1[$L1-1]==$S2[$L2-2] && $S1[$L1-2]==$S2[$L2-1]) {
            return min (
                DamerauLevenshtein($H1, $S2) + 1,
                DamerauLevenshtein($S1, $H2) + 1,
                DamerauLevenshtein($H1, $H2) + $substitutionCost,
                DamerauLevenshtein(substr($S1, 0, $L1-2), substr($S2, 0, $L2-2)) + 1
            );
        }
        return min (
            DamerauLevenshtein($H1, $S2) + 1,
            DamerauLevenshtein($S1, $H2) + 1,
            DamerauLevenshtein($H1, $H2) + $substitutionCost
        );
    }
}

Answer 2

私たちの実装を見てみましょう(テストとドキュメント付き)。