Tìm kiếm việc thực thi cây hậu tố trong C#?

Question

Tôi đã thực hiện tìm kiếm cơ bản cho một dự án nghiên cứu. Tôi đang cố gắng tìm kiếm hiệu quả hơn bằng cách tạo một suffix tree. Tôi quan tâm đến việc triển khai C# của thuật toán Ukkonen. Tôi không muốn lãng phí thời gian của riêng mình nếu thực hiện như vậy tồn tại.

Answer 1

Hei, vừa thực hiện xong thư viện .NET (C#) chứa các triển khai trie khác nhau. Trong đó:

• Cổ điển Trie
• Patricia Trie
• cây hậu tố
• Một Trie sử dụng thuật toánUkkonen của

Tôi cố gắng để làm cho mã nguồn dễ dàng đọc được. Cách sử dụng cũng rất thẳng về phía trước:

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"); 

Thư viện được kiểm tra và xuất bản là TrieNet Gói NuGet.

Xem github.com/gmamaladze/trienet

Answer 2

Câu hỏi khó. Đây là gần nhất để phù hợp với tôi có thể tìm thấy: http://www.codeproject.com/KB/recipes/ahocorasick.aspx, mà là một thực hiện thuật toán kết hợp chuỗi Aho-Corasick. Bây giờ, các thuật toán sử dụng một cấu trúc suffix-cây giống như mỗi: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Bây giờ, nếu bạn muốn có một cây tiền tố, bài viết này khẳng định có một thực hiện cho bạn: http://www.codeproject.com/KB/recipes/prefixtree.aspx

< hài hước> Bây giờ Tôi đã làm bài tập về nhà của bạn, làm thế nào về bạn cắt cỏ của tôi. (Tham khảo: http://flyingmoose.org/tolksarc/homework.htm) < /hài hước>

Sửa: Tôi tìm thấy một C# cây hậu tố thực hiện đó là một cổng của một C++ một đăng trên một blog: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

Sửa: Có một dự án mới tại Codeplex tập trung vào cây hậu tố: http://suffixtree.codeplex.com/

Answer 3

Dưới đây là việc triển khai cây hậu tố có hiệu quả hợp lý. Tôi đã không nghiên cứu thực hiện của Ukkonen, nhưng thời gian chạy của thuật toán này tôi tin là khá hợp lý, khoảng O(N Log N). Lưu ý số lượng các nút bên trong trong cây được tạo bằng số chữ cái trong chuỗi gốc.

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]); 
     } 
    } 
}