combat your memory's limitations, you have decided that the best method to choose which word should come after the current context is random selection. Because you know the list of all words appear after this context in the original text, you will randoml

Basic Ideas and Constructs

Algorithm

Concept

The key concept of our algorithm is that the next word in the sentence only depends on the last few words that appear before it in the sentence. This is a pretty powerful idea. Said another way, the next word in the sentence only depends on the context of that word. In the training phase of your program (in other words, training your program), you will identify your current context and associate the next word with that context. In the text generation phase, you will randomly select the next word to add to the sentence based on the current context (i.e. the last couple of words in the generated sentence).

Analogy

This algorithm is essentially a model of how people read and write text. When reading each word in a sentence, you consider what you have read so far (i.e. the context) to give meaning to the word. When writing, the context of the sentence determines what words you could choose to write next. It is very similar with our algorithm.

Our program is analogous to reading a book and trying to quickly make a word-for-word rewrite of it solely from memory. You read the book sentence by sentence and associate each word with its context in the sentence (i.e. the couple of the preceding words or that the word starts a sentence). Then, when you try to rewrite the book, you run into a major issue. While you remember all word-context associations with perfect clarity, you are writing so fast that you can't remember where you are in the book or what sentences you have already written. Said another way, your memory while writing only extends to the current sentence you are writing. Therefore, you don't know which word should come next in your attempt to make a duplicate of the book you just read.

To combat your memory's limitations, you have decided that the best method to choose which word should come after the current context is random selection. Because you know the list of all words appear after this context in the original text, you will randomly select one of those words to be the next one in the sentence. After writing this word, it is incorporated into the context which will choose the next word. However, you run into yet another issue: you are writing a sentence so fast that you can only remember the last few words you have written. While this isn't a problem at the beginning of the sentence, as the sentence becomes longer, you will forget more and more of the early words in the sentence. All of the most recently written words (which you can remember) are used as the context to decide which word to write next.

In regards to the program you will be implementing, the “reading” described above is like the training phase of the program and “writing” is like the text generation phase.

Interesting Note

Prefix & Suffix

This project requires you to train your program on a text file as if the computer were reading it. To accomplish this task, you will need to move word by word through the text and apply the training logic outlined above after you retrieve each word. However, before we discuss the program's logic in depth, we need to first establish the definitions of some frequently used terms.

●     Prefix: the fixed-length series of words that represent your current context in the sentence. Any given word in a sentence is dependent on its context in a sentence. Just like in the analogy, our program only has a “memory” of the last pair of words seen. Therefore, a word's context can only be sequence of the 'n' words which directly precede the chosen word that our program can “remember”. We define the prefix to be this context. We say a prefix has 'n' words because the number 'n' can be arbitrarily chosen; however all prefixes must have the same length 'n'.

○     Note: a special case is the context at the start of the sentence. It is special because our program has no memory of the sentence yet and therefore the prefix contains no words. In this case, we assume that this prefix only contains empty strings. We do this because the empty string represents the lack or absence of a word. Using programming terminology, this special “Start-of-Sentence” prefix is an 'n' length array of empty strings.

●     Suffix: the word that immediately comes after a prefix. It is important to note that designating a word as a suffix is completely dependent on what you have chosen as the prefix.

Here is an example to show you exactly what a prefix and suffix are in relation to a sentence.

For the sake of example, let us assume that a prefix is 1 word long. Let's analyze the sentence “CS180 is the best class I have ever taken, ever.” We'll start by declaring the first word to be the starting prefix.

   CS180    is    the    best    class    I    have    ever    taken,    ever.
   |_____|  |__|
    Pref    Suff

Since we have selected “CS180” as our prefix, by definition, the word that immediately follows is a suffix. Hence, the word “is” is a suffix of “CS180”.

Continuing our example from above, we have recognized “is” as the suffix of “CS180”; therefore, the word “is” is our most recent context in the sentence and becomes our current prefix.

   CS180    is    the    best    class    I    have    ever    taken,    ever.
            |__|  |___|
            Pref   Suff

As you can see above, when “is” is our prefix, the suffix is the word “the” because it comes directly after the prefix. In fact, every word in the sentence, except for the first and the last, can be both a prefix and a suffix.

Here is another example of a prefix and a suffix:

   CS180    is    the    best    class    I    have    ever    taken,    ever.
                                                       |____|  |______|
                                                        Pref     Suff

