Python 實作馬可夫鏈演算法：從文字生成隨機文本的完整指南

馬可夫鏈是一種隨機過程模型，根據前一狀態（或前 N 狀態）預測下一狀態的機率分佈。在自然語言處理中，常用於文字生成：分析語料庫中詞彙的轉移機率，再根據機率隨機生成新文本。本文詳細解析 Python 實作的核心邏輯、資料結構設計、關鍵技巧與完整程式碼。

核心概念：N-gram 與狀態轉移

• Prefix（前綴）：固定長度的詞彙序列（本例為 2 個詞，即 Bigram）
• Suffix（後綴）：緊隨前綴之後的下一個詞
• 狀態轉移表：記錄每個前綴對應的所有可能後綴及其出現次數

資料結構設計

# 狀態轉移表：字典
# key: tuple(prefix1, prefix2)  前綴元組
# value: list[suffix1, suffix2, ...]  後綴列表（重複出現代表機率權重）
statetab = {
    ('I', 'am'): ['happy', 'sad', 'happy', 'tired'],
    ('am', 'happy'): ['today', '.'],
    ...
}

關鍵 Python 技巧解析

1. dict.setdefault() — 簡化字典初始化

# 傳統寫法
if (w1, w2) not in statetab:
    statetab[(w1, w2)] = []
statetab[(w1, w2)].append(word)

# 簡化寫法
statetab.setdefault((w1, w2), []).append(word)

setdefault(key, default)：若 key 不存在，設定為 default 並回傳；若存在，直接回傳現有值。一行取代四行判斷邏輯。

2. random.choice() — 加權隨機選取

import random
suffixes = ['happy', 'sad', 'happy', 'tired']
next_word = random.choice(suffixes)  # 'happy' 被選中機率 50%

列表中重複元素天然形成權重，無需額外機率計算。

3. 元組作為字典鍵 — 不可變、可雜湊

prefix = (w1, w2)  # 元組不可變，可作為 dict key
statetab[prefix] = [...]

完整實作程式碼（含詳細註解）

import random
import sys

MAXGEN = 10000      # 最大生成詞數
NONWORD = '\n'      # 特殊標記：句首/句尾邊界

def build_markov_chain(text, prefix_len=2):
    """建立馬可夫鏈狀態轉移表"""
    statetab = {}
    words = text.split()
    
    # 初始化前綴為 NONWORD
    prefix = [NONWORD] * prefix_len
    
    for word in words:
        prefix_tuple = tuple(prefix)
        statetab.setdefault(prefix_tuple, []).append(word)
        # 滑動視窗更新前綴
        prefix.pop(0)
        prefix.append(word)
    
    # 加入結尾標記
    statetab.setdefault(tuple(prefix), []).append(NONWORD)
    return statetab

def generate_text(statetab, prefix_len=2, max_words=MAXGEN):
    """根據馬可夫鏈生成文本"""
    prefix = [NONWORD] * prefix_len
    output = []
    
    for _ in range(max_words):
        prefix_tuple = tuple(prefix)
        suffixes = statetab.get(prefix_tuple, [NONWORD])
        next_word = random.choice(suffixes)
        
        if next_word == NONWORD:
            break
            
        output.append(next_word)
        # 滑動視窗更新前綴
        prefix.pop(0)
        prefix.append(next_word)
    
    return ' '.join(output)

# === 主程式 ===
if __name__ == '__main__':
    # 讀取標準輸入或檔案
    text = sys.stdin.read()
    
    # 建立模型
    chain = build_markov_chain(text)
    
    # 生成文本
    generated = generate_text(chain)
    print(generated)

執行方式與測試

# 建立測試語料 corpus.txt
echo "the cat sat on the mat. the cat ate the rat." > corpus.txt

# 執行生成
python markov.py < corpus.txt
# 可能輸出：the cat sat on the rat. the cat ate the mat.

進階擴展方向

中文文本生成範例（整合 jieba）

import jieba
import random

def build_chain_chinese(text, prefix_len=2):
    words = list(jieba.cut(text))
    statetab = {}
    prefix = ['\n'] * prefix_len
    for word in words:
        pt = tuple(prefix)
        statetab.setdefault(pt, []).append(word)
        prefix.pop(0)
        prefix.append(word)
    statetab.setdefault(tuple(prefix), []).append('\n')
    return statetab

# 使用方式相同
chain = build_chain_chinese("今天天氣很好。今天心情也很好。")
print(generate_text(chain))  # 可能輸出：今天天氣也很好。今天心情很好。

總結

馬可夫鏈文字生成的核心在於狀態轉移表的建立與加權隨機採樣。Python 的 dict.setdefault()、random.choice()、元組鍵值等特性讓實作極為簡潔。理解滑動視窗更新前綴、NONWORD 邊界處理、權重隱含在列表重複中等關鍵細節，即可靈活擴展至高階模型、中文處理、模型持久化等進階應用。