如果你正在做软件构造 Lab2大概率会在 Problem1.4 Graph Poet 上卡一会儿。这个题的核心是用自己实现的有向图接口做一个“诗歌生成器”给一段语料库程序学会词与词之间的前后关系再给你要写的句子自动在相邻单词之间插入一个“桥接词”让整句话读起来有点诗意。我第一次看到题目时也没太明白后来把 Graph 接口、分词、路径查找这几个点串起来发现思路其实很清晰。这篇文章就把完整的解题思路拆开讲适合正在做实验的学生也适合想了解怎么用图做文本生成的人。1. 先读懂题目Graph Poet 本质上是一个“词接龙”任务1.1 从“诗歌生成”这个需求说起Graph Poet 并不是真的在创作诗歌它做的是一个非常朴素的文本变换给定一个语料库corpus程序从里面学习单词之间“谁后面经常跟着谁”的关系然后把你输入的句子中相邻的两个单词之间插入一个它们共同关联的中间词。比如语料库里有I love you和you love me这样的片段当你输入I you时程序发现I后面可以接lovelove后面又可以接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]这会忽略空格、数字和标点只保留英文单词。如果你希望保留dont这种撇号可以改成[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[i1])调用一次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)先取MapString, 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. 实操过程从零搭出可运行的 GraphPoet4.1 项目骨架与优先级无论你做的是哪个版本我建议按这个顺序推进阅读Graph接口理解每个方法的行为。实现一个图的具体类跑通图测试。写GraphPoet的分词方法。实现构造函数中的建图逻辑。实现poem方法先不处理平局只返回第一个候选。补全选择策略和边界情况。用Main类跑一个完整例子。不用一口气写完所有东西。你先把最小可用版本跑起来再逐步加逻辑调试心理负担会小很多。我当时太想一步到位结果第一次运行日志里全是空指针反而不如循序渐进稳。4.2 核心代码GraphPoet 的构建与 poem 方法下面是一个可以直接参考的核心代码骨架。注意这里假设Graph接口的targets返回MapString, Integer键为后继节点值为边权重。public class GraphPoet { private final GraphString graph Graph.empty(); public GraphPoet(Reader corpus) throws IOException { ListString 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) { ListString 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) { MapString, 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 ListString 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); } ListString 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 - b1b - c2c - b1c - d1输入为a d。我们需要找a - ? - d。a的后继只有b而b的后继是c不是d所以找不到桥接词输出a d。输入为a c时a的后继是bb的后继包含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 - p1p - y1x - q2q - y2。输入x y候选有p和q。p的得分是1 1 2q的得分是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)包含bsources(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方法里统一小写这样建图和查询用的是同一套规则。但这也意味着最终输出全是小写看起来不太“诗歌”。如果你觉得难以接受可以额外保存原始单词但实验阶段不建议引入这种复杂度。另一个标点问题是撇号。如果语料里有dont使用[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 只是它的一个应用。把图数据结构写稳了桥接词搜索其实就是几行遍历。如果你卡住了不要先去抠代码先把数据流图画清楚语料库怎么进、图怎么建、输入怎么查每一步想清楚再写。另外一个小技巧测试时制造一个极小语料库比如只有五六个词手工算出期望输出再跑测试定位会快很多。