CSc 150

Objectives

• To practice with binary search trees
• To practice all of the good design principles we've seen within a larger context

Introduction

Your Mission

1. Create a thesaurus from a text file of keywords and synonyms.
2. Create a word counter that determines the frequency of each word in an input file (i.e. the number of times each word appears).
3. Use the previous two data structures to look at each word in the input file, determine if it is overused (appears too many times), and, if so, replace the word with a random synonym (if the entry exists in the thesaurus).

Requirements

You should use a binary search tree to store the thesaurus information. Each node in the tree should contain an entry in the thesaurus and an associated synonym list. The synonym list is really just an unordered collection of words, so reuse your Bag class to store the synonyms. You should be able to insert new entries/synonyms into the thesaurus, delete entries, and print the thesaurus in alphabetical order by entry (especially useful for debugging). You are also required to have a getSynonymFor method which returns a random synonym for a given word.

The frequency information for each word should also be stored in a binary search tree. Like the thesaurus, the tree will be organized by keyword. For those who like to see it in pictures, here's a sampling of how binary search trees will be used to store both the thesaurus info and the word frequency info:

And, as always, you are also not permitted to use any of Java's built-in containers in your program, such as ArrayList, Vector, Stack, LinkedList, etc. Use your own.

Finally, all documentation should be in Javadoc format for this project.

The Algorithm

for each word in the input file
{
   check word counter for frequency of word
   if frequency above some threshold (meaning it's overused)
   {
      check thesaurus for an entry
      if entry not there
         write out original word
      else  // entry is there
      {
         get a random synonym for that entry
         write out the random synonym
      } 
   }
   else  // word not overused
      write out original word
}

The threshold for word overuse should be easily changeable in your program. 2 is a good default (so a word is overused if it appears more than twice in the file). You should flesh out this algorithm using top-down design.

Why a BST?

For this project, both the word counter and the thesaurus will be searched a lot. The word counter gets searched for every word in the input file (to see if it's overused). The thesaurus gets searched for each overused word found. So an ADT with a good running time for searches is preferable. A binary search tree is a good choice since it has an average case running time of O(log n) for the search operation compared to O(n) average case search time for an array or linked list.

Files to Download

• BSTnode.java. This file shows what a node in a BST looks like. It contains a key that implements a Comparable interface as well as some associated data (of type Object). The associated data for this project is either the synonym list for the thesaurus, or the frequency for the word counter.

• LineReader.java. This handles file input for you. It will return the next line of data from a file as an array of Strings. How the line is parsed depends on the delimiter you give the LineReader upon construction. For example, if you give "," (a comma) for a delimiter, then LineReader's primary method, getNextLine will return an array parsed by commas. For example, it will turn this line:

  Al,Barb,Charlie

  into an array of three strings: "Al" in index 0, "Barb" in index 1, and "Charlie" in index 2. This will be useful when creating the thesaurus (whose text file is comma-delimited). When reading the primary input file, you'll want to use a space as a delimiter.

• StringWriter.java. This class handles file output for you. It has a write method, a goToNextLine method, and a closeFile method. Since LineReader gives you input one line at a time, use these methods to write to the output file one line at a time, and call goToNextLine between lines.

• smallThesaurus.txt and bigThesaurus.txt. These are the comma-delimited text files from which you'll build your thesaurus. Each line consists of an entry (the first word) and the remaining words on the line are synonyms. smallThesaurus.txt only contains 10 entries, so you can draw out the BST for this one by hand to see if your BST methods are working. I suggest working with this small one first. bigThesaurus.txt is a thesaurus with over 5000 entries, which should give your code quite a workout once you're sure your program makes the small version correctly.

• lamb.txt and apartment.txt. These are two sample input files that will be (supposedly) improved by your program. Each contains overused words. Of course, you should create your own test files too. When making input files, be sure not to have more than one space between any two words, including between sentences, or else LineReader will treat extra spaces as words.

Where do I start?

• You'll need a BinarySearchTree class to handle tree operations like insertion, deletion, searching, printing, etc. If you use the book's code as a guide, you should be aware of some of the crappy code it has. First, it doesn't provide a way to delete nodes (though we'll talk about that in class). Second, it has a print method instead of a toString method. (Yuck. Why is toString better?) Third, its insert method takes a simple Comparable object (they call it ComparisonKey) as a parameter. (Double yuck. What should it be instead? And why?)

• You'll want to know the right answers, so figure out the frequencies by hand for all the words in the two input files, what the thesaurus BST should look like for the small thesaurus file, and what the word counter BST will look like for the two input files.

• You'll need to write the Comparable interface and a class that implements it.

• Test the LineReader class on all of the text files I gave you to see how the parsing works. PITFALL ALERT: punctuation is going to get in the way. If a word has a trailing punctuation mark, like a comma or period, LineReader will consider the punctuation to be part of the word. This won't affect the thesaurus, but it will affect the primary input files like lamb.txt above. A line like

  really, really cold

  will be parsed to three words: "really," and "really" and "cold". But the frequency of "really" should actually be 2 for the above phrase. Extraneous punctuation should be stripped away when determining frequency. You may assume that all punctuation that appears will just be a single character trailing an actual word.

Extra Credit alert: One can extend our algorithm in many ways. Here are just a couple of ideas that would net extra credit.

• Note that our algorithm does not consider upper and lower case characters. "Computer" and "computer" would be considered two different words having two separate frequencies. It would be nice if they were considered the same word when determining overuse or not. Of course, when printing the final output file, the original cases should remain intact.

• It would be nice if the punctuation I told you to strip away above would still appear in the final output file in their appropriate places. This would require you to remember the punctuation after stripping it away so that you could write it out after, possibly, replacing the word with a synonym.

This project is big. START IT NOW. I'm giving you 2 weeks for a reason. I will be happy to critique and give feedback on designs you come up with, but I won't give you a design outright. That's your job. Think out the design on paper before you write a single line of code. And come see me even if you just want to make sure that you're on the right track.

Grading

• 20 points for correct output.
• 10 points for a working and well-designed BinarySearchTree class including insertion, deletion, searching, and a toString method.
• 10 points for class and method design, including what classes you decided to implement, what methods you placed into what classes, and how modular your code is.
• 10 points for other design issues including complete Javadoc documentation, robustness, reusable code, efficiency, and coherency

As always, practice good programming skills:

• Do not be a slave to the compiler. Figure out yourself if what you are writing makes good English sense and is also legal Java.
• Test Test Test. Writing your own debugging methods can help you test methods that otherwise wouldn't be testable until the entire program is complete. And test as you go! Make sure the little widgets are working before you start embedding them into bigger things.

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Administrative statement