1. Markov Chain Text Generation
  2. Sentence Statistics
  3. Building the Markov Model
  4. Generating a Sentence
  5. Improving the Model
  6. Further Suggestions

Markov Chain Text Generation

I've played around a lot with Markov chain text generators in the past, so I thought I would write up a bit of a tutorial. These kinds of text generators are very different from modern, prompted LLMs - they won't answer questions, or even write particularly lucid responses. Their output is mostly gibberish with the occasional randomly occuring gem. Unsurprisingly, these are mostly used for parody text generation, novelty accounts, and potentially trying to poison scrapers with reams of meaningless babble.

The upshot is that Markov chains are much, much simpler to understand and implement than an LLM. They require far fewer resources and can generate output far faster than a local LLM could, and the required training data is orders of magnitude smaller than is required for LLMs. This makes them a pretty quick and easy project and portable to low-resource systems like microcontrollers.

A Markov model or process is basically a series of probability based decisions. At each node, each branch has a probability of being chosen, and a random choice is made based on those probabilities. The random choice made at each node is independent of the previous choices that were made and has its own set of probabilities. Performing a random walk across nodes in a connected graph is a form of Markovian behaviour, and isn't far off of how a Markov text generator works.

Sentence Statistics

A Markov Text Generator typically works on some very basic sentence statistics, namely what the probability is of X word proceeding Y word. For example, "the cat is in the hat" - in this sentence, the word "the" has a 50% probability of being followed by "cat" and a 50% probability of being followed by "hat". Those would be the two choices of the Markov node for "the", and we would randomly pick one of them. If we do this across many sentences, we can build a simple statistical model of how often and what words tend to follow a given word.

The first step is to take some sample text (our training text) and parse it. This involves finding all words in the text, and counting how many instances of each following word appears. Here's a short Python 3 snippet that takes a sentence and returns a dictionary of these relationships per-word:

# Function to parse a sentence into word counts
def parse_sentence(sentence):
	# Strip whitespace and split on spaces to get words
	words = sentence.strip().split(' ')
	result_dict = {}
	# For each word in the sentence
	for idx, word in enumerate(words):
		# Add to the results if not already there
		if word not in result_dict:
			result_dict[word] = {}
		# If not the last word in the sentence
		if idx < (len(words) - 1):
			# Add the word following this one to the stats or increment
			if words[idx + 1] not in result_dict[word]:
				result_dict[word][words[idx + 1]] = 1
			else:
				result_dict[word][words[idx + 1]] += 1
	return result_dict


print(parse_sentence("Hello world, this is a sentence and this is the end."))

This example sentence results in a dictionary that looks like the following:

{
	'Hello': {'world,': 1}, 'world,': {'this': 1}, 'this': {'is': 2}, 'is': {'a': 1, 'the': 1},
	'a': {'sentence': 1}, 'sentence': {'and': 1}, 'and': {'this': 1}, 'the': {'end.': 1}, 'end.': {}
}

This dictionary captures the probability of one word following another. Looking up a given X word in the dictionary returns a sub-dictionary of zero or more words that follow it, and a count of how often each following word appears. These can be used to make a weighted random choice, with the sub-dictionaries acting as the probability distribution in the Markov chain node.

The cleanliness of your training data will make a big difference on the accuracy of your statistics. Notice that capitalization and punctuation (like periods, commas, and quotes) will be counted as separate words. In terms of the statistics, "end." will be tracked separately from "end", and "Hello" separately from "hello". This may or may not be a problem depending on your use case, but pre-cleaning your training text can go a long way to fixing it.

If you decide to try parsing out punctuation and capitalization automatically, be careful of abbreviations. Many of my automatic parsing attempts have been thwarted by Dr., Mrs. Mr., Mt., St., and other similar non-terminating periods. Quotes and quote matching, especially nested quotes, can also be quite annoying to parse properly. For the small training set sizes typically used in Markov chains manual cleaning is probably faster than trying to debug a parser.

