सी # में प्रत्यय वृक्ष कार्यान्वयन की तलाश में?

Question

मैंने एक शोध परियोजना के लिए एक बुनियादी खोज लागू की है। मैं suffix tree बनाकर खोज को और अधिक कुशल बनाने की कोशिश कर रहा हूं। मुझे Ukkonen एल्गोरिथ के सी # कार्यान्वयन में रूचि है। यदि ऐसा कार्यान्वयन मौजूद है तो मैं अपना खुद का समय बर्बाद नहीं करना चाहता हूं।

Answer 1

हे, बस विभिन्न परीक्षण कार्यान्वयन वाले .NET (सी #) लाइब्रेरी को कार्यान्वित करना समाप्त कर दिया। उनमें से:

• शास्त्रीय trie
• पेट्रीसिया trie
• प्रत्यय trie
• Ukkonen के कलन विधि का उपयोग एक Trie

मैं स्रोत कोड आसान पठनीय बनाने की कोशिश की। प्रयोग भी बहुत सीधे आगे है:

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, जो अहो-कोरासिक स्ट्रिंग मिलान एल्गोरिदम का कार्यान्वयन है। अब http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

यदि आप एक उपसर्ग पेड़ चाहते हैं, यह लेख आपके लिए एक कार्यान्वयन का दावा,:: अब, एल्गोरिथ्म प्रति एक प्रत्यय-पेड़ की तरह संरचना का उपयोग करता> अब जब कि http://www.codeproject.com/KB/recipes/prefixtree.aspx

< हास्य मैंने आपका होमवर्क किया, तुमने मेरे लॉन को कैसे उड़ाया। (संदर्भ: http://flyingmoose.org/tolksarc/homework.htm) < /हास्य>

संपादित: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

संपादित:: मैं एक सी # प्रत्यय पेड़ कार्यान्वयन कि एक सी ++ एक एक ब्लॉग पर पोस्ट की एक बंदरगाह था पाया है कोडेप्लेक्स पर एक नई परियोजना जो प्रत्यय पेड़ पर केंद्रित है: 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]); 
     } 
    } 
}