コードウォーク - 任意のテキストの生成: マルコフ連鎖アルゴリズム（Generating arbitrary text: a Markov chain algorithm） - 《Goプログラミング言語

// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
/*
Generating random text: a Markov chain algorithm
Based on the program presented in the "Design and Implementation" chapter
of The Practice of Programming (Kernighan and Pike, Addison-Wesley 1999).
See also Computer Recreations, Scientific American 260, 122 - 125 (1989).
A Markov chain algorithm generates text by creating a statistical model of
potential textual suffixes for a given prefix. Consider this text:
    I am not a number! I am a free man!
Our Markov chain algorithm would arrange this text into this set of prefixes
and suffixes, or "chain": (This table assumes a prefix length of two words.)
    Prefix       Suffix
    "" ""        I
    "" I         am
    I am         a
    I am         not
    a free       man!
    am a         free
    am not       a
    a number!    I
    number! I    am
    not a        number!
To generate text using this table we select an initial prefix ("I am", for
example), choose one of the suffixes associated with that prefix at random
with probability determined by the input statistics ("a"),
and then create a new prefix by removing the first word from the prefix
and appending the suffix (making the new prefix is "am a"). Repeat this process
until we can't find any suffixes for the current prefix or we exceed the word
limit. (The word limit is necessary as the chain table may contain cycles.)
Our version of this program reads text from standard input, parsing it into a
Markov chain, and writes generated text to standard output.
The prefix and output lengths can be specified using the -prefix and -words
flags on the command-line.
*/
package main
import (
    "bufio"
    "flag"
    "fmt"
    "io"
    "math/rand"
    "os"
    "strings"
    "time"
)
// Prefix is a Markov chain prefix of one or more words.
type Prefix []string
// String returns the Prefix as a string (for use as a map key).
func (p Prefix) String() string {
    return strings.Join(p, " ")
}
// Shift removes the first word from the Prefix and appends the given word.
func (p Prefix) Shift(word string) {
    copy(p, p[1:])
    p[len(p)-1] = word
}
// Chain contains a map ("chain") of prefixes to a list of suffixes.
// A prefix is a string of prefixLen words joined with spaces.
// A suffix is a single word. A prefix can have multiple suffixes.
type Chain struct {
    chain     map[string][]string
    prefixLen int
}
// NewChain returns a new Chain with prefixes of prefixLen words.
func NewChain(prefixLen int) *Chain {
    return &Chain{make(map[string][]string), prefixLen}
}
// Build reads text from the provided Reader and
// parses it into prefixes and suffixes that are stored in Chain.
func (c *Chain) Build(r io.Reader) {
    br := bufio.NewReader(r)
    p := make(Prefix, c.prefixLen)
    for {
        var s string
        if _, err := fmt.Fscan(br, &s); err != nil {
            break
        }
        key := p.String()
        c.chain[key] = append(c.chain[key], s)
        p.Shift(s)
    }
}
// Generate returns a string of at most n words generated from Chain.
func (c *Chain) Generate(n int) string {
    p := make(Prefix, c.prefixLen)
    var words []string
    for i := 0; i < n; i++ {
        choices := c.chain[p.String()]
        if len(choices) == 0 {
            break
        }
        next := choices[rand.Intn(len(choices))]
        words = append(words, next)
        p.Shift(next)
    }
    return strings.Join(words, " ")
}
func main() {
    // Register command-line flags.
    numWords := flag.Int("words", 100, "maximum number of words to print")
    prefixLen := flag.Int("prefix", 2, "prefix length in words")
    flag.Parse()                     // Parse command-line flags.
    rand.Seed(time.Now().UnixNano()) // Seed the random number generator.
    c := NewChain(*prefixLen)     // Initialize a new Chain.
    c.Build(os.Stdin)             // Build chains from standard input.
    text := c.Generate(*numWords) // Generate text.
    fmt.Println(text)             // Write text to standard output.
}

はじめに

このコードウォークでは、マルコフ連鎖アルゴリズムを使用してランダムなテキストを生成するプログラムについて説明します。パッケージコメントには、アルゴリズムとプログラムの動作が記載されています。続行する前にお読みください。

