1 Change Log

With a common lab assignment we do not typically have time to change the lab in response to student questions, concerns, and common misunderstandings. However, as this project lasts three weeks, it is relatively common for small updated, extra hints, and minor typos to be added. This page will list any such modifications.  I recommend checking occasionally for updates on canvas and listening for updates announced in lecture

● Version 1.0 2022-04-10 Initial Version

● Version 1.1 2022-04-21

– Fixed typo in “setData” on page 13.

– Fixed typo on page 7 in the psuedocode for an algorithm for efficiently generating a random choice from the CharBag (when getCount is implemented in O(1) time.) (the if statement really needs to be inside the for looop)

– A few minor cleanups – nothing that changes meaning, but hopefully they make the meaning more clear.

– Redrew the Trie example – the Wikipedia one was kind of noisy, this new one is a bit more “full”, (I got carried away) but also has less irrelivant info on it.

1.1 FAQS

1. No FAQs are posted yet.  Like normal, I’ll update this at least once about a week out from the deadline with common questions

2 Essential Information

2.1 Pacing and Planning

This is a 3-week long assignment. By this point you should have a sense of the depth and complexity of such an assignment.  In terms of code-length.  Expect this project to be somewhere between project 1 and project 2:  There are fewer classes, and therefore less code, than Project 2, but the code is meaningfully more complicated than project 2– requiring you to understand and implement several specific algorithms.  As always, you should Plan time not only for coding, but for understanding and designing solutions to this problem.

Like the other projects – there are several places where key decisions have been left to you. In particular, one of the classes is entirely yours to design outside of the basic required methods. You will be given a goal to meet (in terms of efficiency) – failing to meet that goal will have a small but meaningful effect on your grade.

2.2 Deadline

The deadline for this assignment is Monday May 2nd at 6:00PM. Late work is not generally accepted on projects – there will be a brief grace period on gradescope to help mitigate technical issues – but beyond this grace period late work will not be accepted without an exception.  Unlike labs there is no 1-day-late policy.

2.3 Files

You will be expected to program the following files:

● LetterSample.java – a simple class to represent one “Data point” for the program we are making

● CharBag.java – a class to count how many times each letter has been added to it’s collection

– and to generate a random letter from the bag.

● TrieNode.java – a class representing a node in a Trie tree (A special tree data structure that is very fast at storing strings)

● Trie.java – a class that behaves like a dictionary – specialized for when key-values are short strings.

● Gibberisher.java – a class that can be “trained” in how a written language works, and can then generate “gibberish” words for that language.

Additional testing files may be provided over the course of the project, but ultimately you will be responsible for testing, and debugging, the code on your own.

2.4 Other important restrictions

Individual project – Unlike labs, where partner work is allowed, this project is an individual assignment. This means that you are expected to solve this problem independently relying only on course resources (zybook, lecture, office hours) for assistance.  Inappropriate online resources, or collaboration at any level with another student will result in a grade of 0 on this assignment, even if appropriate attribution is given. Inappropriate online resources, or collaboration at any level with another student without attribution will be treated as an incident of academic dishonesty.

To be very clear, you can ask other students questions only about this document itself (“What is Daniel asking for on page 3?”). Questions such as “how would you approach function X”, “How are you representing data in part 2?”, or even “I’m stuck on part B can you give me a pointer” are considered inappropriate collaboration even if no specific code is exchanged.  Coming up with general approaches for data representation, and finding active ways to become unstuck are all parts of the programming process, and therefore part of the work of this assignment that we are asking you to do independently.  Likewise, you are free to google search for any information you want about the java programming language and included java classes but it is not reasonable to look for information about the problem in this project (I.E.  “how to program card games” would be an inappropriate google search)

Allowed java classes There are A LOT of java classes, which solve many interesting prob- lems. In particular, there are one-or-two java classes that can completely solve major parts of this assignment. Our goal here is not to practice USING data structures to represent complicated data (that was project 1) but instead to BUILD data structures to represent complicated data. As such – Our normal rules for java classes apply:

You are not allowed to use any of the pre-built java classes except those we’ve explicitly discussed in class such as Scanner, Random, String, Character, Arrays etc.  If you are unsure if a java class would be allowed here you should ask.   Using unapproved java classes can lead to failing this assignment.

Specific examples of BANNED java classes:

● Any subclass of java.util.List (java’s list classes like ArrayList and LinkedList)

● Any subclass of java.util.Map (java’s dictionary classes such as HashMap and TreeMap)

● Any subclass of java.util.Set (java’s set classes such as HashSet and TreeSet)

● java.util.Collections

Every data storage task in this problem can be done by-hand without these pre-built data structures. Seeing how to do that is deliberately part of the assignment.

3 Introduction

When time allows, I often like to use nonsense words in my quiz and exam questions. Beyond being simple fun – these nonsense words play an important pedagogical role:  they force you to rely on code reading skills instead of variable name reading skills when understanding code. While it can be difficult to generate “good” nonsense words by-hand, the task is (fortunately) quite possible to automate.

