用于文本算法的.NET库？

Question

你知道任何用于文本算法的.NET库吗？
特别是我对字符串匹配和全文搜索算法感兴趣

• Bitap算法
• Levenshtein距离
• Damerau-Levenshtein距离

我知道我提到的那个代码非常简单,但有数百种文本算法,我不想自己编写代码.
如果没有已知的这种.NET库,你可以提一下C,C++库,编码包装器比零编码更容易.

Answer 1

您可能有兴趣查看Google Code上的google-diff-match-patch库.他们有Myer的diff算法的实现,它声称也"实现"了Bitap算法.

它有你正在寻找的C#源代码以及Java,C++,Lua和Python的实现.虽然我对如何在实践中使用Bitap没有最好的理解(Google Code项目中有演示),但我认为你最感兴趣的是从当前版本的第1476行开始的匹配函数.

更新:

一点点挖掘在CodeProject的C#中找到了Levenshtein的实现.

此外,这个C#类文件包含SourceForge上的Levenshtein实现.该实现是Corsis(又名Tenka Text)项目的一部分.作者声称,YetiLevenshtein方法(在第741行附近)比上面引用的算法的CodeProject版本中使用的实现快2到10倍.

更新#2:

我刚刚用它的Levenshtein距离的C#版本发现了wikibook 算法实现,并且必须包含它,因为它看起来非常直观而且非常重要.这个wikibook看起来像一个很好的参考,一般保持在手.

Levenshtein在C#中的距离(由Wikibooks提供)

    private Int32 levenshtein(String a, String b)
    {

        if (string.IsNullOrEmpty(a))
        {
            if (!string.IsNullOrEmpty(b))
            {
                return b.Length;
            }
            return 0;
        }

        if (string.IsNullOrEmpty(b))
        {
            if (!string.IsNullOrEmpty(a))
            {
                return a.Length;
            }
            return 0;
        }

        Int32 cost;
        Int32[,] d = new int[a.Length + 1, b.Length + 1];
        Int32 min1;
        Int32 min2;
        Int32 min3;

        for (Int32 i = 0; i <= d.GetUpperBound(0); i += 1)
        {
            d[i, 0] = i;
        }

        for (Int32 i = 0; i <= d.GetUpperBound(1); i += 1)
        {
            d[0, i] = i;
        }

        for (Int32 i = 1; i <= d.GetUpperBound(0); i += 1)
        {
            for (Int32 j = 1; j <= d.GetUpperBound(1); j += 1)
            {
                cost = Convert.ToInt32(!(a[i-1] == b[j - 1]));

                min1 = d[i - 1, j] + 1;
                min2 = d[i, j - 1] + 1;
                min3 = d[i - 1, j - 1] + cost;
                d[i, j] = Math.Min(Math.Min(min1, min2), min3);
            }
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)];

    }

Answer 2

我设法使用 WikiPedia + Google Code 搜索的组合找到了我需要的大多数算法的实现。

http://en.wikipedia.org/wiki/Category:Algorithms_on_strings
http://www.google.com/codesearch

尽管奇怪的是没有人创建关于这个主题的项目，但感兴趣的人可以就此进行合作。