2

我实际上必须实现一个字符串比较，最后得到一个匹配百分比（不仅仅是布尔结果匹配/不匹配）。所以，为了做到这一点，我找到了 Levenstein 距离算法。但现在的问题在于性能。例如，我有 1k 个字符串要相互比较，现在大约需要 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

4

您实际上在做的是使用Needleman-Wunsch (NW) 算法，对吗？
NW 算法基于计算 DP 矩阵，其中每个字段取决于 3 个相邻字段：左侧、左上角和顶部。因此，它通常是逐行解决的。
但是，如果您想并行化它，那么最常见的想法之一是通过对角线求解 DP 矩阵。这样，您可以独立计算反对角线中的每个字段。

这就是您的函数 getLevensetinDistance 现在的工作方式：您逐行计算，这意味着您必须逐个字段计算并且不可能进行并行化，如图所示：

在此处输入图像描述

您需要更改您的函数 getLevesteinDistance 以便能够并行化它。这是我之前描述的对角线思想的图片，其中对角线中的每个字段都可以独立计算，这意味着您可以进行并行化（可以并行计算具有相同数量的字段）：

在此处输入图像描述

你能解释一下如何并行调用你的算法吗？由于您的函数 getLevensteinDistance() 接受两个字符串，除非比较多对字符串，否则我认为并行调用它没有任何意义，但是您已经提到您为此并行调用函数 compare()。

顺便说一句，它应该是 Levenshtein，而不是 Levenstein :)。

此外，我实际上最终为 Levenshtein 距离实现了一个 C/C++ 库，它是最长字符串的最快实现之一，您可以在这里查看：https ://github.com/Martinsos/edlib - 也许这是一个更好的选择比实现你自己的，虽然它只适用于一个线程（但你可以自己在多个线程上运行它）。

于 2013-04-16T11:50:01.427 回答
0

我发现了一个名为 SimMetrics 的 supa dupa 库，其中包含许多相似性算法的实现，当我对它们进行基准测试时，在我的案例中会有一些很棒且有用的更快。

如果你也有兴趣：http: //sourceforge.net/projects/simmetrics/

于 2013-04-17T13:05:42.173 回答