c - 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

为了简单和速度，我会使用第一个，但可以想象第二个可以节省空间。

任一代码中都不需要 char letter 元素。 这是多余的，因为查找单词的方式是获取键的一个字母并将其用作子节点数组的索引，或者用作映射的键​​，以便选择子节点。 无论哪种方式，您都不需要看字母。

您知道该单词是否不在 trie 中的方法是，如果您击中了 null 子节点，或者您耗尽了 key 而没有击中 isWord 子节点。

顺便说一句，如果您的 trie 不包含太多单词，并且它不经常更改，那么通过将其转换为临时代码，您始终可以节省大约一个数量级的速度。

<小时/>

编辑我所说的临时代码的意思是，特里树是一种有限状态机，而有限状态机是一种程序。因此，您编写了一个程序来读取排序后的字典，但它没有构建 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。在每个节点，编译器都会确定是否需要跳转表，因此您不必担心这一点。