2.3 KiB
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
go install github.com/zg/markovbot/cmd/markovbot@latest
Use
# 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
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.
go test -race ./...
go test -bench=. ./...