0

I have been trying to implement and re-implement speller but so far, I haven't been so lucky. This is what I get for a custom smaller dictionary and a text file:

MISSPELLED WORDS

nice

WORDS MISSPELLED:     1
WORDS IN DICTIONARY:  6
WORDS IN TEXT:        1
TIME IN load:         0.00
TIME IN check:        0.00
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.00

Here is what inside the small dictionary i made and a text file i want to be checked:

  1. Dictionary:

    cat
    nice
    caterpillar
    catch
    hello
    I
    
  2. Text file to be checked:

    nice hi
    

And here is my source code:

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>


#include "dictionary.h"

//Trie Data Structure.
typedef struct node
{
    bool isWord;
    struct node* children[27];
}node;

//Make new node function prototype.
node* newNode(void);
//free node function prototype.
void freenode(node* node);

//Declaring root here so that the root is global. and all other global variables
node* root = NULL;

unsigned int wordcount;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    int i;
    node* trav = root;
    int length = strlen(word);
    char worD[length+1];
    int index = 0;
    for (int i = 0; i < length; i++)
    {
        worD[i] = word[i];
        if(isupper(worD[i]))
        {
          worD[i] = tolower(worD[i]);
        }
    }
    worD[length+1] = '\0';

    for (i = 0; i<length; i++)
    {
            int c = word[i];
            if (isalpha(c))
            {
                index = tolower(c) - 'a';
            }else if (c == '\'')
            {
                index = 27;
            }

            if (trav->children[index] == NULL)
            {
                return false;
            }else
            {
             trav = trav->children[index];
            }
    }
    if(trav->isWord && worD[i] == '\0')
    {
    return trav->isWord;
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    //variable for storing indiviual word from the dictionary to  be loaded.
    char word[45+1];
    // children Index
    int index = 0;
    int length = strlen(dictionary);
    root = newNode();
    //a traversal pointer equal to root. We'll use only this traversal pointer.
    node* trav = root;

    //Open the dictionary
    FILE* dictfp = fopen(dictionary, "r");
    //return null if file can't be opened.
    if (dictfp == NULL)
    {
        return false;
    }


    //loop to iterate through all the words in the dictionary file.
    while(!feof(dictfp))
    {
        fscanf(dictfp, "%s\n", word);
        length = strlen(word);

                for (int i = 0; i < length; i++)
                {
                    int c = word[i];
                    if (isalpha(c))
                    {
                        index = tolower(c) - 'a';
                    }else if (c == '\'')
                    {
                        index = 27;
                    }

                    if (trav->children[index] == NULL)
                    {
                        node* newnode = newNode();
                        trav->children[index] = newnode;
                        trav = newnode;

                    }else //"If not not"//if (trav->children[index] != NULL)
                    {
                     trav = trav->children[index];   
                    }
                }
                //set isWord member true.
                    trav->isWord = true;
                //counting the number of words loaded, which is later to be returned by the size functions.
                wordcount++;
    }
    fclose(dictfp);
    return true;
}

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

    return wordcount;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    for (int i = 0; i < 27; i++)
    {
    if (root->children[i] != NULL)
    {
     freenode(root->children[i]);   
    }
    }
    return true;
}




////Make a new node function
node* newNode(void)
{
    node* newnode = malloc(sizeof(node));
    //setting all children pointers to NULL.
    for (int i = 0; i < 27; i++)
    {
        newnode->children[i] = NULL;
    }
    newnode->isWord = false;
    return newnode;
}

//recursive function for free all the children nodes.
void freenode(node* node)
{
    for (int i = 0; i < 27; i++)
    {
        if (node->children[i] != NULL)
        {
            freenode(node->children[i]);
        }
    }
    free(node);
}

I also loose about 200 mb less or more even if i am doing something inside the unload function. But of course, that's something to be concerned about later after check is correctly working.

Thanks in advance!

EDIT:

