Spell-checker in C

I've been trying to implement a spell-checker using a large dictionary against some text file which contains around 2000 words. However, my spell-checker returns all words as being misspelled. I honestly have no idea why — could someone help me?

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

#include "dictionary.h"

#define lenght 45
#define hashtable_size 65536

char word[lenght+1];
int count = 0;

/*
*
* Hash function. Thanks to Brenda from cs50 reddit.
*/
int hash_it(const char* needs_hashing)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(needs_hashing); i<n; i++)
        hash = (hash << 2) ^ needs_hashing[i];
    return hash % hashtable_size;
}

typedef struct node
{
    char* word;
    struct node* next;
}node;

node* previous;
node* hashtable[hashtable_size];


/*
*
* Loads dictionary into memory.  Returns true if successful else false.
*/
bool load(const char* dictionary)
{
    char word[lenght+1];
    FILE* dict = fopen(dictionary,"r");

    for(int i = 0; i < 26;i++)
    {
        hashtable[i] = NULL;
        for(int a = fgetc(dict); a != EOF; a = fgetc(dict))
        {
            count++;

            int hashvalue = hash_it(word);

            node* new = malloc(sizeof(node));

            if(hashtable[hashvalue] == NULL)
            {
                hashtable[hashvalue] = new;
                new -> next = NULL;
            }
            else
            {
                new -> next = hashtable[hashvalue];
                hashtable[hashvalue] = new;
            }
        }
    }
    fclose(dict);
    return true;
}

/*
*
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{

    char tmp[lenght + 1];
    int lenghtw = strlen(word);
    for (int i = 0; i < lenghtw; i++)
    {
        tmp[i] = tolower(word[i]);
    }


    int index = hash_it(tmp);

    if (hashtable[index] == NULL)
    {
        return false;
    }

    node* cursor = hashtable[index];

    while(cursor != NULL)
    {
        if(strcmp(tmp, cursor -> word) == 0)
        {
            return true;
        }
        cursor = cursor -> next;
    }

    return false;
}

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

/*
*
* Unloads dictionary from memory.  Returns true if successful else false.
*/
bool unload(void)
{
    int index = 0;

    while(index < hashtable_size)
    {
        if(hashtable[index] == NULL)
        {
            index++;
        }
        else
        {
            while(hashtable[index] != NULL)
            {
                node* cursor = hashtable[index];
                hashtable[index] = cursor -> next;
                free(cursor);
            }
            index++;
        }
    }
    return true;
}

int main(int argc, char **argv)
{

    if (argc != 2)
        return 3;

    if (!load("dictionary"))
        return 1;

    printf("loaded %d words\n", size());
    printf("word '%s'%s found\n", argv[1], check(argv[1]) ? "" : " not");
    unload();
    return 0;
}

Answers


There are many problems in your code:

  • in the load function, you do not load words from the dictionary into the hash table. You read one character at a time with fgetc() and create a node from an uninitialized local buffer word.

  • the hash_it function only hashes the last 16 characters from the word. Furthermore, hashtable_size is a power of 2, a bad idea. Indeed only the last 8 characters participate in the hash value. This is not a bug, just an inefficient hashing method.

  • in the check function, you copy the word and convert it to lowercase, but you forget to set the final byte of the tmp array to '\0'.

Here is a corrected version of load that reads one word per dictionary line:

bool load(const char *dictionary) {
    char line[256];
    FILE *dict = fopen(dictionary, "r");

    if (!dict)
        return false;

    while (fgets(line, sizeof line, dict) != NULL) {
        char *p = line + strspn(line, " \t");  // skip blanks

        p[strcspn(p, " \t\r\n")] = '\0'; // strip trailing blanks

        if (*p == '\0' || *p == '#' || *p == ';')
            continue;  // ignore blank lines and comments

        count++;

        int hashvalue = hash_it(p);
        node *np = malloc(sizeof(node));

        np->word = strdup(p);
        np->next = hashtable[hashvalue];
        hashtable[hashvalue] = np;
    }
    fclose(dict);
    return true;
}

Need Your Help

search the registry with Java

java registry emulation blackberry-simulator

I've never worked with the registry before and it seems a bit intimidating, as I know very little about it . I need to asses if any Blackberry emulators are installed, and get their location if fou...

How to get locale currency price for in-app purchases in iOS?

iphone ios objective-c in-app-purchase

I want to find out user's App Store location. It means they are in US, Australia(AUD) store. Following code used.