15,561,125 members
Articles / Desktop Programming / Windows Forms
Article
Posted 31 Oct 2016

21.7K views
21 bookmarked

# Random Name Generation Using Markov Chains

Rate me:
This article describes the building of Markov Chains and their use for generating random names or words.

## Introduction

Recently I needed an application which can generate random, human-readable names. My searches lead me to Markov Chains, and how they can be built and used for random words or names generation.

I found an old post exposing a C++ implementation, on which I based my approach. The map-building implementation mainly inherits from this C++ implementation, but I completely changed the random generation part, which I considered as unoptimized (relying on huge strings manipulations), at least for a .NET managed solution.

This article describes the resulting implementation, and provides a basic Winforms application around it.

## Background

I will not describe here the basic concept behind Markov chains; this has already been done by people who have much more expertise than me on the subject, including here on CodeProject. You will find in the Links section below a list of relevant articles about them.

Let's just explain the general principle of the random generation:

1. A list of known/acceptable words has to be provided first so that a map can be built.
2. A map is built, referencing each letters-sequence (to a given depth) and how frequently it appears in the samples, as well as the place in the words a sequence can appear at (at start, in the middle, or at the end of the word).
3. This map is then used to generate random words. A former list of already generated and/or forbidden words can be provided, so that the algorithm does not generate the same word twice.

### What does a map look like?

A map associates a sequence of one or more letters to a list of possible next characters; for each of these possible following characters, a counter is maintained about the number of occurrences as well as the position in the string.

Let's see a depth-1 map built on the single word 'test'. This would look like:

Sequence   Next   First   Inner   Last
--------   ----   -----   -----   ----
t      e       1       0      0
e      s       0       1      0
s      t       0       0      1

If we increase the depth of the map to two characters, the following occurrences will be added to the above list:

Sequence   Next   First   Inner   Last
--------   ----   -----   -----   ----
te      s       1       0      0
es      t       0       0      1

### How is the map used to generate random words?

• First, as sequence is randomly chosen amongst all available sequences.
• Then, a list of all following characters (for all sequences, not only for the one randomly chosen) is built; if a character belongs to the possible following characters of chosen sequence, its frequency is taken from the one in the map; if it does not belong to possible following characters for this sequence, it is given a minimal frequency instead (which can be chosen). So that unavailbale combinations in the samples still have a slight chance to appear in the results.
• Finally, a random character is chosen from above list, and its chance to be chosen is proportional to its frequency.

## Implementation

### The Position enumeration

The Position enumeration is used to query a map for a specific frequency value.

C#
public enum Position : byte
{
First,
Inner,
Last
}

### The StateFrequency class

The StateFrequency class is quite simple, and just holds three integer variables to store frequency information about a given state. It also has a few methods allowing to increment internal fields.

C#
public class StateFrequency : IEquatable<StateFrequency>
{
public int FirstCount { get; private set; }
public int InnerCount { get; private set; }
public int LastCount { get; private set; }

public StateFrequency()
: this(0, 0, 0) { }

private StateFrequency(int firstCount, int innerCount, int lastCount)
{
FirstCount = firstCount;
InnerCount = innerCount;
LastCount = lastCount;
}

{
IncrementFirst(other.FirstCount);
IncrementInner(other.InnerCount);
IncrementLast(other.LastCount);
}

public bool Equals(StateFrequency other)
{
if (other == null)
{
return false;
}
if (ReferenceEquals(this, other))
{
return true;
}
return ((other.FirstCount == FirstCount) && (other.InnerCount == InnerCount) && (other.LastCount == LastCount));
}

public override bool Equals(object obj)
{
return (obj is StateFrequency) ? Equals((StateFrequency)obj) : false;
}

public overrride bool GetHashCode()
{
int hash = 351;
hash += FirstCount.GetHashCode();
hash *= 13;
hash += InnerCount.GetHashCode();
hash *= 13;
return hash + LastCount.GetHashCode();
}

public int GetValue(Position position)
{
switch (position)
{
case Position.First:
return FirstCount;
case Position.Last:
return LastCount;
case Position.Inner:
default:
return InnerCount;
}
}

public void Increment(int count = 1)
{
IncrementFirst(count);
IncrementInner(count);
IncrementLast(count);
}

public void IncrementFirst(int count = 1)
{
FirstCount += count;
}

public void IncrementInner(int count = 1)
{
InnerCount += count;
}

public void IncrementLast(int count = 1)
{
LastCount += count;
}

public override string ToString()
{
}
}

## Using the code

The MarkovChainsNameGenerator class is the only class that has to be used.

First, one has to add a reference to the RandomNameGenerator.Core.dll library.

Then, the library can be used this way:

C#
using RandomNameGenerator.Core;

int Main()
{
// Here I am presenting an initialization without any parameter specified.
// It means the generator will be initialiazed with its default values.
// You can customize these.
MarkovChainsNameGenerator generator = new MarkovChainsNameGenerator();
generator.TrainMapBuilder(@"C:\path\to\the\samples\file");
IEnumerable<string> names = generator.GetNames(100);
// From there you will get a list of a hundred random names generated from provided samples file.
}

## Using the provided Windows Forms application

Here is how application's main screen looks like:

