c - 如何在C中使trie存储单词的重出现

Question

我的特里树的当前节点存储一个字符和一个位置(这是文本中当前正在读取的单词结束的位置)。

如果我在位置 100 处读取了一个单词“foo”，在位置 200 处读取了另一个单词“foo”，我的节点如何存储这两次出现？有没有一种快速的方法(使用数组或更快的方法来实现)或者我需要实现链接列表？

Answer 1

所以，你的 trie 节点看起来像这样

struct trie_node {
    struct trie_node *next;
    strict trie_node *child;
    wchar_t           character;
    off_t             position;
};

您可以使用size_t position;当然，如果数据始终在内存中。

如果我们假设许多前缀没有映射到特定位置(因为它们不是完整的单词)，则对位置使用单独的数组可能会很有用，即。

struct positions {
    size_t            count_max;
    size_t            count;
    off_t             position[];
};

struct trie_node {
    struct trie_node *next;
    struct trie_node *child;
    wchar_t           character;
    struct positions *position;
};

不对应完整单词的字符节点可以有NULL position成员。 count_max对应于分配的职位数量 count对应于当前的职位数。必要时可以重新分配数组并调整其大小。这种数组大小调整在实际应用中很常见； (重新分配的)开销被认为是完全可以接受的，特别是与替代方案相比。

<小时/>

另一个有趣的选择是使用线性数组来按文本中出现的顺序表示单词，其中 position trie 节点中的成员指定数组中第一次出现的索引。每个数组条目将包含下一个出现的索引，以及可选的返回 trie 节点的链接:

#include <stdlib.h>
#include <limits.h>

struct trie_node {
    struct trie_node  *next;
    struct trie_node  *child;
    wchar_t            character;
    size_t             index;     /* NO_INDEX if no occurrences */
    size_t             occurs;    /* Num of occurrences, optional */
    wchar_t            word[];    /* Optional, entire word */
};

/* When 'index' refers to 'none', use: */
#define  NO_INDEX  SIZE_MAX

struct occurrence {
    off_t              offset;
    size_t             next;
    struct trie_node  *node;    /* Optional */
};

容器结构将包含数组，并且特里树将卡在其上:

struct text {
    size_t             count_max;
    size_t             count;
    struct occurrence *occurrences;
    struct trie_node  *trie;
};

然后，您的函数将采用指向 struct text 的指针。 .

occurrences struct text 中的数组可以根据需要动态重新分配。 (这也是为什么 trie 节点中的 first 成员是数组的索引，而不是指针:如果它是指针，我们可能必须遍历整个 trie 才能更新重新分配数组时所有节点的指针，否则。)

请注意，因为我们使用 size_t作为数组的索引，NO_INDEX是最大可能值，并且 size_t是无符号整数类型，检查 if (i < count) 就足够了验证索引 i有效。

每个 trie 节点对应一个完整的单词有 index != NO_INDEX ，以及 C99 灵活阵列成员 word初始化为完整单词(包括尾随 L'\0' )。 occurs成员将拥有该单词出现的次数，如果有用的话。 (除了我们人类可能对每个单词出现的次数感兴趣之外，没有需要。)

此方案允许直接访问文本中的单词序列。

如果出现的次数在数组中递增的偏移量中，则可以使用二分搜索来查找特定偏移量之间的单词。因为每次出现都有一个指向 trie 节点的反向链接，其中包含 word 中的完整单词。成员，很容易打印出文件中出现的任何单词，而不必扫描整个字典树。

我写这个答案是因为我想展示如何以这种方式组合两种截然不同的数据结构，可以开辟非常有效的数据访问方法。我不能说它是否有用，因为有用性取决于正在解决的问题。