Princeton Algorithms, Part II, WordNet
普林斯顿大学算法课 WordNet 题解与代码
首先要理解什么是 WordNet，这里定义了同义词集、下位词、上位词、逻辑门等计算语言学的复杂概念，确实不太好懂，但是总体上说，它是一个有根的有向无环图 a rooted DAG，但是它不一定是树。
image
同义词集列表中第一个字段是 id，第二个字段是同义词集，构成同义词集的各个名词之间用空格分隔，第三个字段与本次作业无关。
image
上位词列表中第一个字段表示同义词的 id，后续字段是改同义词的上位词 id 号，一个词可以有多个上位词，所以可能有多个字段，这就相当于是确定了 DAG 中的边的关系。
image
在 WordNet 的类的构造中，参数为 null 或者单词不是 WordNet 中有效的单词，给出异常，这个比较好做。难以理解的是 The input to the constructor does not correspond to a rooted DAG. 这个要求，我们如何才能确定自己构造的是不是一个有根的有向无环图？实际上，algs4.jar 中的 Digraph（有向图）给出了 2 个函数，indegree() 和 outdegree() 可以很方便地计算一个顶点的入度和出度，我们可以通过这个来判断是不是一个 rooted DAG。
除了是不是单根，还需要调用 DirectedCycle 或者 Topological 去检查是不是有环。
private void validate(Digraph g) {
assert g != null;
int vertexNumber = g.V();
int rootNumber = 0;
for (int i = 0; i < vertexNumber; i++) {
// 出度为 0 的点是根节点（没有上位词的同义词集）
if (g.outdegree(i) == 0) {
rootNumber++;
}
}
// 根节点不足 1 或者大于 1 都不满足条件
if (rootNumber != 1) {
throw new IllegalArgumentException();
}
// The program uses neither 'DirectedCycle' nor 'Topological' to check whether the digraph is a DAG.
DirectedCycle dc = new DirectedCycle(g);
if (dc.hasCycle()) {
throw new IllegalArgumentException();
}
}
最近公共祖先比较好理解，推广到顶点的集合也很简单，就是找到所有 SAP 的最短的。
求公共祖先的过程是一个广度优先搜索的过程。
while (!q.isEmpty()) {
int x = q.poll();
Iterable<Integer> bag = g.adj(x);
// 加入后面的点
for (int vv : bag) {
if (!visited[vv]) {
q.add(vv);
visited[vv] = true;
// 更新距离
int d = distanceV.get(x);
int dd = distanceV.getOrDefault(vv, d + 1);
distanceV.put(vv, dd);
}
}
}
具体的策略是，先对 v 点做一次广搜，直到根结点，在每一次搜索的时候记录下 depth。
然后对 w 做一次广搜，搜索过程中遇到符合条件的（搜索过的），都是祖先，记录下 depth 并相加，取最小的 depth 就是最近公共祖先。
最多对所有的点访问 2 次（从 v 出发一次，从 w 出发一次），所以时间复杂度只与点的个数有关。
if (distanceV.containsKey(x)) {
// 更新最短的 LCA
int minDistance = distanceV.get(x) + distanceW.get(x);
if (sap[0] == -1 || minDistance < sap[0]) {
sap[0] = minDistance;
sap[1] = x;
}
}
// 这里不是 else 的关系，要继续往上找
Iterable<Integer> bag = g.adj(x);
for (int vv : bag) {
if (!visited[vv]) {
q.add(vv);
visited[vv] = true;
// 更新距离
int d = distanceW.get(x);
int dd = distanceW.getOrDefault(vv, d + 1);
distanceW.put(vv, dd);
}
}
另外在实现的时候需要注意性能和安全，例如有些可以在构造的时候就缓存出来的值就在构造的时候缓存好，不要等用的时候再去遍历。
validate(word);
// 直接查缓存就可以了
return synsetToIdMap.containsKey(word);
以及有些返回类型是 Iterable 的，一定要确保返回类型不可变，不要返回原来的那个，要 new 一个新的去返回。
// 时刻记得做成不可变的
this.g = new Digraph(g);
// 时刻注意这种类型返回的时候一定要不可变，所以这里返回的时候返回一个新的，不返回原来那个
return new ArrayList<>(synsetToIdMap.keySet());
Princeton 的作业质量高还在于它的异常处理，需要注意所有不合法情况的判断，本题中对应的是单词为 null，更进一步的是单词不存在于单词集中。而对于图，则需要满足 DAG 和 rooted 这两个条件。
封装的情况也需要考虑，例如本题，在搜索 sap(int, int) 和 sap(Iterable, Iterable) 的时候，可以将这两个功能抽象出来，做一次封装。
最简单的当然是写 sap(int, int)，然后对于 sap(Iterable, Iterable) 的情况，做一次双重循环，对于每一个 i 对于每一个 j 做一次 sap(i, j) 并取最小值。
但是这样的写法是不是真的足够好？在搜索的时候是不是重复搜索了很多？
所以我们可以按下面代码所述，进行更合理的封装和优化，对于已经搜索过的，就不再搜索了。
需要注意的是本题存在的映射关系有：“已知 id 获取同义词集”，“已知单词获取该单词对应的同义词集”这两种。其中，“已知单词获取该单词对应的同义词集”可以由“已知单词获取 id”和“已知 id 获取同义词集”完成，所以我们只需要保存“已知单词获取 id”和“已知 id 获取同义词集”这样两个 HashMap 即可。
Outcast 就非常简单了，WordNet 写好了以后直接调用，取最大值就好。
完整代码参见 https://gitlab.jxtxzzw.com/jxtxzzw/coursera_assignments 或者 https://www.jxtxzzw.com/archives/5263
网友评论