Markov chain text generator

From Rosetta Code
Markov chain text generator is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

This task is about coding a Text Generator using Markov Chain algorithm.

A Markov chain algorithm basically determines the next most probable suffix word for a given prefix.

To do this, a Markov chain program typically breaks an input text (training text) into a series of words, then by sliding along them in some fixed sized window, storing the first N words as a prefix and then the N + 1 word as a member of a set to choose from randomly for the suffix.

As an example, take this text with N = 2:

now he is gone she said he is gone for good

this would build the following table:

PREFIX               SUFFIX
now he               is
he is                gone, gone
is gone              she, for
gone she             said
she said             he
said he              is
gone for             good
for good             (empty) if we get at this point, the program stops generating text

To generate the final text choose a random PREFIX, if it has more than one SUFFIX, get one at random, create the new PREFIX and repeat until you have completed the text.

Following our simple example, N = 2, 8 words:

random prefix: gone she
suffix: said
new prefix: she + said
new suffix: he
new prefix: said + he
new suffix: is
... and so on

gone she said he is gone she said

The bigger the training text, the better the results. You can try this text here: alice_oz.txt

Create a program that is able to handle keys of any size (I guess keys smaller than 2 words would be pretty random text but...) and create output text also in any length. Probably you want to call your program passing those numbers as parameters. Something like: markov( "text.txt", 3, 300 )




C++[edit]

In this implementation there is no repeated suffixes!

 
#include <ctime>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
#include <map>
class markov {
public:
void create( std::string& file, int keyLen, int words ) {
std::ifstream f( file.c_str(), std::ios_base::in );
fileBuffer = std::string( ( std::istreambuf_iterator<char>( f ) ), std::istreambuf_iterator<char>() );
f.close();
if( fileBuffer.length() < 1 ) return;
createDictionary( keyLen );
createText( words - keyLen );
}
private:
void createText( int w ) {
std::string key, first, second;
size_t next, pos;
std::map<std::string, std::vector<std::string> >::iterator it = dictionary.begin();
std::advance( it, rand() % dictionary.size() );
key = ( *it ).first;
std::cout << key;
while( true ) {
std::vector<std::string> d = dictionary[key];
if( d.size() < 1 ) break;
second = d[rand() % d.size()];
if( second.length() < 1 ) break;
std::cout << " " << second;
if( --w < 0 ) break;
next = key.find_first_of( 32, 0 );
first = key.substr( next + 1 );
key = first + " " + second;
}
std::cout << "\n";
}
void createDictionary( int kl ) {
std::string w1, key;
size_t wc = 0, pos, textPos, next;
next = fileBuffer.find_first_not_of( 32, 0 );
if( next == -1 ) return;
while( wc < kl ) {
pos = fileBuffer.find_first_of( ' ', next );
w1 = fileBuffer.substr( next, pos - next );
key += w1 + " ";
next = fileBuffer.find_first_not_of( 32, pos + 1 );
if( next == -1 ) return;
wc++;
}
key = key.substr( 0, key.size() - 1 );
while( true ) {
next = fileBuffer.find_first_not_of( 32, pos + 1 );
if( next == -1 ) return;
pos = fileBuffer.find_first_of( 32, next );
w1 = fileBuffer.substr( next, pos - next );
if( w1.size() < 1 ) break;
if( std::find( dictionary[key].begin(), dictionary[key].end(), w1 ) == dictionary[key].end() )
dictionary[key].push_back( w1 );
key = key.substr( key.find_first_of( 32 ) + 1 ) + " " + w1;
}
}
std::string fileBuffer;
std::map<std::string, std::vector<std::string> > dictionary;
};
int main( int argc, char* argv[] ) {
srand( unsigned( time( 0 ) ) );
markov m;
m.create( std::string( "alice_oz.txt" ), 3, 200 );
return 0;
}
 
