>> ZAMYLA CHAN: Let's make a spell checker.
If you open speller.c, then you'll see that most of the functionality for
checking a text file against a dictionary is already made for you.
./speller, passing in a dictionary text file and then another text file,
will check that text file against the dictionary.
>> Now, dictionary text files will contain valid words, one per line.
Then speller.c will call Load on the dictionary text file.
It'll call a function called Check on every word in the inputted text file,
printing all misspelled words.
>> Speller.c will also call Size to determine the number of words in
dictionary and call Unload to free up memory.
speller.c will also keep track of how much time is used to conduct of these
processes, but we'll get to that later.
>> So what do we need to do?
We need to fill in dictionary.c.
In dictionary.c, we have the helper function Load, which loads the
dictionary.
The function Check, which checks if a given word is in the dictionary.
The function Size returns the number of words in the dictionary.
And finally, we have Unload, which frees the dictionary from memory.
>> So first, let's tackle Load.
For each word in the dictionary text file, Load will store those words in
the dictionary data structure of your choosing, either a
hash table or a trie.
I'll go over both in this walk through.
>> First let's talk about hash tables.
Say you had 10 billiard balls and you wanted to store them.
You might put them all in a bucket, and when you needed a specific
numbered ball, you'd take one out of the bucket at a time
looking for that ball.
And with only 10 balls, you should be able to find your ball in a reasonable
amount of time.
>> But what if you had 20 balls?
It might take a little longer now.
What about 100?
1,000?
Now, it would be much easier if you had multiple buckets.
Maybe one bucket for balls numbered zero through nine, another bucket for
balls numbered 10 through 19, and so on.
>> Now when you needed to look for specific ball, you could automatically
go to one specific bucket and search through that bucket.
And if each bucket has approximately 10 balls, then you could easily search
through it.
>> Now, since we're dealing with dictionaries, one single bucket for
all of the words in the dictionary will probably be far too few buckets.
So let's take a look at hash tables.
>> Think of it as an array of buckets.
And in this case, the buckets are our linked lists.
And we'll distribute all of our words amongst these multiple linked lists in
an organized way using a hash function, which will tell us which
bucket a given key, a given word, belongs to.
>> Let's represent this schematically.
The blue boxes here contain values and red boxes point to another value
pointer pair.
We'll call these pairs nodes.
Now, each bucket, as I said earlier, is a linked list.
In linked lists, each node has a value, as well as a pointer to the
next value.
>> Now, dealing with linked lists, it's very important that you
don't lose any links.
And another fact to remember is that the last node, if it doesn't point to
another node, points to null.
>> So how do we represent this in C?
We define our struct here.
And the value in this case is a char array of length.
Length plus 1, where length is the maximum length of any word, plus 1 for
the null terminator.
And then we have a pointer to another node called Next.
>> So let's make a small linked list.
First, you'll want to malloc your node, which create space in memory the
size of your node type.
And make another node, again mallocing.
>> Now if you want to assign a value to a word, then we might say node1 arrow
word equals "Hello." This arrow operator dereferences the pointer and
accesses the struct's variables.
This way, we don't have to use both the dot and the star operator.
>> So then I have node2 arrow word equals "world." And there, the values are
populated in my nodes.
To make the links, I'll pass in node1 arrow next, accessing that node star,
that node pointer, equals node2, pointing node1 to node2 two.
And there we have a linked list.
>> So that was just one linked list, but a hash table is a whole array of
linked lists.
Well, we'll have the same node structure as before.
But if we wanted an actual hash table, then we can just make a node pointer
array here.
For example, size 500.
>> Now notice, there's going to be a trade off between the size of your
hash table and the size of your linked lists.
If you have a really high number of buckets, imagining having to run back
and forth in a line to find your bucket.
But you also don't want a small number of buckets, because then we're back to
the original problem of how having too many balls in our bucket.
>> OK, but where does our ball go?
Well, we first need to have a ball, right?
So let's malloc a node for every new word that we have.
node* new_node equals malloc(sizeof(node)).
>> Now that we have this structure, we can scan in, using the function
fscanf, a string from our file, if that's a dictionary file, into
new_node arrow word, where new_node arrow word is our
destination of that word.
>> Next, we'll want to hash that word using a hash function.
A hash function takes a string and returns an index.
In this case, the index has to be less than the number of
buckets that you have.
>> Now, hash functions, when you're trying to find one and create one of
your own, remember that they have to be deterministic.
That means that the same value needs to map to the same bucket every time
that you hash it.
>> It's kind of like a library.
When you take a book, based on the author, you know which shelf it should
go on, whether it's shelf number one, two, or three.
And that book will always belong on either shelf one, two, or three.
>> So, if new_node arrow word has the word from your dictionary, then
hashing new_node arrow word will give us the index of the
bucket of the hash table.
And then we'll insert that into that specific linked list indicated by the
return value of our hash function.
>> Let's look at an example of inserting a node into the
beginning of a linked list.
If head is a node pointer that indicates the beginning of a linked
list, and new_node indicates the new node that you want to enter in, just
assigning head to new_node would lose the link to the rest of the list.
So we don't want to do this.
>> Rather, we want to make sure that we hold on to every
single node in our program.
So running new_node arrow next equals head and then head equals new_node
will preserve all of the links and not lose any.
>> But what if you want your list to be sorted, because having a sorted linked
list might be easier for searching it later on?
Well, for that, you'll need to know how to traverse linked lists.
>> To traverse a linked list, let's have a node pointer, a node*, to act as
your cursor, indicating which node you're at, starting
at the first element.
Looping until cursor is null, we can conduct certain processes and then
advance the cursor when we need using cursor arrow value.
>> Remember, this is the same thing as saying star cursor, dereferencing
cursor, then using the dot operator value.
So updating the cursor is by assigning the cursor to cursor arrow next.
>> Say you determine that D becomes in between C and E. To insert the node,
have the new_node D point to the node E, which is cursor next.
And then C, the cursor, can then point to D. That way, you maintain a list.
Be careful not to lose your links by moving the cursor arrow next to D
right away.
>> All right.
So that's how you might insert nodes, load them in, load words into those
nodes, and insert them into your hash table.
So now let's look at tries.
>> In a trie, every node will contain an array of node pointers, one for every
letter in the alphabet plus an apostrophe.
And each element in the array will point to another node.
If that node is null, then that letter isn't going to be the next letter of
any word in a sequence, because every word indicates whether it's the last
character of a word or not.
>> Let's look at a diagram.
Hopefully things will be a bit clearer.
In this diagram, we see that only certain letters and certain substrings
are being listed out.
So you can follow certain paths, and all of those paths will lead you to
different words.
>> So how do we represent this in C?
Well, every node now is going to have a Boolean value indicating whether
that node is the end of a given word or not.
And then it'll also have an array of node pointers called children, and
there are going to be 27 of them.
And remember, you'll also want to keep track of your first node.
We're going to call that root.
>> So that's the structure of a trie.
How do we represent this as a dictionary?
Well, to load words in, for every dictionary word, you're going to want
to iterate through the trie.
And each element in the children corresponds to a different letter.
>> So checking the value at children index i, where i represents the
specific index of the letter that you're trying to insert.
Well, if it's null, then you'll want to malloc a new node and have children
i point to that node.
>> If it's not null, then that means that that given branch, that given
substring, already exists.
So then you'll just move to that new node and continue.
If you're at the end of the word that you're trying to load in the
dictionary, then you can set that current node that you're on to true.
>> So let's look at an example of inserting the word "fox" into our
dictionary.
Pretend we start with an empty dictionary.
The first letter, F, will be located in children index five of the roots
children array.
So we insert that in.
>> The letter O will then be in children index 15, after that F. And then X
will be even below that, branching off of the O's children.
And then because X is the last letter of the word "fox," then I'm going to
color that green to indicate that it's the end of the word.
In C, that would be setting the Is Word Boolean to the value true.
>> Now what if the next word that you're loading in is the word "foo"?
Well, you don't need to malloc any more space for F or for O, because
those already exist.
But the last O in foo?
That one, you'll have to malloc.
Make a new node for that, setting the Is Word Boolean to true.
>> So now let's insert "dog." Dog will start with index three of the roots
children, because D hasn't been created yet.
And we'll follow a similar process as before, creating the substring dog,
where's the G is colored green because that's the end of a word.
>> Now, what if we want to insert "do"?
Well, this is a substring of dog, so we don't need to malloc anymore.
But we do need to indicate where we've reached the end of that word.
So the O will be colored green.
Continuing that process for every single word in your dictionary, you've
loaded them in into either your hash table or your trie.
>> speller.c will pass in strings for dictionary.c to check them.
Now, the Check function has to operate under case insensitivity.
That means that capital letters and lowercase letters and a mix of both
should all equate to true if any combination of that is in the
dictionary.
You can also assume that strings are only going to contain alphabetical
characters or apostrophes.
>> So let's look at how you might check with a hash table structure.
Well, if the word exists, then it can be found in the hash table.
So then you can try to find that word in the relevant bucket.
>> So which bucket would that word be in?
Well, you'd get the number, that index of the bucket, by hashing that word
and then searching in that linked list, traversing through the entire
linked list, using the String Compare function.
>> If the end of the linked list is reached, meaning that your cursor
reaches null, then the word is not to be found in the dictionary.
It won't be in any other bucket.
So here, you might see how there might be a trade-off between having either
sorted linked lists or unsorted ones.
Either will take more time during load or more time during check.
>> How might you check in a trie structure?
We're going to travel downwards in the trie.
For each letter in the inputted word that we're checking, we'll go to that
corresponding element in the children.
>> If that element is null, then that means that there are no substrings
containing our input word, so the word is misspelled.
If it's not null, we can move to the next letter of the word that we're
checking and continue this process until we reach the end
of the input word.
And then we can check if Is Word is true.
If it is, then great.
The word's correct.
But if not, even though that substring exists in the trie, the word is
misspelled.
>> When the function Size is called, size should return the number of words that
are in your given dictionary data structure.
So if you're using a hash table, you can either go through every single
linked list in every single bucket counting the number
of words are there.
If you're using a trie, you can go through every non null
path in your trie.
Or while you're loading the dictionary in, maybe you can keep track of how
many words you're loading in.
>> Once speller.c finishes checking the text file against the dictionary, then
it's done and so it calls Unload, where your job is to free anything
that you've malloced.
So if you use a hash table, then you need to be especially careful to avoid
memory leaks by not freeing anything prematurely and holding onto every
single link before you free.
>> So for every element in the hash table and for every node in the linked list,
you'll want to free that node.
How do you go about freeing a linked list?
Setting your node pointer cursor to the head, to the beginning of the
linked list, then while your cursor isn't null, you can set a temporary
node pointer to your cursor.
Then advance the cursor.
And then you can free that temporary value while still holding on to
everything afterwards.
>> What if you're using a trie?
Then the best way to do this is to unload from the very
bottom to the top.
By traveling to the lowest possible node, you can free all pointers in
that children and then backtrack upwards, freeing all elements in all
of the children arrays, until you hit your top root node.
Here's where Recursion will come in handy.
>> To make sure that you've probably freed everything that you've malloced,
you can use Valgrind.
Running Valgrind will run your program counting how many bytes of memory
you're using and making sure that you've freed them all, telling you
where you might have forgotten to free.
So run that and once Valgrind tells you and gives you the go ahead, then
you've finished unload.
>> Now, a couple of tips before you go off and start implementing your
dictionary.
I'd recommend to pass in a smaller dictionary when you're trying to test
things out and debugging with GDP.
The usage of speller is ./speller, an optional dictionary, and then a text.
>> By default, it loads in the large dictionary.
So you might want to pass in the small dictionary, or maybe even make your
own, customizing your dictionary and your text file.
>> And then finally, I'd also recommend to take a pen and paper and draw
things out before, during, and after you've written all of your code.
Just make sure that you've got those pointers just right.
>> I wish you the best of luck.
And once you've finished, if you'd like to challenge the big board and
see how fast your program is compared to your classmates', then I encourage
you to check that out.
>> With that, you've finished the speller PSet.
My name is Zamyla, and this is CS50.