Марковская цепь: база данных SQL и представление Java

Question

Теперь этот вопрос немного неясен. У меня есть текстовая цепочка markov, которую я сгенерировал, анализируя набранный пользователем текст. Он используется для генерации почти связной строки тарабарщины и работает путем сохранения вероятности того, что данное слово будет следующим словом в текстовой последовательности на основе текущего слова в последовательности. В 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% шанс быть кошкой или собакой соответственно.

У меня двоякий вопрос:

• Как лучше всего представить этот объект в 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 будут древовидной картой, ключами которой являются кумулятивная вероятность, а значением будет следующее слово.

Так что это будет что-то вроде:

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

В реляционной базе данных вы можете просто иметь одну таблицу с тремя столбцами: текущее слово, следующее слово и вес. Таким образом, вы в основном храните ребра графа переходов состояний вашей цепи Маркова

Вы также можете нормализовать его в две таблицы: таблицу вершин для хранения слов по идентификаторам слов и таблицу границ, в которой хранятся идентификатор текущего слова, идентификатор следующего слова и вес, но если вы не хотите хранить дополнительные поля со своими словами, Я не думаю, что это необходимо.