bool check(const char* word)
{
    node* trav = root;
    int length = strlen(word);
    char worD[length];
    int index = 0;
    for (int i = 0; i < length; i++)
    {
        worD[i] = word[i];
        if(isupper(worD[i]))
        {
          worD[i] = tolower(worD[i]);
        }
    }
    worD[length-1] = '\0';

    for (int i = 0; i<length; i++)
    {
            int c = word[i];
            if (isalpha(c))
            {
                index = tolower(c) - 'a';
            }else if (c == 39)
            {
                index = 26;
            }

            if (trav->children[index] == NULL)
            {
                return false;
            }else
            {
             trav = trav->children[index];
            }
    }
    if(trav->isWord && worD[length-1] == '\0')
    {
    return true;
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    int length;
    //variable for storing indiviual word from the dictionary to  be loaded.
    char word[45+1];
    // children Index
    int index = 0;
    root = newNode();
    //a traversal pointer equal to root. We'll use only this traversal pointer.
    node* trav = root;

    //Open the dictionary
    FILE* dictfp = fopen(dictionary, "r");
    //return null if file can't be opened.
    if (dictfp == NULL)
    {
        return false;
    }


    //loop to iterate through all the words in the dictionary file.
    while(!feof(dictfp))
    {
        trav = root;
        fscanf(dictfp, "%s", word);
        length = strlen(word);
        wordcount++;
                for (int i = 0; i < length; i++)
                {
                    int c = word[i];
                    if (isalpha(c))
                    {
                        index = tolower(c) - 'a';
                    }else if (c == 39)
                    {
                        index = 26;
                    }

                    if (trav->children[index] == NULL)
                    {
                        node* newnode = newNode();
                        trav->children[index] = newnode;
                        trav = newnode;

                    }else //"If not not"//if (trav->children[index] != NULL)
                    {
                     trav = trav->children[index];   
                    }
                }
                //set isWord member true.
                    trav->isWord = true;
                //counting the number of words loaded, which is later to be returned by the size functions.
                // wordcount++;
    }
    fclose(dictfp);
    return true;
}
1

Both load and check have problems.

In load, trav is not reset to point at root after adding a word to the dictionary, so the only actual word in the trie is the first word from the dictionary.

wordcount is off by 1. The logic you have in your while loop is to read a word, process it, and then check for end of file. The EOF condition is only detected when it is actually encountered. When the last word is read, the EOF is not detected until the next read. So, the code is processing one extra word (either garbage data or the last word twice), and adding one extra word to the count.

check() has this line:

worD[length+1] = '\0';

That's one past the end of worD.

Both load and check don't handle apostrophe correctly. There is no trav->children[27].

You need to be careful about array element counts. You tend to make the mistake of using the number of elements as the index of the last element when the last element is the number of elements minus 1.

Side notes:

Why length=strlen(dictionary); ? The \n in the fgets read from the dictionary is not necessary.

In check, no need to test isupper when using tolower. tolower will only operate on an upper. Anything else will just be copied.

[EDIT: post-comments] Actually, your code isn't checking one less word than in the text file, it's adding one extra word in the load, as described above. The reason it seems like check is one word short is an anomaly in the speller.c file. Because of some past issues, they've written speller.c so that the dictionary and text file need to end with a line feed after the last word and then EOF. You can test this by running your program with a line feed at the end of the input file and then without to see what happens.

Back to your code. Without the line feed, you're missing the last word from the dictionary in your trie, but it's adding one extra to the count, so the count looks right - even though you've only processed 5 words in a 6 word dictionary. Then, using the same file as both the plain text and the dictionary (that's how everyone is testing, it's a good test), speller.c causes that last word to be skipped. Your code never sees it.

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

2
  • how does it count one extra word? the dictionary says 6 words in the dictionary and there are exactly 6 words in there. – yousafe007 Apr 21 '16 at 13:38
  • I've altered my source code for check and load. Take a look. But I still don't get why it checks one word less for a text input. – yousafe007 Apr 21 '16 at 14:51

You must log in to answer this question.

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