企业官网建设流程全解析

如果你也在做软件构造实验二，大概率会在Graph Poet这道题前停下来多看一眼。这个任务本身很抽象：给一段英文语料，把相邻单词之间的关系抽象成一张有向带权图，然后给定一句输入，程序自动在单词之间寻找“桥词”并插入，最终拼出一段带着诗意的句子。听起来像某种自然语言处理小玩具，但它挂在实验二里其实是为了训练一件事——怎么把一个真实问题拆解成图模型，并且复用你已经写好的Graph接口。

我当时前后改了三天，踩过标点没剥干净的坑，也在bridge权重选错上翻过车。这题的难点不在于算法有多深，而在于所有细节都在“听起来很合理”的地方埋着雷。这篇就把我完整的解题思路、建模方式、代码结构、测试方法和踩坑记录都摊开讲，希望对正在做这道题的人有实际帮助。

提示：以下内容以课程通用背景为前提，学校编号不同、实验说明版本不同，具体规则以你拿到的实验文档为准，但核心思路通用。

1. 拿到题之后，先别急着写代码

1.1 这个任务到底在做什么

Graph Poet的任务分两半看。

前半段：读入一份英文语料，把语料中所有相邻出现的单词对转换成图里的边。比如语料里有这样一句：

I like Java. I love Java.

按单词划分后得到序列：I -> like -> Java -> I -> love -> Java。相邻单词之间产生两条边：I -> like、like -> Java、Java -> I、I -> love、love -> Java。如果同一个单词对出现多次，边的权重累加。

后半段：给定一句输入文本，例如：

I Java

正常情况下这两个词之间没有直接连边，但图中存在两条路径：I -> like -> Java和I -> love -> Java。like和love就是所谓的“桥词”。程序需要把桥词插回原句，输出：

I like Java

或者

I love Java

如果存在多个桥词，还需要按照一定规则选择其中一个。

这个过程本质上就是一个“模板补全”：你告诉程序两个词，程序去图里找一条长度为2的路径，把中间那个节点作为连接词填回去。这就是为什么这个题目叫“Graph Poet”——图诗，因为它生成的句子像是用词汇碎片拼接出来的诗句。

1.2 为什么要用图来解决

可能有人会想：我直接用字符串匹配不就行了吗？语料里找哪些词同时出现在“前一个词后面”和“后一个词前面”，这不就是两层遍历吗？

确实可以，但你要意识到两个问题。

第一，语料规模一旦变大，纯字符串匹配会把大量时间浪费在无关词上。而图结构天然给了你“从某个节点出发能到达哪些节点”的索引能力，查找桥词只需要两次邻居查询。

第二，这是软件构造实验，不是算法实验。这个题考察的是“抽象能力”：你能不能把一段文本中的语言关系抽象成一种可计算的结构。图的节点是单词，边是邻接关系，权重是共现频率，桥词是路径中间节点。这套模型一旦建立，后面所有操作都有了统一的思考框架。

我最初拿到题时也差点直接写一堆HashMap硬撸，后来看到实验前面的Graph接口设计，才意識到这就是为GraphPoet准备的。你前面实现的Graph、ConcreteEdgesGraph、ConcreteVerticesGraph，到这里全都要复用上。

2. 数据建模：把一首诗变成一张图

2.1 节点和边怎么定义

节点用String表示单词，图类型就是Graph<String>。这个选择没有悬念，关键在边怎么建。

边的语义是：单词A后面紧跟着单词B，则在A和B之间建立一条有向边，方向从A到B。如果A和B相邻出现多次，边的权重累加。这里要注意的是：

边必须跨行处理。

语料是一首完整的诗，很多时候换行处反而是语言联系最紧密的地方。比如：

Hello world Hello Java

第一行末尾的world和第二行开头的Hello之间也构成相邻关系。如果只按行内处理，会漏掉不少边。我当时就是先按行读入，下意识只对行内单词建边，结果后面的桥词怎么都找不全。正确做法是：读入全文后，把整个语料看作一个连续的单词流，再做滑动窗口式的相邻配对。

另一个容易漏的点是文件末尾的换行。如果文件以换行符结束，最后会多出一个空字符串，需要过滤掉。

2.2 词频权重要存哪里

