markov text
An n-gram Markov chain trained on this site's own prose — raise the order and watch it go from noise to fluent to plagiarism.
- " "62.5%
- "l"13.9%
- "n"11.1%
- "b"4.2%
- "u"4.2%
- "s"2.8%
- "v"1.4%
the model
A Markov chain assumes the next thing depends only on the last few things, and nothing before that. Fix a window of tokens and the whole model is one conditional distribution,
estimated by the crudest possible method: count. Every window of tokens in the source is a context, every token that followed one is tallied, and generating means walking that table and drawing from the counts. There is no training, no optimisation and no parameters beyond the counts themselves. The panel underneath the output shows the live distribution — the context the chain is sitting on, every token that ever followed it, and which one was drawn.
what the order buys
At order 1 a character model knows only the current letter, and produces pronounceable noise: the letter frequencies are right and nothing else is. By order 3 words appear, most of them real. By order 5 or 6 the clauses scan and the punctuation lands in sensible places. Nothing was added between those settings except memory — the model never learns what a word is, it just conditions on enough characters that word boundaries survive by themselves.
Switching to word tokens jumps several rungs at once, because the hard part — spelling — is now free. Word order 2 reads like someone skimming the site and paraphrasing badly, which is a fair description of what it is doing.
and what it costs
Keep raising the order and the output gets better right up to the point where it stops being the model’s own. The highlight in the output marks the longest run that appears verbatim in the source, and the counter reports its length. On this site’s demo prose, measured across nine seeds, the median longest run grows from 8 characters at order 1 to 32 at order 6, 115 at order 10 and 189 at order 12. In word mode it goes from 41 characters to 514 by order 4 — whole paragraphs, reproduced exactly.
That is not a flaw in the implementation, it is what a high-order n-gram model is. Push the order far enough and almost every context appears exactly once in the source, so there is only ever one continuation and the chain has no choice but to replay what it read. The interesting band is narrow, and it sits exactly where the model has enough memory to be fluent and not so much that it is quoting.
Switch to the posts to watch that band narrow. They are about a fifteenth the size of the demo prose, so their contexts run out sooner and memorisation arrives earlier: at character order 6 the median run is 86 characters against 32 on the larger corpus, and word order 2 already copies 340 characters at a stretch. More data is what buys the right to a longer memory.
the ancestor
Andrey Markov introduced these chains to extend the limit theorems of probability to sequences whose terms depend on each other, and the first thing he applied them to was text. In January 1913 he presented an analysis of the first twenty thousand letters of Pushkin’s Eugene Onegin, worked through by hand with each letter classified only as vowel or consonant — 43% vowels to 57% consonants, and the pairs counted one by one. The connection to language was made explicit by Claude Shannon in 1948, who generated letter and word approximations to English of exactly this kind to illustrate the redundancy of a source.
n-gram models of this shape were the state of the art in language modelling for decades, and the tension on this page never went away. It is the same one that shows up now as memorisation in far larger models, for the same underlying reason: a model with enough capacity relative to its data will reproduce the data. Everything since has been about generalising from context rather than counting it. The regex visualizer builds the non-probabilistic cousin of this machine: a finite automaton with the same fixed, finite memory and no counts at all.
view source
import { useEffect, useMemo, useRef, useState } from 'react';
export interface Corpus {
id: string;
label: string;
text: string;
}
interface Props {
corpora: Corpus[];
}
type Mode = 'char' | 'word';
// A context key must never be decoded back into tokens. In character mode a
// token can itself be a space, so joining with ' ' and splitting on ' ' does
// not round-trip -- ['a', ' ', 'b'] encodes to "a b" and comes back as four
// tokens. Keys use a separator no token can contain, and generation carries
// the context as an array so nothing ever parses a key back.
const SEP = '\u0000';
const keyOf = (toks: string[]) => toks.join(SEP);
const tokenise = (text: string, mode: Mode): string[] =>
mode === 'word' ? text.split(/\s+/).filter(Boolean) : [...text];
const detokenise = (toks: string[], mode: Mode): string =>
mode === 'word' ? toks.join(' ') : toks.join('');
interface Entry {
total: number;
next: Map<string, number>;
}
// Built over a circular corpus, so every context has at least one successor
// and a walk never dead-ends into a spliced restart. A splice would be a seam
// whose n-grams never appeared in the source, which would quietly break the
// one property this whole model guarantees. The single wrap-around transition
// is one join in tens of thousands.
function buildTable(tokens: string[], order: number): Map<string, Entry> {
const table = new Map<string, Entry>();
const n = tokens.length;
if (n === 0 || order < 1) return table;
const ctx: string[] = [];
for (let k = 0; k < order; k++) ctx.push(tokens[k % n]);
for (let i = 0; i < n; i++) {
const k = keyOf(ctx);
const nxt = tokens[(i + order) % n];
let e = table.get(k);
if (!e) {
e = { total: 0, next: new Map() };
table.set(k, e);
}
e.total++;
e.next.set(nxt, (e.next.get(nxt) || 0) + 1);
ctx.shift();
ctx.push(nxt);
}
return table;
}
// Deterministic, so a seed reproduces a generation exactly -- which is what
// makes the output checkable rather than merely plausible.
function mulberry32(a: number) {
return function () {
a |= 0;
a = (a + 0x6d2b79f5) | 0;
let t = Math.imul(a ^ (a >>> 15), 1 | a);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
function sampleFrom(entry: Entry, rnd: () => number): string {
let r = rnd() * entry.total;
for (const [tok, c] of entry.next) {
r -= c;
if (r < 0) return tok;
}
// only reachable through floating-point drift on the final bucket
let last = '';
for (const tok of entry.next.keys()) last = tok;
return last;
}
interface Step {
context: string[];
choices: [string, number][];
picked: string;
}
function generate(
tokens: string[],
order: number,
table: Map<string, Entry>,
count: number,
seed: number,
): { out: string[]; steps: Step[] } {
const rnd = mulberry32(seed);
const n = tokens.length;
const out: string[] = [];
const steps: Step[] = [];
if (n === 0 || table.size === 0) return { out, steps };
const at = Math.floor(rnd() * n);
const ctx: string[] = [];
for (let k = 0; k < order; k++) ctx.push(tokens[(at + k) % n]);
out.push(...ctx);
for (let i = 0; i < count; i++) {
const e = table.get(keyOf(ctx));
if (!e) break; // unreachable with a circular table
const picked = sampleFrom(e, rnd);
// the last few steps are kept so the panel can show the machine working
if (i >= count - 40) {
const choices = [...e.next.entries()].sort((a, b) => b[1] - a[1]);
steps.push({ context: [...ctx], choices, picked });
}
out.push(picked);
ctx.shift();
ctx.push(picked);
}
return { out, steps };
}
// Longest stretch of the output that appears verbatim in the source, and
// where it sits, so it can be highlighted in place rather than only counted.
//
// Seed and extend: the source is indexed once by short k-grams, then every
// seed match is grown outward one character at a time. The obvious
// alternative -- binary search on run length, slicing the source at every
// position for each probe -- allocates tens of megabytes on a corpus this
// size. Survivable in node, not on a phone.
const SEED_LEN = 6;
function buildIndex(src: string): Map<string, number[]> {
const index = new Map<string, number[]>();
for (let i = 0; i + SEED_LEN <= src.length; i++) {
const g = src.slice(i, i + SEED_LEN);
const at = index.get(g);
if (at) at.push(i);
else index.set(g, [i]);
}
return index;
}
function longestVerbatim(
out: string,
src: string,
index: Map<string, number[]>,
): { len: number; start: number } {
let best = 0;
let bestStart = -1;
for (let i = 0; i + SEED_LEN <= out.length; i++) {
const positions = index.get(out.slice(i, i + SEED_LEN));
if (!positions) continue;
for (const p of positions) {
let l = SEED_LEN;
while (
i + l < out.length &&
p + l < src.length &&
out[i + l] === src[p + l]
) {
l++;
}
if (l > best) {
best = l;
bestStart = i;
}
}
}
if (best > 0) return { len: best, start: bestStart };
// Runs shorter than one seed. In natural text a match of two or three
// characters turns up almost immediately, so this stays cheap.
for (let k = SEED_LEN - 1; k >= 1; k--) {
for (let i = 0; i + k <= out.length; i++) {
if (src.includes(out.slice(i, i + k))) return { len: k, start: i };
}
}
return { len: 0, start: -1 };
}
const MAX_ORDER = { char: 12, word: 5 } as const;
const AMOUNT = { char: 700, word: 130 } as const;
export default function MarkovText({ corpora }: Props) {
const [corpusId, setCorpusId] = useState(corpora[0]?.id ?? '');
const [custom, setCustom] = useState('');
const [mode, setMode] = useState<Mode>('char');
const [order, setOrder] = useState(4);
const [seed, setSeed] = useState(1);
const [showCustom, setShowCustom] = useState(false);
const source = useMemo(() => {
if (corpusId === 'custom') return custom;
return corpora.find((c) => c.id === corpusId)?.text ?? '';
}, [corpusId, custom, corpora]);
const tokens = useMemo(() => tokenise(source, mode), [source, mode]);
const table = useMemo(() => buildTable(tokens, order), [tokens, order]);
const result = useMemo(
() => generate(tokens, order, table, AMOUNT[mode], seed),
[tokens, order, table, mode, seed],
);
const outText = useMemo(() => detokenise(result.out, mode), [result, mode]);
// Indexing the source is the expensive half, so it is memoised on the source
// alone and survives every change of order, seed and mode.
const index = useMemo(() => buildIndex(source), [source]);
const { len: runLen, start: runStart } = useMemo(
() => longestVerbatim(outText, source, index),
[outText, source, index],
);
const runEnd = runStart >= 0 ? runStart + runLen : -1;
const maxOrder = MAX_ORDER[mode];
useEffect(() => {
setOrder((o) => Math.min(o, MAX_ORDER[mode]));
}, [mode]);
const lastStep = result.steps[result.steps.length - 1];
const uniqueTokens = useMemo(() => new Set(tokens).size, [tokens]);
const copiedPct = outText.length
? Math.round((runLen / outText.length) * 100)
: 0;
const textareaRef = useRef<HTMLTextAreaElement | null>(null);
useEffect(() => {
if (showCustom) textareaRef.current?.focus();
}, [showCustom]);
return (
<div className="markov">
<div className="controls">
<div className="group">
<span className="group-label">corpus</span>
{corpora.map((c) => (
<button
key={c.id}
type="button"
className={corpusId === c.id ? 'active' : ''}
onClick={() => {
setCorpusId(c.id);
setShowCustom(false);
}}
>
{c.label}
</button>
))}
<button
type="button"
className={corpusId === 'custom' ? 'active' : ''}
onClick={() => {
setCorpusId('custom');
setShowCustom(true);
}}
>
your own
</button>
</div>
</div>
{showCustom && (
<div className="custom">
<textarea
ref={textareaRef}
value={custom}
spellCheck={false}
placeholder="Paste some text — a few paragraphs is enough to see the effect, and more is better."
onChange={(e) => setCustom(e.target.value)}
aria-label="your own corpus"
/>
</div>
)}
<div className="controls">
<div className="group">
<span className="group-label">tokens</span>
{(['char', 'word'] as Mode[]).map((m) => (
<button
key={m}
type="button"
className={mode === m ? 'active' : ''}
onClick={() => setMode(m)}
>
{m === 'char' ? 'characters' : 'words'}
</button>
))}
</div>
<label className="orderctl">
<span className="group-label">order</span>
<input
type="range"
min={1}
max={maxOrder}
step={1}
value={order}
onChange={(e) => setOrder(Number(e.target.value))}
/>
<span className="ordernum">{order}</span>
</label>
<button type="button" onClick={() => setSeed((s) => s + 1)}>
regenerate
</button>
</div>
<div className="output">
{source.length === 0 ? (
<span className="empty">
Nothing to learn from yet — paste some text above.
</span>
) : runStart >= 0 ? (
<>
{outText.slice(0, runStart)}
<mark title={`${runLen} characters copied verbatim`}>
{outText.slice(runStart, runEnd)}
</mark>
{outText.slice(runEnd)}
</>
) : (
outText
)}
</div>
<div className="stats">
<span>
source <strong>{source.length.toLocaleString()}</strong> chars,{' '}
<strong>{uniqueTokens.toLocaleString()}</strong> distinct{' '}
{mode === 'char' ? 'characters' : 'words'}
</span>
<span>
<strong>{table.size.toLocaleString()}</strong> contexts
</span>
<span className={copiedPct >= 40 ? 'warn' : undefined}>
longest verbatim run <strong>{runLen}</strong> chars
{outText.length > 0 && <> ({copiedPct}% of the output)</>}
</span>
</div>
{lastStep && (
<div className="stepper">
<div className="steplabel">
<span className="group-label">last choice</span>
<span className="ctx">
after {JSON.stringify(detokenise(lastStep.context, mode))}
</span>
</div>
<ul className="choices">
{lastStep.choices.slice(0, 8).map(([tok, count]) => {
const total = lastStep.choices.reduce((s, c) => s + c[1], 0);
const pct = (count / total) * 100;
return (
<li
key={tok}
className={tok === lastStep.picked ? 'picked' : ''}
>
<span className="tok">{JSON.stringify(tok)}</span>
<span className="bar">
<span style={{ width: `${pct}%` }} />
</span>
<span className="pct">{pct.toFixed(1)}%</span>
</li>
);
})}
{lastStep.choices.length > 8 && (
<li className="more">and {lastStep.choices.length - 8} more</li>
)}
</ul>
</div>
)}
<style>{`
.markov {
border: 1px solid #2a2d31;
background: #0e1113;
}
.markov .controls {
display: flex;
flex-wrap: wrap;
align-items: center;
gap: 0.75rem;
padding: 0.75rem 1rem 0;
}
.markov .group {
display: flex;
align-items: center;
gap: 0.4rem;
flex-wrap: wrap;
}
.markov .group-label {
color: var(--muted);
font-size: 0.75rem;
text-transform: uppercase;
letter-spacing: 0.04em;
}
.markov button {
font-family: inherit;
font-size: 0.75rem;
color: #8a8f98;
background: rgba(0, 0, 0, 0.4);
border: 1px solid #2a2d31;
padding: 0.25rem 0.6rem;
cursor: pointer;
}
.markov button:hover {
color: #e6e6e6;
}
.markov button.active {
color: #0b0d0f;
background: var(--accent);
border-color: var(--accent);
}
.markov .orderctl {
display: flex;
align-items: center;
gap: 0.5rem;
flex: 1 1 12rem;
min-width: 0;
}
.markov .orderctl input[type='range'] {
flex: 1;
min-width: 0;
accent-color: var(--accent);
}
.markov .ordernum {
color: #e6e6e6;
font-size: 0.75rem;
min-width: 2ch;
text-align: right;
}
.markov .custom {
padding: 0.75rem 1rem 0;
}
.markov textarea {
width: 100%;
height: 7rem;
font-family: inherit;
font-size: 0.75rem;
line-height: 1.5;
color: #e6e6e6;
background: #0b0d0f;
border: 1px solid #2a2d31;
padding: 0.5rem;
resize: vertical;
}
.markov .output {
margin: 0.9rem 1rem 0;
padding: 0.75rem;
border: 1px solid #2a2d31;
background: #0b0d0f;
color: #e6e6e6;
font-size: 0.78rem;
line-height: 1.65;
white-space: pre-wrap;
word-break: break-word;
min-height: 7rem;
max-height: 18rem;
overflow-y: auto;
}
.markov .output mark {
background: rgba(124, 242, 156, 0.18);
color: var(--accent);
border-bottom: 1px solid var(--accent);
}
.markov .empty {
color: var(--muted);
}
.markov .stats {
display: flex;
flex-wrap: wrap;
gap: 0.35rem 1.1rem;
padding: 0.6rem 1rem 0;
color: var(--muted);
font-size: 0.72rem;
}
.markov .stats strong {
color: #e6e6e6;
font-weight: normal;
}
.markov .stats .warn strong {
color: var(--accent);
}
.markov .stepper {
padding: 0.75rem 1rem 1rem;
}
.markov .steplabel {
display: flex;
flex-wrap: wrap;
align-items: baseline;
gap: 0.5rem;
}
.markov .ctx {
color: #e6e6e6;
font-size: 0.72rem;
word-break: break-all;
}
.markov .choices {
list-style: none;
margin: 0.5rem 0 0;
padding: 0;
font-size: 0.72rem;
color: var(--muted);
}
.markov .choices li {
display: flex;
align-items: center;
gap: 0.5rem;
padding: 0.1rem 0;
}
.markov .choices .tok {
min-width: 6ch;
max-width: 12ch;
overflow: hidden;
text-overflow: ellipsis;
white-space: nowrap;
}
.markov .choices .bar {
flex: 1;
height: 6px;
background: #1a1d21;
min-width: 0;
}
.markov .choices .bar span {
display: block;
height: 100%;
background: #2f6b45;
}
.markov .choices li.picked .tok,
.markov .choices li.picked .pct {
color: var(--accent);
}
.markov .choices li.picked .bar span {
background: var(--accent);
}
.markov .choices .pct {
min-width: 5ch;
text-align: right;
}
.markov .choices .more {
color: #6d727a;
}
`}</style>
</div>
);
}