Output:
March Hare had just upset the milk-jug into his plate. Alice did not dare to 
disobey, though she felt sure it would all come wrong, and she went on. Her 
listeners were perfectly quiet till she got to the part about her repeating 
'You are old, Father William,' said the Caterpillar. 'Well, I've tried to say 
How doth the little crocodile Improve his shining tail, And pour the waters of 
the Nile On every golden scale! 'How cheerfully he seems to grin, How neatly 
spread his claws, And welcome little fishes in With gently smiling jaws!' 
'I'm sure those are not the right words,' said poor Alice, and her eyes filled 
with tears again as she went slowly after it: 'I never was so small as this before, 
never! And I declare it's too bad, that it is!' As she said this she looked 
down into its face in some alarm. This time there were three gardeners at it, 
busily painting them red. Alice thought this a very difficult game indeed. 
The players all played at once without waiting for the end of me. But the 
tinsmith happened to come along, and he made me a body of tin, fastening my 
tin arms and


D[edit]

Translation of: Kotlin
import std.file;
import std.random;
import std.range;
import std.stdio;
import std.string;
 
string markov(string filePath, int keySize, int outputSize) {
if (keySize < 1) throw new Exception("Key size can't be less than 1");
auto words = filePath.readText().chomp.split;
if (outputSize < keySize || words.length < outputSize) {
throw new Exception("Output size is out of range");
}
string[][string] dict;
 
foreach (i; 0..words.length-keySize) {
auto key = words[i..i+keySize].join(" ");
string value;
if (i+keySize<words.length) {
value = words[i+keySize];
}
if (key !in dict) {
dict[key] = [value];
} else {
dict[key] ~= value;
}
}
 
string[] output;
auto n = 0;
auto rn = uniform(0, dict.length);
auto prefix = dict.keys[rn];
output ~= prefix.split;
 
while (true) {
auto suffix = dict[prefix];
if (suffix.length == 1) {
if (suffix[0] == "") return output.join(" ");
output ~= suffix[0];
} else {
rn = uniform(0, suffix.length);
output ~= suffix[rn];
}
if (output.length >= outputSize) return output.take(outputSize).join(" ");
n++;
prefix = output[n .. n+keySize].join(" ");
}
}
 
void main() {
writeln(markov("alice_oz.txt", 3, 200));
}
Output:
neighbour to tell him. 'A nice muddle their slates'll be in before the trial's over!' thought Alice. One of the jurors had a pencil that squeaked. This of course, Alice could not think of any good reason, and as the monster crawls through the forest he seizes an animal with a leg and drags it to his ear. Alice considered a little, and then said 'The fourth.' 'Two days wrong!' sighed the Hatter. 'I deny it!' said the March Hare. 'Sixteenth,' added the Dormouse. 'Write that down,' the King replied. Here the other guinea-pig cheered, and was immediately suppressed by the officers of the court, all dressed in green clothes and had greenish skins. They looked at Dorothy again. Why should I do this for you? asked the Scarecrow. You are quite welcome to take my head off, as long as the tiger had said, and its body covered with coarse black hair. It had a great longing to have for her own the Silver Shoes had fallen off in her flight through the air, and on the morning of the second day I awoke and found the oil-can, and then she had to stop and untwist it. After a

J[edit]

This seems to be reasonably close to the specification:

require'web/gethttp'
 