Notice that the comma in the string “taken,” is included on the suffix. You do not need to parse out leading or trailing punctuation from a string. According to our grammar, each word is simply a set of characters separated by whitespace.

In all of the diagrams shown so far in this section, the prefix has only consisted of 1 word. However, as stated in the definition, a prefix can be any 'n' sequential words where 'n' >= 1. Below are random examples of prefixes of different lengths.

n = 2
    CS180    is    the    best    class    I    have    ever    taken,    ever.
           |___________| |____|
               Pref       Suff
              
    CS180    is    the    best    class    I    have    ever    taken,    ever.
                                               |____________|  |______|
                                                     Pref        Suff

n = 4
    CS180    is    the    best    class    I    have    ever    taken,    ever.
           |___________________________|  |_|
                       Pref               Suff

    CS180    is    the    best    class    I    have    ever    taken,    ever.
                         |__________________________|  |____|
                                       Pref             Suff

While your program will allow you to specify any arbitrary number of words for prefix length, you need to remember that once you have chosen a prefix size, you must use that same prefix size for all sentences for all texts on which you train your program. If you change the number of words in a prefix, all files will have to be retrained. The technical term for this property is that the prefix length can be any arbitrary but fixed 'n'.

It is important that you understand this terminology, as it will be used throughout the rest of the handout. However, exact details on how you select your prefix during the training and text generation phases will be discussed below.

Algorithm Details

Program Training

●     In general, you will train your program by moving word by word through the training file and associating each unique prefix with all of its suffixes that appear in the text. Duplicate suffixes are allowed.

●     Given that all prefixes are of a fixed length 'n', we define the current prefix as the last 'n' words we have seen in the file.

●     You will start this process with an array of words that represents the current context. The order of these words is significant because the order represents the sequence in which the words were seen. The word at index 0 appeared directly before the word at index 1, and the word at index 1 appeared directly before the word at index 2, etc… This ordering of the words provides the look into the past history of the sentence that defines the context of the next word.

○     At the beginning of the training and at the start of a new sentence, the array of context words should contain the values that are associated with the Start-of-Sentence prefix.

1. Update Suffix List

With your array of context words (described above), you will get the Prefix object associated with those prefix words. Then, you will add the next word in the file (the suffix) to the list of suffixes associated to current prefix. At this point, we can say that the current prefix has been trained on the current suffix.

2. Update Current Prefix

At this point, you must update your current prefix, as we now know the next word in the file. Therefore, we should change our array of prefix words so that the CURRENT suffix, that is the last word read, is now the last prefix word.

However, because a prefix is of length 'n', we cannot simply “add” the CURRENT suffix to the array of prefix words.

Therefore, the array of prefix strings should be updated so that the CURRENT suffix becomes the newest word of the prefix and the oldest word of the prefix is removed.

NOTE: The only case where you update the prefix differently is at the end of a sentence. If the suffix given is at the end of the sentence, you set the current prefix to be the special Start-of-Sentence prefix.

3. Repeat

Since your array of prefix strings has been updated to reflect the current prefix, you can go back to step 1. You should repeat this process until there are no more words in the file to add as suffixes. At that point, you are done.

Graphical Example

We will assume we are given a training file containing the text “I am not a machine. I am a human!” and that the number of words in a prefix is 2. In all subsequent examples, the text of “||” under specific words shows which words are in the current prefix.

"" ""  I am not a machine. "" ""  I am a human!
|_____|

As the above figure shows, the current prefix is comprised of two empty strings to denote the start of the sentence. Then, we get the Prefix object associated with the current prefix strings (the Start-of-Sentence prefix) from the StringArrayMap, add the next word to the prefix object's list of suffixes, and update the array of prefix words. The following output displays the state of the program after executing steps 1 and 2 once.

"" ""  I am not a machine. "" ""  I am a human!
   |_____|

Now, our current prefix is an empty string followed by the word “I”. Executing steps 1 and 2 again, the program proceeds to the following state:

"" ""  I am not a machine. "" ""  I am a human!
       |____|

At this point, our current context/prefix is the word “I” followed by the word “am”. If we execute steps 1 and 2 a few more times, we reach the following states:

"" ""  I am not a machine. "" ""  I am a human!
         |______|

"" ""  I am not a machine. "" ""  I am a human!
            |_____|

"" ""  I am not a machine. "" ""  I am a human!
                |__________|

