除了考慮字母出現的機率和在各種長度中各個字母出現的機率，今天我們也把字母的排列順序列入考量。例如，我們看到一個字 m _ s s，我們知道他有很高的機率會是母音，因此，a, e, i, o, u就是我們下一個猜測的目標。

在這裡，我們開發一個Bigram的語言模型。在開始訓練這個模型之前，有幾件事需要注意：(1) 要記得加上開頭標籤 $；(2) 要記得針對Bigram以上的模型設計對應的平滑方法。在這裡我們決定使用 linear interpolation （線性插值法）來smooth高元和低元模型，而插值法中要用到的 \lambda 值我們設為0.75（建議在0.7~0.8之間）。

我們猜格子的順序會從最左邊開始猜，因此最開始會在p($)的條件下猜字母。猜的過程中可能第一個字還沒猜到，後面有些就先被猜到了，等我們終於猜到第一個字母後，我們就找下一個「最左邊還沒有被猜到的字」。

from operator import itemgetter

bigram_counts = defaultdict(Counter) # 這個dict的key是各個字母，value是可能接在這個字母後面之字母的Counter

bigram_inter = defaultdict(list) # 根據interpolation後的機率，將接續在一個字母後面的可能字母照出現機率排序

# 開始儲存Bigram model
for word in training_set:
    this_count = Counter()
    word = '$' + word # 字首加上開頭標籤
    for i, letter in enumerate(word):
        if i+1 != len(word):
            this_count[word[i+1]] += 1
            bigram_counts[letter] += this_count
            this_count = Counter()

set_lambda = 0.75 # 設定interpolation的lambda

# Bigram Interpolated Model: p = lambda*p(w_i|w_(i-1)) + (1-lambda)*p(w_i)
# p(w_i|w_(i-1)) = count(w_i and w_(i-1)) / count(w_(i-1))
# p(w_i) = count(w_i) / sigma(count(w_i))
for key in bigram_counts.keys():
    sigma_count_wi = sum(unigram_counts.values()) # sigma(count(w_i))
    count_wi1 = sum(bigram_counts[key].values()) # count(w_(i-1))

    # 計算p(w_i|w_(i-1))和p(w_i)
    prob_of_letter = {}
    for letter in range(97,123):
        p_wi_wi1 = bigram_counts[key][chr(letter)] / count_wi1 # p(w_i|w_(i-1))
        p_wi = unigram_counts[chr(letter)] / sigma_count_wi # p(w_i)
        prob_of_letter[chr(letter)] = set_lambda*p_wi_wi1 + (1-set_lambda)*p_wi

    # 將接續在一個字母後面的可能字母照出現機率排序
    this_list = []
    for i in range(26):
        this_list.append(sorted(prob_of_letter.items(), key=itemgetter(1), reverse=True)[i][0])
    bigram_inter[key] = this_list
    

def bigram_guesser(mask, guessed, counts=bigram_counts): # add extra default arguments if needed
    """
        實現Bigram Guesser的方法，根據使用了線性插值法的Bigram model，回傳猜測的字母。
    """
    
    mask = ['$'] + mask
    w_i_1 = "" # 找到最左邊非 '_' 的字母 -> w_(i-1)
    # 找w_i_1
    for i in range(len(mask)):
        if mask[i] == '_':
            w_i_1 = mask[i-1]
            break
    copy_bi_model = bigram_inter[w_i_1].copy()
    
    # 將已經猜過的字母去除
    for letter in guessed:
        if letter in copy_bi_model:
            copy_bi_model.remove(letter)

    return copy_bi_model[0]


#hangman(np.random.choice(test_set), bigram_guesser, 26, True)

result = test_guesser(bigram_guesser)
print()
print("平均猜錯次數：", result)

可以觀察到，用了進步版的猜字方法，平均猜錯次數可以下降1~2次。有興趣的人還可以試試看用其他平滑方法調整n-gram model，或者用更高元的語言模型來實作猜字方法。

今天的Jupyter Notebook在這裡。