C에서 Trie 구조에 단어를 추가

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 기능을 사용하기에는 너무 큰 바이트를 사용하고 있다고 생각합니다. 시도하고 작은 문제로 먼저 나누십시오. 작은 문제를 풀면 더 큰 문제가 쉽게 될 것입니다.

먼저, 우리는 실제로 트라이 노드를 만들어야합니다 (add_word에서 이렇게하려고하면 추악 할 것입니다). 이제 다음을 수행하는 함수를 만들어 보겠습니다.

문자열을 직접 사용하는 대신 복사본을 생성한다는 점에 유의해야합니다. 이렇게하면이 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"이면 루트 노드 (빈 문자열)와 루트 노드의 유일한 자식 "hello"라는 두 개의 노드 만 존재합니다. 공통 접두어를 "hello"와 공유하는 다른 단어를 추가하려는 경우 (예 : "hey", "hello"를 2 개의 노드로 나눌 필요가 있습니다 : "he", 루트 노드의 자식, "llo", "he"의 자식. 자,이 우리를 위해 분할 노드를 처리하는 함수를 만들어 보자 :

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

을 능력으로 노드를 두 문자열 사이에 공통의 접두사의 길이를 찾을 작성하고, 분할 노드를, 우리는 모든 기본적인 작업이 필요했다 우리의 트라이를 조작하고 횡단합니다.

이제 Trie 구조에서는 재귀가 자주 발생합니다. 그래서, 당신은 trie (루트 노드)와 Trie에서 일치시킬 단어를받는 척하십시오. 이 단어는 우리 아이 중 하나와 공통 접두사를 공유하거나 그렇지 않습니다. 그렇지 않다면, 우리는 값이이 단어 인 새로운 노드를 간단히 생성하여 우리의 자식 목록에 추가 할 수 있습니다. 그러나 그렇게되면 공통 접두어의 길이에 따라 몇 가지 다른 경우가 생깁니다.

사례 1 : 단어가 우리 자녀와 정확하게 일치합니다 (즉, 단어가 동일 함). 이 경우, 우리 자녀는이 단어와 정확히 일치합니다. 우리는 단순히 번역을 업데이트하고 중지 할 수 있습니다 (새 노드를 만들지 않아도 됨).

사례 2 : 단어는 전체적으로 우리 아이의 접두사입니다.이 경우 두 부분으로 나누어야합니다. 첫 번째 단어는 우리의 말이고 두 번째 단어는 이전에 우리 아이에게 저장된 단어의 나머지 부분입니다. 첫 번째 부분은 새로운 자식이되고, 우리는 번역을 그 안에 저장합니다. 두 번째 부분은 우리 아이의 자식이됩니다.

사례 3 : 우리의 자녀는 그 단어의 접두어입니다. 이 경우 word (접미사 만 줄임)에서 공통 접두어를 제거합니다. 그런 다음 우리 아이를 뿌리로 한 하위 트리 (즉, 재귀)에 접미사를 추가합니다.

사례 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; 
} 

그리고 그게 전부입니다! 긴 대답, 나는 생각한다. 그러나 그것은 재미 있었다.