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

我已经实施了一个研究项目的基本搜索。 我试图通过构建后缀树来提高搜索效率。 我对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

这是一个合理有效的后缀树的实现。 我还没有研究过Ukkonen的实现，但我认为这个算法的运行时间非常合理，大约为O(N Log N) 。 请注意，创建的树中的内部节点数等于父字符串中的字母数。

 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using NUnit.Framework; namespace FunStuff { public class SuffixTree { public class Node { public int Index = -1; public Dictionary Children = new Dictionary(); } public Node Root = new Node(); public String Text; public void InsertSuffix(string s, int from) { var cur = Root; for (int i = from; i < s.Length; ++i) { var c = s[i]; if (!cur.Children.ContainsKey(c)) { var n = new Node() {Index = from}; cur.Children.Add(c, n); // Very slow assertion. Debug.Assert(Find(s.Substring(from)).Any()); return; } cur = cur.Children[c]; } Debug.Assert(false, "It should never be possible to arrive at this case"); throw new Exception("Suffix tree corruption"); } private static IEnumerable VisitTree(Node n) { foreach (var n1 in n.Children.Values) foreach (var n2 in VisitTree(n1)) yield return n2; yield return n; } public IEnumerable Find(string s) { var n = FindNode(s); if (n == null) yield break; foreach (var n2 in VisitTree(n)) yield return n2.Index; } private Node FindNode(string s) { var cur = Root; for (int i = 0; i < s.Length; ++i) { var c = s[i]; if (!cur.Children.ContainsKey(c)) { // We are at a leaf-node. // What we do here is check to see if the rest of the string is at this location. for (var j=i; j < s.Length; ++j) if (cur.Index + j >= Text.Length || Text[cur.Index + j] != s[j]) return null; return cur; } cur = cur.Children[c]; } return cur; } public SuffixTree(string s) { Text = s; for (var i = s.Length - 1; i >= 0; --i) InsertSuffix(s, i); Debug.Assert(VisitTree(Root).Count() - 1 == s.Length); } } [TestFixture] public class TestSuffixTree { [Test] public void TestBasics() { var s = "banana"; var t = new SuffixTree(s); var results = t.Find("an").ToArray(); Assert.AreEqual(2, results.Length); Assert.AreEqual(1, results[0]); Assert.AreEqual(3, results[1]); } } }