Worte zu einer Trie-Struktur in C Addieren

Question

Hallo Ich versuche, eine Trie-Struktur für ein Englisch auf Spanisch Wort-Wörterbuch zu erstellen.

Hier ist, was ich bisher:

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

Ich weiß nicht, wohin man von hier zu gehen. Jede Hilfe wäre sehr geschätzt. Dank!

Answer 1

Nun, ich glaube, Sie nehmen eine zu große mit Ihrem add_word Funktion Biss. Versuchen Sie, und brechen sie zunächst in kleinere Probleme auf. Sobald Sie die kleineren Probleme zu lösen, wird wahrscheinlich das größere Problem einfacher worden.

Als erstes müssen wir tatsächlich Trie-Knoten erstellen (versuchen, dies in add_word zu tun wäre, hässlich). So lassen Sie uns nun eine Funktion machen das tut dies:

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

Sie sollten beachten, dass wir Kopien der Saiten schaffen, anstatt sie direkt verwenden. Das macht das Leben einfach auf Nutzer dieser Trie-Bibliothek und ermöglicht es uns auch, sie zu befreien, wenn sie nicht mehr benötigt werden, ohne Sorge, wenn der Benutzer sie an anderer Stelle verwendet. Allerdings ist es eine wichtige Entscheidung, da es bedeutet, sind wir verantwortlich für diese Strings sichergestellt werden später befreit. Auch wir verwenden strdup, was bedeutet, dass wir die Annahme machen, dass die Saiten an uns vorbei sind „sauber“ (dh. Mit einem NULL-Zeichen beendet).

Wie auch immer, so können wir jetzt Knoten erstellen. Kommen wir nun auf mehr Trie-Probleme. Offensichtlich gehen müssen Sie die Länge des gemeinsamen Präfix von 2 Strings finden zu können. Wenn Sie dies nicht tun, kann man nichts anderes tun. So können wir die folgende Funktion verwenden:

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

Das ist ziemlich einfach, aber es ist eine Notwendigkeit. Wenn wir vergleichen, um ein Wort gegen einen Präfix Knoten, die Länge des gemeinsamen Präfixes zu wissen, wird uns sagen, ob es eine genaue Übereinstimmung oder eine teilweise Übereinstimmung ist. Genaue Übereinstimmung bedeutet, dass wir nur brauchen, um den Knoten zu aktualisieren. Teilweise Übereinstimmung in dem untergeordneten Knoten führen zu müssen, „Split“ in 2 und wird höchstwahrscheinlich bedeutet wir auf der Trie weiter zu gehen haben. Diese Idee der Spaltung Knoten ist von entscheidender Bedeutung. Wenn es nur ein Wort in der Liste, zum Beispiel. „Hallo“, dann wird es nur zwei Knoten sein: der Wurzelknoten (leere Zeichenkette) und der einzige Kind „Hallo“ Root-Knoten. Wenn wir jetzt wollen ein anderes Wort, dass Aktien ein gemeinsamen Präfix mit „Hallo“, zB hinzuzufügen. „Hey“, müssen wir „Hallo“ in zwei Knoten aufgeteilt: „er“, ein Kind des Wurzelknotens und „llo“, ein Kind von „er“. So lassen Sie uns erstellen eine Funktion, die das Aufteilen von Knoten für uns behandelt:

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

Mit der Fähigkeit, die Länge des gemeinsamen Präfix zwischen zwei Zeichenketten zu finden, erstellen Sie Knoten und Split-Knoten, haben wir alle grundlegenden Operationen notwendig, um zu manipulieren und unsere Trie durchqueren.

Nun fließt Rekursion oft sehr gut mit Trie-Strukturen. Also, so tun Sie einen Trie (der Wurzelknoten) und ein Wort Übereinstimmung in der Trie gegeben. Dieses Wort wird entweder einen gemeinsamen Präfix mit einem unseren Kindern teilen oder nicht. Wenn nicht, dann können wir einfach einen neuen Knoten erstellen, dessen Wert ist dieses Wort und fügen Sie ihn in die Liste unserer Kinder. Wenn es jedoch der Fall ist, dann laufen wir in verschiedene Fälle, je nachdem, wie lange das gemeinsame Präfix war.

Fall 1: Die Wortübereinstimmungen mit unserem Kind genau (das heißt, sind die Worte gleich). In diesem Fall ist unser Kind eine exakte Übereinstimmung zu diesem Wort, und wir können einfach die Übersetzung und Stopp aktualisieren (keine Notwendigkeit, irgendwelche neue Knoten erstellen).

Fall 2: Das Wort, in seiner Gesamtheit, ist ein Präfix unseres Kindes. In diesem Fall müssen wir das Kind in zwei Teile teilen; das erste unser Wort zu sein, der zweite den Rest des Wortes darstellen vorher bei unserem Kind gespeichert. Der erste Teil der neuen Kind wird, und wir speichern die Übersetzung darin, der zweite Teil wird ein Kind unseres Kindes.

Fall 3: Unser Kind, in seiner Gesamtheit, ist ein Präfix des Wortes. In diesem Fall entfernen wir den gemeinsamen Präfix aus Wort (shorten Wort nur das Suffix). Wir fügen dann das Suffix Wort zu dem Unterbaum in unserem Kind verwurzelt (dh. Recurse).

Fall 4: Der gemeinsame Präfix ist kürzer als die beiden Wörter. In diesem Fall müssen wir zuerst das Kind teilen. Das Präfix wird das neue Kind, mit dem Zusatz, wie das Kind des Kindes. Wir entfernen dann das Präfix von dem Wort, und fügen Sie dann den Rest des Wortes auf den Unterbaum in unserem Kind verwurzelt (dh. Recurse).

Und das ist alle 4 Fälle. Mit dieser bewaffnet, können wir now leicht eine Funktion schreiben, um jede dieser Fall zu behandeln, Rekursion mit dem Trie zu durchqueren nach unten.

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

Und das ist es! Lange Antwort, nehme ich an, aber es hat Spaß gemacht.