如何在 C 中使 trie 存储一个词的重现

Question

我的 trie 的当前节点存储一个字符和一个位置（这是文本中当前正在读取的单词结束的位置）。

如果我在第 100 位读到一个词 "foo"，在第 200 位读到另一个词 "foo"，我的节点如何存储这 2 次出现？有没有快速的方法（使用数组或更快实现的东西）或者我需要实现链表？

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对应当前职位数。必要时可以重新分配数组并调整其大小。这种数组大小调整在实际应用中很常见；（重新分配的）开销被认为是完全可以接受的，尤其是与替代方案相比。

另一个有趣的选择是使用线性数组按照出现的顺序表示文本中的单词，trie 节点中的 position 成员指定第一次出现的索引大批。每个数组条目将包含下一次出现的索引，加上可选的 link 返回到 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 */
};

容器结构将包含数组，而 trie 将挂起它：

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

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

的指针

struct text 中的 occurrences 数组可以根据需要动态重新分配。（这也是为什么 trie 节点中的 first 成员是数组 的索引 而不是指针：如果它是指针，我们可能必须通过整个尝试更新所有节点的指针，当重新分配数组时，否则。）

注意，因为我们使用一个size_t作为数组的索引，NO_INDEX是最大的可能值，而size_t是无符号整数类型，所以足以检查 if (i < count) 以验证索引 i 是否有效。

对应一个全词的每个trie节点都有index != NO_INDEX，C99灵活数组成员word初始化为全词（包括尾部L'[=30=]'）。 occurs 成员将有单词出现的次数，如果有用。（没有需要，除了我们人类可能对每个单词的出现次数感兴趣。）

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

如果出现在数组中递增的偏移量中，则可以使用二进制搜索来查找特定偏移量之间的单词。因为每次出现都有一个返回 link 的 trie 节点，其中包含 word 成员中的完整单词，所以很容易打印出文件中出现的任何单词，而无需扫描整个特里。

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

如何在 C 中使 trie 存储一个词的重现

How to make trie store reincidence of a word in C

c

trie

string-matching