企业官网建设流程全解析

如果你正在做软件构造 Lab2，大概率会在 Problem1.4 Graph Poet 上卡一会儿。这个题的核心是用自己实现的有向图接口做一个“诗歌生成器”：给一段语料库，程序学会词与词之间的前后关系，再给你要写的句子，自动在相邻单词之间插入一个“桥接词”，让整句话读起来有点诗意。我第一次看到题目时也没太明白，后来把 Graph 接口、分词、路径查找这几个点串起来，发现思路其实很清晰。这篇文章就把完整的解题思路拆开讲，适合正在做实验的学生，也适合想了解怎么用图做文本生成的人。

1. 先读懂题目：Graph Poet 本质上是一个“词接龙”任务

1.1 从“诗歌生成”这个需求说起

Graph Poet 并不是真的在创作诗歌，它做的是一个非常朴素的文本变换：给定一个语料库（corpus），程序从里面学习单词之间“谁后面经常跟着谁”的关系，然后把你输入的句子中相邻的两个单词之间，插入一个它们共同关联的中间词。比如语料库里有I love you和you love me这样的片段，当你输入I you时，程序发现I后面可以接love，love后面又可以接you，于是它会把love插进去，输出I love you。插进去的这个词就是桥接词。

为什么这算“诗歌”？因为语言模型本质上就是在背词与词之间的共现规律。像love这种词被插在两个看似无关的词中间，整个句子会带上一种跳跃感。比如输入storm city，如果语料里有storm dark city这种片段，程序可能输出storm dark city，瞬间就有了画面感。理解了这一点，你就知道题目并不神秘：它就是一个受限的词接龙，图的路径长度被限制为 2，中间只允许一个桥接词。

1.2 题目里那些容易被忽略的隐藏条件

实际做起来你会发现，题目描述很短，但隐含细节很多。以我看到的版本来说，有这么几个点要特别注意：

• 你需要先实现一个泛型Graph接口，图节点类型是String，边权重表示单词共现次数。GraphPoet 基于这个接口工作，不能自己偷偷用现成的图库。
• 分词规则通常要求忽略大小写和标点。语料库里的Hello, world!会被拆成hello和world，逗号、感叹号、空格都是分隔符。
• 如果两个相邻单词之间有多条桥接路径，即存在多个候选中间词，题目可能不会明确说怎么选。常见做法是选择“两条边的权重之和最大”的中间词，或者按字典序打破平局。
• 输入文本中的单词顺序不能变，你只负责在某些空隙插入新词，不能删除或调换原有单词。
• 空语料库、空输入、找不到桥接词这些边界情况都要有明确的输出策略。通常是原样输出输入文本，或者直接返回空字符串。

我在刚开始做题时忽略了一点：语料库本身可能是多行的，不能只按行读。如果只读了一行，后面几行全丢，构建出来的图会缺很多边，导致大量桥接词找不到。后面排查测试失败时才发现是这个原因。

2. 整体设计思路：先画数据流，再拆模块

2.1 数据流其实只有三步

Graph Poet 的完整数据流可以压缩成三个阶段。第一阶段是“建图”：读取语料库，分词，遍历相邻词对，往图里加边或累加权重。第二阶段是“查图”：读取用户输入，分词，遍历相邻词对，在图中找是否存在长度为 2 的路径。第三阶段是“拼串”：把找到的桥接词按顺序插入原句，输出最终结果。

这三个阶段可以对应三个核心方法：构造函数GraphPoet(Reader corpus)负责建图；poem(String input)负责查图和拼串；内部再拆一个tokenize方法负责分词。我建议在动笔写代码之前，先用文字把这个数据流写清楚，甚至画一张简单的流程图。不要一上来就写方法体，否则很容易写着写着发现图的方向反了，或者桥接词插入的位置错了。

我自己当时犯过的最大错误是把建图和查图混在一起。一开始想在poem方法里直接遍历语料库，每接收一次输入就重建一次图，结果又慢又乱。后来改成构造函数里一次性建图，poem里只做查询和拼接，代码立刻清爽了很多。

