Spell checker using trie

Question

This program implements spell checking by loading a given dictionary file into a trie structure and comparing against a given text file: Usage: speller [dictionary] text. When run, each misspelled word is printed along with benchmarks:

This was part of a problem set with a given mess of skeleton code (speller.c), which I've done my best to make presentable for code review here. The goal was to get the best timing possible (see reqs below), so we've been instructed to use getrusage to gather benchmarks. Please don't focus much critique on speller.c as it is a given piece of the problem set.

Other requirements were as follows:

• You may assume that any dictionary passed to your program will be structured exactly like ours, lexicographically sorted from top to bottom with one word per line, each of which ends with \n. You may also assume that dictionary will contain at least one word, that no word will be longer than LENGTH (a constant defined in dictionary.h) characters, that no word will appear more than once, and that each word will contain only lowercase alphabetical characters and possibly apostrophes.
• You may assume that check will only be passed strings with alphabetical characters and/or apostrophes.
• Your implementation of check must be case-insensitive.

---

One area I'm specifically interested in review is performance. I ran gperf and callgrind to profile my code and made some changes based on analysis; however, it seems that load_dict might be underachieving when I compare to staff solution benchmarks (run on same environment). Does anything stick out that could be improved to get better performance?

---

speller.c

#include "dbg.h"
#include "dictionary.h"

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

#undef difference_in_seconds
#undef getrusage

#define DEFAULT_DICT "dictionaries/large"

typedef struct {
    struct rusage before;
    struct rusage after;
    double time_load;
    double time_check;
    double time_size;
    double time_unload;
    unsigned misspellings;
    unsigned word_count;
    unsigned dict_wc;
} BenchmarkData;

static bool init_load_dict(const char *dictionary, BenchmarkData *bm_data);
static bool init_spell_check(const char *text, BenchmarkData *bm_data);
static void init_dict_word_count(BenchmarkData *bm_data);
static bool init_dict_unload(const char *dictionary, BenchmarkData *bm_data);
static void print_benchmarks(const BenchmarkData *bm_data);
static double difference_in_seconds(const struct rusage* b, const struct rusage* a);

int main(int argc, char* argv[])
{
    check(argc == 2 || argc == 3, "Usage: speller [dictionary] text");
    char *dictionary = (argc == 3) ? argv[1] : DEFAULT_DICT;
    char *text = (argc == 3) ? argv[2] : argv[1];
    BenchmarkData bm_data;

    init_load_dict(dictionary, &bm_data);

    printf("\nMISSPELLED WORDS\n\n");
    init_spell_check(text, &bm_data);

    init_dict_word_count(&bm_data);
    init_dict_unload(dictionary, &bm_data);
    print_benchmarks(&bm_data);

    return 0;
error:
    return 1;
}

static bool init_load_dict(const char *dictionary, BenchmarkData *bm_data)
{
    getrusage(RUSAGE_SELF, &bm_data->before);
    bool loaded = load_dict(dictionary);
    getrusage(RUSAGE_SELF, &bm_data->after);
    check(loaded, "Could not load dictionary (%s).", dictionary);
    bm_data->time_load = difference_in_seconds(&bm_data->before, &bm_data->after);
    return loaded;
error:
    return false;
}

static bool init_spell_check(const char *text, BenchmarkData *bm_data)
{
    FILE *in = fopen(text, "r");
    check(in, "Failed to open text.");
    char word[LEN_MAX_WORD+1];
    int index = 0;

    // read text
    for (int c = fgetc(in); c != EOF; c = fgetc(in)) {
        if (isalpha(c) || (c == '\'' && index > 0)) {
            word[index] = c;
            index++;
            if (index > LEN_MAX_WORD) {
                while ((c = fgetc(in)) != EOF && isalpha(c));
                index = 0;
            }
        } else if (isdigit(c)) {
            while ((c = fgetc(in)) != EOF && isalnum(c));
            index = 0;
        } else if (index > 0) {
            // end of word
            word[index] = '\0';
            bm_data->word_count++;
            getrusage(RUSAGE_SELF, &bm_data->before);
            bool misspelled = !check_spelling(word);
            getrusage(RUSAGE_SELF, &bm_data->after);
            bm_data->time_check += difference_in_seconds(&bm_data->before, &bm_data->after);
            if (misspelled) {
                printf("%s\n", word);
                bm_data->misspellings++;
            }
            index = 0;
        }
    }
    check(ferror(in) == 0, "File stream error(s) occured.");

    fclose(in);
    return true;
error:
    fclose(in);
    unload_dict();
    return false;
}

