C# 'daki sonek ağacı uygulaması mı arıyorsunuz?

Question

Araştırma projesi için temel bir arama gerçekleştirdim. Aramayı suffix tree oluşturarak daha verimli yapmaya çalışıyorum. Ukkonen algoritmasının C# uygulamasında ilgileniyorum. Böyle bir uygulama varsa kendi zamanımı yuvarlamak için zaman kaybetmek istemiyorum.

Answer 1

Hei, yalnızca farklı trie uygulamalarını içeren .NET (C#) kitaplığını uygulamayı bitirdi. Bunlar arasında:

• Klasik tray
• Patricia tray
• Son ek tray

Ben kaynak kodu kolay okunur hale getirmek için çalıştı Ukkonen en algoritması kullanarak bir tray. Kullanımı çok basittir de:

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

kütüphane de test edilmiş ve ayrıca TrieNet Nuget paket olarak yayınlanmaktadır.

Bkz. github.com/gmamaladze/trienet

Answer 2

Zor soru. İşte bulabildiğim en yakın eşleşme: Aho-Corasick string eşleştirme algoritmasının bir uygulaması olan http://www.codeproject.com/KB/recipes/ahocorasick.aspx. > Şimdi bu http://www.codeproject.com/KB/recipes/prefixtree.aspx

< ZAH: Bir önek ağacı istiyorsanız, bu yazı sizin için bir uygulama olduğunu iddia, Şimdi http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

: Artık, algoritma başına bir sonek-ağaç gibi yapı kullanır Ev ödevini yaptım, nasıl çimlerimi biçersin? (Referans: http://flyingmoose.org/tolksarc/homework.htm) < /MİZAH>

Düzenleme: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

Düzenleme: Bir blogda yayınlanan bir C++ birinin bir liman olan bir C# eki ağaç uygulanmasını bulundu yoktur Codeplex'teki yeni bir proje eki ağaçlara odaklanır: http://suffixtree.codeplex.com/

Answer 3

Burada, son derece verimli olan bir sonek ağacının bir uygulaması vardır. Ukkonen'in uygulamasını incelemedim, fakat bu algoritmanın çalışma zamanının yaklaşık O(N Log N) olduğunu düşünüyorum. Oluşturulan ağaçtaki iç düğüm sayısının üst dizedeki harf sayısına eşit olduğunu not edin.

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