2.2 模块划分：Graph 接口与 GraphPoet 分离

实验通常要求你至少实现一个Graph接口的具体类，比如边列表实现ConcreteEdgesGraph或顶点实现ConcreteVerticesGraph。GraphPoet 只依赖Graph接口，不关心底层是哪种实现。这种分层的好处是：你可以先单独测试图，再测试 Poet；如果图的方法有问题，不会和诗歌生成逻辑混在一起排查。

推荐的项目结构是：

• graph包：Graph接口，以及两个具体实现类。
• poet包：GraphPoet类和Main类。
• test目录：分别对应Graph的测试和GraphPoet的测试。

实际操作时，我建议先完成一个图实现并通过全部图测试，再写 Poet。如果两个事情同时做，一旦测试失败，你很难判断问题是出在图结构还是出在查词逻辑。图测试通过等于你的地基是稳的，后面加楼层时不需要怀疑地基。

2.3 为什么一定要用图，而不是直接查字典

有同学可能觉得，我用两个HashMap也能做同样的事：第一个记录word1 -> word2 -> 次数，第二个记录word2 -> word3 -> 次数，查的时候循环一下。确实可以，但课程让你实现图不是为了炫技，而是为了锻炼“抽象”的能力。图是对“节点和关系”的通用抽象，边权重可以表示频次、距离、成本等各种含义。你今天用它做诗歌生成，明天换一个题目求最短路径，图接口还能复用。

从维护角度来说，图接口把add、remove、set、vertices、sources、targets这些操作规范好了，语义清晰。如果自己写两个 Map，你今天能看懂，过两周再看可能就忘了哪个 Map 是第一层、哪个是第二层。图接口的命名本身就是文档。

3. 核心实现细节与关键抉择

3.1 分词与文本清洗：坑最多的地方

分词是整个实验里最容易被低估的环节。表面上只需要按空格分割，但实际语料库里充满标点、换行、大小写和数字。我的做法是：先用Reader读出全部文本，然后用正则表达式提取连续字母。核心正则可以是[a-zA-Z]+，这会忽略空格、数字和标点，只保留英文单词。如果你希望保留don't这种撇号，可以改成[a-zA-Z']+，但要注意撇号出现在开头的情况。

统一大小写也是一个关键点。我的策略是全部转成小写，这样Hello和hello在图里是同一个节点。如果你不统一大小写，Hello world和hello world会被当作完全不同的词对，权重无法累加。对诗歌生成来说，小写已经够用；如果要保留原文大小写，需要额外存一层映射关系，复杂度会明显上升，建议实验阶段先不搞。

还有一个容易被忽略的坑：句子边界。直接按正则分词会把"Hello world. How are you"拆成hello world how are you，然后错误地建立world -> how这条跨句边。如果你不希望跨句连词，最好先按句号、问号、感叹号把文本切成句子，再在每个句子内部做分词。但题目如果没有明确要求，你也可以不处理，只需要在文档里说明你的策略。测试用例通常不会故意刁难跨句问题，但如果你的图总是多出一些莫名其妙的边，可以往这个方向怀疑。

3.2 图的构建：权重怎么累加，自环怎么办

图构建的核心逻辑是遍历分词后得到的单词列表，对每个相邻对(words[i], words[i+1])调用一次set方法。如果这条边已经存在，就把权重加一；如果不存在，就设置权重为一。用接口语义来说，set方法返回旧权重，所以你可以这样写：

int oldWeight = graph.set(src, dst, 1); if (oldWeight != 0) { graph.set(src, dst, oldWeight + 1); }

如果你的set方法语义是“设置权重并返回旧值”，那上面的写法就是安全的。有些版本的set约定weight == 0表示删除边，所以建图时一般不会传 0。

自环也需要想清楚。语料库里如果有la la la，你会建立la -> la的边，权重为二。这在图结构上是合法的，Graph 实现应该允许自环。查找桥接词时，如果输入是la la，自环可能让程序找到中间词也是la，输出变成la la la。这不算错误，是数据驱动的合理结果。只要你的实现不会因为自环进入死循环就行。

