Project 2A: NGordnet (NGrams) | CS 61B Fall 2022
Copyright By PowCoder代写 加微信 powcoder
Course Info
Project 2A: NGordnet (NGrams)
In this project, we will build a browser based tool for exploring the history of word usage in English texts. We have provided the front end code (in Javascript and HTML) that collects user inputs and displays outputs. Your Java code will be the back end for this tool, accepting input and generating appropriate output for display.
A video introduction to this project can be found at this link.
To support this tool, you will write a series of Java packages that will allow for data analysis. Along the way we’ll get lots of experience with different useful data structures. The early part of the project (proj2a) will start by telling you exactly what functions to write and classes to create. The later parts (proj2b) will leave more open to your own design.
To get started, use git pull skeleton main as usual. You’ll also need to download the project 2 datafiles (not provided via github for space reasons). You can find them at this link. You should unzip this file (How to unzip folders on Windows; How to unzip folders on Mac) into the proj2 directory such that the “data” folder is at the same level as the “ngordnet” and “static” folders. Note that we’ve set up hidden .gitignore files in the skeleton code so that git will avoid uploading these data files. This is intentional. Uploading the data files to github will result in a lot of headaches for everybody, so please don’t mess with any filed called .gitignore. If you need to work on multiple machines, you should download the zip file once for each machine.
You should also go to the library-fa22 folder and run git pull to make sure you have all the library files you’ll need for this project. When adding libraries to your project, select ALL libraries in the library-fa22 directory (or, just import the directory as a whole).
If NgordnetQuery doesn’t compile, make sure you are using Java version 15 (preview) or higher (preferably 17+).
A video guide to setting up your computer for this project can be found at this link (video now available!).
Proj2A: Building an Ngrams Viewer #
The Google Ngram dataset provides many terabytes of information about the historical frequencies of all observed words and phrases in English (or more precisely all observed ngrams). Google provides the Google Ngram Viewer on the web, allowing users to visualize the relative historical popularity of words and phrases. For example, the link above plots the relative popularity of the phrases “global warming” (a 2gram) and “to the moon” (a 3gram).
In project 2a, you will be build a version of this tool that only handles 1grams. In other words, you’ll only be able to handle individual words. We’ll only use a small subset (around 300 megabytes) of the full 1grams dataset, as larger datasets will require more sophisticated techniques than we teach in 61B.
Most of your work for project 2a will be in the ngordnet.ngrams package, though some work will also be in ngordnet.main, as well as potentially the ngordnet.plotter package.
TimeSeries #
The first class you’ll need to write is TimeSeries.java. For this class, you will fill in the methods of the ngordnet/ngrams/TimeSeries.java file that we’ve provided in the skeleton.
Note: there are two constructors for this class, and you must complete them both.
A TimeSeries is a special purpose extension of the existing TreeMap class where the key type parameter is always Integer, and the value type parameter is always Double. Each key will correspond to a year, and each value a numerical data point for that year.
For example, the following code would create a TimeSeries and associate the number 3.6 with 1992 and 9.2 with 1993.
TimeSeries ts = new TimeSeries();
ts.put(1992, 3.6);
ts.put(1993, 9.2);
The TimeSeries class provides additional utility methods to the TreeMap class which it extends:
List
List
TimeSeries plus(TimeSeries x): Returns the yearwise sum of x and this.
TimeSeries dividedBy(TimeSeries x): Returns the yearwise quotient of this and x.
For example, the following code will create a TimeSeries of cat and dog populations and then compute their sum. Note that there is no value for 1993 because that year does not appear in either TimeSeries.
TimeSeries catPopulation = new TimeSeries();
catPopulation.put(1991, 0.0);
catPopulation.put(1992, 100.0);
catPopulation.put(1994, 200.0);
TimeSeries dogPopulation = new TimeSeries();
dogPopulation.put(1994, 400.0);
dogPopulation.put(1995, 500.0);
TimeSeries totalPopulation = catPopulation.plus(dogPopulation);
// expected: 1991: 0,
// 1992: 100
// 1994: 600
// 1995: 500
List
(Arrays.asList(1991, 1992, 1994, 1995));
assertEquals(expectedYears, totalPopulation.years());
List
(Arrays.asList(0.0, 100.0, 600.0, 500.0));
for (int i = 0; i < expectedTotal.size(); i += 1) {
assertEquals(expectedTotal.get(i), totalPopulation.data().get(i), 1E-10);
You may not add additional public methods to this class. You’re welcome to add additional private methods.
TimeSeries objects should have no instance variables. A TimeSeries is-a TreeMap. That means your TimeSeries class also has access to all methods that a TreeMap has, see https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/TreeMap.html.
The provided TestTimeSeries class provides a simple test of the TimeSeries class. Feel free to add your own tests. Note that the unit tests we gave you do not evaluate the correctness of the dividedBy method.
You’ll notice in the test above that we did not directly compare expectedTotal with totalPopulation.data(). This is because doubles are prone to rounding errors, especially after add or especially division operations operations (for reasons that you will learn in 61C). Thus, assertEquals(expectedTotal, totalPopulation.data()); may unexpectedly return false. Instead, the code above iterates through the two lists and compares them with an epsilon of 1E-10, meaning that so long as the two values are within 1E-10 of each other, they are considered equal.
You may assume that the dividedBy operation never divides by zero.
You should never impute any zeroes. In other words, nowhere should you have any code which fills in a zero if a value is unavailable.
NGramMap #
The NGramMap class will provide various convenient methods for interacting with Google’s NGrams dataset. This task is more open-ended and challenging than the creation of the TimeSeries class. As with TimeSeries, you’ll be filling in the methods of an existing NGramMap.java file.
As an example, the code below first creates an NGramMap from the top_14377_words.csv and total_counts.csv files (described below), then performs various operations related ot the occurrences of the word “fish” and “dog” in the period between 1850 and 1933.
// creates an NGramMap from a large dataset
NGramMap ngm = new NGramMap("./data/ngrams/top_14377_words.csv",
"./data/ngrams/total_counts.csv");
// returns the count of the number of occurrences of fish per year between 1850 and 1933.
TimeSeries fishCount = ngm.countHistory("fish", 1850, 1933);
assertEquals(136497.0, fishCount.get(1865), 1E-10);
assertEquals(444924.0, fishCount.get(1922), 1E-10);
TimeSeries totalCounts = ngm.totalCountHistory();
assertEquals(2563919231.0, totalCounts.get(1865), 1E-10);
// returns the relative weight of the word fish in each year between 1850 and 1933.
TimeSeries fishWeight = ngm.weightHistory("fish", 1850, 1933);
assertEquals(136497.0/2563919231.0, fishWeight.get(1865), 1E-7);
TimeSeries dogCount = ngm.countHistory("dog", 1850, 1876);
assertEquals(75819.0, dogCount.get(1865), 1E-10);
List
fishAndDog.add(“fish”);
fishAndDog.add(“dog”);
TimeSeries fishPlusDogWeight = ngm.summedWeightHistory(fishAndDog, 1865, 1866);
double expectedFishPlusDogWeight1865 = (136497.0 + 75819.0) / 2563919231.0;
assertEquals(expectedFishPlusDogWeight1865, fishPlusDogWeight.get(1865), 1E-10);
The NGramMap has the following constructors and functions you’ll need to fill in for this part:
NGramMap(String wordsFilename, String countsFilename): The constructor for a NGramMap.
TimeSeries countHistory(String word): Returns yearwise count of the given word for all available years.
TimeSeries totalCountHistory(): Returns yearwise count of all words for all time. This data should come from the data in the file specified by countsFilename, not from summing all words in the file given by wordsFilename.
TimeSeries weightHistory(String word): Returns yearwise relative frequency (a.k.a. normalized count) of the given word for all time. For example, if there were 100,000 words across all volumes in 1575 and 2,100 occurrences of the word “guitar”, then weightHistory(“guitar”) would have a value of 2100/100000 for the year 1575. If a word does not appear in a given year, that year should not be included in the TimeSeries.
TimeSeries summedWeightHistory(Collection
Additionally, another version of countHistory, weightHistory, and summedWeightHistory that take starting and ending year arguments.
Most of the work will be in the constructor. Make sure to pick your data structures carefully. As we saw in the Disjoint Sets lecture, picking the wrong data structures will make your life difficult and your code slow. If you find that your methods are very annoying to write, reconsider your data structures and try again.
You may not add additional public methods to this class. You’re welcome to add additional private methods.
Rather than using one of the large input files (e.g. top_14377_words.csv), we recommend starting with one of the smaller input files, either very_short.csv or words_that_start_with_q.csv.
Our provided tests only cover some methods. And some methods are only tested on a very large file. You may need to write additional tests.
You should never impute any zeroes. In other words, nowhere should you have any code which fills in a zero if a value is unavailable.
If it helps speed up your code, you can assume year arguments are between 1400 and 2100.
The N File Formats #
The NGram dataset comes in two different file types. The first type is a “words file”. Each line of a words file provides tab separated information about the history of a particular word in English during a given year.
airport 2007 175702 32788
airport 2008 173294 31271
request 2005 646179 81592
request 2006 677820 86967
request 2007 697645 92342
request 2008 795265 125775
wandered 2005 83769 32682
wandered 2006 87688 34647
wandered 2007 108634 40101
wandered 2008 171015 64395
The first entry in each row is the word. The second entry is the year. The third entry is the number of times that the word appeared in any book that year. The fourth entry is the number of distinct sources that contain that word. Your program should ignore this fourth column. For example, from the text file above, we can observe that the word wandered appeared 171,015 times during the year 2008, and these appearances were spread across 64,395 distinct texts. For this project, we never care about the fourth entry (total number of volumes).
The other type of file is a “counts file”. Each line of a counts file provides comma separated information about the total corpus of data available for each calendar year.
1470,984,10,1
1472,117652,902,2
1475,328918,1162,1
1476,20502,186,2
1477,376341,2479,2
The first entry in each row is the year. The second is the total number of words recorded from all texts that year. The third number is the total number of pages of text from that year. The fourth is the total number of distinct sources from that year. Your program should ignore the third and fourth columns. For example, we see that Google has exactly one English language text from the year 1470, and that it contains 984 words and 10 pages. For the purposes of our project the 10 and the 1 are irrelevant.
You may wonder why one file is tab separated and the other is comma separated. I didn’t do it, Google did. Luckily, this difference won’t be too hard to handle.
Implementation Requirements and Tips #
There is a lot to think about for this part of the project. We’re trying to mimic the situation in the real world where you have some big open ended problem and have to figure out the approach from scratch. This can be intimidating! It will likely take some time and a lot of experimentation to figure out how to proceed. To help keep things from being too difficult, we’ve at least provided a list of methods to implement. Keep in mind that in the real world (and in proj2b and proj3), even the list of methods will be your choice.
Your code should be fast enough that you can create an NGramMap using top_14377_words.csv. Loading should take less than 60 seconds (maybe a bit longer on an older computer). If your computer has enough memory, you should also be able to load top_49887_words.csv.
Avoid using a HashMap or TreeMap as an actual type argument for your maps. This is usually a sign that what you actually want is a custom defined type. In other words, if your instance variables include a nested mapping that looks like HashMap
We have not taught you how to read files in Java. We recommend using the In class. The official documentation can be found here. However, you’re welcome to use whatever technique you’d like that you learn about online. We provide an example class FileReaderDemo.java that gives examples of how to use In.
Setting Up a Web Server to Handle NgordnetQueries #
You should only do this part when you are fairly confident that TimeSeries and NGramMap are working properly.
HistoryTextHandler #
In this final part of project 2a, we’ll do a bit of software engineering. While this content isn’t strictly related to data structures, it is incredibly important to be be able to take projects and deploy them for real world use.
In your web browser, open up the ngordnet_2a.html file in the static folder. You can do this from your finder menu in your operating system, or by right clicking on the ngordnet_2a.html in IntelliJ, clicking “open in”, then “browser”. You can use whatever browser you want, though TAs will be most familiar with Chrome. You’ll see a web browser based interface that will ultimately (when you’re done with the project) allow a user to enter a list of words and get back a visualization.
Try entering “cat, dog” into the “words” box, then click “History (Text)”. You’ll see that nothing useful shows up. Optional: If you open the developer tools in your web browser (see Google for how to do this), you’ll see an error that looks like either “CONNECTION_REFUSED” or “INVALID_URL”. The problem is that the Javascript tries to access a server to generate the results, but there is no web server running that can handle the request to see the history of cat and dog.
Open the ngordnet.main.Main class. This class’s main first creates a HugNgordnetServer object. The API for this class is as follows: First, we call startUp on the HugNgordnetServer object, then we “register” one or more NgordnetQueryHandler using the register command. The precise details here are beyond the scope of our class.
The basic idea is that when you call hns.register(“historytext”, new DummyHistoryTextHandler(ngm));, an object of type DummyHistoryTextHandler is created that will handle any clicks to the History (Text) button.
Try running the ngordnet.main.Main class. Now open the “ngordnet_2a.html” file again, enter “cat, dog” again, then click “History (Text)”. This time, you should see a message that says
You entered the following info into the browser:
Words: [cat, dog]
Start Year: 2000
End Year: 2020
Now open ngordnet.main.DummyHistoryTextHandler, you’ll see a handle method. This is called whenever the user clicks the History (Text) button.
The expected behavior should instead be that when the user clicks “History (Text)” for the prompt above, the following text should be displayed:
cat: {2000=2.2087865424288107E-5, 2001=2.1437214466628103E-5, 2002=2.102009752618858E-5, 2003=2.1099354925803245E-5, 2004=2.1206903424010284E-5, 2005=2.2309178237122984E-5, 2006=2.1424257048399093E-5, 2007=2.1961829380775218E-5, 2008=2.210883364588823E-5}
dog: {2000=4.3433705100722223E-5, 2001=3.843462523591703E-5, 2002=4.022916153294561E-5, 2003=4.1551264004814845E-5, 2004=4.338616138022879E-5, 2005=4.829061466921298E-5, 2006=4.4223714489931575E-5, 2007=4.743844248399713E-5, 2008=5.1908191802793454E-5}
These numbers represent the relative popularity of the words cat and dog in the given years. Due to rounding error, your numbers may not be exactly the same as shown above. Your format should be exactly as shown above, specifically the word, followed by a colon, followed by a space, followed by a string representation of the appropriate TimeSeries where key value pairs are given as a comma separated list inside curly braces, with an equals sign between the key and values. Note that you don’t need to write any code to generate the string representation of each TimeSeries, you can just use the toString method.
Now it’s time to implement the HistoryText button!
Create a new file called HistoryTextHandler.java that takes the given NgordnetQuery and returns a String in the same format as above.
Modify the Main.java so that your HistoryTextHandler is used when someone clicks History (Text). In other words, instead of registering DummyHistoryTextHandler, you should register your HistoryTextHandler class instead.
The constructor for HistoryTextHandler should be of the following form: public HistoryTextHandler(NGramMap map).
Use the DummyHistoryTextHandler.java as a guide, pattern matching where appropriate. Being able to tinker with example code and bend it to your will is an incredibly important real world skill. Experiment away, don’t be afraid to break something!
For project 2a, you can ignore the k instance variable of NgordnetQuery.
Use the .toString() method built into the TimeSeries class that gets inherited from TreeMap.
For your HistoryTextHandler to be able to do something useful, it’s going to need to be able to access the data stored in your NGramMap. DO NOT MAKE THE NGRAM MAP INTO A STATIC VARIABLE! This is known as a “global variable” and is rarely the appropriate solution for any problem. Hint: Your HistoryTextHandler class can have a constructor.
HistoryHandler #
The text based history from the previous section is not useful for much other than autograding your work. Actually using our tool to discover interesting things will require visualization.
The ngordnet
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com