CMSC 132: Project (Random Text Generation)

Project #2 (Random Text Generation)	CMSC 132
Due Date: Mon Mar 3, 6:00 pm	Object-Oriented Programming II
Type of Homework: Closed	Spring 2008

Objective

The objective of this project to practice using the Java Collections Framework

This homework is considered a closed homework. Make sure you read the open/closed policy before continuing working on this project.

Project Clarifications

Any clarifications or corrections associated with this project will be available at:

http://www.cs.umd.edu/class/spring2008/cmsc132/projects/p2/clarifications.html

Overview

For this project you must implement the methods of the DenseBag and MarkovText classes. These methods will allow us to generate random text. You will need to design and write additional classes in order to help you implement the functionality of those two named classes. In particular, you will need to write two classes that implement the Iterator interface; one to provide an Iterator for DenseBag, and one to implement the functionality of the MarkovText.markovIterator(java.util.Random) method. You may use inner classes if you wish.

Documentation for this project can be found at javadoc documentation

Your project will be graded as follows:

Tests (90 %)
- Public JUnit tests (30 %)
- Release JUnit tests (60 %)
Student Tests (5 %)
Style (5 %)

Markov Chains

OK, we know about finite state machines. A first-order Markov chain is a system where states are chosen randomly, with the probability distribution for the next state being determined only by the current state. For example, you could model weather prediction as the following Markov chain:

If it is sunny today, there is a 90% chance it will be sunny tomorrow, otherwise it will be cloudy.
If it is cloudy today, there is a 50% chance it will be sunny tomorrow, otherwise it will be cloudy.

In a second-order Markov chain, the probability of each state is based on the previous two states; in a third-order Markov chain, the probability of each state is based on the previous three states. More pointers on Markov Chains at:

DenseBag class

As part of this project, you will implement a "Dense Bag". A bag is like a Set, but with repeats allowed. A dense bag is a bag where we expect to get lots of repeats. In this project, bags will contain words, so a typical "dense bag" might contain:

[170 occurrences of "cow", 200 occurrences of "dog", 1717 occurrences of "cat"]

Note that in the example above you will not actually store 170 separate copies of the word "cow" in your DenseBag object (nor will you even store 170 separate references to the word "cow") -- rather you will create just one copy, and associate the number 170 with this copy to keep track of the number of occurrences of "cow" that are supposed to be in the bag.

Read the javadoc for the DenseBag class to see what methods you must implement and what they must do. Note that for the DenseBag class, you need to go beyond the functionality needed for this project, and provide a good, general-purpose implementation of a DenseBag. We will be testing features of your DenseBag implementation that are not needed for the Markov chain text generation.

Markov Chain Text Generation

We are going to read in a corpus of text (also referred to as "training sequence"), and use that to build a Markov chain transition table. For example, using a third-order Markov transition table, we might find that the word sequence "what was the" occurs three times. Twice it is followed by "matter" and once by "cause". In generating new text, if we have a sequence of words ending in "what was the", then we randomly choose which word to add next. One third of the time, we choose "cause", and two thirds of the time we choose "matter".

Lots of people have had this idea, including:

Although lots of people have done this before, we are going to take our own, unique OO approach to the problem.

Creating an Order-n Markov "Transition Table"

Let's suppose we are going to generate random text based on the following input stream (also referred to as "training sequence").

This is a nice sentence. This is another sentence. This is another sentence.

From the list of words described above, the program will build a "transition table", which will be a map. For a markov chain of Order-n, the map will use Lists of n words as the keys. The values that the map assigns to the keys will be DenseBag objects containing words.

Here's how it works. Suppose we are generating a Markov Transition Table of Order-2. Let's consider a typical sequence of two words taken from the input in the example above. The sequence of two words [This, is] occurs in three places in the input. In two places, "This is" is followed by the word "another". In the other spot, "this is" is followed by "a". So in the transition table there would be an entry mapping the List [This, is] to a DenseBag containing [2 occurrences of "another", 1 occurrence of "a"].