static void init_dict_word_count(BenchmarkData *bm_data)
{
    getrusage(RUSAGE_SELF, &bm_data->before);
    bm_data->dict_wc = get_dict_word_count();
    getrusage(RUSAGE_SELF, &bm_data->after);
    bm_data->time_size = difference_in_seconds(&bm_data->before, &bm_data->after);
}

static bool init_dict_unload(const char *dictionary, BenchmarkData *bm_data)
{
    getrusage(RUSAGE_SELF, &bm_data->before);
    bool unloaded = unload_dict();
    getrusage(RUSAGE_SELF, &bm_data->after);
    check(unloaded, "Could not unload dictionary (%s).", dictionary);
    bm_data->time_unload = difference_in_seconds(&bm_data->before, &bm_data->after);
    return unloaded;
error:
    return false;
}

static void print_benchmarks(const BenchmarkData *bm_data)
{
    printf("\nWORDS MISSPELLED:   %d\n", bm_data->misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", bm_data->dict_wc);
    printf("WORDS IN TEXT:        %d\n", bm_data->word_count);
    printf("TIME IN load:         %.2f\n", bm_data->time_load);
    printf("TIME IN check:        %.2f\n", bm_data->time_check);
    printf("TIME IN size:         %.2f\n", bm_data->time_size);
    printf("TIME IN unload:       %.2f\n", bm_data->time_unload);
    printf("TIME IN TOTAL:        %.2f\n\n", bm_data->time_load + bm_data->time_check +
                                             bm_data->time_size + bm_data->time_unload);
}

static double difference_in_seconds(const struct rusage* b, const struct rusage* a)
{
    if (!b || !a) {
        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);
    }
}

dictionary.c

#include "dbg.h"
#include "dictionary.h"
#include "trie.h"

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

static TrieNode *root;

bool check_spelling(const char *word)
{
    return Trie_search(&root, word);
}

bool load_dict(const char *dictionary)
{
    // newlines
    char word[LEN_MAX_WORD+2];

    root = Trie_create();
    check(root, "Failed to create Trie.");
    FILE *in = fopen(dictionary, "r");
    check(in, "Failed to open dictionary.");

    while (fgets(word, sizeof(word)+1, in)) {
        if (!Trie_insert(&root, word)) {
            return false;
        }
    }

#if DEBUG
    Trie_print(&root);
#endif
    fclose(in);
    return true;
error:
    return false;
}

unsigned get_dict_word_count()
{
    return Trie_get_word_count();
}

bool unload_dict()
{
    Trie_reset_word_count();
    return Trie_destroy(&root);
}

dictionary.h

#ifndef DICTIONARY_H_GAISFW03
#define DICTIONARY_H_GAISFW03

#include <stdbool.h>
#include <stdio.h>

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

bool check_spelling(const char *word);
bool load_dict(const char *dictionary);
unsigned get_dict_word_count(void);
bool unload_dict(void);

#endif /* end of include guard: DICTIONARY_H_GAISFW03 */

trie.c

#include "dbg.h"
#include "trie.h"

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

static size_t get_index(const char c);
static bool valid_trie_key(const char key);

enum { INDEX_APOSTROPHE = LEN_TRIE_INPUT_SET-1 };

static size_t trie_word_count = 0;

TrieNode *Trie_create()
{
    return calloc(1, sizeof(TrieNode));
}

bool Trie_insert(TrieNode **root, const char *word)
{
    check(root, "Root is null.");
    const char *key;
    size_t index;
    TrieNode *new;
    TrieNode *cur = *root;

    for (key = word; *key && *key != '\n'; ++key) {
        index = get_index(*key);

        // if the next key already exists, advance (and skip insert)
        if (cur->children[index]) {
            cur = cur->children[index];
            continue;
        }

        new = Trie_create();
        cur->children[index] = new;
        cur = new;
    }
    new->end_of_word = true;
    trie_word_count++;
    return true;
error:
    return false;
}

bool Trie_search(TrieNode **root, const char *key)
{
    check(root, "Root node is null.");
    TrieNode *cur = *root;

    while (*key) {
        check(valid_trie_key(*key), "Invalid key input: %c", *key);
        cur = cur->children[get_index(*key)];
        if (!cur) {
            return false;
        }
        ++key;
    }
    return cur->end_of_word;
error:
    return false;
}

