2

こんにちは私は英語からスペイン語の単語辞書のトライ構造を作成しようとしています。

これが私がこれまでに持っているものです：

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

ここからどこへ行けばいいのかわからない。どんな助けでもいただければ幸いです。ありがとう！

4

1 に答える 1

4

ええと、私はあなたがあなたの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をさらに下に移動する必要がある可能性があります。ノードを分割するというこのアイデアは非常に重要です。リストに単語が1つしかない場合、たとえば。「hello」の場合、ルートノード（空の文字列）とルートノードの唯一の子「hello」の2つのノードのみが存在します。ここで、「hello」と共通のプレフィックスを共有する別の単語を追加したい場合、たとえば。「ねえ」、「hello」を2つのノードに分割する必要があります。ルートノードの子である「he」と「he」の子である「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構造で非常にうまく流れることがよくあります。したがって、トライ（ルートノード）とトライで一致する単語が与えられたとしましょう。この単語は、私たちの子供たちの1人と共通の接頭辞を共有するか、共有しません。そうでない場合は、この単語を値とする新しいノードを作成し、それを子のリストに追加するだけです。ただし、そうなると、共通プレフィックスの長さに応じて、いくつかの異なるケースが発生します。

ケース1：単語は私たちの子供と完全に一致します（つまり、単語は同じです）。この場合、子はこの単語と完全に一致し、翻訳を更新して停止するだけで済みます（新しいノードを作成する必要はありません）。

ケース2：単語は、全体として、私たちの子供の接頭辞です。この場合、子を2つの部分に分割する必要があります。最初は私たちの言葉であり、2番目は以前に私たちの子供に保存された残りの言葉です。最初の部分が新しい子になり、その中に翻訳が保存され、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;
}

以上です！長い答えだと思いますが、楽しかったです。

于 2010-01-22T00:44:02.810 に答える