红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【CS61B】Project2A-Ngordnet (NGrams)

发表于 分类于
本文字数： 9.6k 阅读时长 ≈ 17 分钟
CS61B的Project2A，复现了一个简单的Google Books Ngram Viewer

Project2A-Ngordnet (NGrams)

这个项目要求实现一个类似于Google Books Ngram Viewer的查看器，这个系统提供了Google数据库的英文文本中所有被观察到的词汇和短语的历史频率，可以让用户可视化指定词汇与短语在历史上的流行程度

在这个项目中只需要实现一个单词的处理

TimeSeries

TimeSeries是TreeMap的一个拓展，键总是int，值总是double，分别对应一个年份与那个年份对应的数值数据点，如下面的设置：

1
2
3
TimeSeries ts = new TimeSeries();
ts.put(1992,3.6);
ts.put(1993,9.2);

注意：

  • 该对象不具有实例变量
  • 需要比较两个数据，若某年份或数值不可用，不能用零替代
  • 进行比较时，由于双精度数之间的比较在舍入时容易产生误差，故可以使用assertThat(x).isWithin(1E-10).of(y)来进行比较

额外知识：如何对TreeMap进行遍历

拷贝构造

要求创建传入ts的拷贝，且数据只包括startYear到endYear之间的数据

这里使用foreach遍历，对每个key进行判断，若在给定范围内，则加入拷贝TimeSeries

1
2
3
4
5
6
public TimeSeries(TimeSeries ts, int startYear, int endYear) {
    super();
    ts.forEach((key, val)->{
        if(key>=startYear&&key<=endYear)this.put(key, val);
    });
}

years()

要求升序返回当前time series中所有的年份

years为键，使用treemap的keySet方法生成对键的拷贝set，并放入列表并返回

1
2
3
4
5
6
7
8
public List<Integer> years() {
    List<Integer> yearsList = new ArrayList<>();
    for (int it : this.keySet()) {
        yearsList.add(it);
    }

    return yearsList;
}

data()

要求返回当前time series中的所有数据，要与years()中的年份顺序一致

生成yearslist，遍历并使用treemap的get方法获取每个键对应的data值并存入列表并返回

1
2
3
4
5
6
7
8
public List<Double> data() {
    List<Double> dataList = new ArrayList<>();
    List<Integer> yearsList = years();
    for(int it: yearsList){
        dataList.add(this.get(it));
    }
    return dataList;
}

plus()

返回传入ts与当前ts对应年份的data之和，若一方存在年份而另一方不存在，则结果为存在一方的data值，若都不存在就忽略

为了能将当前与ts的time series，我们新建一个hashset，将两个time series的keyset全放入新建的set，遍历，若一边不存在直接将另一边对应value，若都在则相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TimeSeries plus(TimeSeries ts) {
        TimeSeries returnedTs = new TimeSeries();
        Set<Integer> totSet = new HashSet<>();
        totSet.addAll(ts.keySet());
        totSet.addAll(this.keySet());
        for(int it: totSet ){
            if(ts.containsKey(it)&&(!this.containsKey(it))){
                returnedTs.put(it, ts.get(it));
            }
            else if ((!ts.containsKey(it))&&this.containsKey(it)){
                returnedTs.put(it, this.get(it));
            }
            else{
                returnedTs.put(it, ts.get(it)+this.get(it));
            }
        }
        return returnedTs;
    }

dividedby()

返回当前time series除以ts的对应的data，若ts存在当前表不存在的年份，抛出异常

若ts存在而当前不存在则跳过

1
2
3
4
5
6
7
8
9
10
public TimeSeries dividedBy(TimeSeries ts) {
    TimeSeries result = new TimeSeries();
    for(int it: this.keySet()){
        if(!ts.containsKey(it)){
            throw new IllegalArgumentException(it+"is missing in this TimeSeries");
        }
        result.put(it, this.get(it)/ts.get(it));
    }
    return result;
}

