萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 實現馬可夫鏈文本生成:從《程序設計實踐》經典範例到可運行代碼

算法原理

馬可夫鏈文本生成:以 前綴雙詞 為狀態,統計語料中每個前綴後接的後綴詞分佈,生成時隨機選取後綴,滾動更新前綴,直到遇到終止符。

核心數據結構


statetab = {
    ('w1', 'w2'): ['next1', 'next2', ...],  # 前綴元組 -> 後綴列表
    ...
}

完整實現代碼


import random
import sys

MAXGEN = 10000
NONWORD = '\n'          # 句邊界標記

w1 = w2 = NONWORD
statetab = {}

# 1. 讀取全量文本並構建狀態表
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)

# 2. 生成文本
w1 = w2 = NONWORD
for _ in range(MAXGEN):
    suffixes = statetab.get((w1, w2), [NONWORD])
    next_word = random.choice(suffixes)
    if next_word is NONWORD:
        break
    print(next_word, end=' ')
    w1, w2 = w2, next_word

關鍵技巧解析

  1. dict.setdefault(key, []).append(val):一行完成「鍵不存在則建空列表、追加值」,極致簡潔。
  2. random.choice(seq):等概率隨機選取後綴,引入隨機性。
  3. NONWORD 哨兵值:標記句首/句尾,避免特殊判斷邏輯。
  4. 記憶體:statetab 鍵為元組(不可變、可哈希),值為列表(可變、可追加)。

擴展:可變前綴長度(N-gram)


from collections import deque, defaultdict

def build_markov(words, prefix_len=2):
    table = defaultdict(list)
    prefix = deque([''] * prefix_len, maxlen=prefix_len)
    for w in words:
        table[tuple(prefix)].append(w)
        prefix.append(w)
    table[tuple(prefix)].append('')  # 終止符
    return table

def generate(table, prefix_len=2, max_words=1000):
    prefix = deque([''] * prefix_len, maxlen=prefix_len)
    for _ in range(max_words):
        suffixes = table.get(tuple(prefix), [''])
        nxt = random.choice(suffixes)
        if not nxt:
            break
        yield nxt
        prefix.append(nxt)

總結

馬可夫鏈文本生成展示了「統計語言模型」雛形:前綴 → 後綴分佈 → 隨機採樣。Python dict.setdefault + random.choice 以極少代碼實現核心邏輯,是學習 NLP 基礎、構建聊天機器人原型的絕佳切入點。

copyright © 萬盛學電腦網 all rights reserved