In this assignment, we begin the process of integrating a search engine into our web browser. The first step to building a search engine is to be able to analyze web pages based on their content. This will eventually allow us to rate how relevant a particular page is for a given user request. The content of a page is obviously correlated with the words it contains. For this assignment you will use a map implemented as a binary search tree to help you calculate and store the frequencies of words found in a given web page. Then you will print out all words (in alphabetical order) that occur at least the minimum frequency number of times and print each of these word's frequency count.
WORD FREQUENCY ---- --------- artifical 5 cat 3 dog 7 ...
Create a class called StringCountMap that will be used for
mapping Strings to integers. Implement this map as a binary search
tree. For this assignment, you should not the built-in Java classes
that do this task such as TreeMap, HashMap,
TreeSet, or HashSet. Your code should have
the following methods:
void add(String word): add a word to your map. If the word
is not present in the tree, add it with a count of 1. If the word is
already in the map, increment its count.int getCount(String word): get the count
associated with a particular word. get should return 0 if
the word is not in the map.void setTitle(String title): allow the
user to pass a String which represents a "title" for this map. Later
on, we will be using many StringCountMaps, each of which will
correspond to a different web page. It will be convenient to store the
URL for each web page in with the map itself. All this method does is
take the String title and store it in a private instance variable:
it's a one-line setter method.String getTitle(): return whatever String is stored
as the title for this map. It should be a one-line getter method.void print(int minFreqNum): print the title of
the map, then print out all the words (and their frequencies), in
alphabetical order, for words that occur at least
minFreqNum times.
Make sure to test your map appropriately. A main method would be a nice way to do this.
As we have in the past, we will use the Scanner class for reading
in files. In particular, we will use the next() method,
which grabs one token at a time. A token, in this context, is any
string of characters that is not broken up by whitespace or
non-alphanumeric characters.
The code for this part should start in your main method for StringCountMap. (You may wish to move your previous test code to a "test" method, or something like that). In your main method, use a Scanner to read in a file, one token at a time, and output the tokens to the screen as you read them. You should try your program out on an HTML file, since these are the files that describe how web pages are rendered. You can grab html from any web page that you like: in Firefox, go to a web page, then go to the File menu, and choose "Save Page As..." In the "Save As Type" box, choose "Web Page, HTML only." Make sure that you save your HTML file to the same directory where your Java code is. To pass the name of this file off to your Java program, you should use as a command-line argument, just as you did on the Sudoku assignment.
After you have your Scanner code working, you should modify your Scanner usage as follows:
in = new Scanner(new File(args[0]),"ISO-8859-1");
in.useDelimiter("[\\s\\W]+");
The "ISO-8859-1" inside the Scanner constructor indicates that if there are any characters in the dataset with extended ASCII values (above 160), they should be interpreted according to the ISO-8859-1 standard, which means that they should be interpreted as Western European characters. Occasionally students obtain webpages with strange characters: umlauts always cause trouble if you don't do this.
The useDelimiter code above indicates that any characters that are whitespace and not part of words, i.e. punctuation and the like, should be used as delimiters and not actually read. This is less than a perfect solution: your program will still separate words under some circumstances incorrectly from your input file, such as dealing poorly with contractions and that sort of thing. Still, this solution is "good enough" for this assignment, though feel free to tweak it further if you like. You should, though, use the toLowerCase for Strings to convert them all to lower case so that words are counted as equivalent regardless of case.
To summarize: when you complete this part, you should be able to type
java StringCountMap filename.html mincount
(where filename.html is the name of your html file, and mincount is an integer that is 0 or bigger), and your program will appropriately enter all tokens from the HTML file into your map. Your program will then call the print method of your map to print out all tokens in alphabetical order with their word frequencies of mincount or greater.
You will actually use two different StringCountMaps in your main method. One such map will be used for storing frequencies of words. The other will be used for storing words in an "ignore list." The "ignore list" contains a list of HTML tokens that your program should ignore when it reads your HTML file. For example, every HTML file has a
<HTML>token. Your search engine will want to ignore this, since it should focus on actual words in the web page. (Technically, the ignore list is a set, not a map; but I'm not going to ask you to also create a WordSet. Just use StringCountMap and don't worry about the frequencies or the title.)
In the end, your main method for StringCountMap should take three command-line arguments. The first one is the filename of the HTML file to be read. The second is the minumum word frequency to use when printing. The third argument is the filename of the ignore list, which should just be a file containing a list of HTML tokens to ignore. In other words, running the Java program should look like:
java StringCountMap filename.html mincount ignorelist.txt
Part of this assignment involves creating an ignore list. Don't spend a lot of time on this, but see if you can figure out some of the most important HTML tokens to get in here.
Part 1: You should turn in a design document for the project. Think about what your StringCountMap needs to look like and how it needs to be structured. Then think about how to integrate this with reading HTML files and adding an ignore list.
Make sure to include estimates of how long you think each part of the assignment will take you to do.
Parts 2 and 3: Submit the final assignment. Get Part 2 working first before you move on to Part 3.
Have fun, and good luck!
Many thanks to Tia Newhall and Lisa Meeden at Swarthmore College.