在Trie结构中添加单词C

Question

嗨我正在尝试为英语创建一个trie结构以西班牙单词词典。

这是我到目前为止有：

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++ 
    } 
} 

我不知道在哪里可以从这里走。任何帮助，将不胜感激。谢谢！

Answer 1

嗯，我认为你的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; 
} 

就是这样！我想，答案很长，但很有趣。