Chaîne de Markov: base de données SQL et représentation Java

Question

Maintenant, cette question est un peu obscure. J'ai une chaîne markov basée sur le texte que j'ai générée en analysant le texte tapé par l'utilisateur. Il est utilisé pour générer une chaîne de charabia presque cohérente et fonctionne en stockant la probabilité d'un mot donné étant le mot suivant dans une séquence de texte, en fonction du mot courant dans la séquence. En javascript, cet objet ressemblerait à quelque chose comme ce qui suit:

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

Ainsi, par exemple, si le mot courant est transformateur, le mot suivant que nous générons aura une probabilité de 95% d'être film, et 2,5 % de chance d'être chat ou chien respectivement.

Ma question est double:

• Quelle est la meilleure façon de représenter cet objet en Java? Meilleur que je me soucie de 50% de l'accès rapide et de 50% de l'utilisation de la mémoire
• Comment stocker cet objet dans une seule table de base de données (par exemple MySQL)?

Mise à jour:.. En réponse à @ biziclop de la réponse, et @ commentaire de SanjayTSharma, au-dessous de ma classe, je fini par écrire (c'est un travail en cours, licence MIT Il génère actuellement que de premier ordre Chaînes de Markov

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

en les stockant en Java, je devine que vous pensez stocker d'une manière qui est facile de générer une séquence de.

d'abord, vous avez besoin d'un hashmap, les mots étant les clés. Le les valeurs de ce hashmap sera un treemap avec les clés soient la probabilité cumulée et la valeur étant le mot suivant.

donc ce sera quelque chose comme:

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); 

Il est très facile de générer le mot suivant de cette structure.

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(); 
} 

Dans une base de données relationnelle, vous pouvez simplement avoir une seule table avec trois colonnes: mot courant, mot suivant et poids. Vous pouvez donc stocker les bords du graphique de transition d'état de votre chaîne de Markov

Vous pouvez également le normaliser en deux tables: une table de sommets pour stocker les mots par rapport aux identifiants de mots et une table de périphérie qui stocke l'identifiant de mot actuel, mot et poids du mot suivant, mais à moins que vous ne souhaitiez stocker des champs supplémentaires avec vos mots, je ne pense pas que cela soit nécessaire.