CMPS 12B讲解、辅导Java设计、辅导Java程序语言、讲解formats
解析C/C++编程|辅导R语言程序
CMPS 12B: HW 5
It’s not that bard
All assignments must be submitted through git. Please look at the Piazza
guide on submitting assignments.
Follow instructions, and carefully read through the input/output formats.
Please run the checker!
Clearly acknowledge sources, and mention if you discussed the problems
with other students or groups. In all cases, the course policy on collaboration
applies, and you should refrain from getting direct answers from anybody or
any source. If in doubt, please ask the instructors or TAs.
1 Problem description
Main objective: We’re going to do a word analysis of all the compositions of
William Shakespeare. Get the full text of all compositions of William Shakespeare
from the course website, on the HW page. The file is called shakespeare.txt.
(It was obtained from Project Guterberg, so there are some copyright messages
in it.) It is vital that you download the file and save it (right click on
the link, and then save). Do not copy and paste after clicking the
link, since that does funky things with whitespace.
We want to answer the following queries from the text.
For any word length ` and number k, what is the k most frequent word of
length
Format and Output: You should provide a Makefile. On running make,
it should create “Bard.jar”. You should run the jar with two command line
arguments: the first is an input file, the second is the output file.
You must assume that “shakespeare.txt” (with that exact name) is in the
solution directory HW5, which is where the jar file will be created.
You do not need to submit “shakespeare.txt” through git, or any of these
files. You obviously have to submit your java sources, Makefile, and README,
as usual.
Each line of the input file corresponds to a new query. The query is a pair
of numbers: LENGTH RANK. The first number is the length of the word,
the second number is the rank, which starts from 0. The ranking is done in
decreasing order of frequency, and increasing lexicographic order. Thus, if two
1words have the same frequency, then the word that is earlier lexicographically
has the smaller (earlier) rank.
So, “7 0” refers to the most frequent word of length 7. Or, “9 3” refers to
the fourth most frequent word of length 9.
The output for each line is the corresponding word. If no word exists, the
output is ’-’. This can happen if the Bard decided not to use any words of that
length, or there is no word of that rank. For example, if the input file is:
The output file is:
gloucester
messenger
business
personal
-
So “gloucester” is the most frequent word of 10 letters, etc. It turns out that
both “business” and “personal” (both with 8 letters) have the same frequency
of 230, but we rank “business” earlier than “personal”.
Instructions on parsing: It is very important that you follow these instructions.
In general, parsing literary texts is a fairly messy task, since we have
to make numerous decisions on how to split words. There is no one right way,
but you need to follow my way so that your output matches mine.
The short answer on how to parse is to tokenize by whitespace and any of
the following punctuation marks/symbols:
Question mark ()
Comma (,)
Period (.)
Exclamation mark (!)
Colon (:)
Semicolon (;)
Square brackets ([ or ])
Here’s one way of doing this. It is probably convenient to read the file line
by line, to get a string for each line You first replace each of the above symbols,
by a whitespace (like a tab). This can be done by the “replace” method for
strings. (https://www.javatpoint.com/java-string-replace)
Then, you tokenize the resulting string by whitespace. You can use the
“split” method. If the resulting string was called str, the command tokens =
str.trim().split("\\s+") would produce a string array tokens obtained by
splitting str by all whitespace. The trim method just removes any whitespace
at the beginning or end, to prevent empty strings from appearing in tokens.
2Each element (string) in tokens is a word. Furthermore, we will convert all
words lowercase, using the method toLowerCase().
Note that we are not splitting by hyphens, apostrophes, or quotation marks.
One can debate the merits of this, but please follow this scheme for consistency.
Suggestions on coding: You can use any data structures you want, including
any built in Java type/class. Hashtables are incredibly useful for this
problem, so you will want to check out Java’s hashtable class
(https://docs.oracle.com/javase/7/docs/api/java/util/Hashtable.html).
It is possible to pass through the file once, parse as described above, and
produce a hashtable that stores all words with their frequencies. Now, you need
to iterate over the hashtable to collect, for each length, all words of that length.
Then, you can sort these words by decreasing order of frequency, and break ties
among frequency using (increasing) lexicographic order. Comparators are a convenient
way to do this, and there are numerous examples online for this. I liked
the following: https://www.tutorialspoint.com/java/java using comparator.htm.
Basically, if you define a class for words that stores frequencies, you can define
a compare method that compares two objects of this class. Then, you can call
Java’s built in sort function on any arraylist of objects through Collections.sort.
Check out the link above for doing this.
If you set this all up, then the actual task of producing the output is quite
trivial. For each length, you already have words sorted by rank. So you do a
single lookup for each input given.
Example commands and outputs: On the HW website, you will find a
file Examples.zip. Download and unzip it. There are a number of input and
corresponding output files.
test-input.txt, test-output.txt. If you run your program with input
file test-input.txt, the output file should be exactly the same as
test-output.txt. This will be used by the checking script.
more-input.txt, more-output.txt. This is a pretty comprehensive suite
of tests. If you get this correct, you’re reasonably guaranteed to be correct
overall.
2 Grading
You code should terminate within 1 minute for any input file with, say, at most
100 queries. If it doesn’t, we will not give you credit. It’s quite hard to give
partial credit for this problem. You’ll notice that once you get a few corner
cases correct, your code will completely work.
1. (10 points) For a full solution as described above.
2. (3 points) Well, if you pass some test cases, but not others. If your code
works on more-input.txt, this is highly unlikely.
33 Fun facts
Have some fun with this assignment. Can you find out the number of unique
word that dear Bill used? What if you also tokenize by hyphens? What changes?
Some things that I learned.
Not surprisingly, “the” is the most common three letter word.
The longest word without hyphens is “honorificabilitudinitatibus”.
The coolest word, IMHO, is “anthropophaginian”.
“caeser” is more frequent that “brutus”, who both beat “othello”.
Clearly, “tennis” was played in Elizabethan times.
There are two “impossibilities” in all of Shakespeare’s work.