markov.py

#

ngrams and Markov chains 

from collections import Counter
import random
#

Find ngrams from a given list 

def find_ngrams(seq, n):
#

Given a list seq returns a list of ngrams where each element is an n-tuple.

Example:
>>> seq = [1, 2, 1, 3, 1, 2, 7]
>>> find_ngrams(seq, 2)
[(1, 2), (2, 1), (1, 3), (3, 1), (1, 2), (2, 7)]
>>> find_ngrams(seq, 3)
[(1, 2, 1), (2, 1, 3), (1, 3, 1), (3, 1, 2), (1, 2, 7)] 

    ngrams = []
#

Iterate over seq in n-sized slices each converted to an n-tuple and appended to ngrams.

    for i in range(len(seq) - n + 1):
        new_tuple = tuple(seq[i:i+n])
        ngrams.append(new_tuple)
    return ngrams
#

Create Markov model from a given list 


    

  

  

  

    

      

        #
      

      
Given a list seq returns a Markov model of the given order
as a dictionary. The keys are order-sized tuples. The value for each
key is a list of elements in seq that immediately follow
occurances of the key in the seq.


Example:

>>> seq = [1, 2, 1, 3, 1, 2, 7]

>>> markov_model(seq, 1)

{(2,): [1, 7], (3,): [1], (1,): [2, 3, 2]}

>>> markov_model(seq, 2)

{(1, 2): [1, 7], (1, 3): [1], (3, 1): [2], (2, 1): [3]}  

    

    

      
def markov_model(seq, order):

    

  

  

  

    

      

        #
      

      
First use find_ngrams to slice seq appropriately.

    

    

      
    ngrams = find_ngrams(seq, order+1)
    markov = {}

    

  

  

  

    

      

        #
      

      
For each ngram in ngrams (where n = order + 1) the first
(n - 1) elements are used as the key and the last
element is appended to the list of possible
continuations.

    

    

      
    for ngram in ngrams:
        try:
            markov[ngram[:-1]].append(ngram[-1])
        except KeyError:
            markov[ngram[:-1]] = [ngram[-1]]
    return markov

    

  

  

  

    

      

        #
      

      
 Generate Markov chain 

    

    

      

    

  

  

  

    

      

        #
      

      
Given a list seq returns a Markov chain of
the given order with a maximum length of the integer max_length.
In this case, the function assumes that seq is
a list of words, tries to begin the chain with a capitalized word and
end the chain with a terminal punctions ('.', '!', '?').

    

    

      
def markov_chain(seq, order, max_length=50):

    

  

  

  

    

      

        #
      

      
    

    

      
    markov = markov_model(seq, order)

    

  

  

  

    

      

        #
      

      
Start chain with an ngram (n = order) that begins with
an uppercase letter, if possible.
If there are no ngrams that begin with an uppercase letter, start with
any random ngram.

    

    

      
    startkeys = [key for key in markov if key[0][0].isupper()]
    if len(startkeys) == 0:
        startkeys = list(markov.keys())
    key = random.choice(startkeys)

    

  

  

  

    

      

        #
      

      
Markov chain is a list beginning with the start key.

    

    

      
    chain = list(key)

    

  

  

  

    

      

        #
      

      
while loop to generate markov chain.

    

    

      
    while True:

    

  

  

  

    

      

        #
      

      
Choose a random continuation from the elements of
the value for the current key.

    

    

      
        new = random.choice(markov[key])
        chain.append(new)

    

  

  

  

    

      

        #
      

      
break if the new element is the end of a sentence

    

    

      
        if new[-1] in ['.', '!', '?']:
            break

    

  

  

  

    

      

        #
      

      
break if the length of chain is max_length or greater.

    

    

      
        if len(chain) >= max_length:
            break

    

  

  

  

    

      

        #
      

      
Concatenate new element to key and use the appropriate slice
of the resulting tuple as the new key.

    

    

      
        key = (key + (new,))
        key = key[1:]
    return " ".join(chain)

    

  

  

  

    

      

        #
      

      
Assign a multiline string

    

    

      
sonnet = '''From fairest creatures we desire increase,
That thereby beauty's rose might never die,
But as the riper should by time decease,
His tender heir might bear his memory:
But thou contracted to thine own bright eyes,
Feed'st thy light's flame with self-substantial fuel,
Making a famine where abundance lies,
Thy self thy foe, to thy sweet self too cruel:
Thou that art now the world's fresh ornament,
And only herald to the gaudy spring,
Within thine own bud buriest thy content,
And tender churl mak'st waste in niggarding:
Pity the world, or else this glutton be,
To eat the world's due, by the grave and thee.'''

    

  

  

  

    

      

        #
      

      
Open the file 'sonnets.txt' for reading and read the contents.
(You will need to download sonnets.txt to the same directory as this code.)

    

    

      
sonnets = open('sonnets.txt', 'r').read()

    

  

  

  

    

      

        #
      

      
The split() method splits a string into a list of substrings separated
by white space.

Example:

>>> my_string = 'I am Sam'

>>> my_string.split()

['I', 'am', 'Sam']

Try substituting sonnets for sonnet.

    

    

      
text = sonnet.split()

    

  

  

  

    

      

        #
      

      
Check output of find_ngrams

    

    

      
ngrams = find_ngrams(text, 2)
print(ngrams)

    

  

  

  

    

      

        #
      

      
Check output of markov_model

    

    

      
markov = markov_model(text, 1)
print(markov)

    

  

  

  

    

      

        #
      

      
Print out the fist 10 keys of the markov model dictionary

    

    

      
for key in list(markov)[:10]:
    print(key, markov[key])

    

  

  

  

    

      

        #
      

      
Print the n-order markov_chain generated from text. Try using
different values for n.

    

    

      
n = 1
print(markov_chain(text, n))