In this project we will be building a Giberisher class, a class whose primary goal is to generate gibberish – random words that look like real English language words  (I.E. sequences of letters that should  be pronounceable).  In theory, you could also use the Gibberisher class to represent other languages (possibly with slight modifications to the lettering system) To build an efficient Gibberisher,  we will  also need to rely on  a few other problem-specific,  highly optimized data structures.   We will need these data structures to manage our approach – at a high level, the first step of our algorithm will be summarizing an English dictionary of 62,915 words. While this is ultimately a small number for computers – it’s certainly enough that our code will need to be efficient, or else it will take forever!

3.1 Learning Goals

This assignment is designed with a few learning goals in mind:

● Build an advanced tree-based data structure.

● Plan and build a task-specific data structure.

● Demonstrate your understanding of a range of data structure representations by choosing the most appropriate representation for this class.

● Implement an advanced algorithm to “model” and generate English text.

This assignment will build upon our ongoing study of data structures.  The first few classes should be build able with the material we’ve already covered at the point of assignment.  Later parts of this project should still be build able with the course material currently covered, but may make more sense after we’ve covered topics in the future – most notably Tree-based data structures. That said – you should be able to at least start  every part of this assignment at the point it is assigned.

4 Theory: Understanding, and generating, English words

Before describing our algorithm itself, let’s first see a different and simpler algorithm for the same problem. This will highlight the reasoning behind the parts of the algorithm we will want to generate.

4.1 A Bad algorithm for generating English words

Generating random words is actually quite easy:

The above code will generate a random word, made only of the English letters ’a’ through ’z’ forced to have a specific pre-specified length. While this algorithm in theory works – the words it generates are not good.  While randomWord(6) can generate such wonders as “docruf”, it is just as likely to output “aaaaaa” or “zqzzrz” or any other 6 random letters. The words generated by this algorithm are often unpronounceable because it does not understand the “rules” that lead to ‘pronounceable words.

One improvement upon this algorithm would be to make it understand that letters are not all used equally.  Letters like “e” show up much more than letters like “q” and “z”.  Therefore, we could improve this algorithm slightly if we put all the letters used by every English word into a bag, and then picked letters at random from this bag.  If we did this we would find roughly the following distribution of letters in English words.

Using the correct letter frequency does improve things.   Now we generate words like “ime- lesmeldd”, “rosle” and “eioirtgnosddmesdynrutkstiellmssore”. Unfortunately, these words are still far from pronounceable. This algorithm still does not have a good sense of what kind of words can follow other words.

4.2 Models – and their role in generating text

The core of both bad approaches to generating random words is their “model” of English text. A “model” in computer science describes a way of mathematically understanding the world. For our first algorithm, the “model” was simply a list of acceptable letters (a through z). If we wished to use the algorithm on other languages we could simply change the letter list to match that language.

For the second algorithm, the “model” was a relationship between letters and their general rate of use (Captured in the table above).  If we wanted to switch to a different language, we would need a different “model” – a different table to capture letters and their rate of use. In this way the “model” represents both our choice of algorithms, and contains everything the algorithm knows about the language it replicates.

To achieve our goal of random pronounceable words we need a more complicated model.  In particular, we will want a model that understand that there are certain patterns to what letters follow what other letters. As an example, the letters “ont” are followed by many letters in English (’r’ and ’e’ being most common) but the letters “ter” are mostly followed by ‘s’, with other options being less common. Therefore – this will become our model: an organized collection of all 3-letter (or in general k-letter) word segments, associated with a count of letters that follow them.  With this model, we can generate a word letter-at-a-time while still following the “rules” of the language.

This leaves two problems still unexplored: starting, and stopping words. To handle the starting problem we will allow “partial” word segments.  For instance, we will also have a count of words associated with “do” – which represents what letters tend to follow “do” specifically at the start of the word. We can use these “partial segment” word counts to track how English words get started.

The second problem, stopping words, is similarly solvable. We will use a simple approach and add the letter “.” at the end of every word. We will treat this like an ordinary letter – so our table of characters following any given word segment will contain a count of 27 letters:  a-z and also ‘.’ Whenever our algorithm randomly picks “.”  as an appropriate next-letter, we will stop our word there (not including “.” in the word) This will let us generate words of any length – with realistic “ends” to the word.

An example of generating text with this process may help. Here is an example of how the word “demors” might be generated.

1. Initially we have an empty string.  We consult the count of all “first letters” and pick on at random. Let’s say we picked “d” (about 1-in-16 chance (6.2%))

2. We now have the word “d”. Since this is still too small, we check the count of all next letters after “d” (at the start of the word). We pick “e” (used in 38% of words starting with “d”)

3. We now have the word “de”.  This is still to small, so we check the count of all next letters after “de” (at the start of a word). We pick “m” (used in 8.5% of the time)

