¿Busca la implementación del árbol de sufijos en C#?

Question

Implementé una búsqueda básica para un proyecto de investigación. Estoy tratando de hacer la búsqueda más eficiente construyendo un suffix tree. Estoy interesado en una implementación de C# del algoritmo Ukkonen. No quiero perder el tiempo rodando el mío si existe tal implementación.

Answer 1

Hei, acaba de implementar la biblioteca .NET (C#) que contiene diferentes implementaciones. Entre ellos:

• trie Clásica
• Patricia trie
• sufijo trie
• un trie utilizando el algoritmo de Ukkonen

Traté de hacer que el código fuente fácil de leer. El uso también es muy sencillo:

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

La biblioteca está bien probado y también publicado como TrieNet paquete NuGet.

Ver github.com/gmamaladze/trienet

Answer 2

Pregunta difícil. Aquí está lo más cercano a la coincidencia que pude encontrar: http://www.codeproject.com/KB/recipes/ahocorasick.aspx, que es una implementación del algoritmo de concordancia de cadenas Aho-Corasick. Ahora, el algoritmo utiliza una estructura sufijo-árbol-como por: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Ahora, si quieres un árbol de prefijo, este artículo afirma que tiene una aplicación para usted: http://www.codeproject.com/KB/recipes/prefixtree.aspx

< HUMOR> Ahora que Hice tu tarea, ¿qué tal si cortas mi césped? (Referencia: http://flyingmoose.org/tolksarc/homework.htm) < /Humor>

Edición: me encontré con un C# aplicación árbol de sufijos que era un puerto de un C++ uno publicado en un blog: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

Edición: Hay un nuevo proyecto en Codeplex que se centra en árboles de sufijo: http://suffixtree.codeplex.com/

Answer 3

Aquí hay una implementación de un árbol de sufijo que es razonablemente eficiente. No he estudiado la implementación de Ukkonen, pero creo que el tiempo de ejecución de este algoritmo es bastante razonable, aproximadamente O(N Log N). Tenga en cuenta que el número de nodos internos en el árbol creado es igual al número de letras en la cadena primaria.

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