在《程序设计实践》(英文名《The Practice of Programming》)的书中,第三章分别用C语言,C++,AWK和Perl分别实现了马耳可夫链算法,来通过输入的文本,“随机”的生成一些有用的文本。
这里我使用python
编写一个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import randomimport sysMAXGEN = 10000 NONWORD = '\n' w1 = w2 = NONWORD statetab = {} text = sys.stdin.read() words = text.split() for word in words: statetab.setdefault((w1, w2),[]).append(word) w1, w2 = w2, word statetab.setdefault((w1, w2),[]).append(NONWORD) w1 = w2 = NONWORD for i in xrange(MAXGEN): suf = statetab[(w1,w2)] t = random.choice(suf) if t == NONWORD: break print t w1, w2 = w2, t
说明:
程序使用了字典,字典和散列可不是一个东西,字典是键值对的集合,而散列是一种能够常数阶插入,删除,不过可以用散列来实现字典。
字典的setdefault()方法使得程序少了许多条件判断。
random.choice()可以随机取出一个序列中的元素。
每两个前缀词确定一个后缀。