Вопрос реализации Trie

Question

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

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

class WordTree Inherits Dictionary(of Char, WordTree)

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

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

Спасибо.

Обновление:

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

Answer 1

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

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 );
    }
};

Существуют и другие способы подсчета битов Здесь , индекс в векторе - это количество установленных битов в действительном наборе битов. другая альтернатива - это прямой индексированный массив состояний;

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

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

Answer 2

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

Answer 3

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

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

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

Что такое шаблон чтения и обновления?

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

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

Answer 4

Хорошей структурой данных, которая эффективна в пространстве и потенциально обеспечивает поиск сублинейных префиксов, является дерево троичного поиска. У Питера Канковского есть фантастическая статья об этом. Он использует C, но это простой код, когда вы понимаете структуру данных. Как он упомянул, эта структура ispell использует для исправления орфографии.

Answer 5

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