Lua版马尔科夫链算法文本生成器

    Lua程序设计第10章最后一节给出了一个利用马尔科夫链算法实现文本生成器的完整实例，第一次遇到这个算法有种不明觉厉的感觉，通过上网学习发现，这个算法不但实用并且原理很简单，当然这是排除了对算法本身数学推理方面的深究。（既然已经站在了巨人的肩膀上，那就让我多呆一会儿。）废话不多说，直接上代码。

-- read input line and split into words for return

function returnWords ()

local line = io.read()
local pos = 1

return function ()

while line do

local _start , _end = string.find(line , "%w+" , pos)

if(_start) then

pos = _end + 1
return string.sub(line , _start , _end)

else

line = io.read()
pos = 1

end
end

return nil

end
end

--generate a string in this style "w1 w2" (note: there is a blank between w1 and
--w2)

function genpairs(w1 , w2)

return (w1.." "..w2)

end

stattable = {} --a global var which stands for the vocabulary table

--insert (key ,values) in stattable

function insert(index , value)

if not stattable[index] then

stattable[index] = {value}
else

table.insert(stattable[index] , value)

end
end

--build stattable

function init()

local placeholers1 = "#"
local placeholers2 = "#"

for value in returnWords() do

key = genpairs(placeholers1 , placeholers2)

insert(key , value)

placeholers1 = placeholers2
placeholers2 = value

end

insert(genpairs(placeholers1 , placeholers2) , "#")
end

--return num of elements of a table

function getn(table)

local MAXNUM = 100
local count = 0

for num = 1 , MAXNUM do

if table[num] ~= nil then

count = count + 1

else

break;

end
end

return count

end

--generate text

local MAXWORDS = 100
local word1 = "#"
local word2 = "#"

init()

for i = 1 , MAXWORDS do

local textunit = stattable[genpairs(word1 , word2)]
local num = getn(textunit)

local xx = math.random(num)

local textword = textunit[xx]

if "#" ~= textword then

io.write(textword , " ")
word1 = word2
word2 = textword

else

io.write("\n")
break

end
end

我会一边按照程序实际的执行流程一边讲解算法的原理，程序第102行是此脚本真正执行的开始，首先执行init函数，init函数负责生成马尔科夫链的词汇表，这个词汇表就是通常所说的前缀后缀表。马尔科夫链算法会根据指定前缀随机地选择一个后缀用于生成随机文本。这里我们的前缀长度设置为2，算法已经指出前缀的长度对于算法的执行无影响，但是文本生成的随机性和质量和后缀的数目是紧密相连的。init函数首先定义两个占位符（受Boost库的影响），当给定一段文本，第一个单词作为后缀的对应前缀是“# #”，接着程序利用Lua的泛型for返回用户输入文本的每个单词，即词汇表键值对中的值，通过genpairs函数生成词汇表的键，通过insert函数将键值对插入词汇表。insert函数很简单，函数的输入有两个，一个是键，一个是值。如果词汇表中还没有输入的键，就生成一个键值对，如果已经存在输入的键，那么将输入的值插入到该键所对应的值列表的尾端。genpairs返回形式为“w1空格w2”的键，不多介绍。init函数会以“链式”的方式进行：用前两个单词作键，读入的单词作值，完成词汇表插入后，用上次作为键的第二个单词和上次读入的单词组成新键，新读入的单词作为值进行词汇表的插入操作，如此链式般的进行下去，直到输入文本解析完毕。
    有了词汇表后，生成随机文本就一马平川了，我们按照下面的步骤生成随机文本，直到遇到自定义的结束符“#”。
   
    设置w1和w2为文本的前两个词
    Loop:
        用w1空格w2查词汇表，随机地选择一个后缀作为输出文本，记为w3
        如果w3是“#”
            退出循环        
        w1 = w2 , w2 = w3                                                                                    
    这样就完成了利用马尔科夫链算法根据输入文本，按照其统计规律生成一个可读的新文本的所有步骤。
    测试如下：

    执行程序输出的上面一行是用户输入的文本，下面一行则是程序自动生成的随机文本。