...

Codewalk: 生成任意文本:一个马尔可夫链算法

弹出代码
代码位置 左侧右侧 代码宽度 70% 文件路径 显示隐藏
引言
这段代码漫步描述了一个使用马尔可夫链算法生成任意文本的程序。包注释则描述了 该算法以及此程序的操作。请在继续学习前阅读它。
doc/codewalk/markov.go:48,83
模拟马尔可夫链
一个链由一个前缀和一个后缀构成。每一个前缀都是几个单词的一个集合, 而一个后缀就是一个单词。一个前缀可拥有任意数量的后缀。为了模拟这些数据, 我们需要使用一个 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, 并将字符串连同空格一起加入到其中来生成映射键:
前缀                 映射键

[]string{"", ""}     " "
[]string{"", "I"}    " I"
[]string{"I", "am"}  "I am"
doc/codewalk/markov.go:126
Chain 结构体
该链表的完整状态由其自身以及前缀的单词数构成。Chain 结构体 则存储了这些数据。
doc/codewalk/markov.go:125,128
NewChain 构造函数
Chain 结构体拥有两个未导出字段(它们以小写字符开头), 因此我们编写了用 make 初始化 chain 映射并设置 prefixLen 字段的构造函数 NewChain

该构造函数在这种只有一个包(main)的程序中并不是十分必要的, 在可导出的和未导出的字段之间只有一点儿实际的区别。当我们想要构造一个新的 Chain 时,我们可以简单地将该函数的内容直接写出来。 不过使用这些未导出字段是一种好的习惯,它清晰地表明了只有 Chain 的方法及其构造函数才能访问这些字段。此外,像这样构造 Chain 也就意味着我们在以后能够很容易地将它变成它自己的包。
doc/codewalk/markov.go:133,135
Prefix 类型
由于我们会经常用到前缀,因此我们定义了一个实际类型为 []stringPrefix 类型。定义一个清晰的已命名类型能够让我们在使用前缀时更加明确, 而不仅仅是一个 []string。此外,在Go中我们可以为任何已命名的类型 定义方法(而不只是结构体),因此只要我们需要,就能够为 Prefix 添加方法。
doc/codewalk/markov.go:101
String 方法
我们为 Prefix 定义的第一个方法是 String。 它通过将切片元素连同空格一起加入到字符串中来返回一个 Prefixstring 类型的表示。我们将使用此方法来生成链映射的键。
doc/codewalk/markov.go:106,108
构建链
Build 方法从一个 io.Reader 中读取文本并将它解析为存储在 Chain 中的前缀和后缀。

io.Reader 是一个在标准库和其它 Go 代码中广泛使用的接口。我们的代码使用 fmt.Fscan 函数,它从一个 io.Reader 中读取由空格分隔的值。

一旦 ReaderRead 方法返回 io.EOF (文件结束符)或产生一些其它的读取错误时,Build 方法就会返回。
doc/codewalk/markov.go:141,153
缓存输入
该函数可进行一些小的读取,这对于一些 Reader 来说是低效的。 为了效率,我们可以用 bufio.NewReader 来对 io.Reader 进行包装,以此创建一个提供缓存的新 io.Reader
doc/codewalk/markov.go:142
Prefix 变量
在此函数的顶部,我们创建了一个 Prefix 切片 p,并使用 ChainprefixLen 字段作为其长度。我们会使用此变量来保存当前前缀, 并在我们遇到的每一个新单词时改变它。
doc/codewalk/markov.go:143
扫描单词
在我们的循环中,我们用 fmt.FscanReader 将单词读取至 string 类型的变量 s 中。由于 Fscan 使用空格来分隔每一个输入的值,因此每一次调用都只会产生一个单词(包括标点符号), 那正是我们所需要的。

如果 Fscan 遇到了一个读取错误(比如 io.EOF) 或无法扫描到所需要的值(在我们的例子中,就是一个单词的字符串),那么它就会返回一个错误。 无论出现哪种情况,我们都只需停止扫描,用 break 跳出循环即可。
doc/codewalk/markov.go:145,148
将前缀和后缀添加到链中
存储在 s 中的单词为新的后缀。我们通过 p.String 计算出 chain 的映射键来将新的前缀/后缀组合添加到该映射中, 并将该后缀追加到存储在该键下的该切片中。

