{"id":214,"date":"2012-05-10T16:47:20","date_gmt":"2012-05-10T16:47:20","guid":{"rendered":"http:\/\/www.silverclaw.net\/?p=214"},"modified":"2012-05-16T08:11:07","modified_gmt":"2012-05-16T08:11:07","slug":"markov-chains-in-asp-net","status":"publish","type":"post","link":"https:\/\/www.silverclaw.net\/?p=214","title":{"rendered":"Markov chains in ASP.NET"},"content":{"rendered":"

My previous article<\/a> covers the concepts behind Markov chains. In this article, we’ll look at how Markov chains can be generated using C# code. You can\u00a0 download the complete source code of this example on the Downloads<\/a> page.<\/p>\n

To start with, the text will need to be sanitized to remove any symbols and punctuation marks that might interfere with the analysis of the text. You can do this using a regular expression, as in the following code:<\/p>\n

Input = Regex.Replace(Input, @\"[^A-Za-z \\.]\", \"\");<\/pre>\n
Regular expressions like this one are covered in Session 10 of my upcoming ASP.NET, C# and Visual Studio Expert Skills course<\/a>.<\/p>\n
You’ll notice that the full-stop characters are left in place. This is because they’ll be used to indicate the end of a chain. For this to work, however, they’ll need to be separated from the words in the text using the following code:<\/p>\n
Input = Input.Replace(\".\", \" . \");<\/pre>\n
You could do more sanitization at this point to remove double-spaces or HTML tags, but this is enough for this example.<\/p>\n
Next the individual words must be extracted from the text and placed in an array. This can be done using the Split<\/em> method:<\/p>\n
string[] Words = Input.Split(' ');<\/pre>\n
Now the individual words have been placed in the Words<\/em> array.<\/p>\n
Next you’ll need to analyze the text to get the probability data needed to create a Markov chain. To do this, you’ll need a class structure to store the probabilities:<\/p>\n
private class MarkovWord\r\n{\r\n\u00a0\u00a0\u00a0 public MarkovWord(string NewWord, int NewInstances)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Word = NewWord;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Instances = NewInstances;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FollowingWords = new List<MarkovWord>();\r\n\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 public string Word;\r\n\u00a0\u00a0\u00a0 public int Instances;\r\n\u00a0\u00a0\u00a0 public double Probability;\r\n\u00a0\u00a0\u00a0 public List<MarkovWord> FollowingWords;\r\n}<\/pre>\n
Now you’ll need to use this class to extract the probabilities from the text. First you’ll need to extract a unique list of words to use as a ‘top level’:<\/p>\n
string[] UniqueWords = Words.Select(UniqueWord => UniqueWord).Distinct().ToArray();<\/pre>\n
This code uses LINQ to extract a unique list of words from the Words<\/em> collection. Using LINQ in this way is covered in Session 10 of my ASP.NET, C# and Visual Studio Essential Skills course<\/a>.<\/p>\n
Now you’ll need some more complex code to extract the probability data from the text. You’ll need to create a new collection of MarkovWord<\/em> objects and use a foreach<\/em> loop to cycle through each of the unique words.<\/p>\n
List<MarkovWord> MarkovData = new List<MarkovWord>();\r\nforeach (string Word in UniqueWords)\r\n{<\/pre>\n
Now you’ll need to create a new MarkovWord<\/em> object for the current word and a collection of MarkovWord<\/em> objects to store each of the words that follows the current word:<\/p>\n
MarkovWord NewWord = new MarkovWord(Word, 1);\r\nList<MarkovWord> FollowingWords = new List<MarkovWord>();<\/pre>\n
Next, you need to loop through every word in the complete text and look for the current word. You can do this with the following for<\/em> loop:<\/p>\n
for (int Counter = 0; Counter < Words.Length - 1; Counter++)\r\n{<\/pre>\n
When you find an instance of the current word, you need to get the word that follows it in the Words<\/em> array and add it to the FollowingWords<\/em> collection. If it already exists, you’ll increase the Instances<\/em> property of the existing object instead of adding a new one:<\/p>\n
if (Words[Counter] == Word)\r\n{\r\n\u00a0\u00a0\u00a0 string FollowingWord = Words[Counter + 1];\r\n\u00a0\u00a0\u00a0 MarkovWord ExistingWord = FollowingWords.SingleOrDefault(FWord => FWord.Word == FollowingWord);\r\n\u00a0\u00a0\u00a0 if (ExistingWord == null) FollowingWords.Add(new MarkovWord(FollowingWord, 1));\r\n\u00a0\u00a0\u00a0 else ExistingWord.Instances++;\r\n}<\/pre>\n
Now it’s time to calculate the probability of each following word. This is easy to do by simply adding up the total number of following words and dividing the number of instances of each following word:<\/p>\n
double TotalFollowingWords = FollowingWords.Sum(FWord => FWord.Instances);\r\nforeach (MarkovWord FollowingWord in FollowingWords)\r\n{\r\n\u00a0\u00a0\u00a0 FollowingWord.Probability = FollowingWord.Instances \/ TotalFollowingWords;\r\n}<\/pre>\n
Now all that’s needed is to add the finished MarkovWord<\/em> object to the MarkovData<\/em> collection:<\/p>\n
NewWord.FollowingWords = FollowingWords;\r\nMarkovData.Add(NewWord);<\/pre>\n
You have now created the complete data structure needed to create a Markov chain.<\/p>\n
To create the Markov chain, you’ll need a Random<\/em> object:<\/p>\n
Random Randomizer = new Random();<\/pre>\n
You’ll use this to randomly select words for the chain.<\/p>\n
Next, you need to select a starting word and create variables to store the random probability and output string:<\/p>\n
MarkovWord CurrentWord = MarkovData[0];\r\ndouble RandomValue;\r\nstring OutputString = CurrentWord.Word;<\/pre>\n
Now you’ll create a while<\/em> loop to cycle until a full stop is found:<\/p>\n
while (CurrentWord.Word != \".\")\r\n{<\/pre>\n
Within the while<\/em> loop, you will need to generate a random value. This will determine which word is selected from the FollowingWords<\/em> collection.<\/p>\n
bool WordPicked = false;\r\nRandomValue = Randomizer.NextDouble();\r\ndouble CurrentProbability = 0;<\/pre>\n
The NextDouble<\/em> method will populate the RandomValue<\/em> variable with a number from 0.0 to 1.0. The WordPicked<\/em> and CurrentProbability<\/em> variables will be used later.<\/p>\n
Next you’ll need to loop through all of the words in the FollowingWords<\/em> collection and use the RandomValue<\/em> to determine which one is selected:<\/p>\n
foreach (MarkovWord FollowingWord in CurrentWord.FollowingWords)\r\n{\r\n\u00a0\u00a0\u00a0 if (!WordPicked)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CurrentProbability += FollowingWord.Probability;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if (CurrentProbability >= RandomValue)\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WordPicked = true;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OutputString += \" \" + FollowingWord.Word;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 CurrentWord = MarkovData.Single(BaseWord => BaseWord.Word == FollowingWord.Word);\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 }\r\n}<\/pre>\n
This works by adding the probability of each following word to CurrentProbability<\/em> and selecting the word if CurrentProbability<\/em> is greater than or equal to RandomValue<\/em>.<\/p>\n
For example, using the following probabilities:
\nand (0.33333)<\/em>
\nfell (0.66666)<\/em><\/p>\n
…the word and<\/strong> will only be selected if RandomValue<\/em> is less than or equal to 0.33333<\/em>.<\/p>\n
Your code is now complete. A Markov chain is generated and placed in the OutputString<\/em> variable. You can download a complete working version of this code on the Downloads<\/a> page.<\/p>\n","protected":false},"excerpt":{"rendered":"
My previous article covers the concepts behind Markov chains. In this article, we’ll look at how Markov chains can be generated using C# code. You can\u00a0 download the complete source code of this example on the Downloads page. To start … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"gallery","meta":[],"categories":[12],"tags":[],"_links":{"self":[{"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts\/214"}],"collection":[{"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=214"}],"version-history":[{"count":10,"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts\/214\/revisions"}],"predecessor-version":[{"id":233,"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts\/214\/revisions\/233"}],"wp:attachment":[{"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}