Pset 4: Speller (trie) - misspelled words

Question

I'm stuck. In Speller, implemented with trie, I get more misspelled words than I should. The number of words loaded into the dictionary is correct, there are no leaks or error messages. When checking cat.txt, caterpillar is considered misspelled... I think I'm missing something in check(), maybe what happens when pTrav->children[i] == NULL.

Check()

bool check(const char *word)
{
    node* pTrav = root;

    for (int i = 0; i < strlen(word); i++)
    {
        index = get_index(word[i]);

        if (pTrav->children[index] != NULL)
        {
            pTrav = pTrav->children[index];
        }
    }

    return pTrav->is_word;
}

Load()

bool load(const char *dictionary)
{
    // Initialize trie
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        return false;
    }
    root->is_word = false;
    for (int i = 0; i < N; i++)
    {
        root->children[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1]; //[] = Max size of word read into buffer

    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {
        //Traversing pointer starting at root
        node *pTrav = root;

        for (int i = 0, n = strlen(word); i < n; i++)
        {
            // Create index in node corresponding to the current letter or '\'' [0-26]
            index = get_index(word[i]);

            // Create new node initialized to NULL
            if (pTrav->children[index] == NULL)
            {
                new_node = get_node();
                pTrav->children[index] = new_node;
            }
            else
            {
                // Move to next node
                pTrav = pTrav->children[index];
            }
        }

        // At the end of the word (loop) set is_word to true and update counter
        pTrav->is_word = true;
        word_counter++;
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

get_index()

int get_index(char c)
{
    if (isalpha(c))
    {
        return tolower(c) - 'a';
    }
    else
    {
        return APOSTROPHE; // = 26
    }
}

get_node()

struct node *get_node(void)
{
    node *new_n = malloc(sizeof(node));
    if (new_n == NULL)
    {
        return false;
    }
    new_n->is_word = false;
    for (int i = 0; i < N; i++)
    {
        new_n->children[i] = NULL;
    }
    return new_n;
}

Answer 1

Hmmm, interesting problem. ;-) I made a few assumptions on declarations, but they appear to be right. So, let's look at the core block of code that inserts the word into the trie.

    for (int i = 0, n = strlen(word); i < n; i++)
    {
        // Create index in node corresponding to the current letter or '\'' [0-26]
        index = get_index(word[i]);

        // Create new node initialized to NULL
        if (pTrav->children[index] == NULL)
        {
            new_node = get_node();
            pTrav->children[index] = new_node;
// the problem is on THIS line - well, actually, it isn't here!  ;-) @cliffb
        }
        else
        {
            // Move to next node
            pTrav = pTrav->children[index];
        }
    }

Now, lets insert the first letter node. The code drops into the for loop, gets the index for the letter, checks if there's already an existing node for that letter and if not (there isn't), executes pTrav->children[index] = new_node;. OK so far.

But what's the next step? The code is supposed to then step to the node that was just created in preparation for inserting the next node in the sequence. Where is that step?

That next step is missing, so the next node is inserted into the tree at the root level, not at the second level of the trie. Once nodes at the root level are populated, then else code would be executed, stepping further into the trie. In other words, it's a corrupt trie. The only words guaranteed to be correctly populated have a length of 1. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)