2

実際には、最後に一致するパーセンテージを取得する文字列比較を実装する必要があります(ブール結果の一致/不一致だけではありません)。そのために、私はレーベンスタイン距離アルゴリズムを見つけました。しかし、問題は現在、パフォーマンスにあります。たとえば、相互に比較する 1,000 個の文字列があり、現在は約 10 分かかります。それぞれについて、私はすでにアルゴを並行して呼び出しており、それぞれの中で並行して行われています。だから私は疑似言語になりました:

Foreach strings
    Call in parallel the comparaison method.

比較方法内

Foreach stringsToCompare
    Call in parallel the Levenstein Distance algo.

そして、i5 @ 2.6Ghz で 100% の CPU 使用率でまだ 10 分...

これが私の実装です

public static double GetSimilarity(string firstString, string secondString)
{
    if (ReferenceEquals(firstString, null)) throw new ArgumentNullException("firstString");
    if (ReferenceEquals(secondString, null)) throw new ArgumentNullException("secondString");
    if (firstString == secondString) return 100;

    return (1 - GetLevensteinDistance(firstString, secondString) / (double)Math.Max(firstString.Length, secondString.Length)) * 100;
}

private static int GetLevensteinDistance(string firstString, string secondString)
{
    if (ReferenceEquals(firstString, null)) throw new ArgumentNullException("firstString");
    if (ReferenceEquals(secondString, null)) throw new ArgumentNullException("secondString");
    if (firstString == secondString) return 1;

    int[,] matrix = new int[firstString.Length + 1, secondString.Length + 1];

    for (int i = 0; i <= firstString.Length; i++)
        matrix[i, 0] = i; // deletion
    for (int j = 0; j <= secondString.Length; j++)
        matrix[0, j] = j; // insertion

    for (int i = 0; i < firstString.Length; i++)
        for (int j = 0; j < secondString.Length; j++)
            if (firstString[i] == secondString[j])
                matrix[i + 1, j + 1] = matrix[i, j];
            else
            {
                matrix[i + 1, j + 1] = Math.Min(matrix[i, j + 1] + 1, matrix[i + 1, j] + 1); //deletion or insertion
                matrix[i + 1, j + 1] = Math.Min(matrix[i + 1, j + 1], matrix[i, j] + 1); //substitution
            }
    return matrix[firstString.Length, secondString.Length];
}

では、おそらく長いテキストの比較や高度に並列化するのに適した同様のアルゴリズムを知っていますか?

4

2 に答える 2

0

私は類似性アルゴリズムの多くの実装を含むSimMetricsと呼ばれるsupa dupaライブラリを見つけました。それらをベンチマークすると、私の場合ははるかに高速です。

あなたも興味があるなら: http://sourceforge.net/projects/simmetrics/

于 2013-04-17T13:05:42.173 に答える