NGramMap

该类是实现NGramMap的主要类

该类提供了许多方便的方法用于NGram实现，不需要extend其他类

这个类的主要任务是实现constructor，便于解析数据文件并存在合适的数据结构中

输入文件格式

有两种文件类型，

第一种是words file，提供了有关特定单词在特定年份的英语历史记录的制表符分割信息

第一个条目为单词，第二个为年份，第三个为该单词在当年在任何书中出现的次数，第四个为包含该单词的不同来源的数量，程序需要忽略第四列

第二种为counts file，每一行都提供了每一年可用数据总语料库的信息，用逗号分隔

第一个条目是年份，第二个条目是当年从所有语料中记录的总单词数，第三个条目是该年的文本总页数，第四个是该年的不同来源总数，程序需要忽略第三四列

使用In类读取文件

Java中可以使用In类读取文件

可以在这里看到详细文档

这是一个读取文件的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main;

import edu.princeton.cs.algs4.In;

import static utils.Utils.*;

public class FileReadDemo {
    public static void main(String[] args) {
        In in = new In(SHORT_WORDS_FILE);
        int i = 0;

        while (!in.isEmpty()) {
            i += 1;
            String nextLine = in.readLine();
            System.out.print("Line " + i + " is: ");
            System.out.println(nextLine);
            System.out.print("After splitting on tab characters, the first word is: ");
            String[] splitLine = nextLine.split("\t");
            System.out.println(splitLine[0]);
        }
    }
}

构造函数

由于计算频率需要知道每个单词每年的数量与当年所有单词的总数量，我们需要map来存储年份->总单词量的映射与单词->对应Time Series的映射（提示中写道尽量避免使用map嵌套，故我们使用自己的Time Series，这样也可以方便操作数据与提高性能）

读取文件使用的类是课程给定的In类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public NGramMap(String wordsFilename, String countsFilename) {
    yearCount = new TimeSeries();
    wordsCount = new HashMap<>();
    In inWords = new In(wordsFilename);
    In inCounts = new In(countsFilename);
    while(!inWords.isEmpty()){
        String nextLine1 = inWords.readLine();
        String[] splitLine1 = nextLine1.split("\t");
        TimeSeries temp = wordsCount.get(splitLine1[0]);
        if (!wordsCount.containsKey(splitLine1[0])){
            temp = new TimeSeries();
            wordsCount.put(splitLine1[0], temp);
        }

        temp.put(Integer.parseInt(splitLine1[1]), Double.parseDouble(splitLine1[2]));
    }
    while(!inCounts.isEmpty()){
        String nextLine2 = inCounts.readLine();
        String[] splitLine2 = nextLine2.split(",");
        yearCount.put(Integer.parseInt(splitLine2[0]), Double.parseDouble(splitLine2[1]));
    }

}

我们创建了两个存储文件内容的结构

  • yearCount－负责记录每一年的总次数作为分母，使用TImeSeries类而非普通的map，方便后续进行操作
  • wordsCount - 负责记录每一个单词在不同年份出现的次数，故使用了int与TimeSeries的嵌套

wordsCount的读入有些麻烦，首先需要读取当前单词对应的TimeSeries，若为空则证明还未存在过，则创建新的TimeSeries并存入，最后将对应单词的年份－个数组成的TimeSeries（temp）存入wordsCount

countHIstory()

返回一个TimeSeries，记录了给定单词在STARTYEAR到ENDYEAR间的出现次数

注意，这里返回的TimeSeries要求深拷贝以避免对原数据造成影响

1
2
3
4
5
6
7
8
9
10
11
public TimeSeries countHistory(String word, int startYear, int endYear) {
   TimeSeries tempSeries = wordsCount.get(word);
   if (tempSeries == null) return new TimeSeries();
   TimeSeries returnedSeries = new TimeSeries();
   for (int it : tempSeries.keySet()){
       if (it >=startYear&&it<=endYear){
           returnedSeries.put(it, tempSeries.get(it));
       }
   }
   return returnedSeries;
}

