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.

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.

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;
}
LectureBSTMap'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 loopthe 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;
}
LectureBSTMap's delete
delete_Recursive(Node root, int key)private Node delete(Node cur, K key): write cur wherever lecture writes root
key == root.keykey.compareTo(cur.key) == 0
key < root.keykey.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

  1. 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?
  2. 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?
  3. What would get("eel") return after removing dog if you forgot cur.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.

MethodWhat it does
readWords(filename)reads a file and returns its words, in order, as an ArrayListprovided
totalWordCount(), uniqueWordCount()all words read; different words (the map's size)provided
writeWordCount(filename)writes every word and its count to a fileprovided
buildMap(words), getCount(word)count the words; look up one word's countTask 3
topWords(n)the n most common wordsTask 4
topWordsNotIn(other, n)the n most common words that another text never usesTask 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:

PythonWordCounter.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.

  1. Get keys = counts.keySet() and values = counts.values(). values.get(i) is the count of keys.get(i).
  2. Make an empty ArrayList top.
  3. While top has fewer than n words and fewer words than keys:
    • Set best = -1, meaning "no word picked yet".
    • Go through every index i. If keys.get(i) is not already in top, and best is -1 or values.get(i) is greater than values.get(best), set best to i.
    • Add keys.get(best) to top.
  4. 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?

  1. For n = 10 and the 43,968 different Reddit words, about how many times does the inner loop run?
  2. 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:

  1. Pick a word only if other.getCount(word) == 0, as well as the conditions you already have.
  2. 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.

SectionWhat it checks
Task 1: removeeach 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 getCountcounts, totals, a second buildMap adding to the first, missing words giving 0, and tiny.txt
Task 4: topWordsorder, ties going to the earlier word, n of 0, n larger than the number of words, an empty WordCounter
Task 5: topWordsNotInskipping 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 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.

  1. 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?
  2. 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?
  3. 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.

Data Structure Analysis

Answer the following questions, using big-O notation where appropriate.

  1. 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?
  2. Give the running time of get and put in 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 with tiny.txt and sorted.txt.
  3. 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?
  4. 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:

  1. 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.
  2. 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?
  3. 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 (containsKey before each put tells 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 .java files compile together.
  • You have run Lab06Tester and every section passes, including Tasks 5 and 6 (keySet, values, maxDepth).
  • You have run Project06Tester and 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.
← Back to Lab 06