Data Structures Problem
Speller
We are going to implement a program that spell-checks a file, like below, using a hash table.
$ ./speller texts/lalaland.txt
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:
This should give you the following files:
dictionaries/ dictionary.c dictionary.h keys/ Makefile speller.c texts/
Understanding
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., n 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 is to implement the fastest spell checker we can! By “fastest,” 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 into 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, meanwhile, 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.
dictionary.h
Open up 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 LENGTH
that has a value of 45
. It’s a constant in the sense that you can’t (accidentally) change it in your own code. In fact, clang
will replace any mentions of LENGTH
in your own code with, literally, 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);
char *
is what we used to call string
. So those three prototypes are essentially just: bool check(const string word);
unsigned int hash(const string word);
bool load(const string dictionary);
And const
, meanwhile, just says that those strings, when passed in as arguments, must remain constant; 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 1
for now, meaning this hash table has just 1 bucket right now. You’ll likely want to increase the number of buckets, as by changing N
, to something larger!
Next, notice that we’ve implemented load
, hash
, check
, size
, and unload
, but only barely, just enough for the code to compile. 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 entirety, but do try to get a sense of its functionality nonetheless. Notice how, by way of a function called getrusage
, we’ll be “benchmarking” (i.e., timing the execution of) your implementations of check
, load
, size
, and unload
. Also notice how we go about passing check
, word by word, the contents 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
$ ./speller dictionaries/large text
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 debug an otherwise enormous structure in memory. In dictionaries/small
is one such dictionary. To use it, execute
$ ./speller dictionaries/small text
text
is the file you wish to spell-check. Don’t move on until you’re sure you 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, the entirety of the King James V Bible and the Koran, 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
$ ~cs50/2019/fall/pset5/speller texts/lalaland.txt
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 CS50 IDE 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.
Makefile
And, lastly, recall that make
automates compilation of your code so that you don’t have to execute clang
manually along with a whole bunch of switches. However, as your programs grow in size, make
won’t be able to infer from context anymore how to compile your code; you’ll need to start telling make
how to compile your program, particularly when they involve multiple source (i.e., .c
) files, as in the case of this problem. And so we’ll utilize a Makefile
, a configuration file that tells make
exactly what to do. Open up Makefile
, and you should see four lines:
-
The first line tells
make
to execute the subsequent lines whenever you yourself executemake speller
(or justmake
). -
The second line tells
make
how to compilespeller.c
into machine code (i.e.,speller.o
). -
The third line tells
make
how to compiledictionary.c
into machine code (i.e.,dictionary.o
). -
The fourth line tells
make
to linkspeller.o
anddictionary.o
in a file calledspeller
.
Be sure to compile speller
by executing make speller
(or just make
). Executing make dictionary
won’t work!
Getting started
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
orMakefile
. -
You may alter
dictionary.c
(and, in fact, must in order to complete the implementations ofload
,hash
,size
,check
, andunload
), but you may not alter the declarations (i.e., prototypes) ofload
,hash
,size
,check
, orunload
. You may, though, add new functions and (local or global) variables todictionary.c
. -
You may change the value of
N
indictionary.c
, so that your hash table can have more buckets. -
You may alter
dictionary.h
, but you may not alter the declarations ofload
,hash
,size
,check
, orunload
. -
Your implementation of
check
must be case-insensitive. In other words, iffoo
is in dictionary, thencheck
should return true given any capitalization thereof; none offoo
,foO
,fOo
,fOO
,fOO
,Foo
,FoO
,FOo
, andFOO
should be considered misspelled. -
Capitalization aside, your implementation of
check
should only returntrue
for words actually indictionary
. Beware hard-coding common words (e.g.,the
), lest we pass your implementation adictionary
without those same words. Moreover, the only possessives allowed are those actually indictionary
. In other words, even iffoo
is indictionary
,check
should returnfalse
givenfoo
's iffoo
's is not also indictionary
. -
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 thatdictionary
will contain at least one word, that no word will be longer thanLENGTH
(a constant defined indictionary.h
) characters, that no word will appear more than once, that each word will contain only 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 if among those more comfortable) 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 on 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
. -
You may search for (good) hash functions online, so long as you cite the origin of any hash function you integrate into your own code.
Now let's implement load, hash, size, check, and unload!
Solution
Speller Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
|