Suchen Sie nach der Suffixbaumimplementierung in C#?

Question

Ich habe eine grundlegende Suche nach einem Forschungsprojekt implementiert. Ich versuche, die Suche effizienter zu machen, indem ich eine suffix tree baue. Ich bin an einer C# -Implementierung des Ukkonen-Algorithmus interessiert. Ich möchte keine Zeit damit verschwenden, selbst zu rollen, wenn eine solche Implementierung existiert.

Answer 1

Hei, gerade fertig mit der Implementierung von .NET (C#) - Bibliothek, die verschiedene Trie-Implementierungen enthält. Unter ihnen:

• Klassische trie
• Patricia Trie
• Suffixbaum
• Ein Trie mit Ukkonen des Algorithmus

Ich habe versucht, den Quellcode leicht lesbar zu machen. Die Nutzung ist auch sehr einfach:

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

Die Bibliothek ist gut getestet und auch als TrieNet NuGet Paket veröffentlicht.

Siehe github.com/gmamaladze/trienet

Answer 2

Harte Frage. Hier ist die nächste Übereinstimmung, die ich finden könnte: http://www.codeproject.com/KB/recipes/ahocorasick.aspx, die eine Implementierung des Aho-Corasick String-Matching-Algorithmus ist. Nun verwendet der Algorithmus eine Suffix-Baumstruktur pro: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Nun, wenn Sie einen Präfix Baum wollen, wird dieser Artikel behauptet, für Sie eine Implementierung haben: http://www.codeproject.com/KB/recipes/prefixtree.aspx

< HUMOR> Jetzt, Ich habe deine Hausaufgaben gemacht, und du machst meinen Rasen mähen. (Referenz: http://flyingmoose.org/tolksarc/homework.htm) < /HUMOR>

bearbeiten: fand ich eine C# Suffixbaum Implementierung, die eine Portierung eines C++ war auf einem Blog gepostet: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

bearbeiten: Es gibt ein neues Projekt bei Codeplex, das sich auf Suffixbäume konzentriert: http://suffixtree.codeplex.com/

Answer 3

Hier ist eine Implementierung eines Suffixbaums, der einigermaßen effizient ist. Ich habe die Implementierung von Ukkonen nicht studiert, aber die Laufzeit dieses Algorithmus ist meiner Meinung nach ziemlich vernünftig, etwa O(N Log N). Beachten Sie, dass die Anzahl der internen Knoten in der erstellten Struktur der Anzahl der Buchstaben in der übergeordneten Zeichenfolge entspricht.

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