Spell Check and Trie implementation

Question

I have written this code for an Edx course called CS50x (a beginner course).

This problem set required me to write a program which:

• loaded a dictionary into some sort of data structure (I choose to implement a trie) and which could take an input text and search for misspellings
• uses a file with an already implemented spell checker that lacked certain functions,
• one skeleton file to use as the base to create the functions that the first file required
• and a problem spec

It's hard to include info from the spec in this post (since a lot of it doesn't make since out of context), but I will try.

Also, a library is included with the virtual machine that is used for the course, so any function that you see which is not defined in the base libraries and you don't see defined in my two code files, then it is probably in the library.

Finally, this code works. This code probably won't compile for you since it is specifically made for one development environment (The CS50 "Appliance").

TLDR Here is the important thing to know: This is a code probably won't work for you since it is staged in a highly customized environment and comes with a custom library (Not sure if I used it in this program)

dictionary.c

The first file is called "dictionary.c" and the goal of it, per the spec, is to implement check, load, size, and unload which will, respectively, check for a word in the data structure, load a word in the data structure, check the size of the data structure, and unload the data structure (free the memory used for it). Dictionary.c contains no main function and is just composed of functions which are used in the second file, "speller.c".

speller.c

Speller.c's purpose in life is to check the spelling of a provided file against the spelling of words in a dictionary. In order to make this file work (it was provided as I stated in the second paragraph) I had to implement dictionary.c. I will include it as it may help your understanding of my code, but it is not important.

TLDR Dictionary is where I implement the trie and speller isn't important (don't review it) because it is pre-provided and is only here to show an implementation of Dictionary.

I should also say that I want to learn how to make this code faster, better formatted, and just general better.

dictionary.c

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

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "dictionary.h"
#include <ctype.h>
//Defines the trie data structure which is used to store the words
struct trieNode{
    char letter;
    bool wordComp;
    bool isRoot;
    struct trieNode* previous;
    struct trieNode* childNodes[27];
 }trie;
 struct trieNode* root;
 //The trie that will be used for the rest of the program
 //Stores wordCount after intialization of dictionary
 int sizeOfDic = 0;
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
    char currChar = ' ';
    currChar = word[0];
    struct trieNode* currNode = root;
    for(int i = 0; currChar != '\0'; i++)
    {
        currChar = word[i];
        if(currChar == '\0')
        {
            break;
        }
        else if(!isalpha(currChar)&&currChar != 39)
        {
            return false;
        }
        else if(currChar != 39)
        {
            currChar = tolower(currChar);
            if(currNode->childNodes[currChar - 'a'] != NULL)
            {
                currNode = currNode->childNodes[currChar - 'a'];
            }
            else
            {
                return false;
            }
            
        }
        else if(currChar == 39)
        {
            if(currNode->childNodes[26] != NULL)
            {
                currNode = currNode->childNodes[26];
            }
            else
            {
                return false;
            }
        }
    }
    if(currChar == '\0' && currNode->wordComp){
        return true;
    }else{
        return false;
    }
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    root = calloc(1,sizeof(struct trieNode));
    //Counts to see whether the word was just an \n or it was really a word
    int cLettCount = 0;
    //counts the number of total words used
    int tWordCount = 0;
    //basic setup stuff
    root->isRoot = true;
    //Pointer to the current node (current node starts as root node).
    struct trieNode* currNode = root;
    struct trieNode* prevNode;
    FILE* dic = fopen(dictionary, "r");
    char currChar = 1;
    //main loop (Goes till end of file)
    while(currChar != EOF){
        //resets letter count
        cLettCount = 0;
        //resets currNode to the root node
        currNode = root;
        currChar = 1;
        //Loop gathers current word and pushes the letters to the trie
        for(int j = 0;  currChar != '\n'; j++){
            currChar = fgetc(dic);
            //Makes sure we're not at the end of a word or at EOF
            if(currChar == '\n'|| currChar == EOF)
            {
                break;
            }
            //Makes sure we only get alpha chars
            else if(!isalpha(currChar) && currChar != 39)
            {
                printf("Nonalpha char %c detected. Quiting...\n", currChar);
                return false;
            }
            //Meat and bones. Adds letters onto the trie
            else if(isalpha(currChar) || currChar== 39)
            {
                bool isNull = false;
                if(currChar == 39){
                    if(currNode->childNodes[26] == NULL)
                    {
                        isNull = true;
                        currNode->childNodes[26] = calloc (1,sizeof (trie));
                    }
                    prevNode = currNode;
                    currNode = currNode->childNodes[26];
                }
                else
                {
                //Finds the node that corrosponds with the letter
                    if(currNode->childNodes[currChar - 'a'] == NULL)
                    {
                        isNull = true;
                        currNode->childNodes[currChar - 'a'] = calloc (1,sizeof (trie));
                    }
                    prevNode = currNode;
                    currNode = currNode->childNodes[currChar - 'a'];
                }
                if(isNull)
                {
                     currNode->previous = prevNode;
                     currNode->isRoot = false;
                     currNode->letter = currChar;
                     currNode-> wordComp = false;
                }else if(!isNull){
                }
            }
        }
        if(currChar == EOF){
                break;
        }
        else if(currChar == '\n'){
            currNode -> wordComp = true;
            tWordCount++;
        }
    }
    fclose(dic);
    sizeOfDic = tWordCount;
    return true;
}

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