Graph接口里已经提供了set方法。调用set(source, target, weight)时，如果边不存在则新建，如果边已存在会返回旧权重。所以累加的逻辑不能写成：

graph.set(words[i], words[i + 1], 1);

这样会覆盖原有权重。正确做法是：

Integer prevWeight = graph.targets(words[i]).get(words[i + 1]); if (prevWeight == null) { graph.set(words[i], words[i + 1], 1); } else { graph.set(words[i], words[i + 1], prevWeight + 1); }

有些同学喜欢自己维护一份Map<String, Map<String, Integer>>来记录权重，再同步到Graph里。我不推荐这么做。Graph本身就是容器，直接在Graph上查询旧权重并累加即可，否则两份数据一旦不一致，排查起来非常痛苦。

2.3 边界情况：大小写、标点、空串

这是Graph Poet最容易翻车的区域，没有之一。

大小写归一化。语料里可能是Hello，输入里是hello，如果不统一，图里查不到对应节点。我的做法是在建图和查询之前统一转小写。这个规则要在readme里写清楚，因为有些实验版本要求保留大小写，但绝大多数情况小写化能让桥词匹配更稳定。

标点剥离。这一条坑掉了无数人。看这个例子：

Hello, world. Hello, Java.

如果直接按空格分割，得到的是Hello,和world.，后面的逗号和句号都粘在单词上。这时候建出来的图节点就是hello,和world.，而你输入hello world时用的是hello和world，永远匹配不上。

我的处理方式是：先把非字母数字字符全部替换成空格，再按空白符分割。实现非常简单：

private List<String> tokenize(String text) { String cleaned = text.replaceAll("[^a-zA-Z0-9]", " "); String[] parts = cleaned.split("\\s+"); List<String> tokens = new ArrayList<>(); for (String part : parts) { if (!part.isEmpty()) { tokens.add(part.toLowerCase()); } } return tokens; }