构建图的时间复杂度是 O(n)，其中 n 是语料库单词数。每次set在普通图实现里可能是 O(1) 或 O(节点数)，整体上完全够用。不要在这里过度优化。

3.3 找桥接词：直接枚举比 BFS 更香

很多人一看到“路径查找”就想到 BFS 或 DFS，但这个问题根本不需要。我们要找的路径固定长度是 2，也就是从一个词出发，经过一个中间词，到达另一个词。最简单直接的做法是枚举第一个词的所有出边邻居，检查每个邻居是否有出边指向目标词。

具体来说，给定相邻对(wordA, wordC)，先取Map<String, Integer> targetsA = graph.targets(wordA)，然后遍历targetsA的 key 集合。对于每个候选桥接词wordB，再查graph.targets(wordB)是否包含wordC。如果包含，说明wordA -> wordB -> wordC是一条长度为 2 的路径。这个逻辑用口语说就是：“A 后面能接什么词？在这些词里面，哪个词后面还能接 C？”

这段逻辑的复杂度是 O(出度A)，对诗歌生成这种小规模任务来说已经非常快。如果你真用 BFS 去搜索深度为 2 的路径，反而要处理访问标记、路径记录等多余逻辑，容易出错。代码越简单越不容易 bug。

3.4 多候选的选择策略：建议用权重和

很多时候，图中会同时存在多条长度为 2 的路径。比如语料库里有a p b也有a q b，那么输入a b时，p和q都能当桥接词。题目如果没有明确选择策略，你需要自己定一个并且写清楚。

我采用的策略是：计算两条边的权重之和，选择总得分最高的候选桥接词。这里的理由很朴素：边的权重表示这个搭配在语料库中出现的次数，两个环节的总权重越高，说明这条路径越“常见”，插进去的词越自然。如果两个候选得分相同，我按字典序选最小的那个，这样程序行为是确定的，测试用例也好写。

有些版本可能要求你选“两个边权重都较高”的路径，比如比较两条边权重的较小值，取较小值最大的那条。这本质上是一种“木桶效应”，更看重搭配合不合理。无论选哪种，你都要保证说明文档和测试代码一致。最怕的是代码里写了一种策略，注释里写了另一种，测试又假设第三种。

3.5 测试驱动：先设计几组关键用例

写实现之前，我建议先把测试用例想好，这样可以逼你理解需求。GraphPoet 的测试至少要覆盖这些场景：

• 空语料库：构造函数不抛异常，poem返回原输入。
• 空输入：返回值是空字符串或合理兜底。
• 单单词输入：没有相邻对，原样返回。
• 唯一桥接词：能正确插入。
• 多候选：能按你定义的选择策略输出正确桥接词。
• 大小写差异：Hello和hello能匹配。
• 标点分隔：逗号、句号不影响分词。
• 权重累加：重复出现的词对会让权重增加，且影响桥接词选择。

写完这些测试后，再写实现，你会发现自己不需要反复猜测行为。我当初是先写了实现再补测试，结果因为选择策略没定好，测试多半靠猜。反过来的体验会好很多。

4. 实操过程：从零搭出可运行的 GraphPoet

4.1 项目骨架与优先级

无论你做的是哪个版本，我建议按这个顺序推进：

1. 阅读Graph接口，理解每个方法的行为。
2. 实现一个图的具体类，跑通图测试。
3. 写GraphPoet的分词方法。
4. 实现构造函数中的建图逻辑。
5. 实现poem方法，先不处理平局，只返回第一个候选。
6. 补全选择策略和边界情况。
7. 用Main类跑一个完整例子。

不用一口气写完所有东西。你先把最小可用版本跑起来，再逐步加逻辑，调试心理负担会小很多。我当时太想一步到位，结果第一次运行日志里全是空指针，反而不如循序渐进稳。

4.2 核心代码：GraphPoet 的构建与 poem 方法

