0
\$\begingroup\$

I have this small program that constructs a Markov chain from Tolstoy's War and Peace and allows the user to play with it by generating sentences of variable length in words.

MarkovChain.java

package net.coderodde.markovapp;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import java.util.Set;

public final class MarkovChain {

    /**
     * Number of words per state.
     */
    private final int k;

    /**
     * The array of words.
     */
    private final String[] words;

    /**
     * State transition function. 
     */
    private final Map<List<String>, Map<List<String>, Integer>> map = 
            new HashMap<>();

    /**
     * Maps to each state the number of its following states.
     */
    private final Map<List<String>, Integer> totalCountMap = new HashMap<>();

    /**
     * The list of all states.
     */
    private final List<List<String>> vocabulary = new ArrayList<>();

    private final Random random;

    public MarkovChain(String[] words, int k, Random random) {
        this.words = Objects.requireNonNull(words, "Word array is null.");
        this.k = checkPositive(k);

        if (words.length < k) {
            throw new IllegalArgumentException("number of words < k");
        }

        this.random = Objects.requireNonNull(random, "The random is null.");
        build();
    }

    public MarkovChain(String[] words, int k) {
        this(words, k, new Random());
    }

    public String[] compose(int numberOfWords) {
        checkRequestedNumberOfWords(numberOfWords);
        List<String> startState = 
                vocabulary.get(random.nextInt(vocabulary.size()));

        String[] outputWords = new String[numberOfWords];
        numberOfWords -= k;

        for (int i = 0; i < startState.size(); ++i) {
            outputWords[i] = startState.get(i);
        }

        int index = k;

        while (numberOfWords-- > 0) {
            List<String> nextState = randomTransition(startState);
            outputWords[index++] = lastOf(nextState);
            startState = nextState;
        }

        return outputWords;
    }

    private static <T> T lastOf(List<T> list) {
        return list.get(list.size() - 1);
    }

    private List<String> randomTransition(List<String> startState) {
        Map<List<String>, Integer> localMap = map.get(startState);

        if (localMap == null) {
            return vocabulary.get(random.nextInt(vocabulary.size()));
        }

        int choices = totalCountMap.get(startState);
        int coin = random.nextInt(choices);

        for (Map.Entry<List<String>, Integer> entry : localMap.entrySet()) {
            if (coin < entry.getValue()) {
                return entry.getKey();
            }

            coin -= entry.getValue();
        }

        throw new IllegalStateException("Should not get here");
    }

    private void build() {
        Set<List<String>> filter = new HashSet<>();
        Deque<String> wordDeque = new ArrayDeque<>();

        for (int i = 0; i < k; ++i) {
            wordDeque.addLast(words[i]);
        }

        for (int i = k; i < words.length; ++i) {
            List<String> startSentence = new ArrayList<>(wordDeque);
            filter.add(startSentence);

            wordDeque.removeFirst();
            wordDeque.addLast(words[i]);
            List<String> nextSentence = new ArrayList<>(wordDeque);

            Map<List<String>, Integer> localMap = map.get(startSentence);

            if (localMap == null) {
                map.put(startSentence, localMap = new HashMap<>());
            }

            localMap.put(nextSentence,
                         localMap.getOrDefault(nextSentence, 0) + 1);

            totalCountMap.put(startSentence, 
                              totalCountMap.getOrDefault(startSentence, 0) + 1);
        }

        vocabulary.addAll(filter);
    }

    private int checkPositive(int k) {
        if (k < 1) {
            throw new IllegalArgumentException("k < 1");
        }

        return k;
    }

    private void checkRequestedNumberOfWords(int numberOfWords) {
        if (numberOfWords < k) {
            throw new IllegalArgumentException(
                    "The minimum number of words for composition should be " +
                    k + ". Received " + numberOfWords);
        }
    }
}

TextFileDownloader.java

package net.coderodde.markovapp;

import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.Objects;
import java.util.Scanner;

public final class TextFileDownloader {

    private final String urlText;

    public TextFileDownloader(String urlText) {
        this.urlText = Objects.requireNonNull(urlText, "The URL text is null.");
    }

    public String download() {
        try {
            URL url = new URL(urlText);
            StringBuilder sb = new StringBuilder();
            Scanner scanner = new Scanner(url.openStream());

            while (scanner.hasNextLine()) {
                sb.append(scanner.nextLine());
            }

            return sb.toString();
        } catch (MalformedURLException ex) {
            throw new IllegalStateException("Bad URL", ex);
        } catch (IOException ex) {
            throw new RuntimeException("IO failed", ex);
        }
    }
}

App.java

package net.coderodde.markovapp;

import java.util.Scanner;

public class App {

    private static final int WORDS_PER_STATE = 2;

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        TextFileDownloader fileDownloader = 
                new TextFileDownloader(
                        "http://www.gutenberg.org/files/2600/2600-0.txt");

        String text = fileDownloader.download();
        long end = System.currentTimeMillis();

        outputWithDuration("Downloaded War and Peace in ", start, end);

        start = System.currentTimeMillis();
        String[] words = text.split("(\\s|\\W)+");
        setWordsToLowerCase(words);
        end = System.currentTimeMillis();

        outputWithDuration("Text preprocessing took ", start, end);

        start = System.currentTimeMillis();
        MarkovChain mc = new MarkovChain(words, WORDS_PER_STATE);
        end = System.currentTimeMillis();

        outputWithDuration("Building Markov chain took ", start, end);
        Scanner scanner = new Scanner(System.in);
        System.out.print("> ");

        while (scanner.hasNextInt()) {
            int sentenceLengthInWords = scanner.nextInt();
            System.out.println(concat(mc.compose(sentenceLengthInWords)));
            System.out.print("> ");
        }
    }

    private static void outputWithDuration(String text, long start, long end) {
        System.out.println(text + (end - start) + " milliseconds.");
    }

    private static String concat(String... strings) {
        StringBuilder sb = new StringBuilder();
        String separator = "";

        for (String string : strings) {
            sb.append(separator);
            separator = " ";
            sb.append(string);
        }

        return sb.toString();
    }

    private static void setWordsToLowerCase(String[] words) {
        for (int i = 0; i < words.length; ++i) {
            words[i] = words[i].toLowerCase();
        }
    }
}

Critique request

Please tell me anything that comes to mind. Also, I believe that splitting the text into words can be improved since some words end up "glueed": heis, goingto, etc.

\$\endgroup\$
1
\$\begingroup\$

Your concat method can be simplified with JDK 8:

private static String concat(String... strings) {
    return String.join(" ", strings);
}

And you never close your Scanner in TextFileDownloader.

Your "glueed" words do not come from incorrect splitting but from non-optimal processing in TextFileDownloader: Whenever a line does not end with a space, you are glueing together the last word from the current line with the first word of the next.

A better (still not perfect) approach could be to first read all separate lines and join them together afterwards:

public String download() {
    try {
        URL url = new URL(urlText);
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()))) {
            return reader.lines().collect(Collectors.joining(" "));
        } catch (IOException ex) {
            throw new RuntimeException("IO failed", ex);
        }
    } catch (MalformedURLException ex) {
        throw new IllegalStateException("Bad URL", ex);
    }
}

This also makes use of JDK 7's new try-with-resources statement, which makes dealing with resources much less cumbersome.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.