Phase 1: Words That Don't Exist

Companies really do this. George Eastman wanted a name for his camera that was short, hard to mispronounce, and like no existing word, so he made one up: Kodak. In this homework, you'll build a program that makes up words like that, thousands of them, each one sounding like it belongs to whatever list of words you trained it on.

The Idea, by Hand

Look at the last few letters you've written, and ask: in real words, which letters came next after those letters, and how often? Then choose the next letter with those odds.

The number of letters you look back at is called \( k \), the context length. Here's how it works with \( k = 2 \) and five words to learn from:

So that every letter has two letters before it (even the first one), we put two ^ characters at the start of each word, and a $ at the end to show where the word stops. So melon becomes ^^melon$. Now slide a window three characters wide (the two letters of context and the letter that followed them) along every padded word, and count the three-character sequences you see. Sequences like these are called n-grams; these are 3-grams (or trigrams). In general, a model that looks back \( k \) letters counts n-grams of \( n = k + 1 \) characters. Here are some of the counts:

To invent a word, start with the context ^^ and roll dice. Say you get y (a 1-in-5 chance). The context is now ^y, and the only thing that ever followed ^y was e; then ye was followed only by l. From el, roll a three-sided die: two sides say l and one says o. Say it comes up o. From lo, the die says w two times out of three and n one time out of three. Say n, and from on the only thing next is $, so we stop.

We've made yelon, which isn't any of the five words, but it sounds like it could be. Starting with m, you might make melow the same way. (Try it: what other new words could these five words make? Are there any they can never make?)

A multiset is like a set, except that inserting the same key again doesn't do nothing: it adds one to that key's count. (Python calls this a Counter.) With a few hundred thousand n-grams to count and look up, we'll want it to be fast, which is where hash tables come in.

Building the Code

After cloning the homework repository on the CS 70 server, run make (or cs70-make -H) to build the provided code. It should build without any warnings.

Running wordgen

The program wordgen learns from a list of words (one per line) and invents new ones. The CS 70 server has a list of about 35,000 English words in /cs70/data/ispell.words; try it:

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

You'll get ten "words", followed by some information about what was learned. With the seed -s 127, the first few are

s
xh
dnwosjhojaain
i
cxbrxsgcwidutkk

wordgen has a few options:

• -k K sets the context length (the default is 3, so wordgen counts 4-grams);
• -n N says how many words to invent (the default is 10);
• -s SEED gives the random-number generator a seed, so the same command makes the same words again (without it, you'll get different words each time);
• -d DIR says where to find lists named without a path (the default is /cs70/data/wordlists; see below).

You can give it more than one list, and it will learn from all of them.

Lists to Learn From

The CS 70 server has lists to try in /cs70/data/wordlists (all lowercase, one word per line). You can give wordgen the name of one of these lists without the path, so

./wordgen adverbs

reads /cs70/data/wordlists/adverbs.txt. Here's what's there:

• nouns, verbs, adjectives, adverbs: common English words, sorted by part of speech;
• places-hawaii, places-wales, places-maori, places-gaelic, places-us: place names;
• companies: names of companies listed on stock exchanges;
• names-girls, names-boys, names-androgynous, names-surnames: U.S. first names given mostly to girls, mostly to boys, or to both, and surnames; names-fr-girls, names-fr-boys, names-fr-androgynous: the same for France;
• pokemon and software: just for fun.

You're welcome to make your own lists, too: any file with one word or name per line works. If you'd like to keep them, put them in a lists folder in your repository and run, say, ./wordgen lists/mylist.txt. (Working somewhere other than the CS 70 server? Copy /cs70/data/wordlists and point -d at your copy.)

(When logged in, completion status appears here.)