markov.java

JAVA編寫的馬可夫鏈程式

/* Copyright 2003 by Lawrence Kesteloot */

package com.teamten.a;

import java.io.Reader;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.Set;
import java.util.Random;

/**
 * A Markov chain for characters.  For each set of prefix strings,
 * keeps track of possible next characters and the probability
 * of going to each.
 */

class Markov
{
    /**
     * Map from the prefix string (String) to list of characters
     * (Chain).
     */

    private Map map;
    private String bootstrapPrefix;

    /**
     * Creates a chain based on the Reader with a prefix of
     * length "length".  Reads the entire input stream and
     * creates the Markov chain.
     */

    public Markov(Reader in, int length) throws java.io.IOException
    {
        map = new HashMap();

        CharQueue queue = new CharQueue(length);
        int c;

        for (int i = 0; i < length; i++)
        {
            c = in.read();
            if (c == -1)
            {
                System.out.println("Input is too short");
                return;
            }

            queue.put((char)c);
        }

        bootstrapPrefix = queue.toString();

        // for collapsing whitespace
        boolean wasWhitespace = false;

        while ((c = in.read()) != -1)
        {
            if (Character.isWhitespace((char)c))
            {
                if (wasWhitespace)
                {
                    // collapse continuous whitespace
                    continue;
                }

                c = ' ';
                wasWhitespace = true;
            }
            else
            {
                wasWhitespace = false;
            }

            String prefix = queue.toString();

            Chain chain = (Chain)map.get(prefix);
            if (chain == null)
            {
                chain = new Chain(prefix);
                map.put(prefix, chain);
            }

            chain.add((char)c);
            queue.put((char)c);
        }
    }

    /**
     * Returns the first "length" characters that were read.
     */

    public String getBootstrapPrefix()
    {
        return bootstrapPrefix;
    }

    /**
     * Returns the next character to print given the prefix.
     * Returns -1 when there are no possible next characters.
     */

    public int get(String prefix, Random random)
    {
        Chain chain = (Chain)map.get(prefix);

        if (chain == null)
        {
            return -1;
        }

        int index = random.nextInt(chain.getTotal());

        return chain.get(index);
    }

    /**
     * Prints the contents of the Markov graph.
     */

    public void dump()
    {
        Set keys = map.keySet();

        Iterator i = keys.iterator();
        while (i.hasNext())
        {
            String prefix = (String)i.next();
            Chain chain = (Chain)map.get(prefix);

            chain.dump();
        }
    }

    /**
     * List of possible next characters and their probabilities.
     */

    private static class Chain
    {
        private String prefix;
        private int total;
        private List list;

        public Chain(String prefix)
        {
            this.prefix = prefix;
            total = 0;
            list = new LinkedList();
        }

        public String getPrefix()
        {
            return prefix;
        }

        public int getTotal()
        {
            return total;
        }

        public char get(int index)
        {
            Iterator i = list.iterator();

            while (i.hasNext())
            {
                Link link = (Link)i.next();
                int count = link.getCount();

                if (index < count)
                {
                    return link.getChar();
                }

                index -= count;
            }

            // weird
            return '@';
        }

        public void add(char c)
        {
            Iterator i = list.iterator();
            boolean found = false;

            while (i.hasNext())
            {
                Link link = (Link)i.next();

                if (c == link.getChar())
                {
                    link.increment();
                    found = true;
                    break;
                }
            }

            if (!found)
            {
                Link link = new Link(c);
                list.add(link);
            }

            total++;
        }

        public void dump()
        {
            System.out.println(prefix + ": (" + total + ")");

            Iterator i = list.iterator();

            while (i.hasNext())
            {
                Link link = (Link)i.next();

                System.out.println("    " + link.getChar() + " (" +
                        link.getCount() + ")");
            }
        }

        /**
         * Possible next character and the number of times we've
         * seen it.
         */

        private static class Link
        {
            private char c;
            private int count;

            public Link(char c)
            {
                this.c = c;
                count = 1;
            }

            public void increment()
            {
                count++;
            }

            public int getCount()
            {
                return count;
            }

            public char getChar()
            {
                return c;
            }
        }
    }
}