在Trie结构中添加单词C
嗨我正在尝试为英语创建一个trie结构以西班牙单词词典。在Trie结构中添加单词C
这是我到目前为止有:
struct s_trie_node
{
char * translation; /* NULL if node not a word */
char * word;
/* pointer array to child nodes */
struct s_trie_node * children[UCHAR_MAX+1];
};
int add_word(const char * word, char * translation) {
/* TODO: add word to trie structure
If word exists, append translation to existing string
Be sure to store a copy of translation, since
the string is reused by load_dictionary()
*/
struct s_trie_node * curr = proot;
char * currLetter = word;
while (currLetter != '\0') {
while ((curr -> children) != NULL) {
char * currChildLetter = ((curr -> children) -> word);
char * copyWord = word;
while (copyWord == currChildLetter) {
copyWord++;
currChildLetter++;
}
if (currChildLetter == '\0') {
curr = (curr -> children);
break;
}
(curr -> children)++;
}
currLetter++
}
}
我不知道在哪里可以从这里走。任何帮助,将不胜感激。谢谢!
嗯,我认为你的add_word函数太大了。先尝试并将其分解成更小的问题。一旦你解决了小问题,更大的问题可能会变得更容易。
首先,我们必须实际创建Trie节点(试图在add_word中执行此操作会很难看)。所以,让我们现在做一个函数,它是:
/* Allocates, initializes, and returns a new Trie node. The node will contain
* a copy of word and trans, rather than use them directly. The children array
* will be initialized to all NULL's.
*/
struct s_trie_node * trie_node_create(const char * prefix, const char * trans)
{
struct s_trie_node * n = malloc(sizeof(struct s_trie_node));
int i;
n->word = prefix ? strdup(prefix) : strdup("");
n->translation = trans ? strdup(trans) : NULL;
for (i = 0; i < UCHAR_MAX + 1; i++)
n->children[i] = NULL;
return n;
}
你应该注意到,我们正在创建的字符串的副本,而不是直接使用它们。这使得Trie图书馆的用户可以更轻松地生活,也可以让我们在不再需要时释放它们,而无需担心用户是否在其他地方使用它们。然而,这是一个重要的决定,因为它意味着我们有责任确保这些字符串在以后被释放。此外,我们正在使用strdup,这意味着我们假设传递给我们的字符串是“干净的”(即以NULL字符结尾)。
不管怎样,现在我们可以创建节点。让我们继续讨论更多与Trie相关的问题。显然,你将需要能够找出2个字符串的公共前缀的长度。如果你不能做到这一点,你不能做任何事情。因此,我们可以使用以下功能:
/* Returns length of common prefix of v & w. */
int match(char * v, char * w)
{
char * start = v;
for (; *v && *v == *w; v++, w++);
return v - start;
}
这是非常基本的,但是是必要的。当我们比较一个字与一个前缀节点时,知道这个通用前缀的长度会告诉我们它是完全匹配还是部分匹配。完全匹配意味着我们只需要更新节点。部分匹配可能导致子节点不得不被“分裂”为2,这很可能意味着我们必须沿着Trie进一步下去。这种分割节点的想法是至关重要的。如果列表中只有一个单词,例如。 “hello”,那么将只有2个节点:根节点(空字符串)和根节点的唯一子节点“hello”。如果我们现在想添加另一个与“hello”共享前缀的词,例如。 “hey”,我们需要将“hello”分成两个节点:“he”,根节点的孩子,以及“llo”的孩子“llo”。所以,让我们创建一个函数,将处理拆分节点为我们:
/* Creates a new node that is a child of n. The word stored at n will be
* truncated after location (index into n->word), with the remaining suffix
* of the word belonging to the new child of n.
*/
struct s_trie_node * trie_node_split(struct s_trie_node * n, int location)
{
struct s_trie_node * child;
char * prefix;
char * suffix;
int len = strlen(n->word);
if (location <= 0)
return NULL;
if (location >= len)
return n;
prefix = strndup(n->word, location);
suffix = strndup(n->word + location, len - location);
child = trie_node_create(suffix, n->translation);
memcpy(child->children, n->children,
sizeof(struct s_trie_node *) * UCHAR_MAX);
free(n->word);
n->word = prefix;
n->translation = NULL;
n->children[0] = child;
n->children[1] = NULL;
return n;
}
由于能够找到共同的前缀长度2串之间,创建节点和分裂节点,我们需要所有的基本操作操纵和穿越我们的Trie。
现在,递归通常非常适合Trie结构。所以,假设你有一个trie(根节点)和一个单词来匹配Trie。这个词或者与我们的一个孩子共享一个共同的前缀,或者它不会。如果没有,那么我们可以简单地创建一个新的节点,其值是这个词并将其添加到我们的孩子列表中。但是,如果是这样,那么我们会遇到几种不同的情况,具体取决于常用前缀的长度。
案例1:单词与我们的孩子完全匹配(也就是说,单词是相同的)。在这种情况下,我们的孩子与这个词完全匹配,我们可以简单地更新翻译并停止(不需要创建任何新节点)。案例2:这个词的全部内容是我们孩子的前缀。在这种情况下,我们需要将孩子分成两部分;第一个是我们的词,第二个是先前存储在我们孩子的单词的其余部分。第一部分成为新生儿,我们将翻译存储在其中,第二部分成为我们孩子的孩子。案例3:我们的孩子整体上是这个词的前缀。在这种情况下,我们从单词中删除共同前缀(将单词缩短为仅后缀)。然后,我们将该词的后缀添加到植根于我们孩子的子树(即递归)中。
案例4:通用前缀比两个单词都短。在这种情况下,我们需要先分裂孩子。前缀成为新的孩子,后缀为孩子的孩子。然后,我们删除单词中的前缀,然后将该单词的其余部分添加到植根于我们孩子的子树(即递归)中。
这就是全部4种情况。有了这个武装,我们现在可以轻松编写一个函数来处理这些情况,使用递归遍历树。
/* Add a translation to the Trie rooted at root. */
int trie_add_word(struct s_trie_node * root, char * word, char * trans)
{
struct s_trie_node ** n;
int loc;
for (n = root->children; *n; n++) {
/* Find length of longest common prefix. */
loc = match(word, (*n)->word);
if (!loc) {
continue;
} else {
if (loc != strlen((*n)->word))
trie_node_split(*n, loc);
word += loc;
if (!*word) {
if ((*n)->translation)
free((*n)->translation);
(*n)->translation = strdup(trans);
return 0;
}
return trie_add_word(*n, word, trans);
}
}
/* Failed to find any children that matched. */
if (n - root->children >= UCHAR_MAX) {
fprintf(stderr, "Ran out of room to store children in.");
return -1;
}
*n = trie_node_create(word, trans);
return 0;
}
就是这样!我想,答案很长,但很有趣。
我还要提一下,你应该真的把你的孩子存放在一个链表中;每个节点应该有一个指向它的同胞的指针和一个指向它的第一个孩子的指针。这将使遍历更容易,也将删除您正在进行的UCHAR_MAX事情。 – tixxit 2010-01-22 00:58:03