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

Question

我已经实施了一个研究项目的基本搜索。我试图通过构建suffix tree来提高搜索效率。我对Ukkonen算法的C＃实现感兴趣。如果存在这种实施方式，我不想浪费时间翻身。

Answer 1

嘿，刚刚完成实现.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

Answer 2

难题。这是我能找到的最接近的匹配：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）< /幽默>

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

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

Answer 3

下面是一个相当高效的后缀树实现。我没有研究过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<char, Node> Children = new Dictionary<char, Node>(); 
     } 

     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<Node> VisitTree(Node n) 
     { 
      foreach (var n1 in n.Children.Values) 
       foreach (var n2 in VisitTree(n1)) 
        yield return n2; 
      yield return n; 
     } 

     public IEnumerable<int> 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 (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]); 
     } 
    } 
}