setstats=:dyad define
'plen slen limit'=: x
txt=. gethttp y
letters=. (tolower~:toupper)txt
NB. apostrophes have letters on both sides
apostrophes=. (_1 |.!.0 letters)*(1 |.!.0 letters)*''''=txt
parsed=. <;._1 ' ',deb ' ' (I.-.letters+apostrophes)} tolower txt
words=: ~.parsed
corpus=: words i.parsed
prefixes=: ~.plen]\corpus
suffixes=: ~.slen]\corpus
ngrams=. (plen+slen)]\corpus
pairs=. (prefixes i. plen{."1 ngrams),. suffixes i. plen}."1 ngrams
stats=: (#/.~pairs) (<"1~.pairs)} (prefixes ,&# suffixes)$0
weights=: +/\"1 stats
totals=: (+/"1 stats),0
i.0 0
)
 
genphrase=:3 :0
pren=. #prefixes
sufn=. #suffixes
phrase=. (?pren) { prefixes
while. limit > #phrase do.
p=. prefixes i. (-plen) {. phrase
t=. p { totals
if. 0=t do. break.end. NB. no valid matching suffix
s=. (p { weights) I. ?t
phrase=. phrase, s { suffixes
end.
 ;:inv phrase { words
)
Output:
   2 1 50 setstats 'http://paulo-jorente.de/text/alice_oz.txt'
genphrase''
got in as alice alice
genphrase''
perhaps even alice
genphrase''
pretty milkmaid alice

And, using 8 word suffixes (but limiting results to a bit over 50 words):

Output:
   2 8 50 setstats 'http://paulo-jorente.de/text/alice_oz.txt'
genphrase''
added it alice was beginning to get very tired of this i vote the young lady tells us alice was beginning to get very tired of being such a tiny little thing it did not take her long to find the one paved with yellow bricks within a short time
genphrase''
the raft through the water they got along quite well alice was beginning to get very tired of this i vote the young lady tells us alice was beginning to get very tired of being all alone here as she said this last word two or three times over to
genphrase''
gown that alice was beginning to get very tired of sitting by her sister on the bank and alice was beginning to get very tired of being such a tiny little thing it did so indeed and much sooner than she had accidentally upset the week before oh i beg

(see talk page for discussion of odd line wrapping with some versions of Safari)

Java[edit]

Translation of: Kotlin
Works with: Java version 8
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
 
public class MarkovChain {
private static Random r = new Random();
 
private static String markov(String filePath, int keySize, int outputSize) throws IOException {
if (keySize < 1) throw new IllegalArgumentException("Key size can't be less than 1");
Path path = Paths.get(filePath);
byte[] bytes = Files.readAllBytes(path);
String[] words = new String(bytes).trim().split(" ");
if (outputSize < keySize || outputSize >= words.length) {
throw new IllegalArgumentException("Output size is out of range");
}
Map<String, List<String>> dict = new HashMap<>();
 
for (int i = 0; i < (words.length - keySize); ++i) {
StringBuilder key = new StringBuilder(words[i]);
for (int j = i + 1; j < i + keySize; ++j) {
key.append(' ').append(words[j]);
}
String value = (i + keySize < words.length) ? words[i + keySize] : "";
if (!dict.containsKey(key.toString())) {
ArrayList<String> list = new ArrayList<>();
list.add(value);
dict.put(key.toString(), list);
} else {
dict.get(key.toString()).add(value);
}
}
 
int n = 0;
int rn = r.nextInt(dict.size());
String prefix = (String) dict.keySet().toArray()[rn];
List<String> output = new ArrayList<>(Arrays.asList(prefix.split(" ")));
 
while (true) {
List<String> suffix = dict.get(prefix);
if (suffix.size() == 1) {
if (Objects.equals(suffix.get(0), "")) return output.stream().reduce("", (a, b) -> a + " " + b);
output.add(suffix.get(0));
} else {
rn = r.nextInt(suffix.size());
output.add(suffix.get(rn));
}
if (output.size() >= outputSize) return output.stream().limit(outputSize).reduce("", (a, b) -> a + " " + b);
n++;
prefix = output.stream().skip(n).limit(keySize).reduce("", (a, b) -> a + " " + b).trim();
}
}
 
public static void main(String[] args) throws IOException {
System.out.println(markov("alice_oz.txt", 3, 200));
}
}
Output:
Emerald City is? Certainly, answered the Queen; but it is a lucky thing I am not, for my mouth is only painted, and if I ever get my heart? Or I my courage? asked the Lion in surprise, as he watched her pick up the Scarecrow and said: Come with me, for Oz has made me its ruler and the people gazed upon it with much curiosity. The Tin Woodman appeared to think deeply for a moment. Then he said, The Winkies were sorry to have them go, and they had grown so large in the last few minutes that she wasn't a bit afraid of interrupting him,) 'I'll give him sixpence. I don't believe there's an atom of meaning in it.' The jury all wrote down on their slates, and then added them up, and reduced the answer to it?' said the Mock Turtle. 'No, no! The adventures first,' said the Gryphon hastily. 'Go on with the next verse,' the Gryphon repeated impatiently: 'it begins I passed by his garden, and marked, with one eye,

Julia[edit]

Works with: Julia version 0.6
function markovtext(txt::AbstractString, klen::Integer, maxchlen::Integer)
words = matchall(r"\w+", txt)
dict = Dict()
for i in 1:length(words)-klen
k = join(words[i:i+klen-1], " ")
v = words[i+klen]
if haskey(dict, k)
dict[k] = push!(dict[k], v)
else
dict[k] = [v]
end
end
keytext = rand(collect(keys(dict)))
outtext = keytext
lasttext = outtext
while length(outtext) < maxchlen
lasttext = outtext
valtext = rand(dict[keytext])
outtext = outtext * " " * valtext
keytext = replace(keytext, r"^\w+\s+(.+)", s"\1") * " " * valtext
end
return lasttext
end
 
txt = readstring(download("http://paulo-jorente.de/text/alice_oz.txt"))
println(markovtext(txt, 3, 200))
Output:
Wizard could take upon himself and the Lion looking around him with joy Never have I seen a more
beautiful place It seems gloomy said the Scarecrow If it required brains to figure it out I never

Kotlin[edit]

// version 1.1.51
 
import java.io.File
import java.util.Random
 
val r = Random()
 
fun markov(filePath: String, keySize: Int, outputSize: Int): String {
if (keySize < 1) throw IllegalArgumentException("Key size can't be less than 1")
val words = File(filePath).readText().trimEnd().split(' ')
if (outputSize !in keySize..words.size) {
throw IllegalArgumentException("Output size is out of range")
}
val dict = mutableMapOf<String, MutableList<String>>()
 
for (i in 0..(words.size - keySize)) {
val key = words.subList(i, i + keySize).joinToString(" ")
val value = if (i + keySize < words.size) words[i + keySize] else ""
if (!dict.containsKey(key))
dict.put(key, mutableListOf(value))
else
dict[key]!!.add(value)
}
 
val output = mutableListOf<String>()
var n = 0
var rn = r.nextInt(dict.size)
var prefix = dict.keys.toList()[rn]
output.addAll(prefix.split(' '))
 
while (true) {
var suffix = dict[prefix]!!
if (suffix.size == 1) {
if (suffix[0] == "") return output.joinToString(" ")
output.add(suffix[0])
}
else {
rn = r.nextInt(suffix.size)
output.add(suffix[rn])
}
if (output.size >= outputSize) return output.take(outputSize).joinToString(" ")
n++
prefix = output.subList(n, n + keySize).joinToString(" ")
}
}
 
fun main(args: Array<String>) {
println(markov("alice_oz.txt", 3, 200))
}

Sample output:

but now, to her surprise, she found it was no longer green, but pure white. The ribbon around Toto's neck, and they started off in the right way. But at noon, when the sun was up, they started on their way, and soon saw a beautiful green glow in the sky just before them. On the other side of the garden, where Alice could see this, as she was near enough to look over their slates; 'but it doesn't matter which way you go,' said the King, looking round the court and got behind him, and very soon finished off the cake. 'Curiouser and curiouser!' cried Alice (she was so much disappointed; and the eyes winked again and looked upon her anxiously, as if the Great Oz himself, and driven him out of the room. The cook threw a frying-pan after her as she spoke. Alice did not quite know what to do next, when suddenly a White Rabbit with pink eyes ran close by her. There was nothing else to do, so Alice soon began talking again. 'Dinah'll miss me very much to-night, I should think!' (Dinah was the cat.) 'I hope they'll remember her saucer of milk at

Lua[edit]

Not sure whether this is correct, but I am sure it is quite inefficient. Also not written very nicely.

Computes keys of all lengths <= N. During text generation, if a key does not exist in the dictionary, the first (least recent) word is removed, until a key is found (if no key at all is found, the program terminates).

local function pick(t)
local i = math.ceil(math.random() * #t)
return t[i]
end
 
local n_prevs = tonumber(arg[1]) or 2
local n_words = tonumber(arg[2]) or 8
 
local dict, wordset = {}, {}
local prevs, pidx = {}, 1
 
local function add(word) -- add new word to dictionary
local prev = ''
local i, len = pidx, #prevs
 
for _ = 1, len do
i = i - 1
if i == 0 then i = len end
 
if prev ~= '' then prev = ' ' .. prev end
prev = prevs[i] .. prev
local t = dict[prev]
if not t then
t = {}
dict[prev] = t
end
t[#t+1] = word
end
end
 
for line in io.lines() do
for word in line:gmatch("%S+") do
wordset[word] = true
add(word)
prevs[pidx] = word
pidx = pidx + 1; if pidx > n_prevs then pidx = 1 end
end
end
add('')
 
local wordlist = {}
for word in pairs(wordset) do
wordlist[#wordlist+1] = word
end
wordset = nil
 
math.randomseed(os.time())
math.randomseed(os.time() * math.random())
local word = pick(wordlist)
local prevs, cnt = '', 0
 
--[[ print the dictionary
for prevs, nexts in pairs(dict) do
io.write(prevs, ': ')
for _,word in ipairs(nexts) do
io.write(word, ' ')
end
io.write('\n')
end
]]

 
for i = 1, n_words do
io.write(word, ' ')
 
if cnt < n_prevs then
cnt = cnt + 1
else
local i = prevs:find(' ')
if i then prevs = prevs:sub(i+1) end
end
if prevs ~= '' then prevs = prevs .. ' ' end
prevs = prevs .. word
 
local cprevs = ' ' .. prevs
local nxt_words
repeat
local i = cprevs:find(' ')
if not i then break end
cprevs = cprevs:sub(i+1)
if DBG then io.write('\x1b[2m', cprevs, '\x1b[m ') end
nxt_words = dict[cprevs]
until nxt_words
 
if not nxt_words then break end
word = pick(nxt_words)
end
io.write('\n')
 
Output:
> ./markov.lua <alice_oz.txt 3 200
hugged the soft, stuffed body of the Scarecrow in her arms instead of kissing his
painted face, and found she was crying herself at this sorrowful parting from her
loving comrades. Glinda the Good stepped down from her ruby throne to give the
prizes?' quite a chorus of voices asked. 'Why, she, of course,' said the Dodo,
pointing to Alice with one finger; and the whole party look so grave and
anxious.) Alice could think of nothing else to do, and perhaps after all it might
tell her something worth hearing. For some minutes it puffed away without
speaking, but at last it sat down a good way off, panting, with its tongue
hanging out of its mouth again, and said, 'So you think you're changed, do you?'
'I'm afraid I don't know one,' said Alice, rather alarmed at the proposal. 'Then
the Dormouse shall!' they both cried. 'Wake up, Dormouse!' And they pinched it
on both sides at once. The Dormouse slowly opened his eyes. 'I wasn't asleep,' he
said in a low voice, 'Why the fact is, you see, Miss, we're doing our best, afore
she comes, to-' At this moment Five, who had been greatly interested in

Perl 6[edit]

Works with: rakudo version 2017-01
unit sub MAIN ( :$text=$*IN, :$n=2, :$words=100, );
 
sub add-to-dict ( $text, :$n=2, ) {
my @words = $text.words;
my @prefix = @words.rotor: $n => -$n+1;
 
(%).push: @prefix Z=> @words[$n .. *]
}
 
my %dict = add-to-dict $text, :$n;
my @start-words = %dict.keys.pick.words;
my @generated-text = lazy |@start-words, { %dict{ "@_[ *-$n .. * ]" }.pick } ...^ !*.defined;
 
put @generated-text.head: $words;
 
>perl6 markov.p6 <alice_oz.txt --n=3 --words=200
Scarecrow. He can't hurt the straw. Do let me carry that basket for you. I shall not mind it, for I can't get tired. I'll tell you what I think, said the little man. Give me two or three pairs of tiny white kid gloves: she took up the fan and gloves, and, as the Lory positively refused to tell its age, there was no use in saying anything more till the Pigeon had finished. 'As if it wasn't trouble enough hatching the eggs,' said the Pigeon; 'but I must be very careful. When Oz gives me a heart of course I needn't mind so much. They were obliged to camp out that night under a large tree in the wood,' continued the Pigeon, raising its voice to a whisper. He is more powerful than they themselves, they would surely have destroyed me. As it was, I lived in deadly fear of them for many years; so you can see for yourself. Indeed, a jolly little clown came walking toward them, and Dorothy could see that in spite of all her coaxing. Hardly knowing what she did, she picked up a little bit of stick, and held it out to

Phix[edit]

This was fun! (easy, but fun)

integer fn = open("alice_oz.txt","rb")
string text = get_text(fn)
close(fn)
sequence words = split(text)
 
function markov(integer n, m)
integer dict = new_dict(), ki
sequence key, data, res
string suffix
for i=1 to length(words)-n do
key = words[i..i+n-1]
suffix = words[i+n]
ki = getd_index(key,dict)
if ki=0 then
data = {}
else
data = getd_by_index(ki,dict)
end if
setd(key,append(data,suffix),dict)
end for
integer start = rand(length(words)-n)
key = words[start..start+n-1]
res = key
for i=1 to m do
ki = getd_index(key,dict)
if ki=0 then exit end if
data = getd_by_index(ki,dict)
suffix = data[rand(length(data))]
res = append(res,suffix)
key = append(key[2..$],suffix)
end for
return join(res)
end function
 
?markov(2,100)
Output:

from the alice_oz.txt file:

"serve me a heart, said the Gryphon. \'Then, you know,\' Alice gently remarked; \'they\'d have been ill.\' \'So they were,\' said the
Lion. One would almost suspect you had been running too long. They found the way to send me back to the imprisoned Lion; but every day 
she came upon a green velvet counterpane. There was a long sleep you\'ve had!\' \'Oh, I\'ve had such a capital one for catching mice-oh, 
I beg your pardon!\' cried Alice hastily, afraid that she was shrinking rapidly; so she felt lonely among all these strange people. Her 
tears seemed to Alice a good dinner."

Python[edit]

Markov text generator - Python implementation.
Usage: markov.py source.txt context length

#Import libraries.
import sys
import random
 
#Read a file and return its contents.
def readdata(file):
with open(file) as f:
contents = f.read()
return contents
 
#Make a markov rule for given data.
def makerule(data, context):
rule = {}
words = data.split(' ')
index = context
 
for word in words[index:]:
key = ' '.join(words[index-context:index])
if key in rule:
rule[key].append(word)
else:
rule[key] = [word]
index += 1
 
return rule
 
#Use a markov rule to create a string.
def makestring(rule, length):
oldwords = random.choice(list(rule.keys())).split(' ')#random starting words
string = ' '.join(oldwords) + ' '
 
for i in range(length):
try:
key = ' '.join(oldwords)
newword = random.choice(rule[key])
string += newword + ' '
 
for word in range(len(oldwords)):
oldwords[word] = oldwords[(word + 1) % len(oldwords)]
oldwords[-1] = newword
 
except KeyError:
return string
return string
 
#Main program
data = readdata(sys.argv[1])
rule = makerule(data, int(sys.argv[2]))
string = makestring(rule, int(sys.argv[3]))
print(string)
Output:
marry the pretty milkmaid was much pleased to have her little dog free. The other trees of
the Gates they had at the rapid flight of the castle to yourself. I have my shoulders got
to? And oh, I wish you were me?' 'Well, perhaps not,' said the Scarecrow fell off the
cake.'Curiouser and curiouser!' cried Alice (she was obliged to say to this: so she set to
work, so you have killed the Wicked Witch in all their simple joys, remembering her own
the Silver Shoes, began to work; and he did open his mouth, for his release, for he was
obliged to go on with the Wizard. What shall we do? asked the Witch, sinking her voice
sounded hoarse and strange, and the reason is-' here the country of the land of the court,
arm-in-arm with the name 'Alice!' 'Here!' cried Alice, quite forgetting that she could
remember them, all these strange people. Her tears seemed to be full of tears, until there
was no time to think about stopping herself before she gave her answer. 'They're done with
a deep groan near by. What was that? she asked the girl. Again the eyes move and the Tin
Woodman can chop it down, and felt quite strange at first; but she laughed heartily at the
Scarecrow. The Witch did not have lived much under the window, engaged in a grieved tone;
you're a humbug? asked Dorothy. A balloon, said Oz, for I have no right to command them
once