добавление слов в структуру 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. Эта идея разделения узлов имеет решающее значение. Если в списке есть только одно слово, например. «привет», тогда будет только 2 узла: корневой узел (пустая строка) и единственный дочерний корневой узел «привет». Если мы хотим добавить еще одно слово, которое имеет общий префикс с «привет», например. «эй», нам нужно разделить «привет» на 2 узла: «он», ребенок корневого узла и «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. Это слово будет либо распространять общий префикс с одним из наших детей, либо не будет. Если это не так, мы можем просто создать новый узел, значение которого - это слово, и добавить его в наш список детей. Однако, если это так, то мы сталкиваемся с несколькими различными случаями, в зависимости от того, как долго был общий префикс.

Дело 1: Слово совпадает с нашим ребенком точно (то есть, слова одинаковы). В этом случае наш ребенок точно соответствует этому слову, и мы можем просто обновить перевод и остановить (нет необходимости создавать новые узлы).

Дело 2: Слово в целом является приставкой нашего ребенка.В этом случае нам нужно разбить ребенка на 2 части; первое - наше слово, второе - остальное слово, ранее сохраненное у нашего ребенка. Первая часть становится новым ребенком, и мы сохраняем перевод в нем, вторая часть становится дочерью нашего ребенка.

Дело 3: наш ребенок в целом является префиксом слова. В этом случае мы удаляем общий префикс из слова (сокращаем слово только суффиксом). Затем мы добавляем суффикс слова к поддереву, укорененному на нашем дочернем элементе (т.е. recurse).

Дело 4: общий префикс короче, чем оба слова. В этом случае нам нужно сначала разделить ребенка. Префикс становится новым потомком с суффиксом в качестве дочернего ребенка. Затем мы удаляем префикс из слова, а затем добавляем остальную часть слова в поддерево, укорененное в нашем дочернем элементе (т.е. recurse).

И все 4 случая. Вооружившись этим, мы теперь можем легко написать функцию для обработки каждого из этих случаев, используя рекурсию для перехода по trie.

/* 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; 
} 

И все! Долгий ответ, я полагаю, но это было весело.