Trie Implementation Question

Question

Я реализую trie для интеллектуального ввода текста в VB.NET - в основном автозаполнение в отношении использования trie. Я сделал свою trie рекурсивную структуру данных, основанную на общем классе словаря.

Это в основном:

class WordTree Inherits Dictionary(of Char, WordTree) 

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

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

Спасибо.

Update:

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

Answer 1

Если это всего лишь 26 букв, то в качестве 26-позиционного массива. Затем поиск выполняется по индексу. Вероятно, он использует меньше места, чем словарь, если ведро-список длиннее 26.

Answer 2

Хорошая структура данных, эффективная в пространстве и потенциально обеспечивающая поиск подлинейных префикса, представляет собой тройное дерево поиска. Peter Kankowski has a fantastic article об этом. Он использует C, но это простой код, как только вы понимаете структуру данных. Как он упомянул, это структура, используемая для исправления орфографии.

Answer 3

Я сделал это (реализация trie) в C с 8-битными символами и просто использовал версию массива (как указано в ответе «26 символов»).

ОДНАКО, я предполагаю, что вам нужна полная поддержка Unicode (так как .NET char является unicode, среди других причин). Предполагая, что вам нужна поддержка для юникода, поиск хэша/карты/словаря, вероятно, лучше всего, так как массив записей размером 64 КБ в каждом узле не будет работать очень хорошо.

О единственном взломе, о котором я мог думать, это хранить целые строки (суффиксы или, возможно, «исправления») на ветвях, которые еще не расколоты, в зависимости от того, насколько разрежены дерево, er, trie, , Это добавляет много логики для обнаружения строк с несколькими символами и, тем самым, разбивает их, когда вводится альтернативный путь.

Что такое прочитанный шаблон обновления?

---- обновления июля 2013 ---

Если .NET строки имеют такую ​​функцию Java, чтобы получить байты для строки (как UTF-8), то с массивом в каждом узле, чтобы представить значение байта текущей позиции, вероятно, является хорошим способом. Вы даже можете сделать переменный размер массива с индикаторами первой/последней границы в каждом узле, так как в некоторых случаях МНОГИЕ узлы будут иметь только строчные буквы ASCII или только буквы верхнего регистра или цифры 0-9 в некоторых случаях.

Answer 4

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

class State // could be struct or whatever 
{ 
    int valid; // can handle 32 transitions -- each bit set is valid 
    vector<State> transitions; 

    State getNextState(int ch) 
    { 
     int index; 
     int mask = (1 << (toupper(ch) - 'A')) -1; 
     int bitsToCount = valid & mask; 

     for(index = 0; bitsToCount ; bitsToCount >>= 1) 
     { 
      index += bitsToCount & 1; 
     } 
     transitions.at(index); 
    } 
}; 

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

class State 
{ 
    State transitions[ 26 ]; // use the char as the index. 

    State getNextState(int ch) 
    { 
     return transitions[ ch ]; 
    } 
}; 

Answer 5

Я нашел burst trie's, чтобы быть очень экономичным. Я написал свой собственный burst trie in Scala, который также повторно использует некоторые идеи, которые я нашел в реализации GWT. Я использовал его в конкурсе Stripe's Capture the Flag по проблеме, которая была многоузловой с небольшим объемом оперативной памяти.