0

So my speller works fine with a custom dict, but not with the large dict. This is my code in dictionary.c (haven't modified other files):

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "dictionary.h"


// Represents number of children for each node in a trie
#define N 27
unsigned int words = 0;

// Prototype for index function
unsigned int index(char c);

// Represents a node in a trie
typedef struct node
{
    bool is_word;
    struct node *children[N];
}
node;

// Represents a trie
node *root;

// declare free node function
void clear(node *ptr);

// Loads dictionary into memory, returning true if successful else false
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];

    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {
        words ++;
        node *cursor = root;
        for (int i = 0, l = strlen(word); i < l; i++)
        {
            unsigned int n = index(word[i]);

            node *next_node = cursor->children[n];
            if (next_node == NULL)
            {
                 next_node = malloc(sizeof(node));
                 if (next_node == NULL)
                 {
                     return false;
                 }
                 next_node->is_word = false;
                 for (int j = 0; j < N; j++)
                 {
                     next_node->children[j] = NULL;
                 }
                 cursor->children[n] = next_node;
                 if (i == l - 1)
                 {
                     cursor->is_word = true;
                 }
                 cursor = next_node;
            }
            else
            {
                if (i == l - 1)
                {
                    cursor->is_word = true;
                }
                cursor = cursor->children[n];
            }



        }
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return words;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *cursor = root;

    for (int i = 0, l = strlen(word); i < l; i++)
    {
        unsigned int n = index(word[i]);

        if (cursor->children[n] == NULL)
        {
            return false;
        }

        if (i == l - 1)
        {
            if (cursor->is_word == true)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        cursor = cursor->children[n];
    }
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    clear(root);
    return true;
}


//function to clear a node
void clear(node *ptr)
{
    for (int i = 0; i < N; i++)
    {
        if (ptr->children[i] != NULL)
        {
            clear(ptr->children[i]);
        }
    }
    free(ptr);
}

// Function to get the index of a letter or '\''
unsigned int index(char c)
    {
        unsigned int n;
        if (('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z'))
        {
            n = tolower(c) - 'a';
        }
        else if (c == '\'')
        {
            n = 26;
        }
        else
        {
            n = 1000;
        }
        return n;
    }

Some differences between what the code caught and what should be caught if I run ./speller texts/lalaland.txt: "l', "mia","o","s'... more generally it seems all one letter word are not caught. While debugging I saw that this is because the first pointer-> is_word is always true but I can't figure out why. Again this works with a custom dict so for example if there is just the letter'b' in my file, is_word will be false with custom dict but true with large dict.

Thank you very much for your help !

1
                 if (i == l - 1)
                 {
                     cursor->is_word = true;
                 }

would have to go behind

                 cursor = cursor->children[n];

because otherwise you target the wrong node.

I would place the cursor->is_word after the inner loop, when the cursor is on that node anyway.

Similarly, your check checks one node too early (partially covering the mistake from load). If I had a custom dict of the words "cats" and "caterpillar", you would report "cate" as valid word.

| improve this answer | |
  • Awesome this works thank you! For some reason I thought that the last letter node had to contain "true" when it's actually the last pointer that has to point to true. – Daniel Nov 28 '19 at 19:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .