Markov chain in JavaScript

I made a small Markov Chain joke generator during my coffee break sometime last week. This is in continuation to the last post, where we did a similar thing. I did this specifically to see how well it could be extended in a language which I have typically not used before for ML/NLP.

Let me run you guys through it.

First of all, the Markhov Chains need a bunch of data to tell it how exactly you want your sentences constructed.

str_arr=[sentence1, sentence2,...]

Next, we create a dictionary of all trigrams present across the sentences. To do this, we use all bigrams as keys, and the succeeding word as the corresponding values. The key-value pairs thus form a trigram.

As an example, consider the sentence : “The man had a dog.”

The dictionary for this sentence will have :

[ {[The, man] : [had]}, {[man, had] : [a]}, {[had, a] : [dog]} ]

	trigram_dict = {};
	str_arr.forEach( function(e,i){
	sent = e;
	word_tokens = str.split(" ");
	word_tokens.forEach(
	function(e,i){
	if( i < 1 ){ return true; }
	if( i == ( word_tokens.length - 1 ) ){ return true; }
	// check if key (previous-word current-word) present
	if( !trigram_dict[ word_tokens[i-1]+' '+e] ){
	trigram_dict[ word_tokens[i-1]+' '+e] = [] ;
	}
	//check if next-word available
	if( typeof(word_tokens[i+1]) != "undefined" ){
	trigram_dict[word_tokens[i-1]+' '+e].push(word_tokens[i+1] );
	}
	}
	);
	} );

view raw gistfile1.txt hosted with ❤ by GitHub

Next up, using the dictionary that we just made to create sentences. Here we provide the first two words, and let the function work its magic to complete the sentence. The first two words are used as key to search the dictionary for a candidate third word, which is appended to the first two words. Then the second and third words are taken as key, and so on. If there are multiple words as succession candidates for a particular pair, any one of them becomes the Chosen One randomly. The process continues until no succeeding word is found, and the words collected till then form our new sentence.

	function create(trigram_dict ){
	new_string_arr = ["Yo","mama"];
	prevword=trigram_dict [ new_string_arr[new_string_arr.length-2];
	pprevword=new_string_arr[new_string_arr.length-1] ;
	while( typeof( trigram_dict [prevword+' '+pprevword] ) != "undefined" ){
	candidate_words = trigram_dict [ prevword+' '+pprevword ] ;
	//select word randomly out of all candidates
	item = candidate_words[Math.floor(
	Math.random() * candidate_words.length)];
	new_string_arr.push(item);
	prevword=trigram_dict [ new_string_arr[new_string_arr.length-2];
	pprevword=new_string_arr[new_string_arr.length-1] ;
	}
	new_str = new_string_arr.join(" ");
	//A brand new sentence
	return new_str ;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

That’s it! Some observations I would like to make here: One could try to extend the trigrams to n-grams, but complexity will be going up. Instead of selecting from candidate words randomly, one can have a probability-based selection as well. Instead of just sentences as input (and output) one can have paragraphs and even,(if we dare dream so high), whole essays.