首先获得对应单词的TimeSeries，判断是否为空，为空则返回一个空的

否则遍历keySet，选择在规定区间内的year对应的计数数据存入新的TimeSeries

对应的重载版本取消了年份区间的要求，即深拷贝所有对应word对应年份的数据

这里转移数据时可以使用putAll方法，方便的把所有数据转移到新TimeSeries中

weightHistory()

返回一个TimeSeries，记录了给定单词在STARTYEAR与ENDYEAR间的单词出现频率（该单词在每年出现次数占该年所有单词出现次数的比例）

1
2
3
4
5
6
7
8
9
10
11
public TimeSeries weightHistory(String word, int startYear, int endYear) {
    TimeSeries years = countHistory(word, startYear, endYear);
    TimeSeries result = new TimeSeries();
    for(int year:years.keySet()){
        if(!yearCount.containsKey(year)) continue;
        double weight = yearCount.get(year);
        if (weight==0.0) continue;
        result.put(year, years.get(year)/weight);
    }
    return result;
}

这里我们就可以使用已经创建的countHIstory方法获取该单词在对应年份中的所有计数数据

若年份不存在则跳过，否则我们获取当年的所有单词数（yearCount），这里要额外判断一下，让分母不为0

若符合所有条件，则计算频率并存入TimeSeries

对应的重载版本取消了年份区间的要求，对应调用不同函数即可

summedWeightHistory()

返回一个TimeSeries，记录了在STARTYEAR与ENDYEAR间给定所有单词在每一年的出现频率之和，若不存在则忽略

1
2
3
4
5
6
7
8
9
10
11
12
13
public TimeSeries summedWeightHistory(Collection<String> words,
                                      int startYear, int endYear) {
    TimeSeries result = new TimeSeries();
    for (String word:words){
        TimeSeries single = weightHistory(word, startYear, endYear);
        for (int year: single.keySet()){
            if (!result.containsKey(year)) result.put(year, single.get(year));
            else result.put(year, result.get(year)+single.get(year));
        }

    }
    return result;
}

这里给的是一个words的collection，我们首先需要解包成每一个word，并使用weightHistory计算该单词在规定区间内的权重

遍历single的keySet，若year不存在则先放入第一组的single值，若存在则累加

对应的重载版本取消了年份区间的要求，对应调用不同重载函数就行

HistoryTextHandler

下面需要设计一个前端以便用户交互

运行Main.java，可以发现服务器成功启动的提示，打开ngordnet_2a.html输入数据cat,dog，点击history(text)按钮，显示如下：

1
2
3
4
You entered the following info into the browser:
Words: [cat, dog]
Start Year: 2000
End Year: 2020

这时调用了DummyHistoryTextHandler中的handle方法，最后的期望结果如下：

1
2
cat: {2000=1.71568475416827E-5, 2001=1.6120939684412677E-5, 2002=1.61742010630623E-5, 2003=1.703155141714967E-5, 2004=1.7418408946715716E-5, 2005=1.8042211615010028E-5, 2006=1.8126126955841936E-5, 2007=1.9411504094739293E-5, 2008=1.9999492186117545E-5, 2009=2.1599428349729816E-5, 2010=2.1712564894218663E-5, 2011=2.4857238078766228E-5, 2012=2.4198586699546612E-5, 2013=2.3131865569578688E-5, 2014=2.5344693375481996E-5, 2015=2.5237182007765998E-5, 2016=2.3157514119191215E-5, 2017=2.482102172595473E-5, 2018=2.3556758130732888E-5, 2019=2.4581322086049953E-5}
dog: {2000=3.127517699525712E-5, 2001=2.99511426723737E-5, 2002=3.0283458650225453E-5, 2003=3.1470761877596034E-5, 2004=3.2890514515432536E-5, 2005=3.753038415155302E-5, 2006=3.74430614362125E-5, 2007=3.987077208249744E-5, 2008=4.267197824115907E-5, 2009=4.81026086549733E-5, 2010=5.30567576173992E-5, 2011=6.048536820577008E-5, 2012=5.179787485962082E-5, 2013=5.0225599367200654E-5, 2014=5.5575537540090384E-5, 2015=5.44261096781696E-5, 2016=4.805214145459557E-5, 2017=5.4171157785607686E-5, 2018=5.206751570646653E-5, 2019=5.5807040409297486E-5}

