Simple markov chain generator

chain.py

from __future__ import division
import collections
from StringIO import StringIO
import sys
import random

def analyze(string, k):
    # Maps strings of length k to dictionaries of charcter to frequency counts
    markovchain = collections.defaultdict(lambda: collections.defaultdict(int))

    for i in xrange(len(string)-k):
        substr = string[i:i+k]
        nextchar = string[i+k]

        print "Looking at %r next char %r" % (substr, nextchar)
        markovchain[substr][nextchar] += 1

    # Normalize the counts in each
    for contextstr, chain in markovchain.items():
        # Turn it from a counter dict to a regular dict
        chain = dict(chain)
        total = sum(chain.itervalues())
        print "%r occurred %s times" % (contextstr, total)
        for s in chain.keys():
            chain[s] = chain[s] / total
        markovchain[contextstr] = chain

    # Turn it from a defaultdict back to a regular dict
    return dict(markovchain)

def choose_nextchar(possibilities):
    rvalue = random.random()
    for item,weight in possibilities.iteritems():
        if rvalue < weight:
            return item
        rvalue -= weight
    return item

def generate(markovchain, seed):
    s = seed
    out = sys.stdout
    out.write(s)

    while True:
        nextchar_possibilities = markovchain[s]
        nextchar = choose_nextchar(nextchar_possibilities)
        out.write(nextchar)
        s = s[1:] + nextchar