Project 06 What the Words Say
In Lab 06 you built a map on a binary search tree. This project puts it to work on real text: the complete works of Shakespeare and a year of Reddit comments. Your map will count every word in both, and you will use the counts to answer questions about how the two kinds of writing differ.
This project is about the data, using the BSTMap you already have. Next week you will build a second map, a hash table, and compare how fast the two maps are.
- Finish BSTMap (Task 1): Add remove, using lecture's delete (L24).
- Count words (Tasks 2–3): Complete WordCounter, which counts every word in a text with your map.
- Ask questions (Tasks 4–5): Find each text's most common words, and the words one text uses that the other never does.
- Report (Task 6): Run the provided WordReport on both texts and explain what the results show in your report.
- Coming next: Next week's lab builds a HashMap, which you can plug into WordCounter by changing one line.
Setup
Keep working in Projects/Project06, with your Lab 06 files: MapSet.java, your BSTMap.java, and tiny.txt. Finish Lab 06 first, including Tasks 5 and 6: java Lab06Tester should show every section passing, because this project uses keySet and values. Download the files below and the data.
Download now:
Unzip data.zip into the same folder. It holds two files: CLEANED_shakespeare.txt (365,342 words) and CLEANED_reddit_comments_2015.txt (about 15 million words). Do not hand in the data files; they are large, and we already have them.
dont, and "the" never appears at all. Keep this in mind when you explain your results: some of what you see comes from the cleaning, not from Shakespeare or Reddit.- Predict before you run. Before Task 6, write down which words you expect at the top of each list.
- Test on small input first. Every method can be checked on tiny.txt, where you can count by hand. The real files take several seconds each.
- Run the tester after each task. A method you haven't written yet shows as SKIP.
Task 1 — remove: lecture's delete REUSE
Lecture 24 built deleteKey in three cases (slides 70–98) and then wrote it as one recursive method (slides 102–112). As with put in the lab, the map's bookkeeping is provided. In BSTMap.java, replace the placeholder remove with this:
public V remove(K key) {
V old = get(key); // the value being removed, or null
if (old == null) {
return null; // the key is not in the map
}
root = delete(root, key); // lecture's deleteKey driver (L24 slide 103)
size--;
return old;
}
Then write the two helpers it needs, below remove.
1a. minNode: lecture's minValue (L24, slides 54–69)
// Lecture 24, slide 68
public int minValue(Node root) {
Node min = root;
//find minval
while (min.left != null) {
min = min.left;
}
return min.key;
}
| Lecture | BSTMap's minNode |
|---|---|
public int minValue(Node root) | private Node minNode(Node cur): it returns the node, not just the key, because delete needs the smallest node's key and its value |
return min.key; | return min; |
| the loop | the same: keep going left until there is no left child |
1b. delete: lecture's delete_Recursive (L24, slides 105–112)
// Lecture 24, slide 112
private Node delete_Recursive(Node root, int key) {
if (root == null)
return null;
if (key == root.key) {
if (root.left == null && root.right == null) {
return null;
}
if (root.right == null)
return root.left;
if (root.left == null)
return root.right;
int smallestValue = minValue(root.right);
root.key = smallestValue;
root.right = delete_Recursive(root.right, smallestValue);
return root;
}
if (key < root.key) {
root.left = delete_Recursive(root.left, key);
return root;
}
root.right = delete_Recursive(root.right, key);
return root;
}
| Lecture | BSTMap's delete |
|---|---|
delete_Recursive(Node root, int key) | private Node delete(Node cur, K key): write cur wherever lecture writes root |
key == root.key | key.compareTo(cur.key) == 0 |
key < root.key | key.compareTo(cur.key) < 0 (our key first, as in lecture, so no sign flip) |
int smallestValue = minValue(root.right);root.key = smallestValue; | Node smallest = minNode(cur.right);cur.key = smallest.key;and a new line: cur.value = smallest.value; |
delete_Recursive(root.right, smallestValue) | delete(cur.right, smallest.key) |
The one new line is the value. Lecture's nodes held only a key, so copying the key was enough. Our nodes hold a key and its value, and they must move together, or the smallest word would end up with the deleted word's value.
Ask Yourself — case 3
- In lecture's tree in words (dog, bee, fox, ant, cat, eel, gnu), which word replaces dog when you remove dog? Why that word, and not bee?
- Case 3 ends by deleting the smallest word from the right subtree. Can that word have two children? Which case removes it, and why can't the second delete go on forever?
- What would
get("eel")return after removing dog if you forgotcur.value = smallest.value;?
Run javac *.java and java Project06Tester. The Task 1 section should pass. To watch a removal, add map.remove("dog"); and a display.show(null, "removed dog"); line near the end of BSTDemo's lectureKeys.
Task 2 — Meet WordCounter READ
Open WordCounter.java. A WordCounter holds a map from each word to the number of times it appears, and a count of all the words it has read.
private MapSet<String, Integer> counts; // word -> how many times it appears private int totalWords; // every word read, repeats included
The constructor makes the map with new BSTMap<String, Integer>(). The field's type is MapSet, so next week you can swap in your HashMap by changing only that one line.
| Method | What it does | |
|---|---|---|
readWords(filename) | reads a file and returns its words, in order, as an ArrayList | provided |
totalWordCount(), uniqueWordCount() | all words read; different words (the map's size) | provided |
writeWordCount(filename) | writes every word and its count to a file | provided |
buildMap(words), getCount(word) | count the words; look up one word's count | Task 3 |
topWords(n) | the n most common words | Task 4 |
topWordsNotIn(other, n) | the n most common words that another text never uses | Task 5 |
As in the lab, each method you write starts with a throw placeholder line; delete it when you write the method.
Task 3 — Count the words REUSE
This is the counting loop you know from Python, and the one BSTDemo used in the lab:
| Python | WordCounter.buildMap |
|---|---|
for word in words:
counts[word] = counts.get(word, 0) + 1 | for each word in words:
get the word's count from the map
if the count is null (a new word): put the word with 1
otherwise: put the word with count + 1
add 1 to totalWords |
buildMap adds to the counts already in the map. Calling it twice counts both lists.
getCount(String word) returns how many times word appears, or 0 if it never does. get returns null for a missing word; getCount must turn that null into 0, because a null can't be returned as an int.
Check with tiny.txt: it has 60 words, 20 different, and "it" appears 10 times. Then run the tester; the Task 3 section should pass.
Task 4 — The most common words DESIGN
topWords(int n) returns an ArrayList of the n most common words, most common first. Your map keeps words in alphabetical order, not by count, so you have to search for the largest counts. Do it the simple way: pick the most common word not chosen yet, n times.
- Get
keys = counts.keySet()andvalues = counts.values().values.get(i)is the count ofkeys.get(i). - Make an empty ArrayList
top. - While
tophas fewer than n words and fewer words thankeys:- Set
best = -1, meaning "no word picked yet". - Go through every index i. If
keys.get(i)is not already intop, and best is -1 orvalues.get(i)is greater thanvalues.get(best), set best to i. - Add
keys.get(best)totop.
- Set
- Return
top.
top.contains(word) tells you whether a word is already chosen. Using greater than, not greater than or equal, means that when two words have the same count, the one earlier in the alphabet wins, because keySet lists it first.
For tiny.txt, topWords(6) is [it, of, the, was, age, epoch]: four words tied at 10, then two of the four words tied at 2, alphabetically.
Ask Yourself — is this fast enough?
- For n = 10 and the 43,968 different Reddit words, about how many times does the inner loop run?
- Would this approach work well for listing all 43,968 words by count? Why not?
Task 5 — Words the other text never uses MODIFY
topWordsNotIn(WordCounter other, int n) returns the n most common words in this text that never appear in other. Copy topWords and make two changes:
- Pick a word only if
other.getCount(word) == 0, as well as the conditions you already have. - There may be fewer than n such words. If a whole pass through the words leaves best at -1, there is nothing left to pick: stop and return
top. (Without this,keys.get(-1)crashes.)
For example, if this text is tiny.txt and other holds "it was the age of times", the four most common words other never uses are [epoch, season, belief, best].
Task 6 — Run the report CONNECT
WordReport uses your WordCounter to compute the tables for the three report questions below. You don't need to change it. Before you run it, write down your predictions for Question 1.
javac *.java java WordReport CLEANED_shakespeare.txt CLEANED_reddit_comments_2015.txt
Reading and counting 15 million Reddit words takes several seconds; that is your tree at work. Try java WordReport tiny.txt sorted.txt first to see the layout quickly.
If you see java.lang.OutOfMemoryError, give Java more memory: java -Xmx2g WordReport CLEANED_shakespeare.txt CLEANED_reddit_comments_2015.txt.
Run the basic checks
javac *.java java Project06Tester
Before using the tester, test each method yourself on tiny.txt. Project06Tester works like Lab06Tester: each line says what it did and what should happen, a failed check shows what the answer should be and what yours gave, and unwritten methods show as SKIP. It uses tiny.txt, so keep that file in your folder.
| Section | What it checks |
|---|---|
| Task 1: remove | each of lecture's three cases on lecture's tree in words, removing the root, the value moving with the key, missing keys, an empty map, and 20,000 random calls checked against Java's own sorted map |
| Task 3: buildMap and getCount | counts, totals, a second buildMap adding to the first, missing words giving 0, and tiny.txt |
| Task 4: topWords | order, ties going to the earlier word, n of 0, n larger than the number of words, an empty WordCounter |
| Task 5: topWordsNotIn | skipping the other text's words, running out of words, an empty other, a text compared with itself |
Report Format
Your intended audience is your peers who are not in this class but who have taken a computer science course. Your reader should be able to understand what you built, the important computer science ideas behind it, what experiments you performed, and what your results mean without having completed this assignment themselves.
Your Project 06 folder should look like this
Projects/
└── Project06/
├── Project06 Report (Google Doc)
├── MapSet.java
├── BSTMap.java
├── BSTDisplay.java
├── BSTDemo.java
├── WordCounter.java
├── WordReport.java
├── Lab06Tester.java
├── Project06Tester.java
├── tiny.txt
├── sorted.txt
└── Extension1/ (only if you did an extension)
Do not put the data files (CLEANED_shakespeare.txt, CLEANED_reddit_comments_2015.txt) in your folder; they are large, and we already have them.
Your project report should contain the following sections. Please include a header for each section.
Abstract
Briefly summarize the project in your own words. Identify both the core computer science ideas and the application: a map of ⟨key, value⟩ pairs built on a binary search tree, used to count every word in two large texts and compare how they use language. Briefly identify the questions you investigated. Detailed results belong in the Results section.
Results
Answer the three questions below. For each, include the table WordReport printed, then explain it. The data can't tell you why by itself; your explanation is the important part.
- The most common words. Compare the two top-10 lists. Did they match your predictions? What does each list suggest about who is writing and what they write about? Are any words in both lists? Which of your observations could come from the cleaning rather than from the writers?
- Whose vocabulary is bigger? Reddit has about 41 times as many words as Shakespeare, so of course it has more different words. To compare fairly, WordReport counts the different words in the first 365,342 words of each text, the same number of words from each. Before you look, predict which uses more different words. Then explain the result: why might it come out this way? Is this a fair comparison of one writer with many writers? What else would you want to know?
- Words the other never uses. List the ten most common words in each text that never appear in the other. Group them: which are old forms of words, which are names, which are about things that didn't exist yet, and which surprise you? Pick two and explain why the other text never uses them.
- Evidence: Present the relevant table or numerical result.
- Observation: Describe what the evidence actually shows.
- Interpretation: Explain what you think the result means and why it may have occurred.
Data Structure Analysis
Answer the following questions, using big-O notation where appropriate.
- When WordCounter counts a text, what is stored in each node of your BSTMap? What happens to the tree when buildMap meets a word for the first time, and what happens when it meets a word it has seen before?
- Give the running time of
getandputin your BSTMap, in terms of the height of the tree. What is the height in the best case and in the worst case for n keys? Use what you saw in Lab 06 withtiny.txtandsorted.txt. - When remove deletes a word with two children, why is the smallest word in its right subtree the right one to take its place? Why must its value move along with its key?
- Give the running time of
topWords(n)in terms of n and the number of different words, V. Why is it fine for n = 10, and why would it be a poor way to list every word by count?
Extensions
Describe any work you completed beyond the required project. Focus on the design and behavior of the extension: what capability you added, what classes or methods changed, how the new logic works, and how you determined that it worked. If you did not complete an extension, simply state that no extension was completed. Choose one or more of these, or propose your own:
- Your own words. Pick at least five words and compare how often each appears per 10,000 words in each text (
getCount(word) * 10000.0 / totalWordCount()). Why per 10,000 words rather than the raw counts? Choose words that tell a story, such as love, king, people, or money. - Words used only once. How many words appear exactly once in each text, and what fraction of each vocabulary is that? Why might the fractions differ?
- How fast does the vocabulary grow? Read through a text in order and record how many different words you have seen after every 50,000 words (
containsKeybefore eachputtells you whether a word is new). Make a table or graph for both texts. Do new words keep appearing at the same rate?
References/Acknowledgements
List the people and outside resources that contributed to your work. Include people you worked with or received help from, including TAs and instructors, and acknowledge outside references that helped you understand an algorithm, library, or programming technique.
Before You Submit
Project 06 is due on the date listed on the course's project page.
- Your personal Google Drive Projects/Project06 folder contains your completed Project 06 work.
- All of your
.javafiles compile together. - You have run
Lab06Testerand every section passes, including Tasks 5 and 6 (keySet, values, maxDepth). - You have run
Project06Testerand fixed every[FAIL]and[SKIP]. - You have run WordReport on both data files and included its tables in your report.
- Your report is a Google Doc named Project06 Report in your Projects/Project06 folder.
- Your report includes the Abstract, Results (Questions 1–3), Data Structure Analysis, Extensions, and References/Acknowledgements sections.
- The data files are not in your folder.
- Extensions must be submitted in separate folders inside your Project06 folder using the naming convention
Extension1,Extension2, and so on. Each extension folder must contain ALL files necessary to compile and run that extension (except the data files); do not rely on files located elsewhere in your Project06 folder.