即显示了每一年对应的出现权重

创建一个java文件HistoryTextHandler实现

构造函数

1
2
3
4
5
6
NGramMap map;
Map<String, TimeSeries> wordsHistory;
public HistoryTextHandler(NGramMap map){
    this.map = map;
    wordsHistory = new HashMap<>();
}

使用NGramMap存储存入的map，并用map存储得到的结果以便字符串输出

handle()

handle负责收集输入的数据，在前端页面按下history(text)便会调用该方法，我们在这里计算并存储每个汉字对应的年份与权重

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public String handle(NgordnetQuery q) {
    List<String> words = q.words();
    int startYear = q.startYear();
    int endYear = q.endYear();

    for (String word:words){
        TimeSeries SingleWeight = map.weightHistory(word, startYear, endYear);
        wordsHistory.put(word, SingleWeight);
    }
    return this.toString();
}

遍历words，取出每一个word通过map的方法计算指定年份间的权重，并存入wordsHistory

以字符串形式返回数据，这里需要重写toString方法

@Override toString()

为了可以直接在handle中返回最终结果，需要重写toString方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public String toString(){
    StringBuilder returnedString = new StringBuilder();
    for(String word:wordsHistory.keySet()){
        returnedString.append(word).append(": {");
        TimeSeries wordWeight = wordsHistory.get(word);
        Iterator<Integer> it = wordWeight.keySet().iterator();
        while(it.hasNext()){
            int year = it.next();
            returnedString.append(year).append("=").append(wordWeight.get(year));
            if (it.hasNext()){
                returnedString.append(", ");
            }

        }
        returnedString.append("}").append('\n');
    }
    return returnedString.toString();
}

使用StringBuilder以方便构建字符串，通过遍历wordsHistory的键一点点构建列表

注意，这里在遍历值的时候使用了迭代器，因为最后一个值不能留逗号，故使用迭代器判断还有没有下一个值，有的情况下才加逗号

HistoryHandler

图形实现是靠base64码解码成为图像的

该项目提供了Plot库，有两个重要方法：

  • ngordnet.Plotter.generateTimeSeriesChart提供string列表与TimeSeries，返回对应图像（XYChart类），其中不同TimeSeries有不同颜色，按照string列表分配
  • ngordnet.Plotter.encodeChartAsString将上面方法生成的图像编码为base64码
  • ngordnet.Plotter.displayChart对base64解码并显示图像

创建一个HistoryHandler文件实现图像显示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class HistoryHandler extends NgordnetQueryHandler {
    NGramMap map;
    public HistoryHandler(NGramMap map){
        this.map = map;
    }
    @Override
    public String handle(NgordnetQuery q) {
        List<String> words = q.words();
        List<TimeSeries> lts = new ArrayList<>();
        int startYear = q.startYear();
        int endYear = q.endYear();
        for (String word: words){
            lts.add(map.weightHistory(word,startYear,endYear));
        }

        XYChart chart = Plotter.generateTimeSeriesChart(words, lts);

        return Plotter.encodeChartAsString(chart);
    }
}

模仿demo即可，通过构造函数拷贝传入的map，接受输入的数据，通过map的方法计算权重并加入一个TimeSeries列表，通过内置的Plot库方法生成图表-加密为base64并返回