Это разумное внедрение Боре?


http://en.wikipedia.org/wiki/Trie

Основная идея заключается в поддержке быстрого поиска через соответствующий префикс. В моей реализации, я разрешаю каждом узле хранить все слова, которые соответствуют его данным префиксом, и тогда, если длина слова превышает длину префикса узла, он передает Слово в своих детей для дальнейшего хранения.

public class TrieNode
{
    private string Prefix { get; set; }
    private IList<string> Items { get; set; }
    private IDictionary<string, TrieNode> ChildNodes { get; set; }
    private IEqualityComparer<string> Comparer { get; set; }

    public TrieNode() : this(StringComparer.CurrentCulture) { }
    public TrieNode(IEqualityComparer<string> comparer) : this(comparer, string.Empty) { }

    private TrieNode(IEqualityComparer<string> comparer, string prefix)
    {
        if (prefix == null)
            throw new ArgumentNullException("Invalid prefix");

        this.Prefix = prefix;
        this.Items = new List<string>();
        this.ChildNodes = new Dictionary<string, TrieNode>(comparer);
        this.Comparer = comparer;
    }

    public void Add(string word)
    {
        if (word == null)
            throw new InvalidOperationException("Cannot add null to list");

        if (word.Length < this.Prefix.Length
            || !this.Comparer.Equals(word.Substring(0, this.Prefix.Length), this.Prefix))
        {
            throw new ArgumentException("Parameter does not match prefix.");
        } 

        this.Items.Add(word);

        if (word.Length > this.Prefix.Length)
        {
            string childKey = word.Substring(0, this.Prefix.Length + 1);
            if (!this.ChildNodes.ContainsKey(childKey))                
            {
                this.ChildNodes.Add(childKey, new TrieNode(this.Comparer, childKey));                    
            }

            this.ChildNodes[childKey].Add(word);
        }
    }

    public void AddRange(IEnumerable<string> words)
    {
        foreach (string word in words)
            this.Add(word);
    }

    public ReadOnlyCollection<string> FindMatches(string searchPrefix)
    {
        if (searchPrefix == null)
            throw new InvalidOperationException("Cannot search on null strings");

        if (this.Comparer.Equals(searchPrefix, this.Prefix))
        {
            return new ReadOnlyCollection<string>(this.Items);
        }
        else
        {
            string childKey = searchPrefix.Substring(0, this.Prefix.Length + 1);
            if (this.ChildNodes.ContainsKey(childKey))
                return this.ChildNodes[childKey].FindMatches(searchPrefix);
            else
                return new ReadOnlyCollection<string>(new string[0]); // empty list for no matches 
        }
    }
}

...

TrieNode trie = new TrieNode(StringComparer.CurrentCultureIgnoreCase);
trie.AddRange(new string[] { "Apple", "Banana", "BANANA", "Bar", "Berry", "Cherry", "Coconut", "Date" });

ReadOnlyCollection<string> matches = trie.FindMatches("BA"); // BANANA, banana, Bar

Небольшое беспокойство у меня вызывает то, что каждый узел содержит свой список подходящих слов, что это не набор из своих детей. Я называю это легким, потому что он позволяет легко логике при осуществлении поисков, как только найдено совпадение, нет необходимости для дальнейшего опроса детей и совокупные ответы. С другой стороны, я до конца сохранять одни и те же слова В Н списки, где п - длина слова.

Редактирование ответа предложила вернуться в интерфейс IEnumerable чтобы разрешить ленивый потокового результатов, а также чтобы избежать ненужного копирования. Компромисс заключается в том, что заказ не сохраняется, а код логики (по крайней мере, я пробовал) немного менее удобно. Но быстрые изменения, которые я сделал, чтобы разрешить такие последовательности являются следующие. Во-первых, внутрь добавить метод, только хранение соответствует определенным префиксом

if (this.Comparer.Equals(word, this.Prefix))
{
    // keep each match - preserves number of matches as well as differences 
    // if the comparer allows insensitive equality
    this.Items.Add(word); 
}

А потом FindMatches способ

public IEnumerable<string> FindMatches(string searchPrefix)
{
    if (searchPrefix == null)
        throw new InvalidOperationException("Cannot search on null strings");

    if (this.Comparer.Equals(searchPrefix, this.Prefix))
    {
        return this.Items.Concat(this.ChildNodes.SelectMany(n => n.Value.FindMatches(n.Key)));
    }
    else
    {
        string childKey = searchPrefix.Substring(0, this.Prefix.Length + 1);
        if (this.ChildNodes.ContainsKey(childKey))
        {
            return this.ChildNodes[childKey].FindMatches(searchPrefix);
        }
        else
        {
            return Enumerable.Repeat(string.Empty, 0);
        }
    }
}


5260
4
задан 2 мая 2011 в 06:05 Источник Поделиться
Комментарии
2 ответа

Вместо того, чтобы возвратить коллекцию, почему не возвращают IEnumerable? Затем вы должны проанализировать список копирования, и было бы низкой ценой возвращать перечислимый объект, который на самом деле повторяется через все списки детей.

5
ответ дан 2 мая 2011 в 10:05 Источник Поделиться

Рассмотрим только хранение одного символа в каждом узле. В настоящее время, вы храните это:

given abc, abdfa, abdfb, bcd, efg

a : abc, abdfa, abdfb
. ab : abc, abdfa, abdfb
.. abc : abc
.. abd : abdfa, abdfb
b : bcd
. bc : bcd
.. bcd : bcd
e : efg
. ef : efg
.. efg : efg

Однако, сохраняя характер и логическое ли накопительное префикс был найден:

a : F
. b : F
.. c : T
.. d : F
... f : F
.... a : T
.... d : T
b : F
. c : F
.. d : T
e : F
. f : F
.. g : T

Таким образом, ваш код будет добавить:

public void Add(string wordExcess)
{
/* validation etc here */

if (wordExcess == "")
this.Seen = true;
else
{
// child key is just a char
string childKey = wordExcess[0];
if (!this.ChildNodes.ContainsKey(childKey))
this.ChildNodes.Add(childKey, new TrieNode(this.Comparer, childKey));

string childExcess = wordExcess.Substring(1,wordExcess.Length-1);
this.ChildNodes[childKey].Add(childExcess);
}
}

Затем итерации, чтобы найти спички:

public IEnumerator FindMatches(string searchExcess)
{
/** validation etc here **/

if (searchExcess == "" && this.Seen)
yield return this.Prefix;

if (searchExcess.Length > 0)
{
string childKey = searchExcess[0];
if (this.ChildNodes.ContainsKey(childKey))
{
string childExcess = searchExcess.Substring(1,childExcess.Length-1);
foreach(string match in this.ChildNodes[childKey].FindMatches(searchExcess)
yield return this.Prefix+match;
}
}
else
{
foreach(KeyValuePair <string,TrieNode> pair in this.ChildNodes)
foreach(string match in pair.Value.FindMatches(""))
yield return this.Prefix+match;
}
}

Вот мы и добавления текущего префикса к играм, как вы вернуть их, и родителей вызывать будем делать то же самое. Так.б.С. узел D соответствует "" и возвращает "Д" К гр.матч, который возвращает "С"+"Д" К Б.матч, который возвращает "б"+"диск" и т. д.

5
ответ дан 3 мая 2011 в 01:05 Источник Поделиться