用于文本算法的.NET库?

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

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

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

您可能有兴趣查看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)]; } 

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

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

虽然很奇怪,没有人在这个主题上创建项目,感兴趣的人可以就此进行合作。

如果你正在进行字符串匹配, Lucene.Net值得一看。

但是,我知道这并不完全是你所追求的,虽然你可以用一些C#forms找到大部分算法,但我知道没有包含它们的库(我倾向于在我的个人中保留一些这些算法)图书馆)。

出于兴趣,为什么您需要多个具有几个阈值参数的完全匹配算法?

这是我为Levenshtein / Damerau-Levenshtein距离实施的:

  public static int GetDistance(string left, string right, bool isDamerauDistanceApplied) { if (left.Length == 0) return right.Length; if (right.Length == 0) return left.Length; var lenLeft = left.Length; var lenRight = right.Length; var matrix = new int[lenLeft + 1, lenRight + 1]; for (var i = 0; i <= lenLeft; i++) matrix[i, 0] = i; for (var i = 0; i <= lenRight; i++) matrix[0, i] = i; for (var i = 1; i <= lenLeft; i++) { for (var j = 1; j <= lenRight; j++) { var cost = (left[i - 1] == right[j - 1]) ? 0 : 1; matrix[i, j] = Math.Min(Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1), matrix[i - 1, j - 1] + cost); if (isDamerauDistanceApplied) { // Fixed for string base 0 index. if (i > 1 && j > 1 && left[i - 1] == right[j - 2] && left[i - 2] == right[j - 1]) { matrix[i, j] = Math.Min(matrix[i, j], matrix[i - 2, j - 2] + cost); } } } } return matrix[lenLeft, lenRight]; } 

我建议使用SimMetrics库,它有许多不同的字符串匹配算法。 也可以在NuGet上使用 。

简短的介绍:

SimMetrics是一个相似度量库,例如从编辑距离(Levenshtein,Gotoh,Jaro等)到其他指标(例如Soundex,Chapman)。

GPLv2许可证。

我发现并使用了以下.NET库来实现Tom Petricek的Aho-Corasick文本数学,以解决我遇到的问题。 它对我很有用。