1. The ListView where generated names will be displayed. List's items can be checked or not.
2. Here you can specify in which directory you wish to save the lists of accepted and rejected names. Only accepted names' file name can be specified, rejected names' file name being built relative to the former.
3. Here you have a list of already built and saved maps, as well as buttons allowing to manage them. A specific map has to be activated (with corresponding button) before names can begin being generated.
4. Here you can configure how you want the names to be generated. Batch size corresponds to the number of generated names when you click on 'Generate Names' and 'Commit' buttons below. Total corresponds to the total number of names you finally need. Other parameters already have been explained above.
5. When you click on this button, random names are generated and populate the list. Previous displayed list is discarded, and nothing is added to the accepted and rejected names lists.
6. When you click on this button, a window is opened and displays the list of accepted names so far.
7. When you click on this button, a window is opened and displays the list of rejected names so far.
8. When you click on this button, checked names in the list are added to accepted names list, and unchecked ones are added to rejected names list. Finally the list is populated with a new batch of random names, which cannot already be in accepted and rejected names lits.
9. The status bar displaying a few counters: the total number of names finally needed, the number of names that have been generated so far (along with the ratio related to total number needed), the remaining number of names to be accepted (along with the ratio related to total number needed), the number of accepted names so far (along with the ratio related to the number of names already generated), the number of rejected names so far (along with the ratio related to the number of names already generated), the time spent so far building maps, and the time spent so far generating names.

There is also an Options screen:

It allows to configure:

• the extension of maps save files.
• the extension of maps string dump files.
• whether maps should be dumped upon generation.
• an eventual comment specifier for samples files.
• whether map generation should skip whitespaces.
• the extension of output files (accepted and rejected names).
• the flag added to file name for rejected names.
• the extension of backup files when accepted and rejected lists are being reset.
• the font of main screen's names list.

In this screen you can also reset lists and counters to eventually get back to initial state of application.

And here is the map creation screen:

Dictionary relates to sample names file.

Finally, here is the credits screen:

Blue items in the list are clickable links, and the link they refer to is displayed as a tooltip.

## Notes

• The generic solution provided can theorically be used on other types than strings. Though, I did not try to, nor do I plan to do it someday. If you want to use/adapt it to another type of sequences, you have to provide corresponding delegates (PartitionFunc<T> and AggregationFunc<T>) for given type.
• The code presented in this article is a shortened version of the one provided in the solution. Nothing has been changed in the core implementation, but code in the solution is (almost) fully documented, at least for the reusable part. Windows Forms project is not documented, though, as it is not the subject of this article.
• I used auto-implemented properties for the code presented in this article, for the sake of simplicity. In downloadable solution, though, I am using private fields to store properties' values.
• Thanks to Phillip Piper [^] for his awesome ObjectListView [^], which proves itself more valuable every day.
• I included two samples files if you do not want to spend time searching for one. They are located in the Samples folder in the root folder of the solution. Though, I did not include the generated maps related to these samples files. You will have to generate the map from the application.

## Possible future improvements

• Being able to provide functions to limit specific characters combinations (for example, discard a result if it contains more than two following consonants, or if it contains specific characters combinations).
• Provide already built maps in the Winforms application, for given names, family names, possibly related to a specific culture.
• Implement a solution to generate random full names (given names + family names), possibly related to a specific culture.
• Implement async versions of GetName and GetNames methods.

## History

• 2016/10/29: Version 1.0.0.0 - First publication

Written By
France
Olivier is currently working as a network administrator in an IT Company near Lyon, France.

He discovered computer development in the early 80's, beginning with Basic programs. Since then he has worked with Visual Basic 6, and later with the .NET platform since 2003.

Now he's using .NET products to develop small applications helping him in his every-day tasks. He prefers C# actually.

 First Prev Next
 Bug: Where is the map file? Andrew Lundgren6-Oct-20 6:59 Andrew Lundgren 6-Oct-20 6:59
 Hi there, this code looks wonderfully implemented -- good comments, unit tests, clean architecture, etc. However, I can't get it to run locally. I downloaded the solution and attempted to run the Windows Form app, but it threw an exception about binding one of the controls. I created a simple Console app to test this out, but it's failing due to not having a "Map" loaded. It looks like it should load these maps from a file with a '.dat' extension, but I can't find any in the solution. I attempted to instantiate a new empty one, but that throws this exception: [^] Where can I find the map to load the chaimap data? Thank you!
 Re: Bug: Where is the map file? Andrew Lundgren6-Oct-20 7:01 Andrew Lundgren 6-Oct-20 7:01
 Re: Bug: Where is the map file? phil.o27-Oct-21 14:46 phil.o 27-Oct-21 14:46
 Re: Bug: Where is the map file? Member 1202788825-Nov-21 22:26 Member 12027888 25-Nov-21 22:26
 Re: Bug: Where is the map file? phil.o26-Nov-21 0:34 phil.o 26-Nov-21 0:34
 Does not work k_smithus12-Sep-17 5:48 k_smithus 12-Sep-17 5:48
 Re: Does not work phil.o12-Sep-17 5:58 phil.o 12-Sep-17 5:58
 My vote of 5 Dr. Jones DK1-Nov-16 22:34 Dr. Jones DK 1-Nov-16 22:34
 Re: My vote of 5 phil.o1-Nov-16 22:52 phil.o 1-Nov-16 22:52
 Phonotactics - a better approach Patrick Baggett1-Nov-16 12:12 Patrick Baggett 1-Nov-16 12:12
 Re: Phonotactics - a better approach phil.o1-Nov-16 12:41 phil.o 1-Nov-16 12:41
 Last Visit: 31-Dec-99 19:00     Last Update: 30-Jan-23 15:18 Refresh 1