bool Trie_destroy(TrieNode **root)
{
    check(root, "Root is null.");

    for (int i = 0; i < LEN_TRIE_INPUT_SET; ++i) {
        if ((*root)->children[i]) {
            Trie_destroy(&(*root)->children[i]);
        }
    }

    free(*root);
    return true;
error:
    return false;
}

size_t Trie_get_word_count()
{
    return trie_word_count;
}

void Trie_reset_word_count()
{
    trie_word_count = 0;
}

#if DEBUG
void Trie_print(TrieNode **root)
{
    check(root, "Root is null.");

    for (int i = 0; i < LEN_TRIE_INPUT_SET; ++i) {
        if ((*root)->children[i]) {
            debug(
                "@ %p: %c | EOW? %d",
                (*root)->children[i],
                (char)i + 'a',
                (*root)->children[i]->end_of_word
            );
            Trie_print(&(*root)->children[i]);
        }
    }
error:
    return;
}
#endif

static size_t get_index(const char c)
{
    return (c == '\'') ? INDEX_APOSTROPHE : (tolower(c) - 'a');
}

static bool valid_trie_key(const char key)
{
    return (key == '\'' || isalpha(key));
}

trie.h

#ifndef TRIE_H_NSUGRANT
#define TRIE_H_NSUGRANT

#include "dictionary.h"

#include <stdbool.h>

// eng alphabet(a-z) + apostrophe (')
#define LEN_TRIE_INPUT_SET 27

typedef struct TrieNode {
  struct TrieNode *children[LEN_TRIE_INPUT_SET];
  bool end_of_word;
} TrieNode;

TrieNode *Trie_create();
bool Trie_insert(TrieNode **root, const char *word);
bool Trie_search(TrieNode **root, const char *key);
bool Trie_destroy(TrieNode **root);
size_t Trie_get_word_count(void);
void Trie_reset_word_count(void);
#if DEBUG
void Trie_print(TrieNode **root);
#endif

#endif /* end of include guard: TRIE_H_NSUGRANT */

dbg.h

#ifndef DBG_H_KDNMUF6Q
#define DBG_H_KDNMUF6Q

#include <stdio.h>
#include <errno.h>
#include <string.h>

#define ANSI_COLOR_RED     "\x1b[31m"
#define ANSI_COLOR_GREEN   "\x1b[32m"
#define ANSI_COLOR_YELLOW  "\x1b[33m"
#define ANSI_COLOR_CYAN    "\x1b[36m"
#define ANSI_COLOR_RESET   "\x1b[0m"

#ifdef NDEBUG
#define debug(M, ...)
#else
#define debug(M, ...) fprintf(stderr, ANSI_COLOR_CYAN "[DEBUG]" ANSI_COLOR_RESET " %s:%d:%s: " M "\n", __FILE__, __LINE__, __FUNCTION__, ##__VA_ARGS__)
#endif

#define clean_errno() (errno == 0 ? "None" : strerror(errno))

#define log_err(M, ...) fprintf(stderr, ANSI_COLOR_RED "[ERROR]" ANSI_COLOR_RESET " (%s:%d: errno: %s) " M "\n", __FILE__, __LINE__, clean_errno(), ##__VA_ARGS__)

#define log_warn(M, ...) fprintf(stderr, ANSI_COLOR_YELLOW "[WARN]" ANSI_COLOR_RESET " (%s:%d: errno: %s) " M "\n", __FILE__, __LINE__, clean_errno(), ##__VA_ARGS__)

#define log_info(M, ...) fprintf(stderr, ANSI_COLOR_GREEN "[INFO]" ANSI_COLOR_RESET " (%s:%d) " M "\n", __FILE__, __LINE__, ##__VA_ARGS__)

#define check(A, M, ...) if (!(A)) { log_err(M, ##__VA_ARGS__); errno=0; goto error; }

#define sentinel(M, ...) { log_err(M, ##__VA_ARGS__); errno=0; goto error; }

#define check_mem(A) check((A), "Out of memory.")

#define check_debug(A, M, ...) if (!(A)) { debug(M, ##__VA_ARGS__); errno=0; goto error; }

#endif /* end of include guard: DBG_H_KDNMUF6Q */

Answer 1

Buffer overflow

This line is vulnerable to buffer overflow:

