下一个完整的程序是一个马尔科夫链算法的实现，该算法由Kernighan 和 Pike 在它们的书 The Practice of Programming 中进行了描述。
马尔科夫链算法根据哪个单词能出现在基础文本中由 n 个前序单词组成的序列之后，来生成伪随机文本。对于本例中的实现，我们假定 n 为 2。
程序的第一部分读取原始文本并创建一个表，该表的键为每两个单词组成的前缀，值为紧跟这个前缀的单词所组成的列表。当这个表构建好后，程序就利用它来生成随机文本，随机文本中每个单词出现在它之前两个单词后的概率与其出现在基础文本中相同两个前序单词后的概率相同。最终，我们会得到一串相对比较随机的文本。例如，以本书的英文原版作为基础文本，那么该程序的输出形如：
"Constructors can also traverse a table constructor, then the parentheses in the following line does the whole file in a field n to store the contents of each function, but to show its only argument. If you want to find the maximum element in an array can return both the maximum value and continues showing the prompt and running the code. The following words are reserved and cannot be used to convert between degrees and radians."
要将由两个单词组成的前缀作为表的键，需要使用空格来连接两个单词：
function prefix(w1, w2)
return w1 .. " " .. w2
end
我们使用字符串 NOWORD（换行符）初始化前缀单词及标记文本的结尾。例如，对于文本 "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 中。如果要像表中的某个前缀所对应的列表中插入一个新单词，可以使用如下函数：
function insert(prefix, value)
local list = statetab[prefix]
if list == nil then
statetab[prefix] = {value}
else
list[#list + 1] = value
end
end
该函数首先检查某前缀是否有了对应的列表，如果没有，则以新值来创建一个新列表；否则，就将新值添加到现有列表的末尾。
为了构造表 statetab，我们使用两个变量 w1，w2 来记录最后读取的两个单词。我们使用 18.1 节中的 allwords 迭代器读取单词，只不过修改了其中 “单词” 的定义以便将可选的诸如用逗号和句号等标点包括在内。对于新读取的每一个单词，把它添加到与 w1-w2 相关联的列表中，然后更新 w1 和 w2。
在构造完表后，程序便开始生成具有 MAXGEN 个单词的文本。首先，程序重新初始化变量 w1 和 w2。然后，对于每个前缀，程序从其对应的单词列表中随机地挑选出一个单词，输出这个单词并更新 w1 和 w2。示例 19.1 和示例 19.2 给出了完整的程序。
示例19.1 马尔科夫链程序的辅助定义
function allwords()
local line = io.read()
local pos = 1
return function()
while line do
local w, e = string.match(line, "%w+[,;.:]?()", pos)
if w then
pos = e
return w
else
line = io.read()
pos = 1
end
end
return nil
end
end
function prefix(w1, w2)
return w1 .. " " .. w2
end
local statetab = {}
function insert(prefix, value)
local list = statetab[prefix]
if list == nil then
statetab[prefix] = {value}
else
list[#list + 1] = value
end
end
示例19.2 马尔科夫链程序
local MAXGEN = 200
local NOWORD = "\n"
--创建表
local w1, w2 = NOWORD, NOWORD
for nextword in allwords() do
insert(prefix(w1, w2), nextword)
w1 = w2
w2 = nextword
end
insert(prefix(w1, w2), NOWORD)
--生成文本
w1 = NOWORD
w2 = NOWORD
for i = 1, MAXGEN do
local list = statetab[prefix(w1, w2)]
local r = math.random(#list)
local nextword = list[r]
if nextword == NOWORD then
return
end
io.write(nextword, " ")
w1 = w2
w2 = nextword
end
19.1 练习
- 练习 19.1：使马尔科夫链算法更加通用，以支持任意长度的前缀单词序列。
由于是任意长度，长度未知，所以所有用到 w1 和 w2 的地方都要换成一个表，其余的部分保持不变即可。
local file = io.open("aseprite.txt", "r")
---@return string|nil
function allwords()
local line = file:read()
local pos = 1
return function()
while line do
local w, e = string.match(line, "(%w+[,;.:]?)()", pos)
if w then
pos = e
return w
else
line = file:read()
pos = 1
end
end
return nil
end
end
---@return string
---@param t table
function prefix(t)
local ret = {}
for _,v in ipairs(t) do
table.insert(ret, v)
table.insert(ret, " ")
end
table.remove(ret)
local pre = table.concat(ret)
return pre
end
local statetab = {}
---@return void
---@param prefix string
---@param value string
function insert(prefix, value)
local list = statetab[prefix]
if list == nil then
statetab[prefix] = {value}
else
list[#list + 1] = value
end
end
local MAXGEN = 200
local NOWORD = "\n"
--创建表
---@return table
---@param n number 输入前序序列的长度
function CreateList(n)
local t = {}
for i = 1, n do
table.insert(t, NOWORD)
end
return t
end
local words = CreateList(3)
for nextword in allwords() do
insert(prefix(words), nextword)
for i = 1, #words - 1 do
words[i] = words[i + 1]
end
words[#words] = nextword
end
insert(prefix(words), NOWORD)
--生成文本
local words = CreateList(3)
for i = 1, MAXGEN do
local list = statetab[prefix(words)]
local r = math.random(#list)
local nextword = list[r]
if nextword == NOWORD then
return
end
io.write(nextword, " ")
for j = 1, #words - 1 do
words[j] = words[j + 1]
end
words[#words] = nextword
end
file:close()
