Эффективность реализации Trie

Question

Что является более эффективным. Структура Trie, подобная этой:

struct TrieNode              
{
char letter;              
bool isWord;                
     TrieNode* subNodes[26]; 
};

или структура Trie, подобная этой:

struct TrieNode
{ 
    char letter;
    bool isword;
    map<int, TrieNode*> subNodes;
};

Или есть только лучшая реализация ... Кроме того, кто-нибудь может дать мне объяснение?

Answer 1

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

Если вместо этого вы замените массив связанным списком (а затем немного по нему манипулируете), вы сможете перейти к реализации двоичного дерева (однако структура все равно будет более эффективной, чем традиционное двоичное дерево для поиска, потому что вы не использование сравнения строк на каждом узле, и потому что ваше пространство клавиш перекрывается (поиск «the» и поиск «then» начинаются с одинаковых сравнений).

то есть рассмотрим:

struct TrieNode
{
  char key;
  char *val; /* This is null unless we are an "end node" - you could use the Bool as you do, but I've found this a bit simpler */
  struct TrieNode *siblings; /* traversing this is checking different characters at this position in the string */
  struct TrieNode *children; /* Travesring this list is looking at subsequent positions in the list */
};

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

Answer 2

Я бы использовал первое для простоты и скорости, но, возможно, второе может сэкономить место.

Вам не нужен элемент char letter ни в одном коде.Это избыточно, потому что способ поиска слова состоит в том, чтобы взять букву ключа и использовать его либо как индекс в массиве subNode, либо как ключ в вашей карте, чтобы выбрать subNode.В любом случае, вам никогда не нужно смотреть на letter.

То, как вы узнаете, что слово отсутствует в три, - это если вы нажали нулевой подузел, или если вы исчерпали свой ключ, не нажав isWord subnode.

Кстати, если ваша строка не содержит слишком много слов, и если она не меняется очень часто, вы всегда сэкономите порядка порядка скорости, преобразовав ее в специальный код.

---

РЕДАКТИРОВАТЬ Под специальным кодом я подразумеваю, что три представляет собой разновидность конечного автомата, а конечный автомат - своего рода программу.Таким образом, вы пишете программу для чтения отсортированного словаря, но вместо построения структуры данных trie, она пишет программу на вашем любимом языке, которая выглядит следующим образом:

// XYZ is the prefix string that corresponds to a node in the trie
bool XYZFunc(char* key){
    switch (*key){
    case '\0': return true /* if XYZ is a valid word, else false */; break;
    case 'a': return XYZaFunc(key+1); break;
    case 'b': return XYZbFunc(key+1); break;
    // etc. etc.
    }
}

Это может быть много функций, но в разумных пределах компилятор должен быть в состоянии справиться с этим.Затем, чтобы найти слово, вы просто вызываете функцию верхнего уровня, и она возвращает true или false.На каждом узле компилятор определит, нужна ли ему таблица переходов, поэтому вам не нужно об этом беспокоиться.