用 Lua 编程：10.2 - Lua 编程语言

第一版是为 Lua 5.0 编写的。虽然在很大程度上仍然适用于后续版本，但有一些差异。
第四版针对 Lua 5.3，可在亚马逊和其他书店购买。
购买本书，您还可以帮助支持 Lua 项目。

10.2 – 马尔可夫链算法

我们的第二个示例是马尔可夫链算法的实现。该程序生成随机文本，基于n 个前一个单词在基本文本中可能跟随的单词。对于此实现，我们将使用n=2。

程序的第一部分读取基本文本，并构建一个表，对于每个两个单词的前缀，给出在文本中跟随该前缀的单词列表。构建表后，程序使用该表生成随机文本，其中每个单词都以与基本文本相同的概率跟随前两个单词。结果是，我们得到的文本非常接近随机，但又不完全随机。例如，当应用于本书时，程序的输出有如下片段：“构造函数还可以遍历一个表构造函数，然后下一行中的括号将整个文件存储在一个字段 n 中，以存储每个函数的内容，但只显示其唯一参数。如果您想找到一个数组中的最大元素，可以同时返回最大值，并继续显示提示并运行代码。以下单词是保留字，不能用于在度数和弧度之间转换。”

我们将用两个单词用空格连接起来对每个前缀进行编码

    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 中。要在该表的某个前缀列表中插入一个新单词，我们使用以下函数

    function insert (index, value)
      if not statetab[index] then
        statetab[index] = {value}
      else
        table.insert(statetab[index], value)
      end
    end

它首先检查该前缀是否已经有一个列表；如果没有，它将使用新值创建一个新列表。否则，它将使用预定义函数 table.insert 在现有列表的末尾插入新值。

要构建 statetab 表，我们保留两个变量 w1 和 w2，其中包含最后读取的两个单词。对于每个前缀，我们保留一个列表，其中包含所有紧随其后的单词。

构建表后，程序开始生成包含 MAXGEN 个单词的文本。首先，它重新初始化变量 w1 和 w2。然后，对于每个前缀，它从有效后续单词列表中随机选择一个后续单词，打印该单词，并更新 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