perl -ane 'push@{$m{$a}},$a=$_ for@F;END{
print$a=$m{$a}[rand@{$m{$a}}]," "for 1..100_000
}' <<<'fish fish for fish.'
Given the King James Bible instead of "fish fish for fish." as input, this program produces output like this:25:13 As the hands upon his disciple; but make great matter wisely in their calamity; 1:14 Sanctify unto the arches thereof unto them: 28:14 Happy is our judges ruled, that believe. 19:36 Thus saith the first being one another's feet.
This leans pretty hard on Perl DWIM; a Python version is many times longer:
import random, sys
model, last, word = {None: []}, None, None
for word in (word for line in sys.stdin for word in line.split()):
model.setdefault(last, []).append(last := word)
sys.stdout.writelines(str(word := random.choice(model.get(word) or words)) + " "
for words in [list(model.keys())] for i in range(100_000))
(If you write code like that at a job, you might get fired. I would reject your pull request.)It's probably worth mentioning:
- Markov-chain states don't have to be words. For text modeling, a common thing to do is to use N-grams (of either words or characters) instead of single words for your states.
- It's good to have some nonzero probability to take a transition that hasn't occurred in the training set; this is especially important if you use a larger universe of states, because each state will occur fewer times in the training set. "Laplacian smoothing" is one way to do this.
- Usually (and in my code examples above) the probability distribution of transitions we take in our text generator is the probability distribution we inferred from the input. Potter's approach of multiplying his next-state-occupancy vector Ms⃗ by a random diagonal matrix R and then taking the index of the highest value in the resulting vector produces somewhat similar results, but they are not the same; for example
sum(random.random() * 0.75 > random.random() * 0.25 for i in range(1_000_000))
is roughly 833000, not roughly 750000. It's 5× as common instead of 3×. But I imagine that it still produces perfectly cromulent text.Interestingly, modern compilers derive from Chomsky's theory of linguistics, which he formulated while working on an AI project in the 01950s in order to demolish the dominant theory of psychology at the time, behaviorism. Behaviorism essentially held that human minds were Markov chains, and Chomsky showed that Markov chains couldn't produce context-free languages.