Markov Chain implementation in Javascript

One blustery Saturday this past December, I rode my bicycle over to Manhattan to attend the New York Tech Zine fair, an event hosted by the School For Poetic Computation (SFPC). Amidst the bundled yet fashionable crowds, I noticed a trend across a number of zines — poetry generated by computers. Many of these zine authors said they used Markov chains, implemented in Python, to generate the poetry. Having never heard of Markov chains before, I did some research and decided this technology could be easily enough implemented in Javascript. Here’s my guide as to how to do it.

First off: What’s a Markov chain?

Wikipedia defines a Markov chain as “…a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.”

I found that a little hard to understand — too much jargon! A Markov chain is essentially a way of predicting what will happen next based only on what just happened. For example: if a person just drove one mile down a road, a Markov chain could measure the likelihood of that person’s next move, such as:

• Turning
• Stopping for gas
• Continuing Straight
• Having a spontaneous dance party
• Or really any other possibility.

The way this happens is through taking a data set of past events and recording what happened after each one. For example, if we recorded what happened after 100 drivers went one mile east on highway 20, our data might show us that 75 continued straight, 10 turned, 10 stopped for gas, and 5 had a spontaneous dance party.

We would then have data for what all of those choices might lead to. Having a Markov chain of events like this can be used to create a simulated event chain that theoretically bears some resemblance to how events play out in our data. These are used in fields like economic modeling, predictive consumer behavior, and more. In this article, we’ll demonstrate how to implement a Markov chain to get a computer to generate text.

Generating the Model

The first step will be to generate our model. We’ll have to feed our function some text and get back a Markov chain. We’ll do this by creating a Javascript object, and setting each event (in the case, a word) to be keys, and each instance of a following event (another word) as strings in an array. Here’s what the code might look like, with some extra formatting added in to get rid of variables like case-sensitivity and punctuation.

function markovChainGenerator(text) {
  const textArr = text.split(' ')
  const markovChain = {};
for (let i = 0; i < textArr.length; i++) {
    let word = textArr[i].toLowerCase().replace(/[\W_]/, "")
    if (!markovChain[word]) {
      markovChain[word] = []
      }
    if (textArr[i + 1]) {
      markovChain[word].push(textArr[i + 1].toLowerCase().replace(/[\W_]/, ""));
}
}
return markovChain
}

You might be thinking…you said a Markov chain is a predictive model! Shouldn’t you be recording the likelihood of each following word, rather than just having an array of all the possibilities?”

Yes. You could do it that way, and you might save some space, especially with a large input set. Instead, we’ll make use of Javascript’s native Math.random() function to get random words from our Markov chain arrays. Because multiple instances of a word in each array increase the likelihood of getting that word from a random function, we are able to imitate the the likelihood of a following word without doing too much math ourselves. If we really want to know the likelihood of any following event, we can easily find it with a simple algorithm:

function likelyhood(chain, prev, word) {
const prevArr = chain[prev]
const num = prevArr.filter(w => w === word).length
return `The likelihood that ${word} will come after ${prev} is ${num} out of ${prevArr.length}`
}

Great, we’ve got our Markov Chain. Now what?

Let’s put it to use somewhere!

Our Markov chain text generator code

I hope you’ve learned something from this walk-through, and make some creative use of Markov chains on your own! You can also create Markov chains using groups of characters rather than whole words, which creates another fun and inspiring result. Watch what happens when you mix different kinds of texts — the results may bring unexpected but interesting juxtapositions. Feel free to share your creations in the comments!