72 lines
2.3 KiB
Markdown
72 lines
2.3 KiB
Markdown
# markovbot
|
|
|
|
A bot that answers using Markov chains. A Markov chain is a stochastic model
|
|
describing a sequence of events where the probability of each event depends
|
|
only on the state attained in the previous one.
|
|
|
|
This implementation is order-N: each transition is keyed on the previous N
|
|
tokens. Order 1 is maximally inventive and usually incoherent; higher orders
|
|
track the source corpus more closely and diverge less. Order 2 is the default
|
|
compromise.
|
|
|
|
## Install
|
|
|
|
```sh
|
|
go install github.com/zg/markovbot/cmd/markovbot@latest
|
|
```
|
|
|
|
## Use
|
|
|
|
```sh
|
|
# train (incremental — training again extends the model)
|
|
markovbot train -model m.json -order 2 corpus.txt
|
|
|
|
# generate
|
|
markovbot gen -model m.json -n 40
|
|
|
|
# reply, seeded with an incoming message
|
|
markovbot reply -model m.json "what do you think about go"
|
|
```
|
|
|
|
## Library
|
|
|
|
```go
|
|
c, _ := markov.New(2)
|
|
c.TrainAll(lines)
|
|
out, _ := c.Generate(rand.New(rand.NewSource(seed)), 40)
|
|
```
|
|
|
|
## Design notes
|
|
|
|
**Sampling is reproducible.** Successors are drawn in proportion to observed
|
|
frequency, walking a *sorted* key list rather than the map directly. Go
|
|
randomises map iteration order, so sampling the map in place would make
|
|
output vary between runs even with a fixed seed. Given the same seed, this
|
|
chain always produces the same text — which is what makes it testable.
|
|
|
|
**Counts, not repeated lists.** Each prefix stores successor counts, so
|
|
retraining on the same corpus does not grow memory without bound, and
|
|
sampling stays proportional to what was actually observed.
|
|
|
|
**Saves are atomic.** `SaveFile` writes to a temporary file and renames it
|
|
into place, so an interrupted save cannot leave a truncated model where a
|
|
working one used to be. Totals are *derived* on load rather than trusted from
|
|
the file, so a hand-edited model cannot desynchronise counts from their sum.
|
|
|
|
**Sentinels cannot be injected.** Chain boundaries use `\x00`-prefixed
|
|
sentinels and tokenisation strips them, so a corpus containing those strings
|
|
cannot forge a start or end of sample.
|
|
|
|
## Tests
|
|
|
|
Beyond the usual table-driven cases, the suite pins the statistical
|
|
behaviour: training `a b` 300 times and `a c` 100 times must yield P(b|a) ≈
|
|
0.75 over 20,000 draws. Determinism is checked by regenerating from the same
|
|
seed; concurrency safety is checked under `-race` with training and
|
|
generation running simultaneously.
|
|
|
|
```sh
|
|
go test -race ./...
|
|
go test -bench=. ./...
|
|
```
|