| 10.2 马尔可夫链算法 |
我们第二个例子是马尔可夫链算法的实现，我们的程序以前n(n=2)个单词串为基础随机产生一个文本串。
程序的第一部分读出原文，并且对没两个单词的前缀建立一个表，这个表给出了具有那些前缀的单词的一个顺序。建表完成后，这个程序利用这张表生成一个随机的文本。在此文本中，每个单词都跟随着它的的前两个单词，这两个单词在文本中有相同的概率。这样，我们就产生了一个非常随机，但并不完全随机的文本。例如，当应用这个程序的输出结果会出现“构造器也可以通过表构造器，那么一下几行的插入语对于整个文件来说，不是来存储每个功能的内容，而是来展示它的结构。”如果你想在队列里找到最大元素并返回最大值，接着显示提示和运行代码。下面的单词是保留单词，不能用在度和弧度之间转换。
我们编写一个函数用来将两个单词中间加上空个连接起来：
function prefix (w1, w2)
return w1 .. ' ' .. w2
end
我们用NOWORD（即\n）表示文件的结尾并且初始化前缀单词，例如，下面的文本：
the more we try the more we do
初始化构造的表为：
{
["\n \n"] = {"the"},
["\n the"] = {"more"},
["the more"] = {"we", "we"},
["more we"] = {"try", "do"},
["we try"] = {"the"},
["try the"] = {"more"},
["we do"] = {"\n"},
}
我们使用全局变量statetab来保存这个表，下面我们完成一个插入函数用来在这个statetab中插入新的单词。
function insert (index, value)
if not statetab[index] then
statetab[index] = {value}
else
table.insert(statetab[index], value)
end
end
这个函数中首先检查指定的前缀是否存在，如果不存在则创建一个新的并赋上新值。如果已经存在则调用table.insert将新值插入到列表尾部。
我们使用两个变量w1和w2来保存最后读入的两个单词的值，对于每一个前缀，我们保存紧跟其后的单词的列表。例如上面例子中初始化构造的表。
初始化表之后，下面来看看如何生成一个MAXGEN（=1000）个单词的文本。首先，重新初始化w1和w2，然后对于每一个前缀，在其next单词的列表中随机选择一个，打印此单词并更新w1和w2，完整的代码如下：
-- Markov Chain Program in Lua
function allwords ()
local line = io.read() -- current line
local pos = 1 -- current position in the line
return function () -- iterator function
while line do -- repeat while there are lines
local s, e = string.find(line, "%w+", pos)
if s then -- found a word?
pos = e + 1 -- update next position
return string.sub(line, s, e) -- return the word
else
line = io.read() -- word not found; try next line
pos = 1 -- restart from first position
end
end
return nil -- no more lines: end of traversal
end
end
function prefix (w1, w2)
return w1 .. ' ' .. w2
end
local statetab
function insert (index, value)
if not statetab[index] then
statetab[index] = {n=0}
end
table.insert(statetab[index], value)
end
local N = 2
local MAXGEN = 10000
local NOWORD = "\n"
-- build table
statetab = {}
local w1, w2 = NOWORD, NOWORD
for w in allwords() do
insert(prefix(w1, w2), w)
w1 = w2; w2 = w;
end
insert(prefix(w1, w2), NOWORD)
-- generate text
w1 = NOWORD; w2 = NOWORD -- reinitialize
for i=1,MAXGEN do
local list = statetab[prefix(w1, w2)]
-- choose a random item from list
local r = math.random(table.getn(list))
local nextword = list[r]
if nextword == NOWORD then return end
io.write(nextword, " ")
w1 = w2; w2 = nextword
end