Ищете реализацию суффиксного дерева в C #? - PullRequest
Новая
       31

Ищете реализацию суффиксного дерева в C #?

12 голосов
/ 05 октября 2008

Я реализовал базовый поиск исследовательского проекта. Я пытаюсь сделать поиск более эффективным путем создания дерева суффиксов . Я заинтересован в реализации C # алгоритма Ukkonen . Я не хочу тратить время на свои собственные, если такая реализация существует.

Ответы [ 3 ]

12 голосов
/ 11 октября 2008

Сложный вопрос. Вот самое близкое совпадение, которое я смог найти: http://www.codeproject.com/KB/recipes/ahocorasick.aspx,, который является реализацией алгоритма сопоставления строк Aho-Corasick. Теперь алгоритм использует структуру в виде дерева суффиксов для: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Теперь, если вам нужно дерево префиксов, эта статья утверждает, что имеет реализацию для вас: http://www.codeproject.com/KB/recipes/prefixtree.aspx

<<em> ЮМОР > Теперь, когда я сделал твою домашнюю работу, как насчет того, чтобы ты косил мой газон? (Ссылка: http://flyingmoose.org/tolksarc/homework.htm) <<em> / ЮМОР >

Редактировать : Я нашел реализацию дерева суффиксов C #, которая была портом C ++ и размещена в блоге: http://code.google.com/p/csharsuffixtree/source/browse/#svn/trunk/suffixtree

Редактировать : В Codeplex появился новый проект, ориентированный на суффиксные деревья: http://suffixtree.codeplex.com/

3 голосов
/ 27 сентября 2017

Привет, только что закончил реализацию библиотеки .NET (c #), содержащей различные реализации 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

3 голосов
/ 13 сентября 2013

Вот реализация дерева суффиксов, которое является достаточно эффективным. Я не изучал реализацию Укконена, но время работы этого алгоритма, я считаю, вполне разумно, приблизительно 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 (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]);
        }
    } 
}
...