?首先看一下來自Wolfram的定義
??? 馬爾可夫鏈?zhǔn)请S機(jī)變量{X_t}的集合（t貫穿0,1,...），給定當(dāng)前的狀態(tài)，未來與過去條件獨立。
Wikipedia的定義更清楚一點兒
??? ...馬爾可夫鏈?zhǔn)蔷哂旭R爾可夫性質(zhì)的隨機(jī)過程...[這意味著]狀態(tài)改變是概率性的，未來的狀態(tài)僅僅依賴當(dāng)前的狀態(tài)。
馬爾可夫鏈具有多種用途，現(xiàn)在讓我看一下如何用它生產(chǎn)看起來像模像樣的胡言亂語。
算法如下,
- ??? 找一個作為語料庫的文本，語料庫用于選擇接下來的轉(zhuǎn)換。
- ??? 從文本中兩個連續(xù)的單詞開始，最后的兩個單詞構(gòu)成當(dāng)前狀態(tài)。
- ??? 生成下一個單詞的過程就是馬爾可夫轉(zhuǎn)換。為了生成下一個單詞，首先查看語料庫，查找這兩個單詞之后跟著的單詞。從它們中隨機(jī)選擇一個。
- ??? 重復(fù)2，直到生成的文本達(dá)到需要的大小。
代碼如下
?
import random
class Markov(object):
def __init__(self, open_file):
self.cache = {}
self.open_file = open_file
self.words = self.file_to_words()
self.word_size = len(self.words)
self.database()
def file_to_words(self):
self.open_file.seek(0)
data = self.open_file.read()
words = data.split()
return words
def triples(self):
""" Generates triples from the given data string. So if our string were
"What a lovely day", we'd generate (What, a, lovely) and then
(a, lovely, day).
"""
if len(self.words) < 3:
return
for i in range(len(self.words) - 2):
yield (self.words[i], self.words[i+1], self.words[i+2])
def database(self):
for w1, w2, w3 in self.triples():
key = (w1, w2)
if key in self.cache:
self.cache[key].append(w3)
else:
self.cache[key] = [w3]
def generate_markov_text(self, size=25):
seed = random.randint(0, self.word_size-3)
seed_word, next_word = self.words[seed], self.words[seed+1]
w1, w2 = seed_word, next_word
gen_words = []
for i in xrange(size):
gen_words.append(w1)
w1, w2 = w2, random.choice(self.cache[(w1, w2)])
gen_words.append(w2)
return ' '.join(gen_words)
為了看到一個示例結(jié)果，我們從古騰堡計劃中拿了沃德豪斯的《My man jeeves》作為文本，示例結(jié)果如下。
?
In [1]: file_ = open('/home/shabda/jeeves.txt')
In [2]: import markovgen
In [3]: markov = markovgen.Markov(file_)
In [4]: markov.generate_markov_text()
Out[4]: 'Can you put a few years of your twin-brother Alfred,
who was apt to rally round a bit. I should strongly advocate
the blue with milk'
[如果想執(zhí)行這個例子，請下載jeeves.txt和markovgen.py
馬爾可夫算法怎樣呢？
- ??? 最后兩個單詞是當(dāng)前狀態(tài)。
- ??? 接下來的單詞僅僅依賴最后兩個單詞，也就是當(dāng)前狀態(tài)。
- ??? 接下來的單詞是從語料庫的統(tǒng)計模型中隨機(jī)選擇的。
這是一個示例文本。
這個文本對應(yīng)的語料庫像這樣，
?
{('The', 'quick'): ['brown'],
('brown', 'fox'): ['jumps', 'who', 'who'],
('fox', 'jumps'): ['over'],
('fox', 'who'): ['is', 'is'],
('is', 'slow'): ['jumps'],
('jumps', 'over'): ['the', 'the'],
('over', 'the'): ['brown', 'brown'],
('quick', 'brown'): ['fox'],
('slow', 'jumps'): ['over'],
('the', 'brown'): ['fox', 'fox'],
('who', 'is'): ['slow', 'dead.']}
現(xiàn)在如果我們從"brown fox"開始，接下來的單詞可以是"jumps"或者"who"。如果我們選擇"jumps"，然后當(dāng)前的狀態(tài)就變成了"fox jumps"，再接下的單詞就是"over"，之后依此類推。
提示
- ??? 我們選擇的文本越大，每次轉(zhuǎn)換的選擇更多，生成的文本更好看。
- ??? 狀態(tài)可以設(shè)置為依賴一個單詞、兩個單詞或者任意數(shù)量的單詞。隨著每個狀態(tài)的單詞數(shù)的增加，生成的文本更不隨機(jī)。
- ??? 不要去掉標(biāo)點符號等。它們會使語料庫更具代表性，隨機(jī)文本更好看。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