下面是一个可以直接参考的核心代码骨架。注意这里假设Graph接口的targets返回Map<String, Integer>，键为后继节点，值为边权重。

public class GraphPoet { private final Graph<String> graph = Graph.empty(); public GraphPoet(Reader corpus) throws IOException { List<String> words = tokenize(corpus); for (int i = 0; i + 1 < words.size(); i++) { String src = words.get(i); String dst = words.get(i + 1); int oldWeight = graph.set(src, dst, 1); if (oldWeight != 0) { graph.set(src, dst, oldWeight + 1); } } } public String poem(String input) { List<String> words = tokenize(input); StringBuilder output = new StringBuilder(); for (int i = 0; i < words.size(); i++) { output.append(words.get(i)); if (i + 1 < words.size()) { String bridge = bestBridge(words.get(i), words.get(i + 1)); if (bridge != null) { output.append(" ").append(bridge); } output.append(" "); } } return output.toString().trim(); } private String bestBridge(String wordA, String wordC) { Map<String, Integer> targetsA = graph.targets(wordA); String best = null; int bestScore = -1; for (String wordB : targetsA.keySet()) { if (graph.targets(wordB).containsKey(wordC)) { int score = targetsA.get(wordB) + graph.targets(wordB).get(wordC); if (score > bestScore || (score == bestScore && best != null && wordB.compareTo(best) < 0)) { best = wordB; bestScore = score; } } } return best; } private List<String> tokenize(Reader reader) throws IOException { StringBuilder text = new StringBuilder(); char[] buffer = new char[1024]; int read; while ((read = reader.read(buffer)) != -1) { text.append(buffer, 0, read); } List<String> words = new ArrayList<>(); Matcher matcher = Pattern.compile("[a-zA-Z]+").matcher(text.toString().toLowerCase()); while (matcher.find()) { words.add(matcher.group()); } return words; } }

这里tokenize直接读全部字符，然后用正则提取单词。如果语料库很大，也可以改成用Scanner或 BufferedReader 逐行处理，但实验数据一般不大，全量读进来没毛病。

poem方法里我用trim()去掉首尾多余空格。如果输入为空，words为空，循环不执行，返回空字符串，行为合理。

4.3 手算一个例子：验证输出

我们构造一个极小语料库：

a b c b c d

分词后单词序列是a b c b c d。相邻词对和权重如下：

输入为a d。我们需要找a -> ? -> d。a的后继只有b，而b的后继是c，不是d，所以找不到桥接词，输出a d。输入为a c时，a的后继是b，b的后继包含c，所以插入b，输出a b c。这个例子虽然简单，但能帮助你确认代码里“遍历 targets 的 key”这个思路是否正确。

你可以在测试中构造这种只有唯一答案的用例，这样不需要考虑平局策略，先跑通主流程。

4.4 权重优先级的完整示例

为了更好地验证选择策略，我们构造一个有多候选的语料库：

x p y x q y x q y

分词后：x p y x q y x q y。权重为x -> p1，p -> y1，x -> q2，q -> y2。输入x y，候选有p和q。p的得分是1 + 1 = 2，q的得分是2 + 2 = 4，所以程序应该输出x q y。

这个用例很适合写进测试。它同时验证了两件事：一是正确识别多个候选，二是正确应用权重加和策略。如果程序输出了x p y，说明你的候选选择或权重累计逻辑有问题，需要回头检查set方法是否真的把旧权重取出来了。

5. 常见问题与排查技巧实录

5.1 sources/targets 分不清楚

Graph 接口里有两个方向的方法，非常容易搞混。我的记忆方法是：targets(v)表示“以 v 为起点，指向哪里”，也就是从 v 出发能到达的所有节点；sources(v)表示“谁指向 v”，也就是所有能到达 v 的节点。找桥接词时，我们关心从wordA出发能到哪些节点，所以用targets(wordA)。如果你不小心用成了sources(wordA)，相当于反向查找，测试多半会失败。

