8. Chat126

Implementing MarkovLM.java

1. Review precept exercises, especially FrequencyTable, as well as IntegerSort.java.
2. Create one or more instance variables to support the two freq() methods. One strategy is to maintain two symbol tables—one for the one-argument freq() method and one for the two-argument freq() method.

• For each $k$-gram (a string), the first symbol table tells you how many times it appears in the text (an integer).
• For each $k$-gram (a string), the second symbol table tells you how many times each ASCII character succeeds the $k$-gram in the text (an array of 128 integers).
• Character (i.e., char values) can be used as an index into an array. In Java, characters are 16-bit (unsigned) integers; they are promoted to int values in any context that expects one. For example, array['c'] is equivalent to array[99] because the ASCII code for 'c' is 99.
• You can avoid hardwiring the constant 128 by using a static instance variable: private static final int ASCII = 128;
• This code should appear inside the class block, but before any instance variables or methods. By convention, constant variable names should be ALL_UPPERCASE. The static modifier means that every instance method will refer to the same variable (as opposed to instance variables, for which there is one variable per object); the final modifier means that you can’t change its value, once initialized.

3. Write the constructor to create the circular version of the input text. Then initialize and populate your symbol tables, using the symbol table methods contains(), get(), and put(). This will be a substantial amount of code, relative to the other methods in this class.

• Do not save the original text (or the circular text) as an instance variable because no instance method will need this information after the symbol table is initialized.
• There are a number of approaches for emulating the circular text. One way is to append the first $k$ characters of the input text to the input text.

4. Test: In the main(), try creating some MarkovLM objects. For example:

   String text1 = "banana";
   MarkovLM model1 = new MarkovLM(text1, 2);
   ...
   String text2 = "gagggagaggcgagaaa";
   MarkovLM model2 = new MarkovLM(text2, 2);
   

5. Write the toString() method. Use an enhanced for loop to access each key–value pair in your symbol table and a StringBuilder to generate the required String value. See the FrequencyTable.java from precept for an example.
6. Test the constructor and toString() method: This can help you debug small test cases. In the main(), print some MarkovLM objects. For example:

   String text1 = "banana";
   MarkovLM model1 = new MarkovLM(text1, 2);
   StdOut.println(model1);
   ...
   String text2 = "gagggagaggcgagaaa";
   MarkovLM model2 = new MarkovLM(text2, 2);
   StdOut.println(model2);
   

• Sample output from the code snippet above:

  ab: a 1
  an: a 2
  ba: n 1
  na: b 1 n 1
  
  aa: a 1 g 1
  ag: a 3 g 2
  cg: a 1
  ga: a 1 g 4
  gc: g 1
  gg: a 1 c 1 g 1
  

• You can insert a line break in a String by using the characters \n. For example, if you print "ab\ncd", ab and cd will appear on separate lines.

7. Write the order() method. This should be a one-liner.
8. Using the symbol table instance variables, write the two freq() methods.
9. Use the main() provided above to test your code before continuing. In the main method, you should add more tests of the constructor, order(), and freq() methods.
10. Write the predictNext() method. To generate a random character with probability proportional to its frequency you may call either of the two StdRandom.discrete() methods.
11. It may not be obvious from your final results whether predictNext() is working as intended, so be sure to test it thoroughly. Next, test your complete MarkovLM data type before continuing. (See Testing Your MarkovLM.java Implementation below.)

Implementing Chat126.java

1. Read in k and T from the command line; read the input text from standard input.
2. Create a MarkovLM object of order k using the input text.
3. To generate a trajectory of length T, use the first k characters in the input text as the initial \(k\)-gram and print the initial \(k\)-gram. Then, repeatedly generate and print a new random character according to the Markov model and update the \(k\)-gram to store the last k characters printed.
4. Make sure to test your program on large inputs (we provide several), large outputs, and different values of k.
5. Some FAQs:

• Should my program generate a different output each time I run it? Yes.
• How can I read in the input text from standard input? Use StdIn.readAll(). Do not remove whitespace.
• My random text ends in the middle of a sentence. Is that OK? Yes, that’s to be expected.
• After executing the program, the command prompt appears on the same line as the random text. Is that OK? Yes. It’s because the random text does not end with a newline character. If you want to add a call to StdOut.println() at the end of your program, that’s fine—we promise not to deduct.
• What does this message mean: The local variable ‘T’ must start with a lowercase letter and use camelCase? Since T is a constant, you should declare it as final, e.g., final int T = .... Alternatively, you can rename the constant using a variable name that is more than one character.
• For which values of \(k\) should my program work? It should work for all well defined values of \(k\), from 0 up to, and including, the length of the input text. As \(k\) gets larger, your program will use more memory and take longer.
• My program is slow when \(T\) is large because I am concatenating the \(T\) characters, one at a time, to form string of length \(T\)). What else can I do? Do you need to form the entire string? Why not print the characters, one at a time, as you generate them?
• I get an OutOfMemoryException. How do I tell Java to use more of my computer’s memory? Depending on your operating system, you may have to ask the Java Virtual Machine for more main memory beyond the default. The 500m means 500MB, and you should adjust this number depending on the size of the input text.

  java-introcs -Xmx500m Chat126 7 1000 < input.txt
  

Good afternoon and welcome to Opening Exercises. What a special pleasure it is to greet Princetons Great Class of 2018! I also offer a warm welcome to our new graduate students, faculty and staff members, and all of you who are returning to campus after the summer.

