Use a Markov chain to create a statistical model of a piece of English text. Simulate the Markov chain to generate stylized pseudo-random text.

Perspective. In the 1948 landmark paper A Mathematical Theory of Communication, Claude Shannon founded the field of information theory and revolutionized the telecommunications industry, laying the groundwork for today's Information Age. In this paper, Shannon proposed using a Markov chain to create a statistical model of the sequences of letters in a piece of English text. Markov chains are now widely used in speech recognition, handwriting recognition, information retrieval, data compression, and spam filtering. They also have many scientific computing applications including the genemark algorithm for gene prediction, the Metropolis algorithm for measuring thermodynamical properties, and Google's PageRank algorithm for Web search. For this assignment, we consider a whimsical variant: generating stylized pseudo-random text.

Markov model of natural language. Shannon approximated the statistical structure of a piece of text using a simple mathematical model known as a Markov model. A Markov model of order 0 predicts that each letter in the alphabet occurs with a fixed probability. We can fit a Markov model of order 0 to a specific piece of text by counting the number of occurrences of each letter in that text, and using these frequencies as probabilities. For example, if the input text is "gagggagaggcgagaaa", the Markov model of order 0 predicts that each letter is 'a' with probability 7/17, 'c' with probability 1/17, and 'g' with probability 9/17 because these are the fraction of times each letter occurs. The following sequence of letters is a typical example generated from this model:

g a g g c g a g a a g a g a a g a a a g a g a g a g a a a g a g a a g . . .

We obtain a more refined model by allowing the probability of choosing each successive letter to depend on the preceding letter or letters. A Markov model of order k predicts that each letter occurs with a fixed probability, but that probability can depend on the previous k consecutive letters (k-gram). For example, if the text has 100 occurrences of "th", with 60 occurrences of "the", 25 occurrences of "thi", 10 occurrences of "tha", and 5 occurrences of "tho", the Markov model of order 2 predicts that the next letter following the 2-gram "th" is 'e' with probability 3/5, 'i' with probability 1/4, 'a' with probability 1/10, and 'o' with probability 1/20.

A brute-force solution. Claude Shannon proposed a brute-force scheme to generate text according to a Markov model of order 1:

“ To construct [a Markov model of order 1], for example, one opens a book at random and selects a letter at random on the page. This letter is recorded. The book is then opened to another page and one reads until this letter is encountered. The succeeding letter is then recorded. Turning to another page this second letter is searched for and the succeeding letter recorded, etc. It would be interesting if further approximations could be constructed, but the labor involved becomes enormous at the next stage. ”

Markov model data type. Create an immutable data type MarkovModel to represent a Markov model of order k from a given text string. The data type must implement the following API:

public class MarkovModel
----------------------------------------------------------------------------------------
MarkovModel(String text, int k)      // create a Markov model of order k from given text

   int order()                       // order k of Markov model

   int freq(String kgram)            // number of occurrences of kgram in text
                                     // (throw an exception if kgram is not of length k)

   int freq(String kgram, char c)    // number of times that character c follows kgram
                                     // (throw an exception if kgram is not of length k)

  char rand(String kgram)            // random character following given kgram
                                     // (throw an exception if kgram is not of length k
                                     // or if no such kgram)

For technical reasons that will become apparent later, treat the input text as a circular string: the last character is considered to precede the first character. For example, if k = 2 and the text is the 17-character string "gagggagaggcgagaaa", then the salient features of the Markov model are captured in the table below:

               frequency of   probability that
                next char       next char is 
kgram   freq    a   c   g        a    c    g
----------------------------------------------
 aa      2      1   0   1       1/2   0   1/2  
 ag      5      3   0   2       3/5   0   2/5  
 cg      1      1   0   0        1    0    0
 ga      5      1   0   4       1/5   0   4/5  
 gc      1      0   0   1        0    0    1  
 gg      3      1   1   1       1/3  1/3  1/3  
----------------------------------------------
        17      7   1   9

To implement the data type, create a symbol table, where the key is a string k-gram and the value is an integer array of next character frequencies. You can assume that the input text is a sequence of characters over the ASCII alphabet so that all char values are between 0 and 127.

Text generation client. Write a client program TextGenerator that takes two command-line integers k and T, reads the input text from standard input, builds a Markov model of order k from the input text, and prints out T characters by simulating a trajectory through the corresponding Markov chain (as described below).

% more input17.txt
gagggagaggcgagaaa

% java TextGenerator 2 11 < input17.txt 
gaggcgagaag

% java TextGenerator 2 11 < input17.txt 
gaaaaaaagag

A Markov chain is a stochastic process where the state change depends on only the current state. For text generation, the current state is a k-gram (initially, the first k characters in the input text). The next character is selected at random, using the probabilities from the Markov model. For example, if the current state is "ga" in the Markov model of order 2 discussed above, then the next character is 'a' with probability 1/5 and 'g' with probability 4/5. The next state in the Markov chain is obtained by appending the new character to the end of the k-gram and discarding the first character. A trajectory through the Markov chain is a sequence of such states. Below is a possible trajectory consisting of 9 transitions.

trajectory:          ga  -->  ag  -->  gg  -->  gc  -->  cg  -->  ga  -->  ag  -->  ga  -->  aa  -->  ag
probability for a:       1/5      3/5      1/3       0        1       1/5      3/5      1/5      1/3
probability for c:        0        0       1/3       0        0        0        0        0       1/3
probability for g:       4/5      2/5      1/3       1        0       4/5      2/5      4/5      1/3

