Markov chain text generator

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++

In this implementation there is no repeated suffixes!

<lang cpp>

1. include <ctime>
2. include <iostream>
3. include <algorithm>
4. include <fstream>
5. include <string>
6. include <vector>
7. 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;

} </lang>

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