Procedural Blog Posts with Markov Chains

I’m sick of blog posts written by LLMs. Let’s go back to the good old days, when content was procedurally generated by real algorithms. From now on, I’m writing all my blog posts using Markov chains like a 1980s Usenet bot (specifically, this one). But first I’ve got to figure out how.

With an algorithm description from Wikipedia and a tentative grasp on the Rust programming language, let’s get started.

How It Works

The MVS¹ algorithm I’m recreating crawls a body of source text and extracts trigrams – groups of three sequential words. For each unique bigram of two starting words, a list of possible third words is built.

For example, you might get a trigram Dogs are {good | great | fluffy}.

Any of the third words could reasonably follow the first two – we know that because each combination appeared at least once in the text. This allows MVS to generate vaguely natural language by:

1. Starting with one trigram² and choosing the third word at random.
2. Finding a trigram that matches the last two words and choosing another third word at random.
3. Repeating until you run out of matching trigrams.

Sounds simple enough.

The Code

Data Structures

First, let’s think about how to represent bigrams and trigrams in code.

A trigram maps unique two-word pairs to sets of possible third words. Fundamentally, that sounds like a hash map with string tuples as keys and hash sets as values. Storing word choices in a set rather than a vector means that common word combinations from the text have the same chance of being randomly selected as uncommon combinations since they can only appear once, which is faithful to the original MVS description.

My initial design looked like this:

/// A pair of starting words
pub type Bigram = (String, String);

/// Possible third words
pub type Choices = HashSet<String>;

/// A mapping of bigrams to associated choices
pub type Trigrams = HashMap<Bigram, Choices>;

I discovered later on that it was important to 1) track which bigrams could be used to start posts, and 2) implement some trigram methods, so I ended up encapsulating both into simple structs:

/// A pair of starting words
pub type Bigram = (String, String);

/// Possible third words and metadata
#[derive(Debug)]
pub struct BigramData {
    choices: HashSet<String>,
    at_start: bool,
}

/// A mapping of bigrams to associated data
#[derive(Debug)]
pub struct Trigrams {
    map: HashMap<Bigram, BigramData>,
}

Now that I had a way to store trigrams, the next step was generating them from text.

Text to Trigrams

To convert a block of text to trigrams, we can iterate over every word, creating entries into a hashmap for each bigram word pair and inserting word choices into the associated hash set.

impl Trigrams {
    pub fn new() -> Self {
        Self { map: HashMap::new() }
    }

    pub fn from_str(text: &str) -> Self {
        let mut model = Trigrams::new();
        let words = text.split_whitespace().collect::<Vec<&str>>();

        for i in 0..words.len() - 2 {
            model
                .map
                // Find or insert the bigram in the hash map
                .entry((words[i].to_string(), words[i + 1].to_string()))
                .or_insert_with(|| BigramData {
                    at_start: i == 0,
                    choices: HashSet::new(),
                })
                // Store the new word choice
                .choices
                .insert(words[i + 2].to_string());
        }

        model
    }
}

If you were working with huge datasets, you’d want a more memory efficient streaming approach that only keeps three words in memory at a time, but eagerly collecting a vector of words from an in-memory string will be fine for my needs.

Running this with a simple sentence input returns three trigrams, as expected:

Trigrams::from_str("I am a Markov chain");

/*
1. I am {a}
2. am a {Markov}
3. a Markov {chain}
*/

There’s not much you could do with these trigrams since each only provides one choice, but with a larger input text you’d start to see the potential for more flexible outputs.

Now that we can turn input text into trigrams, it’s time to start turning trigrams into new output text.

Generating Text

Following the algorithm description I outlined at the start, new text is generated from a trigram by:

1. Picking a random bigram that appeared at the start of a post and writing it to a string buffer.
2. Repeatedly finding new bigrams that match the last two words, choosing a new third word, and writing those into the buffer.
3. Exiting when we find a bigram that didn’t appear in the text.

In code, that looks like:

pub fn generate_word_sequence(trigrams: &Trigrams) -> String {
    let mut rng = rand::rng();
    let mut post = String::new();

    // Choose a suitable starting bigram
    let (first_bigram, _) = trigrams
        .map
        .iter()
        .filter(|(_, data)| data.at_start)
        .choose(&mut rng)
        .expect("No starting trigrams found.");

    write!(post, "{} {}", first_bigram.0, first_bigram.1).unwrap();
    let mut current_bigram = first_bigram.clone();

    loop {
        // Choose a random word to follow our bigram
        let next_word = match trigrams.map.get(&current_bigram) {
            Some(data) => data.choices.iter().choose(&mut rng).unwrap().clone(),
            // No matching bigram - stop generating words
            None => break,
        };

        write!(post, " {}", next_word).unwrap();
        // Update the bigram to match the last two words
        current_bigram = (current_bigram.1, next_word);
    }

    post
}

The Blog Post

After writing some additional code to scrape text from my blog’s source files, stripping out frontmatter, section headings, Markdown, and footnotes, I fed all ~22k words into a trigram.

Here’s the intro to my next blog post, written (if you can believe it) entirely by a Markov chain.

After a software update on my computer and interface, the cat method was blazingly fast compared to the parser, but I don’t work for Google or have access to our checkerboard. Today, August 23rd, I have run this analysis? Probably either by exporting a massive CSV and processing as possible before pulling any data from the server time over websockets to reduce latency. Occasionally re-sync clients to account for edges and calculate slope from our original 10 bits? If we were looking for convenient, reliable solutions we wouldn’t be building The Worst Compression Algorithm™.

Compelling stuff!