Today we carry on a tradition that dates back at least to 1802, when Nassau Hall was the site of an opening exercise for Princeton students. The event switched to other sites before moving in 1929 to the University Chapel, where we gather today. Todays interfaith ceremony is far different from the Christian services that greeted students in 1929, but the chapels soaring architecture and inspirational spaces continue to invite all of us, whatever our religious or ethical traditions might be, to reflect on the larger purposes that should guide our community as we begin another year on this glorious campus.

Today you join the ranks of students who have left their marks on the Princeton campus and the world for generations through their intellect, creativity and passion. You, the 1,312 members of the Class of 2018, are an extraordinarily accomplished, inspiring and diverse group. You hail from 46 states, as well as the District of Columbia. You come from 50 countries outside of the United States from Chile to the Czech Republic, from Iceland to India, from Nigeria to New Zealand. You grew to become upstanding, compassionate citizens in Happy Valley, Oregon, and Niceville, Florida. You weathered the ups and downs of life in Boiling Springs, Pennsylvania, and Frostburg, Maryland. And you learned to appreciate the lyrical majesty of language in Ho Ho Kus, New Jersey, and Oologah, Oklahoma.

Example 1 output: random Eisgruber, using order 7 model

java-introcs Chat126 7 798 < opening-exercises.txt

Good afternoon and welcome to a universities around you here.

I often ask Princeton is a truly global institution. As scholars who matter most to you. And you here.

I often ask Princeton you have come to our social natures, and, more specifically, with drums and choirs and distinguished teachers, whose contributions will become upstanding.

This Universitys GREAT CLASS OF 2018! Welcome new members play indispensable roles in helping our Universitys GREAT CLASS OF 2018! I also offer insignificant, or puzzling, or uninteresting, or unsympathetic may turn out to be discourse in all disciplines here as rich with meaningful, not just of any story, can make it easy to feel without knowing exactly what he was destined to appreciate the lyrical majesty of language in Ho Ho Kus, New Jersey, and

[Enter DUKE SENIOR, AMIENS, and two or three Lords, like foresters]

DUKE SENIOR Now, my co-mates and brothers in exile, Hath not old custom made this life more sweet Than that of painted pomp? Are not these woods More free from peril than the envious court? Here feel we but the penalty of Adam, The seasons’ difference, as the icy fang And churlish chiding of the winter’s wind, Which, when it bites and blows upon my body, Even till I shrink with cold, I smile and say ‘This is no flattery: these are counsellors That feelingly persuade me what I am.’ Sweet are the uses of adversity, Which, like the toad, ugly and venomous, Wears yet a precious jewel in his head; And this our life exempt from public haunt Finds tongues in trees, books in the running brooks, Sermons in stones and good in every thing. I would not change it.

AMIENS Happy is your grace, That can translate the stubbornness of fortune Into so quiet and so sweet a style.

DUKE SENIOR Come, shall we go and kill us venison? And yet it irks me the poor dappled fools, Being native burghers of this desert city, Should in their own confines with forked heads Have their round haunches gored.

Example 2 output: random Shakespeare, using order 6 model

java-introcs Chat126 7 1135 < as-you-like-it.txt

DUKE SENIOR Now, my co-mates and thus bolden’d, man, how now, monsieur Jaques, Unclaim’d of his absence, as the holly! Though in the slightest for the fashion of his absence, as the only wear.

TOUCHSTONE I care not for meed! This I must woo yours: your request than your father: the time, That ever love I broke my sword upon some kind of men Then, heigh-ho! sing, heigh-ho! sing, heigh-ho! sing, heigh-ho! unto the needless stream; ‘Poor deer,’ quoth he, ‘Call me not so keen, Because thou the creeping hours of the sun, As man’s feasts and women merely players: Thus we may rest ourselves and neglect the cottage, pasture? Enter DUKE FREDERICK Can in his time in my heartily, And have me go with your fortune In all this fruit Till than bear the arm’s end: I will through Cleanse the uses of the way to look you. Know you not, master, Sighing like upon a stone another down his bravery is not so with his effigies with my food: To speak my mind, and inquisition And unregarded age in corners throat, He will come hither: He dies that hath engender’d: And you to the bed untreasured of the brutish sting it.

• We actually asked ChatGPT this question, and here’s its response (slightly edited):
• Markov models and Large Language Models (LLMs) are both used for generating text but operate on different principles.
  • Markov Models: These are based on the Markov property, which states that the future state of a system depends only on its present state, not on the sequence of events that preceded it. In the context of text generation, a Markov model predicts the next word in a sequence based current k-gram.
  • Large Language Models (LLMs): These are more sophisticated models based on neural networks, particularly variants like GPT (Generative Pre-trained Transformer) models. LLMs leverage deep learning techniques to capture complex patterns and dependencies in text data. They are trained on large corpora of text and can generate coherent and contextually relevant sequences of text. Unlike Markov models, LLMs do not rely solely on fixed-length context windows but instead learn contextual representations of words and phrases based on their entire input sequence.
• While both Markov models and LLMs can generate text, LLMs generally produce more fluent and contextually appropriate text due to their ability to capture long-range dependencies and contextual nuances. However, Markov models are simpler and more interpretable, making them suitable for certain text generation tasks, especially when computational resources are limited.

• We are implementing the model Shannon described in his landmark paper. But the one reads until this letter is encountered method in his quote on the assignment page is, ironically, not a statistically accurate example of his model. If we run your program with input wawawaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaawy then w should be followed by a 75% of the time, while the read until model will follow w with a only 15% of the time. What would be involved in simulating this other model? Which one do you think gives more realistic text?
• Here’s a website that generates pseudo-random computer science papers. It uses something called a context-free grammar instead of a Markov chain, but otherwise is similar in spirit to what you are doing on this assignment.
• Here are Garfield comics generated by a Markov chain.