Vous recherchez l'implémentation d'arborescence de suffixe en C #?

Question

J'ai mis en place une recherche de base pour un projet de recherche. J'essaie de rendre la recherche plus efficace en construisant un arbre de suffixe . Je suis intéressé par une implémentation C # de l'algorithme Ukkonen . Je ne veux pas perdre mon temps à rouler le mien si une telle implémentation existe.

Answer 1

Hei, vient de terminer l’implémentation de la bibliothèque .NET (c #) contenant différentes implémentations. Parmi eux:

• Trie classique
• Patricia trie
• Suffixe trie
• Un test utilisant l'algorithme d'Ukkonen

J'ai essayé de rendre le code source facilement lisible. L’utilisation est également très simple:

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 bibliothèque a été testée et publiée dans le paquet TrieNet NuGet.

Voir github.com/gmamaladze/trienet

Answer 2

Question difficile. Voici le plus proche du match que j'ai pu trouver: http://www.codeproject.com/KB/ recipes / ahocorasick.aspx , qui est une implémentation de l'algorithme de correspondance de chaînes Aho-Corasick. Maintenant, l'algorithme utilise une structure semblable à un arbre de suffixes selon: http://fr.wikipedia.org / wiki / algorithme Aho-Corasick

Maintenant, si vous voulez une arborescence de préfixes, cet article prétend avoir une implémentation pour vous: http://www.codeproject.com/KB/recipes/prefixtree.aspx

< HUMOUR > Maintenant que j'ai fait tes devoirs, que dirais-tu de tondre ma pelouse? (Référence: http://flyingmoose.org/tolksarc/homework.htm ) & Lt ; / HUMOUR >

Modifier : j'ai trouvé une implémentation d'arborescence de suffixe C # qui était le port d'un port C ++ posté sur un blog: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

Modifier : Codeplex a créé un nouveau projet axé sur les arborescences de suffixes: http: //suffixtree.codeplex.com/

Answer 3

Voici une implémentation d’une arborescence de suffixes raisonnablement efficace. Je n'ai pas étudié la mise en œuvre d'Ukkonen, mais la durée d'exécution de cet algorithme est, je pense, assez raisonnable, environ O(N Log N). Notez que le nombre de nœuds internes dans l’arborescence créée est égal au nombre de lettres de la chaîne parente.

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 (cur.Index + j >= Text.Length || 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]);
        }
    } 
}