Какой разумный способ реализовать Trie в .NET? - PullRequest
Новая
       27

Какой разумный способ реализовать Trie в .NET?

8 голосов
/ 08 сентября 2010

Я понял концепцию trie .Но я немного запутался, когда дело доходит до реализации.

Самый очевидный способ, которым я мог бы подумать, чтобы структурировать тип Trie, это иметь Trie для поддержки внутреннего Dictionary<char, Trie>.На самом деле я написал один таким образом, и он работает , но ... это кажется излишним.У меня сложилось впечатление, что дерево должно быть легким, и наличие отдельного Dictionary<char, Trie> для каждого узла не кажется мне очень легким.

Есть ли более подходящий способ реализации этой структурычто мне не хватает?

ОБНОВЛЕНИЕ : ОК!Основываясь на очень полезном вкладе Джона и Леппи, я до сих пор придумал:

(1) У меня есть тип Trie, который имеет закрытый член типа _nodesTrie.INodeCollection.

(2) Интерфейс Trie.INodeCollection имеет следующие члены: 

interface INodeCollection
{
    bool TryGetNode(char key, out Trie node);
    INodeCollection Add(char key, Trie node);
    IEnumerable<Trie> GetNodes();
}

(3) Существует три реализации этого интерфейса: 

class SingleNode : INodeCollection
{
    internal readonly char _key;
    internal readonly Trie _trie;

    public SingleNode(char key, Trie trie)
    { /*...*/ }

    // Add returns a SmallNodeCollection.
}

class SmallNodeCollection : INodeCollection
{
    const int MaximumSize = 8; // ?

    internal readonly List<KeyValuePair<char, Trie>> _nodes;

    public SmallNodeCollection(SingleNode node, char key, Trie trie)
    { /*...*/ }

    // Add adds to the list and returns the current instance until MaximumSize,
    // after which point it returns a LargeNodeCollection.
}

class LargeNodeCollection : INodeCollection
{
    private readonly Dictionary<char, Trie> _nodes;

    public LargeNodeCollection(SmallNodeCollection nodes, char key, Trie trie)
    { /*...*/ }

    // Add adds to the dictionary and returns the current instance.
}

(4) Когда Trie создается впервые, его член _nodes равен null.Первый вызов Add создает SingleNode, а последующие вызовы Add идут оттуда в соответствии с шагами, описанными выше.

Имеет ли это смысл?Это похоже на улучшение в том смысле, что несколько уменьшает "громоздкость" Trie (узлы больше не являются полноценными Dictionary<char, Trie> объектами до тех пор, пока у них не появится достаточное количество дочерних элементов).Однако, это также стало значительно более сложным.Это слишком запутанно?Должен ли я пойти сложным путем, чтобы достичь чего-то, что должно было быть простым?

Ответы [ 4 ]

4 голосов
/ 08 сентября 2010

Ну, вам нужно, чтобы у каждого узла было что-то, что эффективно реализует IDictionary<char, Trie>.Вы можете написать свою собственную пользовательскую реализацию, которая изменяет свою внутреннюю структуру в зависимости от количества подузлов:

  • Для одного подузла используйте только char и Trie
  • Для небольшого числа используйте List<Tuple<char, Trie>> или LinkedList<Tuple<char,Trie>>
  • Для большого числа используйте Dictionary<char, Trie>

(только что увидев ответ Леппи, этоя полагаю, о гибридном подходе, о котором он говорит.)

3 голосов
/ 08 сентября 2010

Если ваши символы из ограниченного набора (например, только заглавные буквы латинского алфавита), тогда вы можете сохранить массив из 26 элементов, и каждый поиск будет просто 

Trie next = store[c-'A']

, где c - текущий символ поиска.

3 голосов
/ 08 сентября 2010

Реализация его в качестве словаря, на мой взгляд, не реализация Trie - это реализация словаря словарей.

Когда я реализовал Trie, я сделал это так же, как предлагалосьby Damien_The_Unbeliever (+1 там): 

public class TrieNode
{
  TrieNode[] Children = new TrieNode[no_of_chars];
}

В таком случае в идеале требуется, чтобы ваша программа поддерживала только ограниченное подмножество символов, обозначенных no_of_chars, и чтобы вы могли сопоставить входные символы с выходными индексами.Например, если вы поддерживаете AZ, вы, естественно, отобразите A на 0, а Z на 25.

Когда вам нужно добавить / удалить / проверить существование узла, вы затем сделаете что-то вроде этого: 

public TrieNode GetNode(char c)
{
  //mapping function - could be a lookup table, or simple arithmetic
  int index = GetIndex(c);
  //TODO: deal with the situation where 'c' is not supported by the map
  return Children[index];
}

В реальных случаях я видел, что это оптимизировано, так что, например, AddNode будет принимать ref TrieNode, так что узел может быть обновлен по требованию и автоматически помещен в Children родительского TrieNode в правильном месте.

Вместо этого вы также можете использовать троичное дерево поиска, поскольку накладные расходы памяти для дерева могут быть довольно сумасшедшими (особенно если вы намерены поддерживать все 32 тыс. Символов Юникода!), А производительность TST довольно внушительна (а также поддерживаетпоиск префиксов и подстановочных знаков, а также поиск Хэмминга).Точно так же TST могут изначально поддерживать все символы Юникода без необходимости сопоставления;так как они работают над операцией больше / меньше / равно вместо абсолютного значения индекса.

Я взял код отсюда и немного его адаптировал (он был написан до обобщения).

Я думаю, вы будете приятно удивлены TST;как только я его реализовал, я полностью уклонился от Триса.

Единственная сложность - поддерживать равновесие TST;проблема, с которой вы не столкнулись в Tries.

2 голосов
/ 08 сентября 2010

Есть несколько способов, но использование списка одиночных ссылок, вероятно, самый простой и легкий.

Я бы сделал несколько тестов, чтобы увидеть количество дочерних узлов каждого узла. Если не так много (скажем, 20 или меньше), подход со списком ссылок должен быть быстрее, чем хеш-таблица. Вы также можете сделать гибридный подход в зависимости от количества дочерних узлов.

...