CS 70

Phase 8: Using Your Search Tree

To round out our assignment, we'll use our TreeSet class template as an actual dictionary of English words.

We've provided a source file, minispell.cpp, which uses TreeSet<std::string> to provide a proof-of-concept for a rudimentary spelling checker. It's basically the same program you saw in Homework 6, but with some additional options to control insertion style.

Let's Go!

Adapt Your Makefile to Build minispell and Build It

Adjust your Makefile so that you build the program minispell (the executable will link just minispell.o since TreeSet is now a class template), and create this executable.

It will help if your Makefile has an OPTFLAGS= variable, as you then can set that variable from the command-line to easily have make build everything with optimization, as, for example,

make clean
make OPTFLAGS="-O3 -flto" LDFLAGS="-flto" minispell

or, if your LDFLAGS variable in your Makefile includes other libraries, you should instead run

make clean
make OPTFLAGS="-O3 -flto" LDFLAGS="-lsomelibraryineed -flto" minispell

where you replace -lsomelibraryineed with whatever else you need to link (because specifying LDFLAGS= on the command line overrides whatever is in your Makefile).

Run minispell

If you run the program with the --help argument, it will produce a usage message:

> ./minispell --help
Usage: ./minispell [options] [file-to-check ...]
Options:
  -h, --help             Print this message and exit.
  -f, --file-order       Insert words in the order they appear (default).
  -s, --shuffled-order   Insert words in random order, by shuffling the input.
  -b, --balanced-order   Insert words in a balanced order
  -r, --random-insert    Use a tree with RANDOMIZED insertion style (default)
  -t, --root-insert      Use a tree with ROOT insertion style
  -l, --leaf-insert      Use a tree with LEAF insertion style
  -S, --use-std-set      Use std::set instead of TreeSet
  -n, --num-dict-words   Number of words to read from the dictionary.
  -m, --num-check-words  Number of words to check for spelling.
  -d, --dict-file        Use a different dictionary file.

Default dictionary file: /cs70/data/smalldict.words
Default file to check:   /cs70/data/ispell.words

If you run it without arguments, you should see output similar to

> ./minispell
Reading words from /cs70/data/smalldict.words... done!
Inserting into TreeSet, using randomized insertion (in order read)... done!
 - insertion took 0.000517011 seconds
 - 341 nodes, height 20, average depth 8.78299
 - median word in dictionary: 'long'

Reading words from /cs70/data/ispell.words... done!
Looking up these words in the dictionary... done!
 - looking up took 0.00717264 seconds
 - 34831 words read, 325 in dictionary

Exploration

There are five dictionary files available in /cs70/data/ that you can use with this program:

smalldict.words
A small dictionary of 341 common English words.
ispell.words
The main dictionary used by the ispell spelling checker, containing 34,831 common words.
largedict.words
A larger dictionary of 281,478 English words, mostly taken from scrabble word lists.
web2
A dictionary of 234,937 words, originally based on some version of “Webster's Dictionary” and provided on most Unix systems.
all.words
The above dictionaries combined, for a total of 410,239 words.

Explore some of the other options to the program by doing some other runs. Also, feel free to run the program multiple times to see if/when the program output varies.

Interesting things to try include running

./minispell -r -d /cs70/data/all.words /cs70/data/web2

and contrasting the results with running

./minispell -S -d /cs70/data/all.words /cs70/data/web2

Questions

Answer these here on the page; your answers are saved as you go.

  • Sherlock speaking

    this week, we expect you to do these written questions after the coding part.

Question 1.1

Sample Runs

Copy and paste the results of running each of the commands below:

LEAF insertion of 10,000 words in file order (sorted)

./minispell -l -f -n 10000 -d /cs70/data/ispell.words /cs70/data/smalldict.words

ROOT (top) insertion of 10,000 words in file order (sorted)

./minispell -t -f -n 10000 -d /cs70/data/ispell.words /cs70/data/smalldict.words

RANDOMIZED insertion of 10,000 words in file order (sorted)

./minispell -r -f -n 10000 -d /cs70/data/ispell.words /cs70/data/smalldict.words

Question 1.2

Exploration

There are other options to the minispell program (run ./minispell --help for details). Explore.

Tell us about what you explored and something you learned/discovered:

Question 2.1

Let's contrast the ROOT insertion scheme for building trees with the LEAF insertion scheme for building trees… (Note: some options below are about lookup in such trees after they've been built, not insertion.)

Select all that are true when we are inserting sorted data:

Question 2.2

Here's a plot of the time performance of exists looking up each of the items in a tree of size $$n$$. The tree was built by inserting the items in sorted order. The graph shows time per item.

success.png

(The TreeSet/LEAF and TreeSet/ROOT lines overlap significantly.)

What can you conclude about lookup performance in trees built with TreeSet's LEAF and ROOT insertion styles? The graph is consistent with a single lookup in a tree of size $$n$$ requiring …

Question 2.3

From the same graph, what can you conclude about the performance of lookup in std::set (which is actually a red-black tree)? The graph is consistent with a single lookup in a tree of size $$n$$ requiring …

Question 2.4

From the same graph, which scheme is the RANDOMIZED insertion scheme's performance most similar to?

Question 2.5

Real-world experiments often have sources of noise beyond what we model in theory. Overall, we can consider that this graph

Question 2.6

Here's a plot of the time performance of insert, inserting $$n$$ items in sorted order. The graph shows time per item.

ordered.png

Previously, the lines for TreeSet's LEAF scheme and TreeSet's ROOT scheme overlapped so closely that you could barely see the LEAF line. Now they are radically different, and the line for ROOT insertion quickly becomes horizontal.

Explain what a horizontal line means in a graph like this, and why the lines were previously aligned, but now are so different.

Question 3

Worst-Case Behavior

A random tree with $$n$$ nodes has a worst-case average depth of $$\frac{n-1}{2}$$ and a worst-case height of $$n-1$$.

How close were you able to get to this worst-case with randomized insertion?

Briefly explain your answer. (You answered a similar question in Homework 6 about shuffled insertion, so, ideally, say something fresh rather than repeating that answer.)

Can you make a more balanced tree by inserting the data in shuffled order and using randomized insertion? Briefly explain your answer.

(When logged in, completion status appears here.)