At this point, step 2 hasn't ended and the prefix string hasn't been updated. Notice that the last prefix word ends in a period. When we finish step 2, notice what happens to the prefix.

"" ""  I am not a machine. "" ""  I am a human!
                           |_____|

Because the previous sentence ended, the prefix updated to 2 empty strings to denote that the current prefix is the start of the sentence. If we execute steps 1 and 2 again, the program moves to the following state:

"" ""  I am not a machine. "" ""  I am a human!
                              |_____|

Take a look at the first entry in the table of prefix strings. Notice that even though the word “I” is already contained by the array of suffixes, another string “I” is added to it. That is why the array of suffixes for a Prefix object is the array of all suffixes seen after this prefix. Your implementation must support this ability to add multiple copies of the same string to the array of suffixes, or your program will not work. If we execute steps 1 and 2 again, we get:

"" ""  I am not a machine. "" ""  I am a human!
                                  |____|

Notice that the prefix associated with {“”, “I”} now has an array of possible suffixes where both entries are the string “am”. Because we have seen this prefix before, we add the suffix to the already existing object's suffix list instead of creating a new Prefix object. The rule is that if a prefix has not been seen before, create a new one and then add the suffix to that new prefix. However, if a Prefix object already exists for current prefix strings, get the old Prefix object (using a StringArrayMap instance) and add the suffix to that Prefix object.

If we continue in a similar fashion to the last step in the training, the program state moves to this:

"" ""  I am not a machine. "" ""  I am a human!
                                       |________|

At this point, because the last prefix word would end the sentence (because it ends with an exclamation point), the current prefix strings should be updated to the refer to the Start-of-Sentence prefix. However, because there are no more words in the file, the training step ends.

Text Generation

●     Many aspects of the text generation phase are similar to the ones used to train the program (e.g. updating the current prefix with a given suffix).

●     At the start of sentence generation, you need to initialize the array of current prefix words to the Start-of-Sentence prefix (i.e. array of empty strings), just like at the beginning of the program training section.

In general, the dynamic text generation works by getting the Prefix object associated with a given array of prefix words, selecting a random suffix from the Prefix object's list of suffixes, and then updating the prefix strings to include the chosen word. If the last word in the updated prefix would cause the sentence to end, sentence generation stops and you return the sentence. Otherwise, repeat this process until the randomly selected suffix would cause the sentence to end.

1. Generate Next Word

Get the current Prefix object using the prefix words array. Select the next word to add to the sentence by randomly choosing a suffix from the prefix's list of possible suffixes (generated from the training step).

2. Update Current Prefix

In the same manner as training your program, you need to update your current prefix. However, instead of updating it to include the next word in the file, we are updating the prefix to contain the next word in the sentence. Conveniently, the next word in the sentence is the random suffix we just got in the previous step! Therefore, you should update the prefix such that the word you just generated becomes the last word in the current prefix.

3. Check for Termination

Before you go and add another word to the sentence, you need to check if the sentence has ended. If the last word in the prefix would cause the sentence to end (e.g. ends in a '.' or '!'), end sentence generation and return the string containing the sentence. Otherwise, go back to step 1.

Note: a word is considered to be at the end of the sentence if it ends with terminating punctuation or terminating punctuation followed by normal punctuation. The definitions for normal and terminating punctuation characters are given in the skeleton code.

Graphical Example

Using the example text and training from above example, at the start of text generation, the program state is:

"" ""
|_____|

The current prefix is the Start-of-Sentence prefix (denoted by the empty strings). If we execute steps 1, 2, and 3, the program moves to:

"" "" I
   |____|

Notice that the word “I” is selected to be the next word from the list of suffixes associated with the Start-of-Sentence prefix. Then, once the next word is chosen, the prefix updates to include that word. If we then execute all 3 steps of text generation once again, the program changes to:

"" "" I am
      |____|

The word “am” is selected to be the next word from the list of suffixes associated with the {“”, “I”} prefix. This is because, due to our training text, “am” is the only word seen after a {“”, “I”} prefix. However, take a look at the suffixes associated with the {“I”, “am”} prefix. The next possible word could either be “not” or “a”, and the word that is chosen will have profound impact on the rest of the sentence.

If the word “not” is chosen, the prefix will become {“am”, “not”} and the sentence will eventually become “I am not a machine.” On the other hand, if the word “a” is chosen, the prefix will become {“am”, “a”} and the sentence will eventually become “I am a human!”

Implementation Details

