Speller

Problem to Solve
For this problem, you'll implement a program that spell-checks a file, a la the
below, using a hash table.

Etext WORDS MISSPELLED: 718 WORDS IN DICTIONARY: 143091 WORDS IN TEXT: 103614 TIME IN
load: 0.05 TIME IN check: 0.09 TIME IN size: 0.00 TIME IN unload: 0.01 TIME IN TOTAL:
0.15

Background
Theoretically, on input of size n, an algorithm with a running time of n is
"asymptotically equivalent," in terms of O , to an algorithm with a running
time of 2n. Indeed, when describing the running time of an algorithm, we
typically focus on the dominant (i.e., most impactful) term (i.e., in this
case, since n could be much larger than 2). In the real world, though, the
fact of the matter is that 2n feels twice as slow as n.

The challenge ahead of you is to implement the fatest spell checker you can!
By "fatest," though, we're talking actual "wall-clock," not asymptotic, time.

In speller.c , we've put together a program that's designed to spell-check a

file after loading a dictionary of words from disk to memory. That dictionary,
meanwhile, is implemented in a file called dictionary.c . (It could just be
implemented in speller.c , but as programs get more complex, it's often
convenient to break them into multiple files.) The prototypes for the functions
therein, meanwhilem are defined not in dictionary.c itself but in dictionary.h
instead. That way, both speller.c and dictionary.c can #include the file.
Unfortunately, we didn't quite get around to implementing the loading part. Or
the checking part. Both (and a bit more) we leave to you! But first, a tour.

Understanding
dictionary.h

Open dictionary.h , and you'll see some new syntax, including a few lines that
mention DICTIONARY_H . No need to worry about those, but, if curious, those
lines just ensure that, even though dictionary.c and speller.c (which you'll
see in a moment) #include this file, clang will only compile it once.
Next notice how we #include a file called stdbool.h . That's the file in which
bool itself is defined. You've not needed it before, since the CS50 Library
used to #include that for you.

Also notice our use of define , a "preprocessor directive" that defines a

"constant" called LENGHT that has a value of 45 . In other words, it's not a
variable, just a find-and-replace trick.

Finally, notice the prototypes for five functions: check , hash , load , size and
unload . Notice how three of those take a pointer as an argument, per the * :

bool check(const char *word);

unsigned int hash(const char *word);
bool load(const char *dictionary);

And const meanwhile, just says that those strings, when passed in as
arguments, must remain cosntant; you won't be able to change them,
accidentally or otherwise!

dictionary.c

Now open up dictionary.c . Notice how, atop the file, we've defined a struct
called node that represents a node in a hash table. And we've declared a
global pointer array, table , which will (soon) represent the hash table you will
use to keep track of words in the dictionary. The array contains N node
pointers, and we've set N equal to 26 for now, to match with the default
hash function as described below. You will likely want to increase this
depending on your own implementation of hash .

Next, notice that we've implemented load , check , size , and unload , but only
barely, just enough for the code to compile. Notice too that we'vw
implemented hash with a sample algorithm based on the first letter of the
word. Your job, ultimately, is to re-implement those functions as cleverly as
possible so that this spell checker works as advertised. And fast!

speller.c

Okay, next open up speller.c and spend some time looking over the code and
comments therein. You won't need to change anything in this file, and you
don't need to understand its entirely, but try to get a sence of its
functionality nonetheles. Notice how, by way of function called getusage , we'll
be "benchmarking" your implementations of load , check , size , and unload .
Also notice how we go about passing check , word by word, the contentes of
some file to be spell-checked. Ultimately, we report each misspelling in that
file along with a bunch of statistics.

Notice, incidentally, that we have defined the usage of speller to be

Usage: ./speller [dictionary] text

where dictionary is assumed to be a file containing a list of lowercase words,

one per line, and text is a file to be spell-checked. As the brackets suggest ,
provision of dictionary is optional; if this argument is omitted, speller will use
dictionaries/large by default. In other words running

./speller text

will be equivalent to running

./speller dictionaries/large text

