マルコフ連鎖：SQLデータベースとJavaの表現

Question

今、この質問はあいまいです。私は、ユーザーが入力したテキストを解析して生成したテキストベースのマルコフチェーンを持っています。それは、シーケンスの現在の単語に基づいてテキストシーケンス内の次の単語である確率を格納することによって、ちょっとばかばかしい言葉を生成するのに使用されます。 JavaScriptでは、このオブジェクトは、次のようなものになります。現在の単語が変圧器である場合

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 
    } 
    // ... 
} 

ので、例えば、我々は生成次の単語があること、映画の95％のチャンスがありますし、そして2.5それぞれ猫や犬の確率。

私の質問は2つあり：

• Javaでこのオブジェクトを表現する最良の方法は何ですか？私が気に入っているのは、高速アクセスについては50％、メモリ使用については50％です。
• このオブジェクトをどのようにして単一のデータベーステーブル（たとえばMySQL）に格納しますか？

アップデート：@のbiziclopの答えに応じて、およびSanjayTSharmaさんのコメント@、私のクラスの下に私が書いてしまいました（それは、MITライセンス進行中の作業だそれは現在唯一の一次マルコフ連鎖を生成

。

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<String, TreeMap<String, Float>> chain; 
    Set<String> 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<String, TreeMap<String, Float>>)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<String, Float> 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 <= 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() <= 0) return; 
     if(n <= 0) return; 

     chain = new HashMap<String, TreeMap<String, Float>>(); 
     known_words = new HashSet<String>(); 
     rand = new Random(new Date().getTime()); 

     /** Generate the Markov Chain! **/ 
     StringTokenizer st = new StringTokenizer(input_text); 

     while (st.hasMoreTokens()) { 
      String word = st.nextToken(); 
      TreeMap<String, Float> wordmap = new TreeMap<String, Float>(); 

      // 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! 
    } 
} 

Answer 1

Javaでそれを格納することにより、私はあなたからシーケンスを生成するのは簡単だ方法でそれを保存する考えを推測しているが。

まずあなたは言葉が鍵であることと、ハッシュマップを必要とザこのハッシュマップの値はキーがあるツリーマップになります累積確率を計算し、値は次の単語である。

だから、のようなものになります。

HashMap<String, TreeMap<Double, String>> words = new HashMap<String, TreeMap<Double,String>>(); 

    TreeMap<Double, String> appleMap = new TreeMap<Double, String>(); 
    appleMap.put(0.2d, "cake"); 
    appleMap.put(1.0d, "sauce"); 
    words.put("apple", appleMap); 

    TreeMap<Double, String> transformerMap = new TreeMap<Double, String>(); 
    transformerMap.put(0.95d, "movie"); 
    transformerMap.put(0.975d, "cat"); 
    transformerMap.put(1.0d, "dog"); 
    words.put("transformer", transformerMap); 

それは、この構造から次の単語を生成することは非常に簡単です。

private String generateNextWord(HashMap<String, TreeMap<Double, String>> words, String currentWord) { 
    TreeMap<Double, String> probMap = words.get(currentWord); 
    double d = Math.random(); 
    return probMap.ceilingEntry(d).getValue(); 
} 

リレーショナルデータベースでは、現在の単語、次の単語、および重みの3つの列を持つ単一の表を持つことができます。あなたは基本的にあなたのマルコフ連鎖の状態遷移グラフのエッジを保存しています

単語idsに対する単語を保存するための頂点テーブルと現在の単語IDを格納する頂点テーブルの2つのテーブルに正規化することもできます。あなたの言葉で余分なフィールドを保存しない限り、これは必要ではないと私は思います。