Divide your program up into several functions, each of which has a single task to accomplish. Follow the design guidelines demonstrated in the previous homework assignment:
Representing the Markov Chain
The states in your Markov chain will be words. Use a dictionary to represent the Markov chain, with each unique word as a separate key. The value associated with each key represents the full set of transitions away from that word. The value is a list of all the words that followed the key in the source text. For example, say our source text is:
The quick brown fox jumps over the brown log and trips over the brown log and lands on its face.
Then here is a selection of key-value pairs for the dictionary representing the Markov chain trained on this text:
chain['The'] = ['quick']chain['quick'] = ['brown']chain['brown'] = ['fox', 'log', 'log']chain['fox'] = ['jumps']chain['and'] = ['trips', 'lands']chain['over'] = ['the', 'the']chain['the'] = ['brown', 'brown']chain['on'] = ['its']chain['its'] = ['face.']
This is only a selection of the key-value pairs for this Markov chain; as stated above, this dictionary would actually have one key for each unique word in the sentence (except the last word, if that one is unique, since it has no successors).
Notice that we don't explicitly represent transition probabilities here. Instead, to transition out of a state, we will just pick a random entry from the list of possible next states; states may be repeated in this list (like “log” in the list for “brown”) and thereby be more likely to be chosen.
Notice also that the value associated with each key is always a list, even if that list contains only one item. This is important to make your code clean.
Training the Markov Chain
The states in your Markov chain will be all the “words” in the file. A “word”, for our purposes, is just a sequence of non-whitespace characters, separated from other words by one or more whitespace characters. (Whitespace characters are spaces, newlines, tabs, etc.) Conveniently enough, there is a string method that gives you a list of all the words (as we just defined them) in a given string. You may have to do some additional work to make sure that your list of words doesn't contain any empty strings; sometimes those can crop up.
(Notice that in the example dictionary above, capitalization and punctuation were included in words. So "The" and "the" are considered different words, as would be "face." and "face" and "Face". This is intentional; it adds to the quality of the sentences you generate. So make sure that you don't remove capitalization or strip punctuation!)
So, once you've got this list of words, step through it one-by-one and build the transition lists. When adding a transition (say, from word A to word B) to the dictionary, you must first check if the key (A) is already in the dictionary. If so, you simply append B to the list already defined for that key. If not, though, you need to add the key to the dictionary, and associate it with a new list. (What should the contents of that list be?)
You'll probably need to refer to the documentation of Python dictionary methods for this task. Remember that the method has_key() is defined for dictionaries (so is the operator in, which does the same thing); this is precisely what you need in order to decide what to do.
Choosing Starting Places
Before we can start bouncing around the Markov chain, we need to know where to start. This start state will be the first word of our sentence. Naturally, we need to choose one of the states whose word is capitalized. To make this choice easy, you will first generate a list of all the keys that begin with a capital letter. We'll call these “start words”.
The following code snippet prints out all the keys in the dictionary called “chain”; you may find it helpful to construct a similar for-loop:
for key in chain.iterkeys():
print key
Generating Sentences
To generate a sentence from the Markov chain, we first pick a random start word, then pick the next word by choosing randomly from the list associated with that start word. Then we pick the next word after that by choosing from the list associated with the current word. We keep doing this until we reach an “end word” — one whose last character is ., ?, or !. At this point, we can construct a single string by joining together, in order, all the states that we visited.
Note that the example text files I gave you have all the quotation marks, etc. stripped from them, so that this simple rule for identifying end words will work. If you'd like to use other text samples (which you should! It's fun!), you'll either need to manually or automatically strip out the quotation marks, etc., or build a more sophisticated function for testing whether a given word is an end word.
Python has a module called random that you should use to make these random selections. Check out the documentation of the random module. In particular, the functions random.randrange() and random.sample() might be useful. Remember that you need to have the line import random at the top of your source code in order to have access to the functions defined in that module.
