I'm busy working on techniques for procedural name generation, because, quite frankly, existing approaches seem to leave a lot to be desired. My requirements are:

• Near unlimited number of names can be generated
  
• Names look and sound reasonable
  
• Names can be generated in a variety of languages/dialects
  

I started out with a simple Markov generator (because Markov chains seem to be the weapon of choice in the text generation arena), but I quickly found a lack of balance between order 2-3 Markov chains, which often return impossible (in the context of valid English spelling) character sequences, and degenerate order 4 chains, which just return selections from their input text.

So I decided that a better avenue might be to explore a pronunciation model, where we generate names based on phonemes, and then translate the results back into text (i.e. graphemes).

I've built a system that does braindead-simple (but suprisingly effective) text->phoneme conversion in order to train the model, and then uses a pair of Markov chain models to actually generate the text. The first Markov model is used to generate procedural strings of phonemes, and the second is used to translate that string into legal grapheme sequences (i.e. text). Look at a few examples of the output...

# trained with the 1,000 most popular American baby names of 2011
kegan
declan
maver
elisay
dan
jared
mikay
peytonykeelynn
klare
adwin

# trained with the 360 most popular Spanish names
vicen
fidela
ysaas
uma
rosa
valentin
florena
gabrah
wendra
dino

# trained with the ~2,000 most popular Russian names
vilma
soree
pera
ovarsonaya
tonya
stopolina
belga
alina
sascha
prosdoia

# and for completeness, ~200 names from Tolkien
aldor
anardil
acainaro
atanamir
barahir
aldaron
baggins
bregil
arthedain
bifhad

Apart from a tendency to spit out verbatim names from the training set, and the (fairly rare) long junk name, this seems to work pretty well. But I'd like to make it better - which is where you guys come in.

I don't have enough of a background in linguistics to know where I should be looking for techniques/approaches to improve my algorithm. I'd be very appreciative of any links to relevant literature in the field, or just general brainstorming on approaches I could apply...

[attachment=10206:fabula.zip]
(python source and word lists are attached, if you want to have a poke around)

Your mapping to phonemes and back to text doesn't seem to work very well for Spanish

Ja, my phoneme map is currently hard-coded for English. In theory that should be as simple as loading up a new map for each language - but English is the only language that I was able to find a decent pre-built table for

I have had reasonable results using a weighted average of two-letter and three-letter Markov chains, plus a filter to remove the occasional really long name. You mat want to also filter out names that were in the input.

I've tried with Spanish, English and Japanese toponyms, and also with a list of Star Wars character names (all around 500 inputs). I was pretty satisfied with the results, but perhaps I am more easily satisfied than you are.[/quote]
That is roughly what I tried as a first attempt (and seems to be the most common approach). My main issue with this (and it could be somewhat an artefact of my implementation) is that even with a relatively large input text, a three-letter Markov chain basically ends up stringing together discrete 3-letter chunks that appear often.

What do you want to focus on improving the most? Weeding out junk? Reducing verbatim repetition? Ensuring few duplicates are generated? Better quality in the names which are generated?

Junk is the biggest overall problem - I want this to run without human intervention, so I won't be able to filter out junk. That said, my current system only generates junk when it generates extremely short/long names, which provides a fairly easy way to filter them out.

After that quality is the most important. Apart from incorrect phoneme maps, the Spanish/Russian/Tolkien generators do fairly well, but the English one really kind of sucks, I think because my training data contains many non-traditional English names (i.e. American is a melting pot, many cultures names are in the sample). I can probably solve this with a more traditionally English data set, but I haven't had time to find/construct one.

Verbatim repetition is not really that much of a problem. I don't want the entire world to be populated by Johns and Daves, but if there are a few of them it won't break immersion.

I wonder whether some research into the way names evolved may help. For example roots in professions (Baker, Miller, etc), linguistic simplifications/shifts, family traditions (Donald -> MacDonald, Ander -> Anderson). It may give you a way to generate plausible names from actual roots.[/quote]
A simple probability driven table of prefixes/suffixes could do wonders for the 'mac, mc, son' case. A table of professions and a mutator function could server for the other. I like these ideas.

This is good stuff, keep it coming!