doc/codewalk/markov.go:6,44

マルコフ連鎖のモデル化

連鎖はプレフィックスとサフィックスで構成されます。各プレフィックスは一定数の単語であり、サフィックスは単一の単語です。プレフィックスには任意の数のサフィックスを持つことができます。このデータをモデル化するために、map[string][]stringを使用します。各マップキーはプレフィックス（string）であり、その値はサフィックスのリスト（文字列のスライス、[]string）です。

ここに、このデータ構造によってモデル化されたパッケージコメントからの例の表があります:

map[string][]string{
    " ":          {"I"},
    " I":         {"am"},
    "I am":       {"a", "not"},
    "a free":     {"man!"},
    "am a":       {"free"},
    "am not":     {"a"},
    "a number!":  {"I"},
    "number! I":  {"am"},
    "not a":      {"number!"},
}

各プレフィックスは複数の単語で構成されていますが、マップにはプレフィックスを単一のstringとして保存します。プレフィックスを[]stringとして保存する方が自然に思えるかもしれませんが、マップのキータイプは等価性を実装する必要があるため（スライスはそうではありません）、これを行うことはできません。

したがって、私たちのコードのほとんどでは、プレフィックスを[]stringとしてモデル化し、文字列をスペースで結合してマップキーを生成します:

Prefix               Map key
[]string{"", ""}     " "
[]string{"", "I"}    " I"
[]string{"I", "am"}  "I am"

doc/codewalk/markov.go:77

Chain構造体

連鎖テーブルの完全な状態は、テーブル自体とプレフィックスの単語の長さで構成されます。Chain構造体がこのデータを保存します。

doc/codewalk/markov.go:76,79

NewChainコンストラクタ関数


 このコンストラクタ関数は厳密には必要ありません。このプログラム全体が単一のパッケージ（`````main`````）内にあるため、エクスポートされたフィールドと非公開フィールドの間に実質的な違いはほとんどありません。新しいChainを構築したいときに、この関数の内容をそのまま書くこともできます。しかし、これらの非公開フィールドを使用することは良いプラクティスです。Chainのメソッドとそのコンストラクタ関数のみがこれらのフィールドにアクセスすべきことを明確に示します。また、`````Chain`````をこのように構造化することで、将来的に独自のパッケージに簡単に移動できるようになります。   
doc/codewalk/markov.go:82,84  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=60&amp;hi=60#mark)   
Prefix型  
 プレフィックスを頻繁に扱うため、具体的な型`````[]string`````を持つ`````Prefix`````型を定義します。名前付き型を定義することで、プレフィックスを`````[]string`````ではなく明示的に扱うことができます。また、Goでは任意の名前付き型（構造体だけでなく）にメソッドを定義できるため、必要に応じて`````Prefix`````に対して動作するメソッドを追加できます。   
doc/codewalk/markov.go:60  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=63&amp;hi=65#mark)   
Stringメソッド  
 `````Prefix`````に定義する最初のメソッドは`````String`````です。これは、スライス要素をスペースで結合することによって`````string`````の表現を返します。このメソッドを使用して、チェインマップで作業する際にキーを生成します。   
doc/codewalk/markov.go:63,65  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=88&amp;hi=100#mark)   
チェインの構築  
 `````Build`````メソッドは、`````io.Reader`````からテキストを読み取り、`````Chain`````に保存されるプレフィックスとサフィックスに解析します。   
 `````io.Reader`````は、標準ライブラリや他のGoコードで広く使用されているインターフェース型です。私たちのコードは、`````fmt.Fscan`````関数を使用して、`````io.Reader`````からスペース区切りの値を読み取ります。   
 `````Build`````メソッドは、`````Reader`````の`````Read`````メソッドが`````io.EOF`````（ファイルの終わり）を返すか、他の読み取りエラーが発生するまで返します。   
