I've always had a hard time coming up with names. It occurred to me that I could have my computer do it using n-gram models. Here's some output from a program I hacked out in the last couple of hours:

quote:

---

$ ./ngram.py 5 25 firstnames.txt surnames.txt
Americk
Gisell
Destina
Marlo
Piercedes
Zanderson
Fernard
Mollin
Madelinda
Bryana
Lelani
Brenne
Felica
Gianca
Arace
Brenderson
Cynthias
Malakaila
Maximillan
Khalia
Hillar
Charley
Jamiro
Melandon
Belena
181 duplicates

---

"firstnames.txt" and "surnames.txt" are the training set - just files full of names. This is a 5-gram model. The output is 25 names where every 5-letter sequence is guaranteed to have the same probability as every 5-letter sequence in the training set. It does generate names in the training set (the 181 duplicates), but it doesn't display those.

http://axon.cs.byu.edu/~neil/ngram/

Download all the files. It's a command-line program, so there's no friendly GUI. You'll need Python installed, which is standard in Linux, and easy to install in Windows:

In more intuitive terms, it generates random words that sound kind of like the words you feed it. On top of that, there are many subtleties of its behavior that you'd only understand or even care about if you'd studied temporal probabilistic models.

Ahem. My inner nerd is showing through. Excuse me while I cover it up. Don't peek, now.

I fed it Alice in Wonderland and it churned out these delightful words:

quote:

---

aroundrence
Serpill
seatered
bream
forgetter
Turt
sudded
existerpill
flamping
musion
expent
onely
greathinkling
tillion
hisk
witnestillarm
sobster

---

And this was fun:

quote:

---

./ngram.py 5 10 slavic_surnames.txt japanese_surnames.txt
Nakanishida
Goncharoff
Shimaru
Umenov
Tashi
Hayashimamoto
Vernacki
Asakurai
Shige
Solovkin

---

So have you done swear words yet?

Doesn't Luke whine to Uncle Owen about going into Tashi station to pick up some power converters?

A suggestion: make it eliminate duplicates from the list it generates. When working with a limited data set, such as a list of the countries of the world, it generates quite a few duplicates:

Finlands
Island
Britania
Ukrain
Britania
Island
Swazil
Braziland
Armenistan
Senegro
Vatic
Colomon
Turkmenia
Angolia
Island
Turkmenia
Angolia
Turkmenia
Myanmark
Austral
Senegro
Armenistan
Nicaraguay
Myanmark
Belarussalam

(Edited to put URL of new version.)

One problem with removing duplicates from the list is that it may run indefinitely on some inputs. If you make it generate characters with a 7-gram model and suppress duplicates in its own generated list, it'll generally keep trying the same names over and over. I'll probably just have it uniquify (that's a proper computer-sciencey term, I swear) the list before it spits it out.

I'll also add weights. Right now, if you feed it a list of 100 Slavic names and 1000 French names, it'll generate mostly French-sounding names. I'll have it pre-normalize the weights too, so it'll do what you expect without having to adjust the weights on your own. I've wanted to do that for a while now.

I'll post here again when the changes are up.

On your web page, it might make sense to call the first number the "gibberish factor," and limit it from 1 to 6. 1 is a unigram model, which just selects characters without regard to what came before. At higher ns it looks at the preceeding n-1 characters to figure out what to output next. The higher the number is, the more the words resemble actual words.

What I'm doing with the Perl script is basically just passing the parameters to your Python script and printing the results it gets back. So it's your script that's doing all the heavy lifting; I'm just putting a front end on it.

Eric, any chance you can modify the CGI to accept a list of words or names and use those instead of yours?

Hmm. The Python script only accepts filenames as parameters for word lists.

http://axon.cs.byu.edu/~neil/ngram/

It'll do sentences with the "-s" switch, but it's really for entertainment value more than anything. Because of data sparsity (that whole "almost all sentences are unique" thing), it doesn't make much sense to go above a 3-gram with sentences. It also doesn't parse sentences very well in the first place.

Alice in Wonderland, 3-gram model:

quote:

---

`There's certainly too much pepper in that case I can find them.' As she said this, she came upon a heap of sticks and dry leaves, and the arm that was trickling down his cheeks, he went on, `I must be a great interest in questions of eating and drinking.

---

So if you've got an insane character and you need some dialogue, this'll fix you right up.

You can now put an integer or decimal weight after each input file. It pre-normalizes the weights, too: if you give it "scottish_surnames.txt japanese_surnames.txt" both Scottish and Japanese names will be well-represented in the output regardless of how many names each file contains. I've been doing things like this:

quote:

---

./ngram.py 5 10 synonyms_ugly.txt alice.txt 0.1
cantageous
mephitical
blemistic
fractionable
fraughter
debase
unwelcomely
snappetizing
blotten
dangersometimes

---

Mix Scottish names with physics words:

aninstry
Dunderven
Cossic
Scotinum

Use them all in a sentence:

"Craig Dunderven, the Cossic expert in aninstry, discovered Scotinum -- in his closet, where his physicist wife had stored it."

We'll call a list of sequences of tokens a "corpus." (In this case, the tokens are letters.) An n-gram model is nothing more than an n-1th order Markov model that you induce ("train") from the corpus.

Let's say you're doing trigrams. That means you need a probability distribution P(token[i] | token[i-1], token[i-2]). To "train," you initialize a counter for each 3-token combination, loop over each sequence a token at a time, and for each three-token sequence, increment the counter. (You pad the beginning of each sequence with two start tokens, '<S>', and append a stop token, '</S>'.) Now that you've got token counts, you can normalize them to get P(token[i] | token[i-1], token[i-2]).

The function SimpleNGramModel.train() does this part. It also does all the lower-order n-grams as well.

So you've got probability distributions over tokens. Now what? Well, you can generate random token sequences and calculate how probable they are (the product of the probabilities of each token given the two before), but that could take a while. Instead, you do this:

1. Start with <S><S>, let i = 2.

2. Pick a token from P(Token | token[i-1], token[i-2]). If this is zero for all tokens, pick from P(Token | token[i-1]). If this is zero for all tokens, pick from P(Token). Assign the pick to token[i].

3. If token[i] == </S>, stop. Otherwise, i++, goto 2.

The generate() function does this part. The rest of the script just parses files and makes calls to generate().