As part of your design, you have to figure out how to define the first and last map entries associated with a training sequence. One possibility is to use the empty string (which never occurs in training sequences) as a special marker. For example, for an Order-1 Markov Transition Table trained on the sequence [ "a", "a", "b" ], we might generate the map:

    [""]  = {"a" = 1}

    ["a"] = {"a" = 1, "b" = 1}

    ["b"] = {"" = 1}

For an Order-2 Markov Transition Table trained on the sequence [ "a", "a", "a", "b" ], we would generate the map:

    ["", ""]   = {"a" = 1}

    ["", "a"]  = {"a" = 1}

    ["a", "a"] = {"a" = 1, "b" = 1}

    ["a", "b"] = {"" = 1}

For an Order-n Markov Transition Table, the first map entry will have a list of n empty strings mapped to the first word in the training sequence. The map list entry representing the end of the training sequence, will map to a dense bag that contains an empty string (regardless of the order used). Keep in mind that other strings besides the empty string can be associated with this list entry (see Order-2 Markov Chain example below).

Example

Below is the Transition Table for the Order-2 Markov Chain generated by the following text:

This is a nice sentence. This is another sentence. This is another sentence.

["",""]               = {"This" = 1}

["", This]            = {"is" = 1}

[This, is]            = {"a" = 1, "another" = 2}

[is, a]               = {"nice" = 1}

[a, nice]             = {"sentence." = 1}

[nice, sentence.]     = {"This" = 1}

[sentence., This]     = {"is" = 2}

[is, another]         = {"sentence." = 2}

[another, sentence.] = {"This" = 1, "" = 1}

Below is the transition table you would get if you were using Order-3.

["","",""]                 = {"This" = 1}

["","", This]              = {"is" = 1}

["", This, is]             = {"a" = 1}

[This, is, a]              = {"nice" = 1}

[is, a, nice]              = {"sentence." = 1}

[a, nice, sentence.]       = {"This" = 1}

[nice, sentence., This]    = {"is" = 1}

[sentence., This, is]      = {"another" = 2}

[This, is, another]        = {"sentence." = 2}

[is, another, sentence.]   = {"This" = 1, "" = 1}

[another, sentence., This] = {"is" = 1}

Your program should be able to generate a Markov Transition Table from a list of words using any order specified (1, 2, 3, 17, whatever...)

Generating Random Text using the Transition Table

Once your transition table is complete, you can use it to generate random text. Let's do an example using the Order-2 Transition Table described above.

To start things off, look up List ["",""] in the map. We get back a DenseBag containing [1 occurrence of "This"]. No choices here -- we will select the word "This" and now consider the list ["", This].
Okay, look up the List ["", This] in the map. We get back the DenseBag containing [1 occurrence of "is"]. Okay, still no choices. We take the word "is" and now consider the list [This, is].
Okay, look up the List [This, is] in the map. We get back the DenseBag containing [1 occurrence of "a", 2 occurrences of "another"]. This is where the randomization comes in! Since there are 3 total things in the bag, 1/3 of the time we will select the word "a" and 2/3 of the time we will select "another". Let's imagine that in this example we happened to choose "another". Now we'll consider [is, another].
Looking up [is, another] yields a dense bag containing [2 occurrences of "sentence."]. No choice here, we'll choose "sentence" and consider the List [another, sentence.]
Looking up [another, sentence.] yields a dense bag containing [1 occurrence of "This", 1 occurrence of ""]. Randomization will be used again! Since there are a total of 2 things in the bag, 1/2 of the time we will select "This" and 1/2 of the time we will select "". Let's imagine that in this example we happened to choose "". The process stops. If instead of "" we choose "This", then we will next consider [sentence.,This].

Additional Information

