title: Markov Chain Text Generation
body: <p>We were just assigned a new project in my data structures class -- Generating text with markov chains. </p>
  
  <p><strong>Overview</strong></p>
  
  <p>Given an input text file, we create an initial seed of length n characters.  We add that to our output string and choose our next character based on frequency analysis..</p>
  
  <blockquote>
    <p>This is the cat and there are two dogs.</p>
  </blockquote>
  
  <pre><code>Initial seed: "Th"
  Possible next letters -- i, e, e
  Therefore, probability of choosing i is 1/3, e is 2/3.
  
  Now, say we choose i. We add "i" to the output string. Then our seed becomes
  hi and the process continues.
  </code></pre>
  
  <p><strong>My solution</strong></p>
  
  <p>I have 3 classes, Node, ConcreteTrie, and Driver</p>
  
  <p>Of course, the ConcreteTrie class isn't a Trie of the traditional sense.  Here is how it works:</p>
  
  <p>Given the sentence with k=2:</p>
  
  <blockquote>
    <p>This is the cat and there are two dogs.</p>
  </blockquote>
  
  <p>I generate Nodes Th, hi, is, ... + ... , gs, s.
  Each of these nodes have children that are the letter that follows them.  For example, Node Th would have children i and e.  I maintain counts in each of those nodes so that I can later generate the probabilities for choosing the next letter.</p>
  
  <p><strong>My question:</strong></p>
  
  <p>First of all, what is the most efficient way to complete this project?  My solution seems to be very fast, but I really want to knock my professor's socks off.  (On my last project A variation of the Edit distance problem, I did an A*, a genetic algorithm, a BFS, and Simulated Annealing -- and I know that the problem is NP-Hard)</p>
  
  <p>Second, what's the point of this assignment?  It doesn't really seem to relate to much of what we've covered in class.  What are we supposed to learn?</p>