void unloadHelper(struct trieNode* currNode)
{
    for(int i = 0; i < 27; i++)
    {
        if(currNode->childNodes[i] !=NULL)
        {
            unloadHelper(currNode->childNodes[i]);
        }
    }
        free(currNode);
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    unloadHelper(root);
    return true;
}

speller.c

/****************************************************************************
 * speller.c
 *
 * Computer Science 50
 * Problem Set 6
 *
 * 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 "/home/cs50/pset6/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 ti_load = 0.0, ti_check = 0.0, ti_size = 0.0, ti_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
    ti_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
            tolower(c);
            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
            ti_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
    ti_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
    ti_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", ti_load);
    printf("TIME IN check:        %.2f\n", ti_check);
    printf("TIME IN size:         %.2f\n", ti_size);
    printf("TIME IN unload:       %.2f\n", ti_unload);
    printf("TIME IN TOTAL:        %.2f\n\n", 
     ti_load + ti_check + ti_size + ti_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);
    }
}

Answer 1

• Naming

  Many names in your program are not very meaningful. check can mean anything. In your context it means that the word is known, valid, correct (pick one), so the function shall be named along the lines of isWordKnown. Pretty much the same can be said about calculate.

• main

  It does too much. As a rule of thumb, main shall parse a command line and call appropriate functions. A heavy duty for loop must be replaced by a higher-level actions. As much as I can tell, what it's supposed to be doing is

  read_a_word;
  validate_the_word;
  

  Try to accommodate this pattern.

• Global variables

  Try to avoid them at all costs. The wider is the scope, the harder is reasoning about the variable. At least restrict them to a file scope:

  static struct trieNode * root;
  

• check() is unnecessary complicated.

  Consider instead

  bool check(struct trieNode * root, const char* word)
  {
      char currChar;
  
      for(int i = 0; (currChar = word[i]) != '\0'; i++)
      {
          if (currChar == '\'') {
              index = 26;
          } else if (isalpha(currChar)) {
              index = tolower(currChar) - 'a';
          } else {
              return false;
          }
  
          if ((node = node->childNodes[index]) == NULL)
              return false;
      }
  
      return (currChar == '\0' && node->wordComp);
  }
  

  You may notice that the loop body naturally disintegrates into 2 distinct operations: calculating the index and navigating the tree. I would seriously consider to factor out index calculation into a separate function. This would help immensely once you'd decide to change the alphabet (like, accept accents, or switch to Croatian).

  PS: you may also notice that I decided to pass a root node as a parameter. This enables a complete separation of code from data.

• Data; performance; etc.

  Nothing is certain until it is measured; however the gut feeling is that too much space is wasted. Consider how many English words end with ing - and each ing takes 80+ pointers just to encode less than 3 bytes (ed and s are equally wasteful). Side note: English spelling is very regular; look at rispell for hoops a Russian speller has to jump through!