c# - sufijos - prefijos de visual basic

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

Question

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

Answer 1

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 usa una estructura de árbol de sufijos por: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Ahora, si desea un árbol de prefijos, este artículo afirma tener una implementació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 >

Editar : Encontré una implementación de árbol de sufijo C # que era un puerto de C ++ publicado en un blog: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

Editar : Hay un nuevo proyecto en Codeplex que se centra en árboles de sufijos: http://suffixtree.codeplex.com/

Answer 2

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

Answer 3

Hei, acaba de finalizar la implementación de la biblioteca .NET (c #) que contiene diferentes implementaciones. Entre ellos:

• Trie clásico
• Patricia trie
• Sufijo trie
• Un trie usando el algoritmo de Ukkonen

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

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 probada y también se publicó como el paquete TrieNet NuGet.

Ver github.com/gmamaladze/trienet