DenseBag choose( )
From the choose( ) method project documentation:
- Given a random number generator, randomly choose an element from the Bag according to the distribution of objects in the Bag (e.g., if a Bag contains 7 a's and 3 b's, then 70% of the time choose should return an a, and 30% of the time it should return a b). This operation can take time proportional to the number of unique objects in the Bag, but no more. This operation should not affect the Bag.
Your choose() method will be tested to ensure that:
- The results of choose( ) reflect the distribution of objects in the Bag. I.e., if a DenseBag contains 9 a's and 1 b, invoking choose( ) 100 times would yield around 90 a's and 10 b's.
- The algorithm you use for choose( ) is proportional to the # of unique elements, not the total # of elements. I.e., the choose( ) method should take about the same time for a DenseBag containing 10 a's and a DenseBag containing 10 million a's.
To generate random numbers, use the nextInt(int n) method of the class Random, which will return a random integer value between 0 and n-1 with uniform probability.

To randomly choose between events with different probabilities, you can assign events to different ranges of numbers corresponding to the probabilities, then select the event corresponding to the random number generated within this range.

Example:
- Given 3 events A(50%), B(45%), C(5%) & object r from class Random .
- Assign the range of values between 0-99 to A, B, C in some combination preserving their probability.
  - Assignment 1: A(0-49), B(50-94), C(95-99)
  - Assignment 2: C(0-4), B(5-49), A(50-99)
- Generate x = r.nextInt(100), where x will be between 0 and 99
- Choose between A, B, C depending on the value of x
  - For Assignment 1, if x=44, then pick A. If x=96, then pick C.
  - For Assignment 2, if x=44, then pick B. If x=96, then pick A.
DenseBag hashcode( )
From the hashcode( ) method project documentation:
- Return a hashCode that fulfills the requirements for hashCode (such as any two equal DenseBags must have the same hashCode) as well as desired properties (two unequal DenseBags will generally, but not always, have unequal hashcodes).
Your hashcode() method will be tested to ensure that:
- Two DenseBag objects that are equal (according to equals( )) have the same hashcode.
- Two DenseBag objects that are not equal will usually not have the same hashcode.
In general, a hashcode( ) method should also be significantly less expensive to compute than the equals( ) method (otherwise why even use a hashcode?), but we will not be testing for efficiency.

The hashcode( ) method should thus compute the hashcode from the same attributes of an object that are used by the equals( ) method, but do it in a simpler/superficial way.

Example hashcode( ) implementations:
- For String hashcode( )
  - could simply take the first letter of the String and convert it to an integer value
  - two equal strings would be guaranteed to have the same hashcode (1st letters must be identical)
  - would be more efficient than comparing the entire string
  - BUT, would perform poorly if tested with multiple strings beginning with same letter
- For List hashcode( )
  - could simply take the hashcode( ) of the first element in the list
  - two equal lists would be guaranteed to have the same hashcode (1st elements must be identical)
  - would be more efficient than comparing the entire list
  - assumes hashcode( ) is implemented properly for elements in the list
  - BUT, would perform poorly if tested with multiple lists beginning with same element
- For Set hashcode( )
  - could add the hashcode( ) of all the elements in the Set
  - two equal Sets would be guaranteed to have the same hashcode (integer sums are equal regardless of order of addition)
  - simply taking the hashcode( ) of the first element in the Set would not work (since Sets are unordered, and two equal Sets could have different 1st elements)
Simply converting an object to a String and using the string's hashcode( ) would not work if two equal objects generate different strings, and would probably be inefficient in any case since the toString() method would likely do more work than equals( ).

Markov Text Applet

You project includes a Java applet to help test your Markov text generator. The applet provides a GUI for entering/editing training data (or downloading training data directly from an URL), then displays the generated text. The GUI also allows you to specify the order of the Markov chains. Some training data you may use can be found at:

Honors Section Requirement

Students in the honor section must implement remove for the DenseBag iterator.

Submission

Submit your project using the submit project option associated with Eclipse.

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects. We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Program.