Lua实现马儿可夫链算法

本文主要是介绍Lua实现马儿可夫链算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

马尔可夫链算法根据哪个单词能出现在基础文本中由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 ragument, 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 wo 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 thenstatetab[prefix] = {value}elselist[#list + 1] = valueend
end

该函数首先检查某前缀是否已经有了对应的列表，如果没有，则以新值来创建一个新列表；否则，就将新值添加到现有列表的末尾。
为了构造表statetab，我们使用两个变量W1和w2来记录最后读取的两个单词。我们使用allwords迭代器读取单词，只不过修改了其中"单词"的定义以便将可选的诸如逗号和句号等标点符号包括在内。对于新读取的每一个单词，把它添加到与w1-w2相关联的列表中，然后更新w1和w2。
在构造完表后，程序便开始生成具有MAXGEN个单词的文本。首先，程序重新初始化变量w1和w2。然后，对于每个前缀，程序从其对应的单词列表中随机地选出一个单词，输出这个单词，并更新W1和w2。如下示例：

示例马儿可夫链的辅助定义

function allwords()local line = io.read()  -- 当前行local pos  = 1			-- 当前行的当前位置return fucntion ()		-- 迭代函数while line do			-- 当还有行时循环local w, e = string.match(line, "(%w[,;.:]?)()",pos)if w then			-- 发现一个单词？pos = e 		-- 更新位置return w  		-- 返回该单词elseline = io.read() -- 没找到单词；尝试下一行pos  = 1		 -- 从第一个位置重新开始endendreturn nil 				-- 没有行了：迭代结束
endfunction prefix (w1,w2)return w1 .. " " .. w2 
endlocal statetab = {}function insert (prefix,value)local list = statetab[prefix]if list == list thenstatetab[prefix] = {value}elselist[#list + 1] = valueend
end

示例：马尔科夫链程序

local MAXGEN = 200
local NOWORD = "\n"-- 创建表
local w1,w2 = NOWORD, NOWORD
for nextword in allwords() doinsert(prefix(w1,w2),nextword)w1 = w2; w2 = nextword;
end
insert(prefix(w1,w2),NOWORD)-- 生成文本
w1 = NOWORD; w2 = NOWORD    -- 重新初始化
for i = 1 , MAXGEN dolocal list = statetab[prefix(w1,w2)]-- 从列表中随机选出一个元素local r = math.random(#list)local nextword = list[r]if nextword == NOWORD then return endio.write(nextword," ")w1 = w2; w2 = nextword
end