How can we randomly generate names? We could string together random letters, but this often leads to nonsense names.
This happens because we fail to take into account the relationships between letters. For instance, ‘U’ often follows ‘Q’, ‘SH’ is typically followed by a vowel, ‘OO’ is often followed by a consonant, and ‘X’ is rarely found between consonants. We need to generate random letters while still maintaining these typical relationships. How can we do this without hand-programming a large set of rules?
We can use a Markov model to generate names that match a certain style we want.
To start, we need a list of names in the style we want to emulate, for example Elvish or Welsh names. We go through each name letter by letter and record which letters follow which. So given the short list of Lee, Leo and Liam, we can see that ‘e’ and ‘i’ can come after the letter ‘L’. Then, when generating a name and we need a random letter to come after ‘L’, we restrict our choice to letters we know can follow it, such as ‘e’ or ‘i’. We can organize our model into a dictionary which can look like:
model[ "L" ] = [ 'E', 'E', 'I' ]
model[ "E" ] = [ 'E', 'O', '*' ]
model[ "I" ] = [ 'A' ]
model[ "_" ] = [ 'L'', 'L', 'L' ]Notice how there is a ‘*’ as a letter in our model for ‘E’. This asterisk signifies that ‘E’ was the last letter of a name, which was Lee. If we want to generate a letter to come after “E” we can randomly choose ‘E’, ‘O’ or ‘*’ to follow. If the choice is ‘*’ the name is classed as complete and the name generator stops.
We also have an underscore in our model, this underscore represents the start of a name with all three of our names starting with ‘L’.
To generate a name we start with ‘_’. We look into our model and pick a random letter from the list for ‘_’, in this case the only choice is ‘L’. We then repeat the process for ‘L’, picking a random possible choice from our model for ‘L’, for example ‘I’. We continue to do this until one of the random characters we choose is a * which represents the end of the name. Our names list is far too small to be able to generate unique names and will mostly output names already in the list. To increase randomness you must gather a list with many examples. Try the generator below:
What we have just created is a Markov chain with order 1. The order represents how much information we look at to make a decision, our current model is order 1 because we look at just a single letter to decide what the next letter would be. This can cause issues with some names. For instance look at our model for the letter “L”.
model[ 'L' ] = [ 'I', 'I', 'I', 'E', U', 'L', 'E', '*', 'O' ]One possible option to follow ‘L’ is another ‘L’. Since we only look at the last letter to generate the next, if you are unlucky you can generate a name with 4 or 5 letter ‘L’s in a row. To make a better generator we can increase the order. A model with order 2 will look at what letter follows pairs of letters. An example model is below:
model[ 'LL' ] = [ 'I' ]
model[ 'LE' ] = [ 'E', 'O']
model[ 'EE' ] = [ '*' ]
model[ 'EO, ] = [ '*' ]
model[ '__' ] = [ 'L' ]
model[ '_L' ] = [ 'E', 'E', 'I' ]Now the only letter that can follow two ‘L’s is an ‘I’. Notice how we also need an entry for two underscores now. What this all means is that when we are generating a name the last two letters of our name will influence the next letter, rather than just the last letter alone. You can increase the order to 3 or higher, meaning you look at the previous X amount of letters. Increasing the order increases the accuracy towards the supplied names list. This means you will find that you generate names already in your list more often. Decreasing the order means names will be more random and therefore more chaotic.
Increasing the amount of names you supply increases the quality of the random names. Below is an order 2 Markov chain with the first 150 Pokemon as source names.
Implementation
Below is a commented python implementation:
import random
# our source names
nameDB = [
"Liam", "Noah", "Oliver", "Theodore", "James",
"Henry", "Elijah", "Alexander", "Lucas", "William",
"Benjamin", "Levi", "Michael", "David", "Anthony",
"Matthew", "Logan", "Ryan", "Thomas", "Andrew"
]
# our model will be a dictionary and we will use an order 2 model
markovModel = {}
order = 2
# generate the underscore prefix based on our order. this will be added to the start of all names,
# we use the underscore prefix to understand what letters commonly start the names
underscorePrefix = ""
for i in range(order):
underscorePrefix = underscorePrefix + "_"
# build our markov model. Go through every name and create a database
# of what letters can follow other letters.
def buildMarkovModel(markov, names):
#go through every name
for name in names:
# edit the name to add underscore prefix and * ending
# lee becomes __lee* (for order 2)
name = underscorePrefix + str(name) + "*"
#loop through each character, use -order to avoid overflow
for i in range(len(name) - order):
# our state is the subsection of the name that we are looking at
# if our order is 1 then this is just the current letter
state = name[i:i+order]
# nextChar is the character immediatley after our state
nextChar = name[i+order]
#if we havent come across our word subsection then create the list first
if(state not in markov):
markov[state] = []
# add the character to our list for that state, later on we
# can check markov to see what letters follow our current state
# e.g markov["le"] = ["e", "o", "n"]
markov[state].append(nextChar)
def generateName(markov, minLen = 5, maxLen = 8):
name = ""
nextChar = ""
# our starting state is the underscore prefix, signifying the start of a name
state = underscorePrefix
# keep creating the name until we reach a terminating star which
# means our name should finish there
while(nextChar != "*"):
# if we havent hit the minimum length that we want
if(len(name) < minLen):
# get all available nextChars for our state but make sure
# "*" is removed as we dont want to end
chars = [c for c in markov[state] if c != "*"]
# if chars is empty then "*" was our only option and we have to return
# a shorter name ( or you can make it generate another name )
if not chars:
return name
nextChar = random.choice(chars)
# if our name exceeds our maximum length then just return it now
elif(len(name) >= maxLen):
nextChar = "*"
else:
#check our state and grab a random character from the choices available
nextChar = random.choice(markov[state])
if(nextChar != "*"):
name = name + nextChar
# update our state, drop the first character of our state, keep the rest and
# add the newest character to it.
state = state[1:] + nextChar
return name
# build our model
buildMarkovModel(markovModel, nameDB)
# generate and print the name
name = generateName(markovModel)
print(name)
Leave a Reply