使用代码列出金庸小说中使用过的所有成语

jiezi

5 年前

去年的今天，金庸与世长辞，当时 Jerry 在成都地铁一号线下班的路上得知了这个消息，回到家立即写了一篇文章来悼念：金庸的武侠世界和 SAP 的江湖。

一年的时间转瞬即逝，大家都忙碌于各自的生活，很多人对金老的离世已经淡忘了，不过 Jerry 这种金庸的死忠粉，对于这个一周年忌日还是记得很清楚的。

因为 Jerry 手上事情很多，没时间在这个特殊的日子写文章纪念了，就发一小段代码吧。

需求：列出金庸任意一本小说里出现的所有成语。

实现：Jerry 部署在 Github 上的一个 web 应用，链接如下：

http://jerrywang-sap.cn/Fiori…

首先点击超链接“成语全集”：

点击之后，存储于该 web 应用本地存储的一个文本文件里的全部 19830 个成语，以树的形式加载到内存中，并显示在网页上：

然后复制一本金庸小说的内容，粘贴到网页的“内容”区域，点击按钮“测试”：

可以看到仅仅用了 246 毫秒，就将这部一百多万字的《倚天屠龙记》里出现的所有成语，以红色高亮的方式高亮出来。

这个功能咋实现的？Chrome 打开 Jerry 的网页，F12 开启开发者工具，就能看到 JavaScript 源代码，当然也可以从我的 Github 上获得.

Jerry 简单讲下实现原理。Web 应用里有一个文本文件，里面维护了汉语里全部的成语，通过分号分隔。

运行时，这些内容会被加载到内存中，构建成一棵树，如下图所示：

其中叶节点以属性 end 为 true 区分。

成语检索的核心逻辑位于 search 函数里，让我们用《笑傲江湖》里一句响亮的口号“日月神教千秋万载，一统江湖”来单步调试，了解其实现逻辑。

进入 165 行的外层 while 循环，再进入 173 行的内层 for 循环，检测是否有测试字符串第一个字符“日”开头的成语。因为成语是由 4 个字符组成，所以需要用内层 for 循环逐一试探，如果遇到 tblCur.end 为 true 的元素，说明在测试字符串中发现了一个成语。

下图是内层 for 循环第一次执行后的 tblCur 内容：

内层循环执行第二次，此时 tblCur 指向一棵由所有“日月”开头的成语组成的树：

执行内层循环的第三次迭代，因为在树“日 - 月”这个分支下面没有“神”这个节点，所以结束当前的内层循环，通过 break 返回到外层的 while 循环，进行输入字符串第二个字符“月”的新一轮试探，以此类推。

最后从“千”这个字符出发，沿着内存中的树经过路径 ” 秋 - 万 ”，最后来到 end 属性为 true 的叶节点“载”，记下“千”在输入字符串中的偏移量，存到一个数组 arrMatch 中去。

待输入字符串全部试探完毕后，根据 arrMatch 中存放的偏移量，高亮显示对应的字符串，完成检索。

树这个数据结构在这个需求的实现里有着完美的表现。

金庸虽然离开了我们，但他笔下那些人物和发生的故事，将永远流传于这个世上。

要获取更多 Jerry 的原创文章，请关注公众号 ” 汪子熙 ”:

更多阅读