title: Markov Chain: SQL Database and Java Representation
body: <p>Now this question is a bit obscure. I have a text-based markov chain that I've generated by parsing user-typed text. It is used to generate an almost-coherent string of gibberish and works by storing the probability of a given word being the next word in a text sequence, based on the current word in the sequence. In javascript, this object would look something like the following:</p>
  
  <pre><code>var text_markov_chain = {
      "apple" : {
          "cake" : 0.2,
          "sauce" : 0.8
      },
      "transformer" : {
          "movie" : 0.95,
          "cat" : 0.025,
          "dog" : 0.025
      }
      "cat" : {
          "dog : 0.5,
          "nap" : 0.5
      }
      // ...
  }
  </code></pre>
  
  <p>So, for example, if the current word is transformer, then the next word we generate will have a 95% chance of being movie, and a 2.5% chance of being cat or dog respectively.</p>
  
  <p>My question is twofold:</p>
  
  <ul>
  <li>What is the best way of representing this object in Java? Best as in I care 50% about fast access and 50% about memory usage</li>
  <li>How would I store this object in a single database table (for example MySQL)?</li>
  </ul>
  
  <p><strong>Update: In response to @biziclop's answer, and @SanjayTSharma's comment, below my class I ended up writing (it's a work in progress, MIT license. It currently only generates first-order Markov Chains.</strong></p>
  
  <pre><code>import java.io.IOException;
  import java.io.InputStream;
  import java.io.ObjectInputStream;
  import java.util.Date;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Random;
  import java.util.Set;
  import java.util.StringTokenizer;
  import java.util.TreeMap;
  
  public class MarkovChain {
      HashMap&lt;String, TreeMap&lt;String, Float&gt;&gt; chain;
      Set&lt;String&gt; known_words;
      Random rand;
  
      /**
       * Generates a first order Markov Chain from the given text
       * @param input_text The text to parse
       */
      public MarkovChain(String input_text) {
          init(input_text, 1);
      }
  
      /**
       * Generates a nth order Markov Chain from the given text
       * @param input_text The text to parse
       * @param n The order of the Markov Chain
       */
      public MarkovChain(String input_text, int n) {
          init(input_text, n);
      }
  
      /**
       * Reads a Markov Chain from the given input stream. The object is assumed
       * to be binary and serialized
       * @param in The input stream, eg from a network port or file
       */
      public MarkovChain(InputStream in) {
          try {
              ObjectInputStream ob_in = new ObjectInputStream(in);
              chain = (HashMap&lt;String, TreeMap&lt;String, Float&gt;&gt;)ob_in.readObject();
              known_words = chain.keySet();
              ob_in.close();
              in.close();
          } catch (IOException e) {
              //e.printStackTrace();
              chain = null;
              known_words = null;
          } catch (ClassNotFoundException e) {
              //e.printStackTrace();
              chain = null;
              known_words = null;
          }
      }
  
      /**
       * Returns the next word, according to the Markov Chain probabilities 
       * @param current_word The current generated word
       */
      public String nextWord(String current_word) {
          if(current_word == null) return nextWord();
  
          // Then head off down the yellow-markov-brick-road
          TreeMap&lt;String, Float&gt; wordmap = chain.get(current_word);
          if(wordmap == null) {
              /* This *shouldn't* happen, but if we get a word that isn't in the
               * Markov Chain, choose another random one
               */
              return nextWord();
          }
  
          // Choose the next word based on an RV (Random Variable)
          float rv = rand.nextFloat();
          for(String word : wordmap.keySet()) {
              float prob = wordmap.get(word);
              rv -= prob;
              if(rv &lt;= 0) {
                  return word;
              }
          }
  
          /* We should never get here - if we do, then the probabilities have
           * been calculated incorrectly in the Markov Chain
           */
          assert false : "Probabilities in Markov Chain must sum to one!";
          return null;
      }
  
      /**
       * Returns the next word when the current word is unknown, irrelevant or
       * non existant (at the start of the sequence - randomly picks from known_words
       */
      public String nextWord() {
          return (String) known_words.toArray()[rand.nextInt(known_words.size())];
      }
  
      private void init(String input_text, int n) {
          if(input_text.length() &lt;= 0) return;
          if(n &lt;= 0) return;
  
          chain = new HashMap&lt;String, TreeMap&lt;String, Float&gt;&gt;();
          known_words = new HashSet&lt;String&gt;();
          rand = new Random(new Date().getTime());
  
          /** Generate the Markov Chain! **/
          StringTokenizer st = new StringTokenizer(input_text);
  
          while (st.hasMoreTokens()) {
              String word = st.nextToken();
              TreeMap&lt;String, Float&gt; wordmap = new TreeMap&lt;String, Float&gt;();
  
              // First check if the current word has previously been parsed
              if(known_words.contains(word)) continue;
              known_words.add(word);
  
              // Build the Markov probability table for this word
              StringTokenizer st_this_word = new StringTokenizer(input_text);
              String previous = "";
              while (st_this_word.hasMoreTokens()) {
                  String next_word = st_this_word.nextToken();
  
                  if(previous.equals(word)) {
                      if(wordmap.containsKey(next_word)) {
                          // Increment the number of counts for this word by 1
                          float num = wordmap.get(next_word);
                          wordmap.put(next_word, num + 1);
                      } else {
                          wordmap.put(next_word, 1.0f);
                      }
                  }
  
                  previous = next_word;
              } // End while (st_this_word.hasMoreTokens())
  
              /* The wordmap now contains a map of words and the number of occurrences they have.
               * We need to convert this to the probability of getting that word by dividing
               * by the total number of words there were
               */
              int total_number_of_words = wordmap.values().size();
              for(String k : wordmap.keySet()) {
                  int num_occurances = wordmap.get(k).intValue();
                  wordmap.put(k, 1.0f*num_occurances/total_number_of_words);
              }
  
              // Finally, we are ready to add this word and wordmap to the Markov chain
              chain.put(word, wordmap);
  
          } // End while (st.hasMoreTokens())
  
          // The (first order) Markov Chain has now been built!
      }
  }
  </code></pre>