Skip to content

Instantly share code, notes, and snippets.

@Dante83
Created June 23, 2016 06:37
Show Gist options
  • Save Dante83/b5a4f8862c84225d16ce8205355e6cbc to your computer and use it in GitHub Desktop.
Save Dante83/b5a4f8862c84225d16ce8205355e6cbc to your computer and use it in GitHub Desktop.
//
//This is what happens when you get Markov Chains wrong. Magic! >:{D
//
var markov_id = 0;
var markovChain = [];
function parseNameCSVData(){
var rawWordData = $('#name-csv-data').val().split(',');
var words = [];
for(var i = 0; i < rawWordData.length; i++){
words.push(rawWordData[i].trim());
}
//Reset our variables
markov_id = 0;
markovChain = [];
//Implement the primary function for building our markov chain
CreateCharacterMarkovChain(words);
$('#application-status').text('Markov chain created successfully.');
$('#generate-names-btn').on('click', function(){
generateNewWords();
});
}
function generateNewWords(){
var outputWordList = [];
var numberOfWords = parseInt($('#number-of-generated-names').val());
for(var i = 0; i < numberOfWords; i++){
var letterList = [];
//Determine the first letter of the word via a roulette style random number selector
var firstLetters = [];
for(var m = 0; m < markovChain.length; m++){
if(markovChain[m].isBeginningNode){
firstLetters.push(markovChain[m]);
}
}
var orderedFirstLetters = firstLetters.sort(function(a, b){
return a.probability - b.probability;
});
var randSelection = Math.random();
var totalProb = 0.0;
var currentlySelectedId;
var totalCurrentProbability = 0.0;
var currentlySelectedId;
for(var c = 0; c < orderedFirstLetters.length; c++){
totalCurrentProbability += orderedFirstLetters[c].probability;
if(randSelection <= totalCurrentProbability){
currentlySelectedId = orderedFirstLetters[c].id;
letterList.push(markovChain[currentlySelectedId].propertyVal);
break;
}
}
//Now, given this first selected letter, determine the next letter iteratively until
//we reach a markov chain node that represents the final letter in the chain
var isNotEndLetter = true;
while(isNotEndLetter){
currentlySelectedId = markovChain[currentlySelectedId].chooseChild();
letterList.push(markovChain[currentlySelectedId].propertyVal);
if(markovChain[currentlySelectedId].isEndNode){
isNotEndLetter = false;
}
}
//Concactonate our letters into a string and append it to our list
outputWordList.push(letterList.join(''));
}
//Output these words to the page so that the user can enjoy the results of our work
$('#generated-names').empty();
for(w in outputWordList){
$('#generated-names').append('<div class="generated-word-result">' + outputWordList[w] +'</div>');
}
$('#application-status').text(numberOfWords + ' new words created from the current markov chain.');
}
function CreateCharacterMarkovChain(wordList){
//Determine the beginning word nodes
var firstLetterUnnormalizedProbability = [];
var totalForNormalization = 0.0;
for(var w = 0; w < wordList.length; w++){
var firstLetter = wordList[w].charAt(0);
var exists = firstLetterUnnormalizedProbability.indexOf(firstLetter);
if(firstLetter in firstLetterUnnormalizedProbability){
firstLetterUnnormalizedProbability[firstLetter]++;
}
else{
firstLetterUnnormalizedProbability[firstLetter] = 1.0;
}
totalForNormalization++;
}
//Now add the normalized values into a set of new markov chain strands
for(var key in firstLetterUnnormalizedProbability){
var normalizedProbability = firstLetterUnnormalizedProbability[key] / totalForNormalization;
var newMarkovNode = new MarkovNode(key, normalizedProbability, null, 0);
newMarkovNode.isBeginningNode = true;
markovChain.push(newMarkovNode);
}
//Go through all of our markov chain elements and recursively build out their children
for(var mc in markovChain){
//Go through the word list and determine
for(var w = 0; w < wordList.length; w++){
//Who's your daddy?
if(wordList[w].charAt(0) === markovChain[mc].propertyVal){
recursiveChildBuilder(wordList[w], 1, markovChain[mc].id);
}
}
}
//Once again go through our markov chain elements and recursively normalize their children
for(var mn = 0; mn < markovChain.length; mn++){
if(markovChain[mn].isBeginningNode){
//Normalize this set of children
//And implement this on each of the child elements
recursiveNormalizer(markovChain[mn].id);
}
}
}
function recursiveNormalizer(parentId){
markovChain[parentId].normalizeChildProbabilities();
for(var c = 0; c < markovChain[parentId].childIds.length; c++){
recursiveNormalizer(markovChain[parentId].childIds[c]);
}
}
function recursiveChildBuilder(word, depth, parentId){
//First, check that this is even a character, if it is then proceed,
//otherwise mark the previous parent node as an end node
//Note To Self: Apparently an empty string is not the same as null. And when no string is found at a location,
//an empty string is exactly what this hell-spawn returns.
if(word.charAt(depth) === ''){
markovChain[parentId].isEndNode = true;
}
else{
//First check if any children exist with this property
var foundLocation = markovChain[parentId].searchChildren(word.charAt(depth));
//If it exists, then iterate it's value, otherwise create a new node
if(foundLocation !== -1){
markovChain[foundLocation].probability++;
}
else if(word.charAt(depth) != null){
foundLocation = markovChain[parentId].createChildren(word.charAt(depth), depth, 1.0);
}
//Increase the depth and re-implement the recursion method
recursiveChildBuilder(word, depth + 1, foundLocation);
}
}
var MarkovNode = function(propertyVal, probability, parent_node, depth){
this.propertyVal = propertyVal;
this.probability = probability;
this.parent_node = null;
if(parent_node !== null){
this.parent_node = parent_node;
}
this.id = markov_id;
this.childIds = [];
this.isEndNode = false;
this.depth = depth;
this.isBeginningNode = false;
markov_id++;
this.createChildren = function(propertyVal, depth, probability){
var newNode = new MarkovNode(propertyVal, probability, markovChain[this.id], depth);
markovChain[newNode.id] = newNode;
this.childIds.push(newNode.id);
return newNode.id;
};
this.normalizeChildProbabilities = function(){
var sumTotal = 0.0;
for(var c = 0; c < this.childIds.length; c++){
sumTotal += markovChain[this.childIds[c]].probability;
}
//Now divide out each of the values in the children by these values
for(var c = 0; c < this.childIds.length; c++){
markovChain[this.childIds[c]].probability = markovChain[this.childIds[c]].probability / sumTotal;
}
};
this.searchChildren = function(property){
returnVal = -1;
for(var c = 0; c < this.childIds.length; c++){
if(markovChain[this.childIds[c]].propertyVal === property){
returnVal = this.childIds[c];
}
}
return returnVal;
}
this.chooseChild = function(){
//Gather all child elements
var children = [];
for(var c = 0; c < this.childIds.length; c++){
children.push(markovChain[this.childIds[c]]);
}
//Organize the children according to their probability
var orderedChildren = children.sort(function(a, b){
return (a.probability - b.probability);
});
//Use a roulette style probability chooser to find the child most likely to be
var randSelection = Math.random();
var totalCurrentProbability = 0.0;
var selectedId;
for(var c = 0; c < orderedChildren.length; c++){
totalCurrentProbability += orderedChildren[c].probability;
if(randSelection <= totalCurrentProbability){
selectedId = orderedChildren[c].id;
break;
}
}
return selectedId;
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment