Too much misspelled in pset5 dictionary

Question

Through my code, I got 19190 misspelled. It seems I have a problem in check though. Anyone who can find any problem here??

dictionary.h

 /**
 * dictionary.h
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Declares a dictionary's functionality.
 */

#ifndef DICTIONARY_H
#define DICTIONARY_H

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

// maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

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

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */

bool load(const char* dictionary);


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



/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void);

#endif // DICTIONARY_H

dictionary.c

  /**
   * dictionary.c
   *
   * Computer Science 50
   * Problem Set 5
   *
   * Implements a dictionary's functionality.
   */




#include "dictionary.h"



     typedef struct node
        {
            char word[LENGTH + 1];
            struct node* next;
        }node;

    int hash_function(char* key)
        {
            int hash = tolower(key[0]) - 'a';
            return hash % 27;
        }


    node* hashtable[27];    
    int sizes = 0;


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    int s = strlen(word);
    char checker[strlen(word) + 1];

    for(int i = 0; i < s; i++)
      {

        if(isupper(word[i]))
        {
          checker[i] =  tolower(word[i]);
        }
        else
          checker[i] = word[i];
      } 




    int a = hash_function(checker);

    node* crawler = malloc(sizeof(node));
    crawler = hashtable[a];
    if (a >= 0)
    { while(crawler != NULL)
     {
        if (strcmp(crawler -> word, checker) == 0)
        {
            return true;

        }
        else
        crawler = crawler -> next;

     }
    }

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
    bool load(const char* dictionary)
    {






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


     while(feof(file) != 0)
      { 

        node* new_node = malloc(sizeof(node));
        fscanf(file, "%s", new_node->word);
        int a = hash_function(new_node-> word);


        if (hashtable[a] == NULL) 
        {
            hashtable[a] = new_node;

            new_node -> next = NULL;
            sizes++;
        }
        else if(hashtable[a] != NULL)
        {

          new_node->next = hashtable[a];
          hashtable[a] = new_node; 

            sizes++;

        }




      }


        return true;
        fclose(file);
    }

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

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    for(int i =0; i < 27; i++)
    {
        node* cursor = hashtable[i];

        while(cursor != NULL)
        {
            node* temp = cursor;
            cursor = cursor->next;
            free(temp);
        }

    }
    return true;
}

speler.c

 /**
 * speller.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a spell-checker.
 */

#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>


#include "dictionary.h"
#undef calculate
#undef getrusage

// default dictionary
#define DICTIONARY "dictionaries/large"

// prototype
double calculate(const struct rusage* b, const struct rusage* a);

int main(int argc, char* argv[])
{
    // check for correct number of args
    if (argc != 2 && argc != 3)
    {
        printf("Usage: speller [dictionary] text\n");
        return 1;
    }

    // structs for timing data
    struct rusage before, after;

    // benchmarks
    double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;

    // determine dictionary to use
    char* dictionary = (argc == 3) ? argv[1] : DICTIONARY;

    // load dictionary
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary);
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not loaded
    if (!loaded)
    {
        printf("Could not load %s.\n", dictionary);
        return 1;
    }

    // calculate time to load dictionary
    time_load = calculate(&before, &after);

    // try to open text
    char* text = (argc == 3) ? argv[2] : argv[1];
    FILE* fp = fopen(text, "r");
    if (fp == NULL)
    {
        printf("Could not open %s.\n", text);
        unload();
        return 1;
    }

    // prepare to report misspellings
    printf("\nMISSPELLED WORDS\n\n");

    // prepare to spell-check
    int index = 0, misspellings = 0, words = 0;
    char word[LENGTH+1];

    // spell-check each word in text
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            // append character to word
            word[index] = c;
            index++;

            // ignore alphabetical strings too long to be words
            if (index > LENGTH)
            {
                // consume remainder of alphabetical string
                while ((c = fgetc(fp)) != EOF && isalpha(c));

                // prepare for new word
                index = 0;
            }
        }

        // ignore words with numbers (like MS Word can)
        else if (isdigit(c))
        {
            // consume remainder of alphanumeric string
            while ((c = fgetc(fp)) != EOF && isalnum(c));

            // prepare for new word
            index = 0;
        }

        // we must have found a whole word
        else if (index > 0)
        {
            // terminate current word
            word[index] = '\0';

            // update counter
            words++;

            // check word's spelling
            getrusage(RUSAGE_SELF, &before);
            bool misspelled = !check(word);
            getrusage(RUSAGE_SELF, &after);

            // update benchmark
            time_check += calculate(&before, &after);

            // print word if misspelled
            if (misspelled)
            {
                printf("%s\n", word);
                misspellings++;
            }

            // prepare for next word
            index = 0;
        }
    }

    // check whether there was an error
    if (ferror(fp))
    {
        fclose(fp);
        printf("Error reading %s.\n", text);
        unload();
        return 1;
    }

    // close text
    fclose(fp);

    // determine dictionary's size
    getrusage(RUSAGE_SELF, &before);
    unsigned int n = size();
    getrusage(RUSAGE_SELF, &after);

    // calculate time to determine dictionary's size
    time_size = calculate(&before, &after);

    // unload dictionary
    getrusage(RUSAGE_SELF, &before);
    bool unloaded = unload();
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not unloaded
    if (!unloaded)
    {
        printf("Could not unload %s.\n", dictionary);
        return 1;
    }

    // calculate time to unload dictionary
    time_unload = calculate(&before, &after);

    // report benchmarks
    printf("\nWORDS MISSPELLED:     %d\n", misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", n);
    printf("WORDS IN TEXT:        %d\n", words);
    printf("TIME IN load:         %.2f\n", time_load);
    printf("TIME IN check:        %.2f\n", time_check);
    printf("TIME IN size:         %.2f\n", time_size);
    printf("TIME IN unload:       %.2f\n", time_unload);
    printf("TIME IN TOTAL:        %.2f\n\n", 
     time_load + time_check + time_size + time_unload);

    // that's all folks
    return 0;
}