4. We now have the word “dem”.  This is big enough, so we check the count of all next letters after “dem” (anywhere in the string). We pick “o” (used 39% of the time)

5. We now have the word “demo”.  Since we are using size-3 letter segments we will check the count of all next-letters after “emo”. We pick “r” (used 26% of the time)

6. We now have the word “demor”. We check the count of all next-letters after “mor”. We pick “s” (used 5.3% of the time)

7. We now have the word “demors”. We check the count of all next-letters after “ors”. We pick “.”  indicating the end of the word.  (70% of the time we saw  “ors” it was the end of the word).

Ignoring the “.” we generated – we can then return our new word:  “demors”.

Putting that process into pseudocode (where k is the sample size, 3 in the above) we have the following:

word  =  ""

While  word  doesn’t  end  with  the  STOP  letter:

sample  =  get  the  last  k  letters  of  word

(this  should  just  be  word  itself,  if  word  is  shorter  than  k)

get  the  letter  counts  for  sample

generate  nextLetter  based  on  those  letter  counts

word  =  word  +  nextLetter

return  word.

As you can see – at each step we will consult a potentially different count of letters to decide what the appropriate “next” letter is.  This large collection of next-letter-counts is the “model” of this problem – and represents everything the computer needs to know about pronounceable English text.

4.3 Representing the letter-counts model

The “model” for this algorithm, therefore, is quite important – as it contains everything the algo- rithm knows about how the English language  “works”.  We will represent this  “model” with two custom purpose data structures:

CharBag   The CharBag data structure will be used to represent letter-counts. For example, the count of all “next letters” after the segment “cti” in our data is:

CharBag{a:1,  b:9,  c:55,  d:0,  e:0,  f:18,  g:0,  h:0,  i:0,  j:0,  k:0,  l:10, m:9,  n:106, o:303,  p:0,  q:0,  r:0,  s:4,  t:9,  u:0,  v:147,  w:0,  x:0,  y:0,  z:0,  .:0}

Which tells us that “ctio” is the most common, but “ctiv”, “ctin”, and “ctic” are all respectable ways to continue a string. We may have thousands of these CharBag objects, each associated with a different series of preceding letters.

Trie   The Trie class will be our organizational tool to hold the thousands of CharBags and associate them with their preceding letters. The Trie data structure is a very specialized data structure for organizing things (like CharBags) when they are specifically associated with short strings.  This will give us VERY FAST access to the correct CharBag for any series of letters our algorithm can generate.

4.4 Training the letter-counts model

The final part to explain of this algorithm is how we generate the model itself.  This process is normally called “training” the model. This training process only needs to happen once, usually at the start of the program. Once the model is “trained” we can re-use it to generate many different words.

Broadly – our approach is simple: show the “model” every English word in the dictionary, and have it count each letter transition. The first step of this process will be splitting each word into a

series of “LetterSamples” – one for each letter in the word (and one extra for “STOP” – the end of the word) These LetterSamples tell us which letters preceded each letter in the word. For example, the “samples” of length 3 for the word “after” are:

●  “” 三 ’a’ (the word starts with a)

●  “a” 三 ’f’ (after a comes f)

●  “af” 三 ’t’ (after af comes t)

●  “aft” 三 ’e’ (after aft comes e)

●  “fte” 三 ’r’ (after fte comes r)

●  “ter” 三 STOP (the string ends after ter)

Note that at the beginning of the string we have “smaller” samples than 3, but once we get into the middle of the word, all samples are maximum length 3. Likewise, note that we will have a sample at the end indicating that this is where the string stops.

As we generate these samples, we will count them. So we will count ‘a’ as a potential first-letter (associated with sequence “”), and we will count ‘e’ as a potential next letter after the sequence “aft” and so-forth. While any one word will not make a big difference to the counts we store – after loading tens of thousands of words we our model will have a pretty good understanding of English language.

4.5 On understanding this algorithm

This algorithm has a lot of moving pieces, I know that. It can be difficult to see all of these parts on their own at the beginning – and it can be hard to visualize (since there are probably more than 100,000 distinct numbers we will need).  Don’t get discouraged at this point.  We’ve decomposed this problem into a series of classes which you can treat as self-contained problems.  Only at the end, once you know how each piece of this puzzle works, will you build the  “Gibberisher” class that represents this entire process. Before you get to that part, try to have answer to the following questions:

● How does this algorithm represent English text?

● How can we generate a word with this algorithm?

● How do we “train” this representation of English text?

These are all questions you can discuss (not-in-code) with other students – as the non-code parts are all listed above.  Of course, if you are having trouble understanding this algorithm at a high level, we are always happy to explain it further over email or in office hours. Likewise, as said, you can also move forward and build most of this project without these pieces clicking just yet.

5 Formal Requirements

There are five required classes for this project.  While these can be implemented in any order, I recommend the following order.

● LetterSample - representing a part of a word, and the letter that follows it.

● CharBag - a datastructure for counting characters.