while (fgets(word, sizeof(word)+1, in)) {

I'm not sure why you added one here, but it makes it possible to overflow the buffer by one character. According to the problem statement, the dictionary will not have any words longer than the buffer, so your code is safe as long as you use the provided dictionary. But for an arbitrary input file, you should remove that +1 from that line.

Uninitialized variables

When I ran your program, I got this as part of the output:

WORDS MISSPELLED:   1629196271

This was due to the variable bm_data being uninitialized in main, and none of the other functions zeroing it either. Since that code was not written by you, you aren't really to blame for that.

Performance in loading

After playing with your code a bit, I found that the loading performance was slow mostly due to lack of buffering. That is to say, calling fgets() to read each word is slower than reading into a big buffer and then parsing through the buffer. When I used fread() to read into a buffer, the dictionary loaded in 0.06 seconds compared to 0.11 seconds when using fgets(). I tried different buffer sizes and I got pretty much the same results with buffer sizes ranging from 64 bytes to 64 KB. Here is code I used:

#define BUFSIZE    1024

bool Trie_insert_file(TrieNode **root, FILE *in)
{
    check(root, "Root is null.");
    char      buffer[BUFSIZE];
    TrieNode *cur = *root;

    while(1) {
        size_t bufLen = fread(buffer, 1, sizeof(buffer), in);
        if (bufLen <= 0)
            return true;
        for (size_t i = 0; i < bufLen; i++) {
            char c = buffer[i];
            if (c == '\n') {
                trie_word_count++;
                cur->end_of_word = true;
                cur = *root;
                continue;
            }
            size_t index = get_index(c);

            if (cur->children[index] == NULL)
                cur->children[index] = Trie_create();
            cur = cur->children[index];
        }
    }
error:
    return false;
}

Answer 2

Why a handle?

bool Trie_insert(TrieNode **root, const char *word)

Consider

bool Trie_insert(TrieNode *current, char *key)

The only use that you had for root and word was to initialize variables with them. Why bother? If you pass by value, you initialize variables with the value.

And to get back to the heading question: why do you pass a handle to root? If you're not familiar with the term, a handle is a pointer to a pointer. You use it when you want to change the pointer. For example, if you might set the root pointer in the function. But you never modify root, only *root (as cur). So you don't need the handle.

I changed cur to current as more obvious what it means. Sure, it doesn't take long to make the cur to current transformation in your head. But this way you don't have to do it at all.

There's also a slight bug here. You check that the handle is not null, but you never check if the pointer *root is not null. So someone could do

TrieNode *root = 0;
Trie_insert(&root, word);

And the program would crash as written. If you change this as I suggested, then it will check the pointer instead of the handle.

    check(current, "Root is null.");

Don't Repeat Yourself (DRY)

        if (cur->children[index]) {
            cur = cur->children[index];
            continue;
        }

        new = Trie_create();
        cur->children[index] = new;
        cur = new;

This seems more complicated than it needs to be. Consider

        // create if this is the first time we're seeing this letter
        if (! current->children[index]) {
            current->children[index] = Trie_create();
        }

        current = current->children[index];

Now we see that it always updates current to current->children[index]. And if current->children[index] doesn't already exist, it creates it. No new. No continue.

Bug

    new->end_of_word = true;

Hah, you say. You got me. Without new, this won't work. However, I say that this was already broken. This assumes that the dictionary is in sorted order, so words like key appear before keyhole. If we break that assumption and read in the dictionary backwards, this won't work. In fact, it will try to set a value in uninitialized memory (since new won't point to anything). This should be

    current->end_of_word = true;

Now it works regardless of read order.

Summary

bool Trie_insert(TrieNode *current, char *key)
{
    check(current, "Root is null.");

    for (; *key && *key != '\n'; ++key) {
        size_t index = get_index(*key);


        // create if this is the first time we see this letter
        if (! current->children[index]) {
            current->children[index] = Trie_create();
        }

        current = current->children[index];
    }

    current->end_of_word = true;
    trie_word_count++;

    return true;
error:
    return false;
}

Now we only declare one variable in the entire function. And that's just a temporary variable that gets reset on each iteration of the loop.

Note that C has always allowed declaring variables after an opening { of a block. The declare at the start of a function style is just a subset of that.

There's a slight argument that the intermediate variables help the function be self-commenting, but in this case I don't see it. The function reads fine to me this way.