Building the Markov Model

To generate interesting sentences, our Markov model needs to be much larger than an individual sentence. We can merge the results of each individual sentence together to create a larger model with many more possibilities for each following word. Statistically, this makes the following-word counts within the model equal to the sum of the following-word counts for each sentence in the training text - so now when we pick the next word (the next choice in the Markov chain), we're using a probability based on the entire text.

Each Markov dictionary can be merged together using the following function. This merges dict_a and dict_b and returns the resulting merged dictionary. This can be used to merge each sentence dictionary into the larger Markov chain dictionary.

# Merge two word probability dictionaries together
def merge_dicts(dict_a, dict_b):
    for key in dict_b:
        if key in dict_a:
            # If key in A and B, look through subkeys (word probabilities)
            for sub_key in dict_b[key]:
                if sub_key in dict_a[key]:
                    # If a subkey already exists in A, add B's count to it
                    dict_a[key][sub_key] += dict_b[key][sub_key]
                else:
                    # If a subkey doesn't exist in A, set it to count in B
                    dict_a[key][sub_key] = dict_b[key][sub_key]
        else:
            # If key in B but not in A, copy whole key over
            dict_a[key] = dict_b[key]
    return dict_a

A second function opens up a TXT file full of sentences, parses them, and merges the results into a single dictionary - the Markov model. It then saves this dictionary as a JSON file appended with "_markov". This means you can separate creating the model and using it, which might be relevant if you're making a very large model with a lot of input text and want to have it pre-computed.

# Train a Markov chain from a text file of sentences
from json import dumps

def parse_file(filename):
    # Open the training TXT file
    with open(filename + '.txt', 'r') as training_fp:
        # Split into lines (one sentence per line) and strip whitespace
        lines = [line.strip() for line in training_fp.read().split('\n')]
        markov_chain = {}
        # For each line, build a probability dict and then merge into markov dict
        for line in lines:
            merge_dicts(markov_chain, parse_sentence(line))
        # Export the complete Markov model as a JSON file
        with open(filename + '_markov.json', 'w') as markov_fp:
            markov_fp.write(dumps(markov_chain, indent=4, sort_keys=True))


# Run the script using picard.txt
if __name__ == "__main__":
    parse_file('picard')

For the input training data, I used Captain Picard's lines from TNG, which I've made available in a cleaned and preformatted file here: Picard Lines. Some important notes about cleaning - all sentences were stripped of terminators (.?!), excess whitespace removed, and the first letter of each sentence was lowercased. All lines with only one word and all duplicate lines were removed. " -- " and " ... " are used as breaks within sentences, and they count as words (splices together a lot of possible combinations for any sentence with -- or ... in it). I went through manually and capitalized the beginning of sentences with names or titles that are capitalized throughout (like "Riker" or "Ambassador") that had been previously lowercased to avoid creating alternate lowercase versions.

The resulting Markov model file in JSON format is available here: Picard Markov model. Looking up a specific word in the model shows us a dictionary of following words and counts for the entire text. For example, the word "tachyon" is followed by the following words:

"tachyon": {
        "beam": 1, "detection": 1, "field": 1, "net": 1, "pulse": 5, "pulse,": 2, "pulses": 3, "scan": 1
}

Note that this isn't a particularly efficient way to store this data. The Markov model is significantly larger than the original source data, since we're using strings and each string is duplicated many times over in sub-dictionaries of various words. The string "and" appears more than 700 times in the model, because "and" can follow so many different words (and has a huge following-word dict itself as well).

Generating a Sentence

Once we have a model, generating sentences is fast and easy, although generating sentences that meet specific requirements can be difficult. For now, the only restriction I'm implementing is the ability to set the wordcount of the output sentence. If we reach the wordcount, we will terminate the sentence; if we reach a dead-end word (a word with no following-words) before we hit the wordcount, we'll retry the whole process again.