doc/codewalk/markov.go:88,100  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=89&amp;hi=89#mark)   
入力のバッファリング  
 この関数は多くの小さな読み取りを行うため、一部の`````Readers`````に対して非効率的です。効率のために、提供された`````io.Reader`````を`````bufio.NewReader`````でラップして、新しい`````io.Reader`````を作成し、バッファリングを提供します。   
doc/codewalk/markov.go:89  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=90&amp;hi=90#mark)   
Prefix変数  
 関数の先頭で、`````Chain`````の`````prefixLen`````フィールドを長さとして使用して、`````Prefix`````スライス`````p`````を作成します。この変数を使用して現在のプレフィックスを保持し、新しい単語に出会うたびにそれを変更します。   
doc/codewalk/markov.go:90  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=92&amp;hi=95#mark)   
単語のスキャン  
 ループ内で、`````Reader`````から`````string`````変数`````s`````に単語を読み取ります。`````fmt.Fscan`````を使用します。`````Fscan`````は各入力値を区切るためにスペースを使用するため、各呼び出しはちょうど1つの単語（句読点を含む）を生成します。これはまさに私たちが必要とするものです。   
 `````Fscan`````は、読み取りエラー（`````io.EOF`````など）に遭遇した場合や、要求された値（この場合は単一の文字列）をスキャンできない場合にエラーを返します。いずれの場合も、スキャンを停止したいので、ループから`````break`````します。   
