Phase 1: Words That Don't Exist

Companies really do make up names for things this way. 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

Imagine that you're writing something. Look back at the last few letters you wrote, and ask yourself: In real words, which letters came next after those letters, and how often did each option appear? Then choose the next letter based on those odds.

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

To ensure 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$, lemur ^^lemur$, and so on.

Now slide a window that's three characters wide (i.e., 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; here we have 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 some 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 adds one to that key's count (instead of being discarded). (Python calls this type a Counter.) With a few hundred thousand n-grams to count and look up from, we'll want our multiset code 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 wordgen program you just built 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 you can use for your word list; try running wordgen with

./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 using the same seed will cause wordgen to make the same words again (without the -s parameter, you'll get different words each time);
• -d DIR says where to look for filenames without a full path (the default location to search is the directory /cs70/data/wordlists; see below).

You can also give wordgen more than one list to work on, and it will learn from all of them.

Lists to Learn From

The CS 70 server has a number of lists you can try out, stored in /cs70/data/wordlists. Each list file contains a set of words, one word per line, all lowercased. You can use one of the provided lists without specifying the full path; for example,

./wordgen adverbs

reads /cs70/data/wordlists/adverbs.txt.

Provided Word Lists

nouns, verbs, adjectives, adverbs

Common English words, sorted by part of speech.

places-hawaii, places-wales, places-maori, places-gaelic, places-us

Place names for the named locations.

companies

Names of companies listed on stock exchanges.

names-girls, names-boys, names-androgynous

U.S. first names given mostly to girls, mostly to boys, or to both.

names-surnames:

U.S. surnames.

names-fr-girls, names-fr-boys, names-fr-androgynous

French first names for girls, boys, and both.

pokemon and software

Just for fun.

You're welcome to make your own lists, too: any file with one (lowercased) word or name per line works. If you'd like to keep your lists, 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.)