We begin by picking a word at random from the model to start our sentence with, and putting it in a list which will contain all the words in our sentence. As long as the list length is less than the specified wordcount, then we'll do the following:

Here's some code that accomplishes this. Note that it relies on Python 3.7+ dictionary behaviour, meaning dict.keys() and dict.values() return in order. If you're using an earlier Python version values() and keys() return in an unspecified (i.e. potentially random) order, so the weights would be scrambled. It uses the choice() and choices() functions from the Python 3 random library, with choices() making the weighted random choice for us.

from json import loads
from random import choice, choices

# Build a sentence of wordcount length from model
def build_sentence(model, wordcount):
    # Pick a random starting word
    sentence = [choice(list(model.keys()))]
    # Loop until we meet length requirement
    while len(sentence) < wordcount:
        # If the following-word dict isn't empty
        if model[sentence[-1]]:
            # Make a weighted random choice and add following word to sentence
            sentence.append(choices(list(model[sentence[-1]].keys()),
                                    weights=list(model[sentence[-1]].values()))[0])
        else:
            # Otherwise we hit a dead end, restart with new sentence
            sentence = [choice(list(model.keys()))]
    # Join the words together and return a string
    return " ".join(sentence)


# Run the script using picard_markov.json
if __name__ == "__main__":
    with open('picard_markov.json', 'r') as model_fp:
        picard_model = loads(model_fp.read())
        for _ in range(10):
            print(build_sentence(picard_model, 15))

And there it is - a Markov generator for Captain Picard... if Picard was perhaps having a serious stroke, or his Locutus side started to kick in again. Statistically, the rate of word occurrences in the output should average (in bulk) towards the rate of word occurrences in the training data. On a sentence-by-sentence case though, it's mostly gibberish. Individual bigrams make sense, since they're from the original training text, but any larger N-gram quickly becomes chaotic and meaningless. Occasionally it'll generate something lucid through pure coincidence, a bit like a fortune cookie. "I'm just a subspace bandwidth" is oddly appealing.

invitation, Ensign, after you've made my associate, Mister Elbrun, if the gauntlet ... why aren't
speaks for a specific artifact ... as you're prepared to have to the Q remember
dissipated by the situation any particular danger from time you we have something we both
intimidation, madame, for protection, I believe Captain Garrett -- activate impulse engines to go back
Spock has entered as skilled leadership of time I brought to investigate once that good
mettle on board who was controlled from the loop by a new information, now live
progress, Counselor Troi away team you're the bureaucracy, but there must send down the same
spy, to forget the one of information is his DNA changed, as a complete systems
care of those incidents aboard this is in yours ... I'm just a subspace bandwidth
pride, will enter the Federation Starship Enterprise ... do not for a serious -- unable

Improving the Model

There's a lot of optional improvements that can be made to the basic Markov generator. You can get into a great deal of complexity trying to generate coherent text with these models. I'll detail some of the more basic upgrades and improvements here.

To start with, we should be formatting our sentences properly - adding a terminator to the end (!?.) and capitalizing the first letter. That's just a straightforward string transformation:

# Properly format a sentence string
def format_sentence(line):
    # Uppercase first letter
    line = line[0].upper() + line[1:]
    # Remove any ending punctuation or whitespace
    while line[-1] in ' ,.;-':
        line = line[:-1]
    # Add a random weighted choice of terminator (?!.)
    return line + choices(['.', '?', '!'], [0.8, 0.1, 0.1])[0]

Another issue is that the sentences end arbitrarily at the required wordcount. This tends to leave incomplete fragments at the end of the sentence. A simple way of (mostly) fixing this without any fancy natural language processing is to use a list of stopwords, and remove any trailing stopwords in a sentence.

Stopwords are very common words ("I", "we", "a", "to", etc.) that are commonly filtered out during natural language processing. They can be valid sentence-ending words, but usually they aren't - there aren't many sentences that can end in "the". I used the NLTK stopword list as a base and added a few entries myself, the stopword file I used is available here: Stopword List.

