2
\$\begingroup\$

This is a Markov text generator I've created in JavaScript. I'm pretty sure the term "Markov" applies, anyway.

The way the generator works is like this: it first divides the source text into unique "chunks" of length n (specified via the order parameter, greater = more coherent result), and, for each chunk, determines which characters follow it how often. When generating a new text, it looks at the last n characters of what it's generated so far, then randomly selects one of its possible followers and appends it to the text.

(The last bit is apparently slightly different from the Dissociated press algorithm, which would output each follower with the same probability and not account for how often they occur.)

Long story short, here's my code. I'd mainly like to know if I'm following the common best practices as far as object orientation goes, I've had little experience with it before, but any kind of feedback is appreciated.

function Markov(sourceText, order) {

    this.sourceText = sourceText;
    this.order = order;

    this._setupFrequencies();

}

Markov.prototype = {

    _setupFrequencies: function() {

        this.frequencies = {};

        // for each substring of length <order>,
        // create an array of characters that can follow it
        for (var i = 0; i < this.sourceText.length - (this.order - 1); i++) {
            var chunk = this.sourceText.substr(i, this.order);
            if (!this.frequencies.hasOwnProperty(chunk)) {

                var followers = [];
                for (var k = 0; k < this.sourceText.length - (this.order - 1); k++) {
                    if (this.sourceText.substr(k, this.order) == chunk) {
                        follower = this.sourceText.substr(k + this.order, 1);
                        followers.push(follower);
                    }
                }

                this.frequencies[chunk] = followers;

            }
        }

    },

    _getRandomChar: function(chunk) {

        if (!this.frequencies.hasOwnProperty(chunk)) {
            return '';
        }
        var followers = this.frequencies[chunk];
        var randIndex = Math.floor(Math.random() * followers.length);
        return followers[randIndex];

    },

    _getRandomChunk: function() {

        var randIndex = Math.floor(Math.random() * this.sourceText.length);
        return this.sourceText.substr(randIndex, this.order);

    },

    generateText: function(length) {

        if (this.sourceText.length <= this.order) {
            return '';
        }

        var text = this._getRandomChunk();

        // take the last <order> characters from the generated string,
        // select one of its possible followers, and append it
        for (var i = this.order; i < length; i++) {
            var currentChunk = text.substr(text.length - this.order);
            var newChar = this._getRandomChar(currentChunk);

            if (newChar != '') { // the last chunk of the source has no follower
                text += newChar;
            } else {
                text += this._getRandomChunk();
            }
        }

        return text;

    }

}

It would then be used like so:

var text = "Call me Ishmael.  Some years ago—never mind how long precisely—having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world.";
var markov = new Markov(text, 3);
console.log(markov.generateText(100));

// results:
// " no money interest me Ishmael.  Some or no money in my particular to in my purse, and sail about a l"
// "y in my purse, I the would sail about a little on shore, and see thought I would sail about a little"
// "  Some Ishmael.  Some Ishmael.  Some Ishmael.  Some Ishmael.  Some years ago—never mind see the worl"
\$\endgroup\$
1
\$\begingroup\$

I think answering my own question is justified here. (?)

While I have no design pattern advice for myself, I've just found a way to greatly improve the performance of setupFrequencies. The code as posted in my question iterates over the entire source text every time a new chunk is found, but it just occurred to me that such an inner loop isn't necessary at all.
Eliminating it not only shortens the code, but also reduces the runtime complexity from O(n²) to O(n) - a huge improvement, especially for longer source texts.

_setupFrequencies: function() {

    this.frequencies = {};

    // for each substring of length <order>,
    // create an array of characters that can follow it
    for (var i = 0; i < this.sourceText.length - (this.order - 1); i++) {
        var chunk = this.sourceText.substr(i, this.order);
        if (!this.frequencies.hasOwnProperty(chunk)) {
            this.frequencies[chunk] = [];
        }
        var follower = this.sourceText.substr(i + this.order, 1);
        this.frequencies[chunk].push(follower);
    }

},
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.