/**
 * Returns number of seconds between b and a.
 */
double calculate(const struct rusage* b, const struct rusage* a)
{
    if (b == NULL || a == NULL)
    {
        return 0.0;
    }
    else
    {
        return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
                 (b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
                ((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
                 (b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
                / 1000000.0);
    }
}

And these are outcome by valgrind

WORDS MISSPELLED:     19190
WORDS IN DICTIONARY:  0
WORDS IN TEXT:        19190
TIME IN load:         0.01
TIME IN check:        0.21
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.22

==19350== 
==19350== HEAP SUMMARY:
==19350==     in use at exit: 1,075,208 bytes in 19,191 blocks
==19350==   total heap usage: 19,192 allocs, 1 frees, 1,075,776 bytes allocated
==19350== 
==19350== LEAK SUMMARY:
==19350==    definitely lost: 1,074,640 bytes in 19,190 blocks
==19350==    indirectly lost: 0 bytes in 0 blocks
==19350==      possibly lost: 0 bytes in 0 blocks
==19350==    still reachable: 568 bytes in 1 blocks
==19350==         suppressed: 0 bytes in 0 blocks
==19350== Rerun with --leak-check=full to see details of leaked memory
==19350== 
==19350== For counts of detected and suppressed errors, rerun with: -v
==19350== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

I was supporsed to get this

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         0.04
TIME IN check:        0.02
TIME IN size:         0.00
TIME IN unload:       0.02
TIME IN TOTAL:        0.08

Answer 1

There are a number of problems. This will point you in the right direction, but you get to have the fun of implementing the fixes. ;-)

First, load() isn't creating a dictionary. Put the following printf line in your load function as shown here:

 while(feof(file) != 0)
  { 
       printf("Start load function.\n");

I think you'll be surprised.

Your massive memory leak is in check(). The first clue was that the number of blocks is exactly the same as the number of words. Look at the following:

node* crawler = malloc(sizeof(node));
crawler = hashtable[a];

You malloc memory and then abandon it by reassigning something else to crawler. Instead, try node* crawler = NULL; or even

node* crawler = hashtable[a];

Also, you're leaving the dictionary file open because the fclose() follows the return. Return will immediately cause the program to return control to the calling function. Nothing that follows will be executed.

In the hash function, you're returning hash % 27. Why 27? You're checking the first letter of the word, which can never be an apostrophe. Also, there's no code to handle an apostrophe anywhere (and not needed since you're not doing a trie.) It's a minor point, but could lead to problems.

There are other errors, but these are the biggest, or subtle enough not to be noticed. How you fix these may affect other issues. This will get you going though.

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

Answer 2

I think the word you are loading in memory and and reading for check are not equal. There is probably a difference of deliminator or next line character between both. I had the same issue when i was doing this pset.