doc/codewalk/markov.go:92,95  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=96&amp;hi=97#mark)   
チェインにプレフィックスとサフィックスを追加  
 `````s`````に保存された単語は新しいサフィックスです。`````chain`````マップに新しいプレフィックス/サフィックスの組み合わせを追加するために、`````p.String`````でマップキーを計算し、そのキーの下に保存されているスライスにサフィックスを追加します。   
 組み込みの`````append`````関数は、スライスに要素を追加し、必要に応じて新しいストレージを割り当てます。提供されたスライスが`````nil`````の場合、`````append`````は新しいスライスを割り当てます。この動作は、マップのセマンティクスと便利に結びついています。設定されていないキーを取得すると、値の型のゼロ値が返され、`````[]string`````のゼロ値は`````nil`````です。プログラムが新しいプレフィックスに遭遇すると（マップ内で`````nil`````値を生成）、`````append`````は新しいスライスを割り当てます。   
 `````append`````関数とスライス全般についての詳細は、[スライス: 使用法と内部](https://golang.org/doc/articles/slices_usage_and_internals.html)の記事を参照してください。   
doc/codewalk/markov.go:96,97  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=98&amp;hi=98#mark)   
プレフィックスにサフィックスをプッシュ  
 次の単語を読み取る前に、アルゴリズムはプレフィックスから最初の単語を削除し、現在のサフィックスをプレフィックスにプッシュする必要があります。   
 この状態では 
``````bash
p == Prefix{"I", "am"}
s == "not"
`


``````bash
p == Prefix{"am", "not"}
`

この操作はテキスト生成中にも必要であるため、PrefixのShiftというメソッド内にこのスライスの変更を行うコードを置きます。

doc/codewalk/markov.go:98

Shiftメソッド


``````bash
p := Prefix{"I", "am"}
copy(p, p[1:])
// p == Prefix{"am", "am"}
`

次に、提供されたwordをスライスの最後のインデックスに割り当てます:

// suffix == "not"
p[len(p)-1] = suffix
// p == Prefix{"am", "not"}

doc/codewalk/markov.go:68,71

テキストの生成


 `````Generate`````は、条件付きのforループを使用して最大`````n`````単語を生成します。   
doc/codewalk/markov.go:103,116  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=107&amp;hi=110#mark)   
潜在的なサフィックスの取得  
 ループの各反復で、現在のプレフィックスの潜在的なサフィックスのリストを取得します。`````chain`````マップのキー`````p.String()`````にアクセスし、その内容を`````choices`````に割り当てます。   
 `````len(choices)`````がゼロの場合、そのプレフィックスに対する潜在的なサフィックスがないため、ループを抜けます。このテストは、キーがマップに存在しない場合にも機能します。その場合、`````choices`````は`````nil`````になり、`````nil`````スライスの長さはゼロです。   
doc/codewalk/markov.go:107,110  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=111&amp;hi=113#mark)   
ランダムにサフィックスを選択  
 サフィックスを選択するために、`````rand.Intn`````関数を使用します。これは、提供された値まで（ただし含まない）ランダムな整数を返します。`````len(choices)`````を渡すことで、リストの全長に対するランダムなインデックスを取得します。   
 このインデックスを使用して新しいサフィックスを選択し、`````next`````に割り当て、`````words`````スライスに追加します。   
 次に、`````Shift`````の新しいサフィックスをプレフィックスにプッシュします。これは`````Build`````メソッドで行ったのと同様です。   
doc/codewalk/markov.go:111,113  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=115&amp;hi=115#mark)   
生成されたテキストの返却  
 生成されたテキストを文字列として返す前に、`````strings.Join`````関数を使用して`````words`````スライスの要素をスペースで区切って結合します。   
doc/codewalk/markov.go:115  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=119&amp;hi=121#mark)   
コマンドラインフラグ  
 プレフィックスと生成されたテキストの長さを簡単に調整できるように、`````flag`````パッケージを使用してコマンドラインフラグを解析します。   
 `````flag.Int`````へのこれらの呼び出しは、`````flag`````パッケージに新しいフラグを登録します。`````Int`````への引数は、フラグ名、そのデフォルト値、および説明です。`````Int`````関数は、ユーザーが提供した値（またはコマンドラインでフラグが省略された場合はデフォルト値）を含む整数へのポインタを返します。   
doc/codewalk/markov.go:119,121  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=123&amp;hi=124#mark)   
プログラムのセットアップ  
 `````main`````関数は、`````flag.Parse`````でコマンドラインフラグを解析し、`````rand`````パッケージの乱数生成器を現在の時間でシードします。   
 ユーザーが提供したコマンドラインフラグが無効な場合、`````flag.Parse`````関数は情報を含む使用法メッセージを印刷し、プログラムを終了します。   
doc/codewalk/markov.go:123,124  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=126&amp;hi=127#mark)   
新しいChainの作成と構築  
 新しい`````Chain`````を作成するために、`````NewChain`````を`````prefix`````フラグの値で呼び出します。   
 チェインを構築するために、`````Build`````を`````os.Stdin`````（`````io.Reader`````を実装）で呼び出し、標準入力から入力を読み取ります。   
doc/codewalk/markov.go:126,127  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=128&amp;hi=129#mark)   
テキストの生成と印刷  
 最後に、テキストを生成するために、`````Generate`````を`````words`````フラグの値で呼び出し、結果を`````text`````変数に割り当てます。   
 次に、`````fmt.Println`````を呼び出して、テキストを標準出力に書き込み、キャリッジリターンを続けます。   
doc/codewalk/markov.go:128,129  
 [](https://golang.org/doc/codewalk/?fileprint=/doc%2fcodewalk%2fmarkov.go&amp;lo=0&amp;hi=0#mark)   
このプログラムの使用  
 このプログラムを使用するには、まず[go](https://golang.org/cmd/go/)コマンドでビルドします: 
``````bash
$ go build markov.go
`

そして、いくつかの入力テキストをパイプしながら実行します:

$ echo "a man a plan a canal panama" \
    | ./markov -prefix=1
a plan a man a plan a canal panama

ここに、GoディストリビューションのREADMEファイルをソース素材として使用してテキストを生成するトランスクリプトがあります:

$ ./markov -words=10 < $GOROOT/README
This is the source code repository for the Go source
$ ./markov -prefix=1 -words=10 < $GOROOT/README
This is the go directory (the one containing this README).
$ ./markov -prefix=1 -words=10 < $GOROOT/README
This is the variable if you have just untarred a

doc/codewalk/markov.go

読者への課題

Generate関数は、wordsスライスを構築する際に多くの割り当てを行います。課題として、io.Writerを受け取り、Fprintで生成されたテキストを書き込むように修正してください。効率的であるだけでなく、GenerateをBuildに対してより対称的にします。

doc/codewalk/markov.go

•