内建函数 append 用于将元素追加到一个切片后面,并在必要时分配新的存储。 当提供的切片为 nil 时,append 会分配一个新的切片。 这种行为对我们的映射语义来说十分方便:检索一个未设置的键时会返回该值类型的零值, 而 []string 类型的零值为 nil。当我们的程序遇到一个新的前缀时 (在该映射中产生一个 nil 值),append 就会分配一个新的切片。

更多有关 append 函数与普通切片的信息见《切片:用法和本质》一文。
doc/codewalk/markov.go:149,150
将后缀转为前缀
在读取下一个单词之前,我们的算法需要我们从前缀中去掉第一个单词,并将当前后缀移到前缀后面。

在此状态下
p == Prefix{"I", "am"}
s == "not" 
p 的新值将为
p == Prefix{"am", "not"}
此操作过程还需要生成文本,因此我们用 Prefix 的名为 Shift 的方法来完成该切片的改变。
doc/codewalk/markov.go:151
Shift 方法
Shift 方法使用内建函数 copy 来将 p 的最后 len(p)-1 个元素复制到该切片的开头,其实也就是将下标为1的元素移到左边 (如果你考虑将0作为最左边的下标的话)。
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:113,116
生成文本
Generate 方法类似于 Build,但它并不是从一个 Reader 中读取单词并将它们存储到一个映射中,而是从该映射中读取单词, 并将它们追加到一个切片(words)后面。

Generate 使用一个有条件的for循环来产生 n 个单词。
doc/codewalk/markov.go:158,171
获取潜在的后缀
随着该循环的每一次迭代,我们为当前前缀检索出了一个潜在的后缀列表。我们访问 chain 映射的 p.String 键,并将其内容赋予 choices

len(choices) 为零,也就是当该前缀没有的潜在后缀时, 我们就中断并跳出该循环。若该键并不存在于该映射中,此测试也能正常工作: 在这种情况下,choices 会是 nil,而 nil 切片的长度为零。
doc/codewalk/markov.go:162,165
随机选择一个后缀
为了选择一个后缀,我们需要使用 rand.Intn 函数。它返回一个不超过(也不包含)给定值的整数。将 len(choices) 传递给它,我们就能得到一个随机的,不超过该列表全长的下标。

我们使用该下标来挑选我们新的后缀,将它赋予 next 并将它追加到 words 切片之后。

接着,我们用 Shift 将新后缀转为前缀,就像我们在 Build 方法中做的那样。
doc/codewalk/markov.go:166,168
返回生成的文本
在将生成的文本作为字符串返回前,我们使用了 strings.Join 方法来将 words 切片的元素加到一起,并用空格分隔。
doc/codewalk/markov.go:170
命令行标记
为了让调整前缀及生成文本长度变得容易,我们使用 flag 包来解析命令行标记。

这些对 flag.Int 的调用会使用 flag 包寄存新的标记。 Int 的实参分别为标记名、默认值以及对它的描述。Int 函数返回指向一个整数的指针,该证书将包含用户提供的值(若该标记在命令行中省略,则为默认值)。
doc/codewalk/markov.go:174,176
程序准备
main 函数首先用 flag.Parse 来解析命令行标记, 并以当前时间作为 rand 包中随机数生成器的种子。

如果用户提供的命令行标记无效,flag.Parse 函数就会打印出其用法信息并结束该程序。
doc/codewalk/markov.go:178,179
创建并构建一个新的 Chain
为了创建新的 Chain,我们以 prefix 标记的值调用了 NewChain

为了构建该链,我们以 os.Stdin(它实现了 io.Reader)调用了 Build,它将从标准输入中读取其输入。
doc/codewalk/markov.go:181,182
生成并打印文本
最后,为了生成文本,我们以 words 标记的值调用了 Generate, 并将其结果赋予变量 text

接着我们调用 fmt.Println 来将文本写入到标准输出,后面跟着个回车。
doc/codewalk/markov.go:183,184
使用此程序
要使用此程序,首先就要用go命令来构建它:
$ 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