字母级的马尔可夫链与随机文本

Question

我想用一本书里的字母出现频率来生成随机文本，文本保存在一个.txt文件里。这样每个新字符（string.lowercase + ' '）都是根据前一个字符来决定的。

我该怎么用马尔可夫链来实现这个呢？或者说，用27个数组来记录每个字母的条件频率会更简单吗？

Answer 1

如果每个字符只依赖于前一个字符，那么你可以计算所有27^2对字符的概率。

Answer 2

我想用一本书的字母频率来生成随机文本，这本书的内容保存在一个txt文件里。

可以考虑使用 collections.Counter 来统计字母频率，方法是每次读取文本文件中的两个字母。

我该如何使用马尔可夫链来实现这个呢？或者用27个数组来表示每个字母的条件频率会更简单吗？

这两种说法是一样的。马尔可夫链是 你要做的事情，而27个条件频率的数组是 你怎么做的。

下面是一些基于字典的代码，可以帮助你入门：

from collections import defaultdict, Counter
from itertools import ifilter
from random import choice, randrange

def pairwise(iterable):
    it = iter(iterable)
    last = next(it)
    for curr in it:
        yield last, curr
        last = curr

valid = set('abcdefghijklmnopqrstuvwxyz ')

def valid_pair((last, curr)):
    return last in valid and curr in valid

def make_markov(text):
    markov = defaultdict(Counter)
    lowercased = (c.lower() for c in text)
    for p, q in ifilter(valid_pair, pairwise(lowercased)):
        markov[p][q] += 1
    return markov

def genrandom(model, n):
    curr = choice(list(model))
    for i in xrange(n):
        yield curr
        if curr not in model:   # handle case where there is no known successor
            curr = choice(list(model))
        d = model[curr]
        target = randrange(sum(d.values()))
        cumulative = 0
        for curr, cnt in d.items():
            cumulative += cnt
            if cumulative > target:
                break

model = make_markov('The qui_.ck brown fox')
print ''.join(genrandom(model, 20))