Phase 8: Inventing Words

Your HashMultiset<T> works, so now it's time to replace wordgen's placeholder with a real model, the one from Phase 1, that counts what comes after each context and rolls dice in proportion to those counts.

You'll be working in wordmodel.cpp, writing three member functions of the WordModel class: train, generate, and isKnown. The class's interface is in wordmodel.hpp, which is provided; read it first.

The WordModel Class

A WordModel is made with a context length, \( k \), and learns from words one at a time:

WordModel model(3);           // k = 3
model.train("melon");         // learn from some words
model.train("lemon");
RandUInt32 rng;               // the course's random-number generator
std::string word = model.generate(rng);   // invent a word
bool real = model.isKnown(word);          // was it one of the training words?

Its private data members are

• contextLength_, which is \( k \);
• alphabet_, a string holding every character seen in training (and END), in the order they were first seen. The provided function rememberCharacters keeps it up to date;
• counts_, a HashMultiset<std::string> that counts n-grams: each context together with the character that came after it. With a context length of \( k \), these are n-grams of \( n = k + 1 \) characters;
• words_, a second HashMultiset<std::string>, which holds the training words themselves.

The class also has three constants: START ('^'), which pads the beginning of a word; END ('$'), which marks the end; and MAX_LENGTH, which stops a word from growing forever, whatever the counts say.

Your Task, Part A: train

train has three jobs:

• call rememberCharacters (that call is already there);
• insert the word into words_; and
• pad the word with \( k \) STARTs at the front and one END at the back, then insert every n-gram (every run of \( k + 1 \) characters) into counts_.

For example, with \( k = 2 \), training on melon pads it to ^^melon$ and counts these six 3-grams:

A word of \( m \) characters always gives \( m + 1 \) n-grams, whatever \( k \) is.

Your Task, Part B: generate

generate invents one word, a character at a time, using this method:

SET context to k STARTs, and word to be empty
while word is shorter than MAX_LENGTH:
      foreach character c in alphabet_, in order:
            LOOK UP its weight: how many times context + c was counted
            ADD that weight to total
      ROLL rng.get(total), which gives a number from 0 to total − 1
      foreach character c in alphabet_, in order, until one is chosen:
            if the roll is less than c's weight, choose c
            otherwise subtract c's weight from the roll
      if the chosen character is END, stop
      ADD the chosen character to word, and slide context along
RETURN word

"Slide the context along" means add the chosen character to the end of the context and drop its first character, so it's always the last \( k \) characters.

You'll probably want to keep the weights from the first loop in a std::vector<size_t>, so that the second loop doesn't have to look them all up again.

Watch Out for \( k = 0 \)

wordgen -k 0 is allowed, and it's interesting: with no context at all, the model only knows how common each letter is. But then the context is an empty string, and context.substr(1) throws an exception on an empty string. context += next; followed by context.erase(0, 1); works for every \( k \), including 0. (At \( k = 0 \), the model can also choose END first and invent an empty word, which wordgen prints as a blank line. That's not a bug.)

Your Task, Part C: isKnown

isKnown says whether a word was one of the training words. That's what words_ is for.

Once you've written all three functions, remove the #pragma line (marked FIXME) from the top of wordmodel.cpp.

Your Task, Part D: Test It

How can you test code that makes random choices? Two ways:

• Use a seed. A RandUInt32 made with a seed, like RandUInt32 rng(42);, makes the same "random" numbers every time, so a test can't pass on Monday and fail on Tuesday.
• Test what must be true whatever the dice say. Trained on the single word abc, the model has no choices to make, so it can only invent abc. That test is already in wordmodel-test.cpp, as an example.

Add at least these tests to wordmodel-test.cpp:

• No new n-grams. Every n-gram of an invented word (padded the same way) must be one that was counted in training. Train a model on a few words, keep your own HashMultiset<std::string> of their n-grams in the test, and check every n-gram of a couple of hundred invented words against it. (Skip the last n-gram of a word that stopped because it reached MAX_LENGTH: that word never chose END, so its padded last n-gram may never have been counted.)
• isKnown. It says yes to the training words, and no to everything else, including words that are nearly the same.

Then run make and ./wordmodel-test, and check it with Valgrind.

Your Task, Part E: Switch It On

Near the top of wordgen.cpp, change

#define WORDGEN_USE_WORDMODEL 0

to

#define WORDGEN_USE_WORDMODEL 1

and run make again. Now try the command from Phase 1:

./wordgen -s 127 /cs70/data/ispell.words

If you choose characters exactly as Part B describes, you'll see

its *
gamentrodybuildes
real *
nondanceshiftier
irreclusted
hood *
wate
madrase
dile
befrongs

followed by some statistics, which go to cerr:

Learned from 34831 words with k = 3; 3 of the 10 invented words were already in the list (*).
316283 n-grams counted, 20828 different ones, 26 characters

and, last of all, your hash table's own statistics: the showStatistics line you wrote the functions for in Phase 7. Your numbers on that line will be different from everyone else's, because they depend on your hash function from Phase 3 (which wordgen uses) and your choices of DEFAULT_NUM_BUCKETS and DEFAULT_MAX_LOAD_FACTOR.

Try this, too: make myhash in stringhash.cpp return str.length() for a moment, run make, and run the same command again. Every n-gram has the same length, so every one lands in the same bucket: your showStatistics line shows the damage, and wordgen takes tens of seconds instead of a tenth of one. (Then put your own hash function back!) This is why Phase 3 mattered.

Now play! Try different values of -k, different lists from /cs70/data/wordlists, and lists of your own. Invented words that happen to be in the training list are marked with a *. The written questions will ask what you notice.

(When logged in, completion status appears here.)