A function to remove these words from the end of the sentence is shown here. It splits the sentence back into a list of words, and works backwards until it hits a non-stopword. If the entire sentence is stopwords theres nothing that can be done, so the original sentence is returned as-is. It also checks for stopwords with common punctuation or terminators attached and will remove those - so this should be done before doing the final formatting on the string.

# Load the stopword file into a list
def get_stopwords(filename):
    with open('stopwords.txt', 'r') as stop_fp:
        return [line.strip() for line in stop_fp.read().split('\n')]


# Remove stopwords from end of sentence
def clean_endings(sentence, stopwords):
    words = sentence.split(' ')
    while words:
        # Handle stopwords with punctuation
        if words[-1][-1] in [',', ':', ';', '-', '.', '?', '!']:
            lastword = words[-1][0:-1]
        else:
            lastword = words[-1]
        # Remove last word if in stopwords
        if lastword in stopwords:
            words.pop(-1)
        else:
            break
    # If entire sentence is stopwords, return original sentence
    if not words:
        return sentence
    # Otherwise, return cleaned sentence
    return " ".join(words).strip()

Another way to make the text look more "realistic" is to vary the lengths of the sentences. There's already a little bit of variation due to the stopword removal process, but it's pretty easy to use line-length statistics to improve this. This also makes the generated text more statistically similar to the training text.

All we have to do is make a probability dictionary of line length : line count. This involves opening the training file, doing a wordcount on every line, and collecting the results in the probability dictionary. Then we can just use choices() again to make a weighted random choice of line length. In theory, the text we generate should have the same distribution of line lengths as the training text, although only over a relatively long average, and skewed a bit by the stopword removal making lines shorter.

# Calculate line length distribution
def calculate_length_distribution(filename):
    with open(filename, 'r') as text_fp:
        sentences = [line.strip() for line in text_fp.read().split('\n')]
        line_distributions = {}
        for line in sentences:
            # Count the words by counting spaces
            wordcount = line.count(' ') + 1
            if wordcount in line_distributions:
                line_distributions[wordcount] += 1
            else:
                line_distributions[wordcount] = 1
    return line_distributions


# Get a weighted random choice of line length from the distribution
def get_line_length(line_distribution):
    return choices(list(line_distribution.keys()), weights=list(line_distribution.values()))[0]

Combining all of these together, we can generate something slightly more Picard-like, although he might still have a serious concussion.

# Run the script using picard_markov.json
if __name__ == "__main__":
    with open('picard_markov.json', 'r') as model_fp:
        picard_model = loads(model_fp.read())
        stopword_list = get_stopwords('stopwords.txt')
        line_lengths = calculate_length_distribution('picard.txt')
        lines = []
        for _ in range(10):
            print(
                format_sentence(
                    clean_endings(
                        build_sentence(picard_model, get_line_length(line_lengths)), stopword_list
                    )
                )
            )

And the output:

Toes, Number One.
Alliance for you should have lost.
Tried using a room filled your Holodeck makes you responsible for the greatest wish.
Young Wesley lost a mood.
Harder!
Moment, Mister La Forge.
Form reading.
Gagh in spite of omission is your return to find the Romulans could move the Array!
Attack, they are asked.
Toast to hold.

Further Suggestions

That's where I'll leave this for now. The complete commented code and text/model files are available to download as a ZIP file here: Markov.zip.

How far you want to go with these models is really up to you. There are still a lot more optimizations and improvements that can be made. Here's a brief list of some ideas:

If you're interested in learning a bit more about Markov chain text generation, I recommend looking up Mark V. Shaney, a classic Usenet bot from the 80s that used a similar system to generate nonsense posts. It's trigram-based, so a third-order Markov chain - which produces a slightly better output than the simple bigram example given here.