调试时可以在纸上画一个小图，把节点和边写出来，然后手动走一遍targets和sources的结果。比如图里有a -> b，那么targets(a)包含b，sources(b)也包含a。这两种方法返回的内容不同，但描述的是同一条边，方向完全不同。

5.2 语料只读了一行

很多人会写成BufferedReader.readLine()只处理当前行，结果语料库第二行以后的内容全丢了。我推荐在tokenize方法里用循环把所有字符读进来，或者用Files.readString一次性读文件，再交给正则处理。如果你使用Reader参数，更要注意read()方法需要循环读取，直到返回-1。

这个问题最隐蔽的地方在于：如果语料库只有一行，测试能过；一旦换一个多行的测试文本，图边就少了，桥接词找不到，测试开始失败。排查时先打印graph.vertices()和graph.targets()，看看里面有多少节点和边，和你预期是否一致。

5.3 选择策略与测试期望不一致

这是最让人头疼的问题，因为代码没有语法错误，逻辑也能跑，但就是输出和测试期望对不上。原因很可能是你的平局处理或评分函数和出题人预设不一致。比如我一开始选择“两条边权重之和最大”，但测试期望的是“按出现顺序取第一个候选”，结果自然不对。

解决方法是把评分函数独立成一个私有方法，让测试可以覆盖。你还可以在最开始就封装一个bestBridge方法，并在注释里写明策略。当你看到测试失败时，先不要改代码，先猜一下测试期望的策略是什么，再对照你自己的策略。通常题目文档里会有线索，比如“choose the most frequently occurring”这类描述。

5.4 大小写和标点导致匹配失败

如果你在构建图时统一小写，但在poem方法里没有统一小写，就会出现Hello和hello匹配不上的问题。我的做法是tokenize方法里统一小写，这样建图和查询用的是同一套规则。但这也意味着最终输出全是小写，看起来不太“诗歌”。如果你觉得难以接受，可以额外保存原始单词，但实验阶段不建议引入这种复杂度。

另一个标点问题是撇号。如果语料里有don't，使用[a-zA-Z]+会拆成don和t，这显然不是我们想要的。使用[a-zA-Z']+可以保留撇号，但正则中的撇号可能匹配到字符串开头的引号。如果要处理这种问题，建议在正则提取前先去掉单独出现的引号，但这不是实验重点，点到为止即可。

5.5 图的内部状态被意外修改

targets和sources如果直接返回内部Map的引用，外部代码可以修改它，导致图结构被破坏。比如在bestBridge中如果不小心调用了targetsA.remove(...)，整张图就废了。接口设计通常会要求返回不可变视图，即用Collections.unmodifiableMap(...)包装，或者返回一个拷贝。但如果你用的图实现没有做防御性拷贝，测试时可能遇到莫名其妙的状态错乱。

作为 GraphPoet 的使用者，你要做一个好公民：只读取返回的 Map，不要尝试修改。如果发现自己的代码里对targets的返回值做了put或remove，立刻改掉。

5.6 调试建议：打印图和分词结果

调试 Graph Poet 最直接的手段是加打印。建图完成后，遍历所有顶点，打印node -> targets的完整内容。这样一眼就能看出边是否缺失、权重是否正确。分词结果也要打印，特别是语料库文本比较长时，你需要确认tokenize是否把单词切得符合预期。

我通常会在测试失败时先跑一个最小示例，把中间结果手动算出来，再和代码输出对比。比如前面提到的a b c b c d那个例子，手动算出桥接词，再让测试跑一遍。如果手动结果和程序输出不一致，就缩小范围：先打印分词，再打印图，再打印每一个候选，基本两三步就能定位问题。

做完这个 Problem1.4，我最大的感受是：Graph 接口实际上是整个 Lab 的核心，GraphPoet 只是它的一个应用。把图数据结构写稳了，桥接词搜索其实就是几行遍历。如果你卡住了，不要先去抠代码，先把数据流图画清楚：语料库怎么进、图怎么建、输入怎么查，每一步想清楚再写。另外一个小技巧：测试时制造一个极小语料库，比如只有五六个词，手工算出期望输出，再跑测试，定位会快很多。