高效地利用空间的 Trie 树

Question

我正在尝试在C语言中实现一个空间高效的Trie树。这是我的结构体：

struct node {
char val; //character stored in node
int key; //key value if this character is an end of word
struct node* children[256];
};

当我添加一个节点时，它的索引是字符的无符号char转换而来。例如，如果我想添加“c”，那么

children[(unsigned char)'c']

这个指针是指向新添加的节点。然而，这种实现方式需要我声明一个256个元素的node*数组。我想要做的是：

struct node** children;

当添加一个节点时，只需为该节点分配空间并进行malloc操作。

children[(unsigned char)'c']

指向新节点。问题在于，如果我不先为孩子们分配空间，那么我显然无法引用任何索引，否则就会出现大错误。

所以我的问题是：我如何实现一个trie，以便它只存储对其子级的非空指针？

- joe smallz

---

为什么不检查 children 是否为 NULL？ - Drakosha

你考虑过使用**有向无环词图(Directed Acyclic Word Graph)**吗？请参考http://en.wikipedia.org/wiki/Directed_acyclic_word_graph。 - Winston Smith

Answer 1

你可以尝试使用德拉布里昂树，每个节点只有一个子指针，每个节点也有一个指向“兄弟”的指针，因此所有兄弟节点都被有效地存储为链表，而不是直接由父节点指向。

- Kevin

---

这难道不会破坏遍历时间吗？ - kyun

@kyun 是的，但正如其他回答者指出的那样，你不能既具有空间效率又具有良好的遍历时间。如果速度是一个问题，三叉树可能是一个不错的选择（每个节点有3个指针：一个指向“较小”的兄弟，一个指向“较大”的兄弟，一个指向子节点）。 - Kevin

不错，我明白那样可以更快。 - kyun

Answer 2

你无法在空间利用率高和子节点的O(1)查找之间两全其美。

当你只为实际添加的条目分配空间而不是空指针时，你就不能再这样做了。

children[(unsigned char)'c']

由于您不能直接索引数组，因此可以采用另一种方法：通过对子元素进行线性搜索，并存储children数组的条目数量。

children[(unsigned char)'c'] = ...;

必须成为

for(i = 0; i < len; i++) {
  if(children[i] == 'c')
     break;
} 
if(i == len) {
  //...reallocate and add space for one item in children
}
children[i] = ...;

如果你的树在某个层级上有很多非空条目，可以按排序顺序插入孩子节点并进行二分搜索。或者，你可以将孩子节点作为链表而不是数组添加。

- Lyke

Answer 3

如果您只想进行英文关键字搜索，我认为您可以将孩子的大小最小化，从256减少到仅26-刚好足够覆盖26个字母a-z。

此外，您可以使用链接列表来使孩子的数量更小，以便我们可以进行更有效的迭代。

我还没有浏览库，但我认为trie实现会有所帮助。

- fatjazz

Answer 4

您可以通过将每个节点的子节点作为节点哈希表来实现空间高效和恒定查找时间。特别是当涉及到Unicode字符并且您的字典中可以拥有的字符集不仅限于52 +一些字符时，这变得更像是一个要求而不是一个美好的愿望。这样，您可以保持使用trie的优势，并同时具有时间和空间效率。

我还必须补充说，如果您使用的字符集接近无限，那么使用节点的链接列表可能会很好。如果您想要一个难以管理的噩梦，可以选择混合方法，其中前几个级别将其子节点保存在哈希表中，而较低级别则将它们保存在链接列表中。对于真正的错误农场，请选择动态方法，在每个链接列表传递阈值时，将其即时转换为哈希表。您可以轻松地摊销成本。

可能性是无穷无尽的！

- bariscaglar