a.java

JAVA編寫的馬可夫鏈程式

/* Copyright 2003 by Lawrence Kesteloot */

package com.teamten.a;

import java.io.FileReader;
import java.io.Reader;
import java.util.Random;

/**
 * Creates a Markov graph from an input file and generates text
 * based on it.  Given two input files, generates two graphs
 * and interpolates between them.
 */

public class A {
    private static final int DEFAULT_PREFIX_LENGTH = 4;
    private static final int LINE_WIDTH = 65;
    private static final int TOTAL_CHARACTERS = 300;

    private static Markov loadMarkov(String filename, int prefixLength)
    {

        FileReader input;
        try
        {
            input = new FileReader(filename);
        }
        catch (java.io.FileNotFoundException e)
        {
            System.out.println("File not found: \"" + filename +
                "\" (" + e + ")");
            return null;
        }

        Markov markov;

        try
        {
            markov = new Markov(input, prefixLength);
        }
        catch (java.io.IOException e)
        {
            System.out.println("Cannot read from \"" + filename +
                "\" (" + e + ")");
            return null;
        }

        return markov;
    }

    private static void usage()
    {
        System.out.println("Usage: A [--prefix n] [--html] input.txt [other.txt]");
    }

    public static void main(String[] args)
    {
        int prefixLength = DEFAULT_PREFIX_LENGTH;
        boolean highlightHTML = false;
        Markov markov1 = null;
        Markov markov2 = null;

        for (int i = 0; i < args.length; i++)
        {
            if (args[i].equals("--prefix"))
            {
                try
                {
                    prefixLength = Integer.parseInt(args[1]);
                }
                catch (Exception e)
                {
                    usage();
                    return;
                }
                i++;
            }
            else if (args[i].equals("--html"))
            {
                highlightHTML = true;
            }
            else if (markov1 == null)
            {
                markov1 = loadMarkov(args[i], prefixLength);
                if (markov1 == null)
                {
                    return;
                }
            }
            else if (markov2 == null)
            {
                markov2 = loadMarkov(args[i], prefixLength);
                if (markov2 == null)
                {
                    return;
                }
            }
            else
            {
                usage();
                return;
            }
        }

        if (markov1 == null)
        {
            usage();
            return;
        }

        Random random = new Random();
        CharQueue queue = new CharQueue(prefixLength);
        float weight = 0;

        queue.set(markov1.getBootstrapPrefix());
        System.out.print(queue.toString());
        int width = prefixLength;
        int c;

        do {
            boolean cameFromSecond = false;

            String prefix = queue.toString();

            // get a character from each chain
            c = markov1.get(prefix, random);
            int c2 = -1;
            if (markov2 != null)
            {
                c2 = markov2.get(prefix, random);
            }
            if (c == -1 && c2 == -1)
            {
                break;
            }

            // choose one if we can
            if (markov2 != null)
            {
                if (c == -1)
                {
                    c = c2;
                    cameFromSecond = true;
                } else if (c2 != -1 && random.nextFloat() < weight)
                {
                    c = c2;
                    cameFromSecond = true;
                }
            }

            if (cameFromSecond && highlightHTML)
            {
                System.out.print("<font color='red'>" + (char)c + "</font>");
            }
            else
            {
                System.out.print((char)c);
            }
            queue.put((char)c);
            width++;

            // line wrap
            if (c == ' ' && width > LINE_WIDTH)
            {
                System.out.println();
                width = 0;
            }

            // go towards second markov chain
            weight += 1.0/TOTAL_CHARACTERS;
        } while (weight < 1 || c != '.');

        System.out.println();
    }
}

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