To generate random text from a Markov model of order k, set the initial state to the first k characters of the input text and print out these k characters. Then, simulate a trajectory through the Markov chain by performing T − k transitions, printing out the random character selected at each step. For example, if k = 2 and T = 11, the following is a possible trajectory leading to the output gaggcgagaag.

trajectory:          ga  -->  ag  -->  gg  -->  gc  -->  cg  -->  ga  -->  ag  -->  ga  -->  aa  -->  ag
output:              ga        g        g        c        g        a        g        a        a        g

Amusement. Once you get the program working, you will find that the random text generated looks more and more like the original text as you increase the order of the model, as illustrated in the examples below. There are many more apparent pearls of wisdom in the full texts on the Web. As you can see, there are limitless opportunities for amusement here. Try your model on some of your own text, or find something interesting on the Web. You need not limit yourself to the English language.

Deliverables. Submit MarkovModel.java, TextGenerator.java, and readme.txt. Also, include two of the most entertaining language-modeling fragments that you discover in your readme.txt.

Extra credit 1. Imagine you receive a message where some of characters have been corrupted by noise. We represent unknown characters by the ~ symbol (we assume we don't use ~ in our messages). Add a method replaceUnknown to MarkovModel.java that decodes a noisy message by replacing each ~ with the best character given our order k Markov model:

String replaceUnknown(String corrupted)  // replace unknown characters with most probable characters

%  java FixCorrupted 4 "it w~s th~ bes~ of tim~s, i~ was ~he wo~st of~times." < wiki_100k.txt 
Noisy    : it w~s th~ bes~ of tim~s, i~ was ~he wo~st of~times.
Fixed    : it was the best of times, it was the worst of times.

String [] replaceNbest(String corrupted, int nbest) // return the nbest most probable 
                                                    // versions of a corrupted message

% java FixCorruptedNbest 4 5 "it was the best of ti~e~, it was t~~ worst of times." < wiki_100k.txt 
Noisy    : it was the best of ti~e~, it was t~~ worst of times.
Nbest 0  : it was the best of times, it was the worst of times.
Nbest 1  : it was the best of tibet, it was the worst of times.
Nbest 2  : it was the best of times, it was two worst of times.
Nbest 3  : it was the best of tiger, it was the worst of times.
Nbest 4  : it was the best of tiles, it was the worst of times.

% java FixCorruptedNbest 5 5 "it wa~~t~~~b~~t~o~~t~m~s~ ~t~~as~t~~~~ors~~~~ ti~~~." < wiki_100k.txt 
Noisy   : it wa~~t~~~b~~t~o~~t~m~s~ ~t~~as~t~~~~ors~~~~ ti~~~.
Nbest 0 : it was the best of times, it was the worst of times.
Nbest 1 : it was the best of times, it was the worships title.
Nbest 2 : it was the best of times, it was the worsenic times.
Nbest 3 : it was the best of times, it was the horse of times.
Nbest 4 : it was the best of times, it was the worsenic title.

	[Enter DUKE SENIOR, AMIENS, and two or three Lords,
	like foresters]

DUKE SENIOR	Now, my co-mates and brothers in exile,
	Hath not old custom made this life more sweet
	Than that of painted pomp? Are not these woods
	More free from peril than the envious court?
	Here feel we but the penalty of Adam,
	The seasons' difference, as the icy fang
	And churlish chiding of the winter's wind,
	Which, when it bites and blows upon my body,
	Even till I shrink with cold, I smile and say
	'This is no flattery: these are counsellors
	That feelingly persuade me what I am.'
	Sweet are the uses of adversity,
	Which, like the toad, ugly and venomous,
	Wears yet a precious jewel in his head;
	And this our life exempt from public haunt
	Finds tongues in trees, books in the running brooks,
	Sermons in stones and good in every thing.
	I would not change it.

AMIENS	Happy is your grace,
	That can translate the stubbornness of fortune
	Into so quiet and so sweet a style.

DUKE SENIOR	Come, shall we go and kill us venison?
	And yet it irks me the poor dappled fools,
	Being native burghers of this desert city,
	Should in their own confines with forked heads
	Have their round haunches gored.

DUKE SENIOR	Now, my co-mates and thus bolden'd, man, how now, monsieur Jaques,
	Unclaim'd of his absence, as the holly!
	Though in the slightest for the fashion of his absence, as the only wear.

TOUCHSTONE	I care not for meed!
	This I must woo yours: your request than your father: the time,
	That ever love I broke
	my sword upon some kind of men
	Then, heigh-ho! sing, heigh-ho! sing, heigh-ho! sing, heigh-ho! unto the needless stream;
	'Poor deer,' quoth he,
	'Call me not so keen,
	Because thou the creeping hours of the sun,
	As man's feasts and women merely players:
	Thus we may rest ourselves and neglect the cottage, pasture?

	[Exit]

	[Enter DUKE FREDERICK	Can in his time in my heartily,
	And have me go with your fortune
	In all this fruit
	Till than bear
	the arm's end: I will through
	Cleanse the uses of the way to look you.
	Know you not, master,
	Sighing like upon a stone another down his bravery is not so with his effigies with my food:
	To speak my mind, and inquisition
	And unregarded age in corners throat,
	He will come hither:
	He dies that hath engender'd:
	And you to
	the bed untreasured of the brutish sting it.