この最初のバージョンは Lua 5.0 向けに書かれました。後続のバージョンでもまだ関連性は高いですが、違いがいくつかあります。
4 番目のバージョンは Lua 5.3 を対象としており、Amazon などの書店で購入できます。
書籍を購入することで、Lua プロジェクトの支援にも役立ちます。

	プログラミング inLua
	パート I. この言語 第 10 章. 完全な例

10.2 – マルコフ連鎖アルゴリズム

2 番目の例はマルコフ連鎖アルゴリズムの実装です。本プログラムは、基本テキストに前の n 個の語のシーケンスに続く語に基づき、ランダムなテキストを生成します。この実装では、n=2 を使用します。

プログラムの最初の部分は基本テキストを読み取り、2 つの語のプレフィックスごとに、テキスト内のそのプレフィックスに続く語のリストを持つテーブルを作成します。テーブルを作成後、プログラムはこのテーブルを使用してランダムなテキストを生成します。このランダムなテキストの各単語は、基本テキストと同じ確率で前の 2 つの単語に従います。結果として、とてもランダムではありませんが、ある程度のランダム性のあるテキストが得られます。たとえば、この本に適用すると、プログラムの出力は「コンストラクタはテーブルコンストラクタをトラバースすることもできます。次の行の括弧はフィールドn内のファイル全体を示し、各関数の内容を格納しますが、その唯一の引数のみを表示します。配列内の最大要素を見つけたい場合は、最大値を返して、プロンプトを表示し続けることもできます。コードを実行しています。次の単語は予約されており、度単位とラジアン単位との変換に使用することはできません。」のようになります。

各プレフィックスは中間に空白を含め 2 つの単語を連結することでコード化します

    function prefix (w1, w2)
      return w1 .. ' ' .. w2
    end

    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

statetab テーブルを作成するために、2 つの変数 w1 と w2 を保持し、最後に読み取られた 2 つの単語を含めます。各プレフィックスについて、それに続くすべての単語のリストを保持します。

テーブルを作成後、プログラムは 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

Copyright © 2003–2004 Roberto Ierusalimschy. All rights reserved.