Imagine taking a book (say, Tom Sawyer) and determining the
probability with which each character occurs. You'd probably find
that spaces are the most common, that the character 'e' is fairly
common, and that the character 'q' is rather uncommon. After
completing this level 0 analysis, you'd be able to produce random
Tom Sawyer text based on character probabilities. It wouldn't
have much in common with the real thing, but at least the characters
would tend to occur in the proper proportion. In fact, here's an
example of what you might produce:
Now imagine doing a slightly more sophisticated level 1 analysis by
determining the probability with which each character follows every
other character. You would probably discover that 'h' follows 't'
more frequently than 'x' does, and you would probably discover that
a space follows '.' more frequently that ',' does. You could now
produce some randomly generated Tom Sawyer by picking a
character to begin with and then always choosing the next character
based on the previous one and the probabilities revealed by the
analysis. Here's an example:
rla bsht eS ststofo hhfosdsdewno oe wee h .mr ae irii ela iad o r te u t mnyto onmalysnce, ifu en c fDwn oee iteo
Now imagine doing a level k analysis by determining the
probability with which each character follows every possible sequence
of characters of length k. A level 5 analysis of Tom
Sawyer for example, would reveal that 'r' follows ''Sawye'' more
frequently than any other character. After a level k analysis,
you'd be able to produce random Tom Sawyer by always choosing
the next character based on the previous k characters (the
seed) and the probabilities revealed by the analysis.
"Shand tucthiney m?" le ollds mind Theybooure He, he s whit Pereg lenigabo Jodind alllld ashanthe ainofevids tre lin--p asto oun theanthadomoere
At only a moderate level of analysis (say, levels 5--7), the randomly
generated text begins to take on many of the characteristics of the
source text. It probably won't make complete sense, but you'll be
able to tell that it was derived from Tom Sawyer as opposed to,
say, The Sound and the Fury. Here are some more examples:
"Yess been." for gothin, Tome oso; ing, in to weliss of an'te cle -- armit. Papper a comeasione, and smomenty, fropeck hinticer, sid, a was Tom, be suck tied. He sis tred a youck to themen
en themself, Mr. Welshman, but him awoke, the balmy shore. I'll give him that he couple overy because in the slated snufflindeed structure's kind was rath. She said that the wound the door a fever eyes that WITH him.
people had eaten, leaving. Come -- didn't stand it better judgment; His hands and bury it again, tramped herself! She'd never would be. He found her spite of anything the one was a prime feature sunset, and hit upon that of the forever.
look-a-here -- I told you before, Joe. I've heard a pin drop. The stillness was complete, how- ever, this is awful crime, beyond the village was sufficient. He would be a good enough to get that night, Tom and Becky.
you understanding that they don't come around in the cave should get
the word "beauteous" was over-fondled, and that
together" and decided that he might as we used to do -- it's
nobby fun. I'll learn you."
You are to implement a Java public class RandomWriter that
provides a random writing application. Your class should have a
public main method that takes the following four command line
- A non-negative integer k
- A non-negative integer length.
- The name of an input file source that contains more than
- The name of an output file result.
Your program should validate the command line arguments by making sure
that k and length are non-negative, that
source contains more than k characters and can be
opened for reading, and that result can be opened for
writing. If any of the command line arguments are invalid, your
program should write an informative error message to
System.err and terminate.
Otherwise, your program should pick k consecutive characters
at random from source and use them as the initial seed in the
random writing process outlined above. Your program should then write
length characters to result. Each of these
additional characters should be chosen based on the current seed.
(Each time a character c is written to result, the
seed is updated by removing its first character and appending
c to the end.)
For example, suppose that k = 2 and the source file contains
the three pirates charted that course the other day
Here is how the first three characters might be chosen:
- A two-character seed is chosen at random to become the initial
seed. Let's suppose that "th" is chosen.
- The first character must be chosen based on the probability that
it follows the seed (currently "th") in the source. The source
contains five occurrences of "th". Three times it is followed by 'e',
once it is followed by 'r', and once it is followed by 'a'. Thus, the
next character must be chosen so that there is a 3/5 chance that an
'e' will be chosen, a 1/5 chance that an 'r' will be chosen, and a 1/5
chance that an 'a' will be chosen. Let's suppose that we choose an
'e' this time.
- The next character must be chosen based on the probability that
it follows the seed (currently "he") in the source. The source
contains three occurrences of "he". Twice it is followed by a space
and once it is followed by 'r'. Thus, the next character must be
chosen so that there is a 2/3 chance that a space will be chosen and a
1/3 chance that an 'r' will be chosen. Let's suppose that we choose
an 'r' this time.
- The next character must be chosen based on the probability that
it follows the seed (currently "er") in the source. The source
contains only one occurrence of "er", and it is followed by a space.
Thus, the next character must be a space.
If your program ever gets into a situation in which there are no
characters to choose from (which can happen if the only occurrence of
the current seed is at the exact end of the source), your program
should pick a new random seed and continue.
There is a simple way to attack this problem. Create a
String object that contains all of the characters from the
source file. To choose the next character, find each occurrence of
the seed in the source and store the character that follows it into an
ArrayList. When you have found all occurrences, choose a
character at random from the ArrayList.
Here are some useful things to know about Java. You'll need to read
the Java documentation for more details.
- A java.util.ArrayList can contain only objects; it
cannot contain a scalar values such as a char. To store a
char into an ArrayList, you need to wrap it in a
- You can use a java.util.Random object to generate
random integers in a specified range.
- A java.io.FileWriter object is useful for writing
strings and characters to a file.
- A java.io.FileReader object is useful for reading one
character at a time from a file.
- A java.lang.StringBuffer object is useful for
efficiently composing characters into a string.
- A java.lang.String object contains several member
functions for searching for substrings.
Project Gutenberg maintains a
huge library of public domain books that you can use as source texts.
If your program generates something that is particularly amusing,
please send it to me so I can share it with the class. Be sure to
identify the source text and the level of the analysis.