3

我正在尝试在 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];
};

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

children[(unsigned char)'c']

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

struct node** children;

然后在添加节点时，只需为节点分配空间并拥有

children[(unsigned char)'c']

指向新节点。问题是如果我不首先为孩子分配空间，那么我显然不能引用任何索引，否则这是一个很大的错误。

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

4

4 回答 4

5

您可以尝试使用de la Briandais trie，其中每个节点只有一个子指针，并且每个节点还有一个指向“兄弟”的指针，以便所有兄弟都有效地存储为链表而不是直接指向由家长。

于 2011-06-22T15:21:56.163 回答
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] = ...;

如果您的树最终在一个级别上有很多非空条目，您可能会按排序顺序插入子项并进行二分搜索。或者您可以将孩子添加为链表而不是数组。

于 2011-06-22T15:25:22.403 回答
1

如果您只想进行英文关键字搜索，我认为您可以将孩子的大小从 256 缩小到仅 26 - 足以覆盖 26 个字母 az。

此外，您可以使用链表来保持子节点的数量更小，这样我们就可以进行更有效的迭代。

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

于 2012-05-28T11:56:39.367 回答
1

通过使每个节点的子节点成为节点的哈希表，您既可以节省空间又可以保持恒定的查找时间。尤其是当涉及 Unicode 字符并且您的字典中可以包含的字符集不限于 52 + 一些时，这更像是一种要求而不是一种精细。这样，您可以保持使用 trie 的优势，同时节省时间和空间。

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

可能性无穷无尽！

于 2013-01-15T22:58:58.617 回答