在C#中寻找后缀树实现？

Question

我已经实施了一个研究项目的基本搜索.我试图通过构建后缀树来提高搜索效率.我对Ukkonen算法的C#实现很感兴趣.如果存在这样的实现,我不想浪费时间自己动手.

Answer 1

难以回答的问题.这是我能找到的最接近的匹配:http://www.codeproject.com/KB/recipes/ahocorasick.aspx,它是Aho-Corasick字符串匹配算法的实现.现在,该算法使用类似后缀树的结构:http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

现在,如果你想要一个前缀树,本文声称有一个实现:http://www.codeproject.com/KB/recipes/prefixtree.aspx

< 幽默 >现在我做完了你的作业,你怎么样修剪我的草坪.(参考:http://flyingmoose.org/tolksarc/homework.htm)< / HUMOR >

编辑:我发现了一个C#后缀树实现,它是在博客上发布的C++端口:http: //code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

编辑:Codeplex上有一个专注于后缀树的新项目:http://suffixtree.codeplex.com/

Answer 2

嘿，刚刚完成了包含不同 trie 实现的 .NET (c#) 库的实现。他们之中：

• 经典树
• 帕特里夏·特里
• 后缀树
• 使用Ukkonen算法的尝试

我试图使源代码易于阅读。用法也很简单：

using Gma.DataStructures.StringSearch;

...

var trie = new UkkonenTrie<int>(3);
//var trie = new SuffixTrie<int>(3);

trie.Add("hello", 1);
trie.Add("world", 2);
trie.Add("hell", 3);

var result = trie.Retrieve("hel");

该库经过充分测试，也作为TrieNet NuGet 包发布。

见github.com/gmamaladze/trienet