Lua 編程：10.2 - Lua 程式語言

第一版是針對 Lua 5.0 編寫的。儘管在很大程度上仍然適用於後續版本，但仍有一些區別。
第四版針對 Lua 5.3，可在 Amazon 和其他書店購買。
購買本書，您還可以幫助支持 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