where text is the file you wish to spell-check. Suffice it to say, the former is
easier to type! (Of course, speller will not be able to load any dictionaries
until you implement load in dictionary.c ! Until then, you'll see Could not load. )

Within the default dictionary, mind you, are 143,091 words, all of which must
be loaded into memory! In fact, take a peek at that file to get a sense of its
structure and size. Notice that every word in that file appears in lowercase
(even, for simplicity, proper nouns and acronyms). From top to bottom, the
file is sorted lexicographically, with only one word per line (each of which
ends with \n ). No word is longer than 45 characters, and no word appears
more than once. During development, you may find it helpful to provide speller
with a dictionary of your own that contains far fewer words, lest you struggle
to debyg an otherwise enormous structure in memory. In dictionaries/small is
one such dictionary. To use it, execute

./speller dictionaries/small text

where text is the file you wish to spell-check. Don't move on until you're
sure you can understand how speller itself works!

Odds are, you didn't spend enough time looking over speller.c . Go back one
square and walk yourself through it again!

texts/

So that you can test your implementation of speller , we've also provided you
with a whole bunch of texts, among them the script from La La Land, the text
of the Affordable Care Act, three million bytes from Tolstoy, some excerpts
from The Federalist Papers and Shakespeare, and more. So that you know
what to expect, open and skim each of those files, all of which are in a
directory called texts within your pset5 directory.

Now, as you should know from having read over speller.c carefully, the output
of speller , if executed with, say,

./speller texts/lalaland.txt

will eventually resemble the below.

Below's some of the output you'll see. For informations's sake, we've
excerpted some examples of "misspellings." And lest we spoil the fun, we've
omitted our own statistics for now.

MISSPELLED WORDS

[...]
AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
[...]
Shangri
[...]
fianc
[...]
Sebastian's
[...]

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

TIME IN load represents the number of seconds that speller spends executing
your implementation of load . TIME IN check represents the number of seconds
that speller spends, in total, executing your implementation of check . TIME IN
size represents the number of seconds that speller spends executing your
implementation of size . TIME IN unload represents the number of seconds
that speller spends executing your implementation of unload . TIME IN TOTAL is
the sum of those four measurements.

Note that these times may vary somewhat across executions of speller ,
depending on what else your codespace is doing, even if you don’t change your
code.

Incidentally, to be clear, by “misspelled” we simply mean that some word is

not in the dictionary provided.

Specification

Alright, the challenge now before you is to implement, in order,

load , hash , size , check , and unload as efficiently as possible using a hash
table in such a way that TIME IN load , TIME IN check , TIME IN size , and TIME IN
unload are all minimized. To be sure, it's not obvious what it even means to
be minimized, inasmuch as these benchmarks will certainly vary as you feed
speller different values for dictionary and for text . But therein lies the
challenge, if not the fun, of this problem. This problem is your chance to
design. Although we invite you to minimize space, your ultimate enemy is
time. But before you dive in, some specifications from us.

You may not alter speller.c or Makefile .

You may alter dictionary.c (and, in fact, must in order to complete the
implementations of load , hash , size , check and unload ), but you may not
alter the declarations of those functions. You may, though, add new
functions and (local or global) variables to dictionary.c .
You may change the value of N in dictionary.c , so that your hash table
can have more buckets.
You may alter dictionary.h , but you may not alther the declarations of the
functions.
Your implementation of check must be case-insensitive. In other words, if
foo is in dictionary, then check should return true given any capitalization
thereof; none of foo , foO , fOo , fOO , fOO , Foo , FoO , FOo ,
and FOO should be considered misspelled.
Capitalization aside, your implementation of check should only return true
for words actually in dictionary . Beware hard-coding common words
(e.g., the ), lest we pass your implemantation a dictionary without those
same words. Moreover, the only possessives allowed are those actually in
dictionary . In other words, even if foo is in dictionary , check should
return false given foo's if foo's is not also in dictionary .
You may assume that any dictionary passed to your program will be
structured exactly like ours, alphabetically 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, that each word will contain oly lowercase
alphabetical characters and possibly apostrophes, and that no word will
start with an apostrophe.
You may assume that check will only be passed words that contain
(uppercase or lowercase) alphabetical characters and possibly
apostrophes.
Your spell checker may only take text and, optionally, dictionary as input.
Although you might be inclined (particularly among those more confortable)
to "pre-process" our default dictionary in order to derive an "ideal hash
function" for it, you may not save the output of any such pre-processing
to disk in order to load it back into memory of subsequent runs of your
spell checker in order to gain an advantage.
Your spell checker must not leak any memory. Be sure to check for leaks
with valgrind .
The hash function you write should ultimately be your own, not one you
search online.