注意这里的取舍：don't会被拆成don和t，it's会变成it和s。这在语义上不太对，但对这道题来说完全够用。如果你想保留撇号，可以把正则改成[^a-zA-Z0-9']，然后额外处理单引号在词首词尾的情况。我的建议是：先明确你的规则，再写代码。规则本身是什么不重要，重要的是规则要稳定、可解释。

空串过滤。split之后可能产生空字符串，建图时空节点会导致后面查询出现null，必须在tokenize阶段就处理掉。

3. Bridge搜索：如何在图里找到那根“桥”

3.1 朴素的遍历方式：两层扫描为什么可行

假设现在要处理输入句子中相邻的两个词w1和w2，需要找一个词w3，使得图中有边w1 -> w3且w3 -> w2。

最直接的想法是遍历图中所有节点candidate，检查它是否同时满足上述两个条件。这个做法在节点数不多时可接受，因为课程实验的语料一般就几百个词。但如果语料规模大，每次查找都遍历所有节点，输入句子又长，复杂度就不好看了。

一个更聪明的做法是只查邻居集合：

Set<String> fromW1 = graph.targets(w1).keySet(); // w1能到达哪些词 Set<String> toW2 = graph.sources(w2).keySet(); // 哪些词能到达w2

候选桥词就是两个集合的交集。这样我们完全不需要遍历所有节点，只需要看与w1和w2直接相连的那部分节点。图的索引能力在这里体现出来了。

3.2 为什么不需要BFS或Dijkstra

看到“找中间词”这个描述，很多人第一反应是“这是不是最短路径问题？要不要BFS？”

不用的。注意任务只要求插入一个桥词，也就是说只需要找长度为2的路径。长度为2的路径根本不需要BFS，直接求两层邻居交集就够了。BFS是用来处理“找最短路径、可能跨多个节点”的情况。如果哪一天题目改成“尽可能多地插入桥词把句子补全”，那才需要上BFS或Dijkstra。

这个理解很重要，它决定了实现复杂度。Graph Poet不是算法题，是工程题，用最匹配需求的工具即可。

3.3 多候选词的取舍规则

如果交集里有多个候选词，怎么选？

常见的规则有几种：

• 计算weight(w1, w3) + weight(w3, w2)，取总权重最大的。
• 计算weight(w1, w3) * weight(w3, w2)，取乘积最大的。
• 取两条边中较小权重的最大值（木桶原理）。
• 如果权重相同，按字母序或语料出现顺序取第一个。

课程实验文档通常会给一个指导规则。如果文档没写，我建议在代码里明确实现一种，并在注释里说明。我用的是“乘积最大优先”，因为边权可以理解为共现频率的近似，乘积更接近“两个转移同时成立”的联合度量。但说句实话，测试用例里一般不会在这个细节上卡人，只要你的规则稳定、可解释、输出可复现就行。

另外要注意一个特别隐蔽的情况：自环。如果w1和w2是同一个词，比如输入I I，而语料里恰好有I I这样的相邻出现，那么候选集合里会包含I自身。如果直接选它，输出会变成I I I，句子被无缘无故加长。一般实现里需要把candidate.equals(w1) || candidate.equals(w2)的节点过滤掉。这个细节在很多同学的实现里都漏了。

4. Poet类实现与整体装配

4.1 Poet类的接口设计与文件读取

GraphPoet类的标准结构是：

public class GraphPoet { private final Graph<String> graph = new ConcreteEdgesGraph<>(); public GraphPoet(File corpus) throws IOException { // 读文件，建图 } public String poem(String input) { // 找桥词，插入，返回新句子 } }

构造函数里读文件时，用BufferedReader按行读，然后不断把内容追加到同一个StringBuilder里，最后统一tokenize。不要每行单独建图，原因前面说了——跨行单词对会漏掉。

建图的循环如下：

List<String> tokens = tokenize(allText); for (int i = 0; i < tokens.size() - 1; i++) { String src = tokens.get(i); String dst = tokens.get(i + 1); Integer prev = graph.targets(src).get(dst); if (prev == null) { graph.set(src, dst, 1); } else { graph.set(src, dst, prev + 1); } }

这里有个小优化：graph.targets(src)返回的是Map<String, Integer>，也就是从源节点出发的所有边。我们不需要每次调用graph.set之前都重新查一次Map吗？其实set内部会处理，但为了拼权重，必须先知道旧值。先查再设，两步操作，逻辑清晰。

4.2 拼接输出：一个循环就能搞定

poem方法的实现是整个类中最容易出小毛病的地方。核心思想是：对输入句子的每一对相邻单词，尝试找桥词，找到就插入。

public String poem(String input) { List<String> words = tokenize(input); if (words.isEmpty()) { return ""; } if (words.size() == 1) { return words.get(0); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < words.size() - 1; i++) { sb.append(words.get(i)).append(" "); String bridge = findBridge(words.get(i), words.get(i + 1)); if (bridge != null) { sb.append(bridge).append(" "); } } sb.append(words.get(words.size() - 1)); return sb.toString(); }

注意几个细节。

第一，words.size() == 1时直接返回原词，因为没有任何相邻对，也就不存在桥词。如果这里不处理，循环根本进不去，最终sb为空，返回空字符串，测试直接挂掉。

第二，最后单独追加最后一个单词，避免多余空格。如果你用的是每次追加两个词再检查桥词的写法，很容易在句子末尾多出一个空格。

第三，findBridge方法返回null表示没有桥词，返回字符串表示要插入的桥词。这比返回Optional更直观，但你要确保调用方判空。

4.3 测试用例怎么写才稳

写测试是软件构造实验的重头戏，Graph Poet的测试尤其要覆盖各种“反直觉”的边界情况。我整理了一份自测清单：

基础桥词：语料a b c，输入a c，输出a b c。

无桥词：语料a b c，输入a d，输出a d。

权重优先：语料中a b c出现两次，a d c出现一次，输入a c，输出应为a b c。

大小写归一：语料Hello World，输入hello world，如果能找到桥词则说明归一化生效。

标点剥离：语料Hello, world.，输入hello world，应该能够正确建图。

空语料：空文件构造GraphPoet，任意输入返回原句。

单输入词：输入只有一个词，原样返回。

自环过滤：语料a a b，输入a b，如果不做自环过滤，可能错误输出a a b。

多行连续文本：语料第一行a b，第二行c d，那么b c这条边必须存在。

把上面这些case写成JUnit测试，跑通了基本就稳了。额外建议：用随机文本生成器构造一个较大的语料，然后跑一遍，重点观察程序性能和是否有隐藏的并发问题。这个实验的Graph实现一般不是线程安全的，但GraphPoet在单线程测试下足够。

5. 常见问题与调试实录

5.1 最常见的几个坑

我把这个题目做下来，遇到的坑基本集中在下面这些地方：

最让我印象深刻的还是第二个坑。我第一次写完建图后，打印Graph的toString，发现所有边的权重都是1。排查了半天，发现我把set当成了“如果存在就自动累加”的方法，实际它的语义是“覆盖”。后来看了Lab前面Graph接口文档里那句“returns the previous weight, or zero if there was no edge”，才算彻底明白。

5.2 调试技巧：用Graph.toString()看全图

Graph接口的toString()方法在调试阶段价值极大。建图完成后，直接打印graph对象，就能看到每个节点有哪些出边和入边。

举个例子，语料是：

I like Java

打印出来的效果类似：

I -> like (1) like -> Java (1)

这能帮你快速确认建图结果是否符合预期。我建议把打印放在构造函数里，用注释标记为“debug purpose”，测试跑完再删。不要小看这一步，很多隐蔽的建模错误都能在输出中一眼看出来。

另外，如果findBridge的结果不对，可以在方法里临时打印候选集合：

Set<String> candidates = new HashSet<>(fromW1); candidates.retainAll(toW2); System.out.println("candidates for " + w1 + " -> " + w2 + ": " + candidates);

看到候选集合，你很快能判断是图建错了，还是选择规则写错了。

5.3 性能和边界数据表现

Graph Poet的性能瓶颈通常不在算法上。每次findBridge需要两次邻居查询和一次集合交集，复杂度大约是O(outDegree(w1) + inDegree(w2))。输入句子有n个词，就执行n-1次，总复杂度线性可控。

但有一个场景要注意：如果语料非常大（几万行文本），tokenize阶段一次性把所有单词存进List可能占用不少内存。不过课程实验的语料一般就是一两首诗，完全不需要担心。

真正需要担心的是输入句子特别长时，StringBuilder的append次数变多。不过Java的StringBuilder有扩容机制，这也不是问题。理论上不需要额外优化，把逻辑写对就足够了。

6. 从这道题能带走的工程素养

6.1 把图当黑盒，才能不被实现绑死

Graph Poet最有价值的一点是：它完全基于Graph<String>接口工作，根本不关心底层是用ConcreteEdgesGraph还是ConcreteVerticesGraph。只要接口稳定，Poet类就能正确运行。

这意味着你可以在Poet里放心调用graph.set、graph.targets、graph.sources，不用管内部是邻接表还是边集合。这种“面向接口编程”的思想，正是软件构造课程反复强调的东西。做这道题的时候，试着把自己想象成Graph的用户，而不是Graph的实现者，你会对接口设计有更深的理解。

我自己的体会是：写ConcreteEdgesGraph时注意边的新建和复用，写ConcreteVerticesGraph时注意vertex的维护，而到了GraphPoet，这些都不重要了。这种分层带来的思维切换，是这个实验的真正训练目标。

6.2 扩展思路：从单bridge到多bridge

做完基础功能后，可以顺手想一想：如果题目改成“插入尽可能多的桥词，让输出句子更连贯”，怎么办？

这个扩展其实不难。只需要对输入句子中每一对相邻单词，都找一条从w1到w2的路径，把路径上的所有中间节点依次插入。找路径就回到了BFS或Dijkstra。实现时要注意路径长度可能超过2，插入顺序必须保持路径方向，否则句子会变得杂乱。

这个扩展实验我没写进最终提交，但自己想了一遍，对理解“为什么单bridge不需要BFS”特别有帮助。

6.3 一点个人体会

最后说点题外话。Graph Poet这个题目做好了，你以后看到很多“文本生成”“智能推荐”类的问题，都会觉得眼熟。本质上都是建模成图，然后在图上做一些邻居查询或路径搜索。比如购物网站里的“买了A的人还买了B”，跟这道题里的桥词查找完全是一个套路。

我在实际调试过程中最大的体会是：这个题几乎所有的bug都出在“输入数据比你想象得更脏”这件事上。标点、换行、大小写、空串，这些数据层面的细节，才是真正拉开完成度的地方。如果你现在正卡在某一个测试用例过不去，建议先打印一下Graph的toString，检查你的图长什么样——八成是建图环节某个词被弄脏了。