For this project, you will also be given the fully implemented StringArrayMap class and will be implementing the methods of three different classes.

1.    Prefix

2.    PrefixGenerator

3.    TextGenerationEngine

You will be given skeleton code of all of these classes and you will need to implement the methods specified below. Note that only general descriptions of the methods are given. For longer explanations and more details, see the comments in the skeleton code

Map Data Structure

A map data structure is an object that associates a given key with a given value and allows you to instantly retrieve values based on their key. For this project, you are given the StringArrayMap class. This class maps String arrays to Prefix objects. You will be storing and retrieving Prefix objects in an instance of this class. The StringArrayMap class has three methods: get, put, and printMap.

/**
 * Returns the Prefix object to which the String[] key is mapped, or null
 * if this map contains no mapping for the String[].
 * @param prefixes - the String[] key whose associated Prefix object is
 * to be returned
 * @return the Prefix object associated with the key, or null if that key
 * has not been mapped
 */
public Prefix getPrefix(String[] prefixes)
 
/**
 * Associates the specified Prefix object with the specified String[] key
 * in this map).
 * If the map previously contained a mapping for the String[] key, the old
 * Prefix object is replaced by the specified Prefix object
 * @param prefixes String[] key with which the specified Prefix object is
 * to be associated
 * @param pref Prefix object to be associated with the specified key
 */
publicvoid putPrefix(String[] prefixes, Prefix pref)
 
/**
* Gives a printed summary of this string map, listing all the trained
* string prefixes, with the corresponding possible non-null suffixes. Note
* that the order is arbitrary, and is not guaranteed to be consistent
*/
publicvoid printMap()

The put method maps a specified String[] with a specified Prefix object. The get method returns the Prefix object mapped with the specified String[], or null if the put method has not been used to creating a mapping. It is required that you store your all created Prefix objects in a StringArrayMap object. Not only is this a part of how we test your code, but not using this class will cause your program to execute too slowly to run.

The printMap function is there for your convenience and testing. When invoked, it will show all suffix strings associated with a given prefix. This method is only intended for your own testing and should never be called on code that you submit for grading.

This class will be given to you as a .jar file (an executable version of the .java & .class files). How to setup your work environment to run your program using the jar will be described below.

Prefix Class

This class will model the prefix described in the algorithm explanation above. You will need to completely implement this class. The skeleton code provides outlines and commented explanations for all the methods you will need to implement. All helper methods and underlying data structures of the class must be implemented by you. Do not change any method signatures for methods provided in the skeleton. The methods you will be required to implement are:

publicstaticvoid initializeSentenceStartArray()
 
publicstaticString[] getStartOfSentencePrefixes()
 
public Prefix(String[] prefixStrings)
 
publicint getNumSuffixes()
 
publicint getNumPrefixes()
 
publicString getPrefixString(int index)
 
publicString getSuffixString(int index)
 
publicvoid addSuffix(String str)
 
publicString getRandomSuffix()
 
publicboolean equals(Object obj)
 
publicString toString()

For details on the purpose and behavior of these functions, see the skeleton code

PrefixGenerator Class

In the PrefixGenerator class, the only method you are required to implement is the trainPrefixMap method. This method should implement the training algorithm described above.

publicstaticvoid trainPrefixMap(StringArrayMap map,String filename)

While this is the only required method in the PrefixGenerator class, it does not have to be the only method in the class. In fact, it is suggested that you use helper methods to perform heavily repeated tasks. While you may create a main method in this class to test your code, there should be no main method in it when you submit for grading.

TextGenerationEngine Class

The main purpose of this class is to dynamically generate sentences. There are three methods you need to implement:

publicstaticString generateSentence(StringArrayMap mapping)
 
publicstaticboolean shouldTerminate(String suffix)
 
publicstatic StringArrayMap retrain(int length)

In the generateSentence method, you should implement the text generation algorithm described above. The shouldTerminate method determines if a word is at the end of the sentence (i.e. should terminate a sentence). The retrain method changes the training of the program so that prefixes are a specified length. More in-depth explanations of these functions are available in the javadocs of the skeleton code.

You will be provided with a main method that will prompt the user for different actions and some static variables and helper methods that may be helpful for your implementation (or they might be used in main). You should not change any pre-existing methods or variables that do not have a TODO comment. However, feel free to add helper methods and class variables.

Hint: The shouldTerminate method will be useful in the trainPrefixMap method.