Created
February 11, 2021 09:46
-
-
Save Caltrop256/b06f1c638de1f0dd3ea12ca0055cb986 to your computer and use it in GitHub Desktop.
Simple node.js Markov-Chain with import/export functionality
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const fs = require('fs'); | |
class ChainItem { | |
static BEGINNING = 0; | |
static MIDDLE = 1; | |
static END = 2; | |
before = Object.create(null); | |
after = Object.create(null); | |
constructor(content, pos) { | |
this.content = content; | |
this.pos = pos; | |
} | |
addAdjacent(index, pos) { | |
if(!index) return; | |
const dict = this[pos]; | |
(dict[index] && dict[index]++) || (dict[index] = 1); | |
}; | |
solveWeightedRandom(dict) { | |
const keys = Object.keys(dict); | |
const weights = keys.map(k => dict[k]); | |
for(let i = 0; i < weights.length; ++i) { | |
weights[i] += weights[i - 1] || 0; | |
} | |
const rand = Math.random() * weights[weights.length - 1]; | |
let index = 0; | |
while(weights[index++] < rand); | |
return keys[index - 1]; | |
} | |
next() { | |
return this.solveWeightedRandom(this.after); | |
} | |
previous() { | |
return this.solveWeightedRandom(this.before); | |
} | |
static from(data) { | |
const item = new ChainItem(data.content, data.pos); | |
item.before = data.before; | |
item.after = data.after; | |
return item; | |
} | |
} | |
class Markov { | |
items = []; | |
beginning = []; | |
add(str) { | |
const words = str.replace(/(\s)+/g, ' ').split(' '); | |
const indicies = new Array(words.length); | |
const offset = this.items.length; | |
let existing = 0; | |
for(let i = 0; i < words.length; ++i) { | |
const pos = !i ? ChainItem.BEGINNING : i == words.length - 1 ? ChainItem.END : ChainItem.MIDDLE; | |
let found = false; | |
for(let j = 0; j < this.items.length; ++j) { | |
const entry = this.items[j]; | |
if(entry.content == words[i] && entry.pos == pos) { | |
indicies[i] = j; | |
existing += 1; | |
found = true; | |
break; | |
} | |
} | |
if(!found) { | |
indicies[i] = (offset + i) - existing; | |
if(pos == ChainItem.BEGINNING) this.beginning.push(indicies[i]); | |
this.items[indicies[i]] = new ChainItem(words[i], pos); | |
} | |
} | |
for(let i = 0; i < indicies.length; ++i) { | |
const item = this.items[indicies[i]]; | |
if(item.pos > ChainItem.BEGINNING) item.addAdjacent(indicies[i - 1], 'before'); | |
if(item.pos < ChainItem.END) item.addAdjacent(indicies[i + 1], 'after'); | |
} | |
} | |
addArray(a) { | |
for(let i = 0; i < a.length; ++i) this.add(a[i]); | |
} | |
startsWith(inp) { | |
for(let i = 0; i < this.beginning.length; ++i) { | |
if(this.items[this.beginning[i]].content.toLowerCase() == inp.toLowerCase()) { | |
return this.generate({ | |
input: this.items[this.beginning[i]], | |
direction: 'next', | |
minimumLength: 1 | |
}); | |
} | |
} | |
} | |
endsWith(inp) { | |
let i = this.items.length; | |
while(i-->0) { | |
const item = this.items[i]; | |
if(item.pos == ChainItem.END && item.content.toLowerCase() == inp.toLowerCase()) return this.generate({ | |
input: item, | |
direction: 'previous', | |
minimumLength: 0 | |
}); | |
} | |
} | |
includes(inp) { | |
let item; | |
let i = this.items.length; | |
while(i-->0) { | |
const _item = this.items[i]; | |
if(_item.pos == ChainItem.MIDDLE && _item.content.toLowerCase() == inp.toLowerCase()) item = _item; | |
} | |
const before = this.generate({ | |
input: item, | |
direction: 'previous' | |
}); | |
const after = this.generate({ | |
input: item, | |
direction: 'next' | |
}).substring(item.content.length); | |
return (before + after).trim(); | |
} | |
generate(options = {}) { | |
const opts = Object.assign({direction: 'next', minimumLength: 1, maximumLength: Infinity}, options); | |
let item = opts.input || this.items[this.beginning[~~(Math.random() * this.beginning.length)]]; | |
let i = 0; | |
let str = ''; | |
while(item) { | |
str = opts.direction == 'next' ? str + item.content + ' ' : item.content + ' ' + str; | |
item = this.items[item[opts.direction]()]; | |
i += 1; | |
} | |
return i >= opts.minimumLength && i <= opts.maximumLength ? str.trim() : this.generate(opts); | |
} | |
export(filePath) { | |
const data = JSON.stringify(this.items); | |
fs.writeFileSync(filePath, data); | |
} | |
static from(filePath) { | |
const data = JSON.parse(fs.readFileSync(filePath)); | |
const chain = new Markov(); | |
let j = 0; | |
for(let i = 0; i < data.length; ++i) { | |
chain.items[i] = ChainItem.from(data[i]); | |
if(data[i].pos == ChainItem.BEGINNING) chain.beginning[j++] = i; | |
} | |
return chain; | |
} | |
} | |
module.exports = { | |
Markov, | |
ChainItem | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment