如何做好网文段落匹配

网文如何段落

1
2
3
为什么最长公共子序列+TF-IDF是最有效方案
为什么大部分人可能用错了Simhash
Ansj分词工具介绍

笔者在一家阅读类App公司日常工作内容是UGC相关，包括章节段落评论部分，有一个场景是：
作家新书发布章节后，用户在阅读时评论，比如划定一个段落评论，过了一段时间，作者发现文章里有错别字需要修改，或者希望删除/合并一些段落，甚至调整段落位置。如何将改动前后的段落匹配，使之前的评论重新关联到新段落，是一个不小的问题。
不过这类短文本匹配不是本人主业，这里讨论难免不足，主要还是介绍一种低成本有效的匹配方案，以及需要考虑的问题点。本文写于2021年，最近我重新编辑修改了下，因为出现了DeepSeek，使用后发现有一些场景可以很好的解决，或许依赖词库，效果不如本文介绍方法，如果有矛盾地方请忽略

我们先来看两个问题：

为什么不使用唯一ID标识段落

历史业务，增加唯一段落标识对内容部门业务的侵入性较大，其次关键的是唯一段落id的标识解决不了问题：

  • 对于内容无改动的或简单合并，或者仅仅调整段落位置，唯一段落标识的确方便，不需要作任何匹配或直接修改映射
  • 但如果是段落拆分，这就要考虑归属哪一段
  • 内容修改，改动必然产生新的唯一段标识，还是需要比较文本或语义相似度才能匹配

为什么不用Diff算法

用diff算法比较文本，似乎令人感觉高大上，比如通过Diff比较算法得到改动所涉及的操作步骤（比如插入、删除、修改），那是否就可以匹配？遗憾的是不能，因为我们的场景和协作编辑文本不同。
编辑文本涉及更深层次的探讨，比如CRDT协同算法，而这些算法其实主要目的是：diff和patch，即通过patch使得文本一致
不少开源工具就基于Myers-Diff或者Pationce-Diff或Bentley-McIlroy、Paul Heckel等各类差分算法，当然还有想GumTree这类树状差异分析。像*nix diff命令算法就是Myers差分算法，而Git的Diff算法也支持：Myers、Minimal、Patience、Histogram，还有近年一些流行前端框架也使用了Diff算法处理元素变更，可能和Myers大同小异，区别可能在支持的操作和路径长短不同，diff算法介绍不是本文内容，但他们其实都不适合作为网文段落修改重新比较的算法：

  • 首先Diff算法不支持语义层面的匹配，而我们希望作者修改段落内容时，支持一定的语义匹配，或者简单说，希望标点符号的修改，不影响匹配。
  • 其次，即便Diff算法满足上面语义匹配，解析diff结果本身工作量不少，像myers，同样需要处理插入、删除、修改，其面临的问题其实和唯一段标识同样多，对于变更依旧需要比较，而解析diff工作量实在不必要，而且对于修改或交换段，Myers算法有时可能是删除大段再插入(Myers删除优于插入)。
  • 最后，通用性考虑。虽然Diff算法高效，但文本比较/匹配需要的是准确和尽可能多匹配上，文本比较就更适合、更通用，比如像epub等格式小说接入几乎可以直接复用，而如果支持插图，如果使用差分diff算法，那么就会不可避免的掺杂一些格式代码，这加大了难度。

方案选择

我最终选择的方案是LCS+TF-IDF余弦相似度两种方案结合起来，个人是下来效果不错，至于为什么不采用ED、Simhash海明距离等，下文也做了简单分析。

先看几类文本匹配场景，文本主要节选自《西游记》或个人杜撰（版权问题），但都是我做匹配中遇到的几个主要问题。代码各位可自行使用，或参考blogcode这里全部。其次假设至少80%内容相似度的才认为段可以匹配。
其他场景，比如段合并，或者段删除了一部分等，如果使用最长公共字串算法，其实等价拆分场景。但也存在合并段且同时某段修改文字较多，导致前后比自己相似度也达不到80%的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 文本txt1， C1-C9，D1-D10表示段落号
put("C1", "菩提老祖想了想，赐给他“孙悟空”一名。猴王非常喜欢这个名字，高兴地说：“好好好，以后我就叫孙悟空了"); // same
put("C2", "见到菩提老祖，美猴王跪在他跟前说：“师父，弟子有礼了！”菩提老祖说：“先别急着拜师，把你的来历一一告诉我吧。"); // 编辑距离不同
put("C3", "孙悟空每天和弟子们待在一起，打扫庭院，养花修树，挑水捡柴，学经论道，不知不觉过去了七年时间。一天，菩提老祖对孙悟空说：“‘道’字门中有三百六十旁门，只要悉心学习都可以学成正果，不知道你想学哪一门呢？”");
put("C4", "拜师后，孙悟空跟孙菩提学习打扫,看起来不得不说学习一门正果更加勤奋了,蚂蝗,还跟网友学习网游学习虚拟网络世界");
put("C5", "赵敏说道，是成昆把张无忌打了一顿");
put("C6", "贾基听了非常高兴，不禁念诗一首:『富士见之女，于西行妖满开之时，即幽明境分开之时，魂兮魄兮，归于白玉楼，尽归尘土兮");
put("C7", "普京与克林顿,没有参与进来，因为锦苑中学司马迁和孙权不再来玩，你说是也不是宋江去了松江府还没来得及说一首");
put("C8", "非UGC，仅用于goodread文插图的点赞功能,subtype=1");
put("C9", "起点孙悟空和刘邦都不知所措不以为然孙权竟会干出这种事情来，说什么都不愿意");
// 文本txt2
put("D1", "菩提老祖想了想，赐给他“孙悟空”一名。猴王非常喜欢这个名字，高兴地说：“好好好，以后我就叫孙悟空了！”");
put("D2", "见到菩提老祖，美猴王跪在他跟前说：“师父，弟子有礼了！”菩提老祖说：“把你的来历告诉我吧，先别急着拜师，");
put("D3", "孙悟空每天和弟子们待在一起，打扫庭院，养花修树，挑水捡柴，学经论道，不知不觉过去了七年时间。一天，菩提老祖对孙悟空说：");
put("D4", "“‘道’字门中有三百六十旁门，只要悉心学习都可以学成正果，不知道你想学哪一门呢？”");
put("D5", "美猴王拜了师傅孙菩提以后，必须说看起来更加勤奋学习正果一门了,蚂蝗,还跟网友自学虚拟网络世界自学网游");
put("D6", "是张无忌把成昆打了一顿，赵敏说道");
put("D7", "接下来，贾基直接念了一首诗:『富士见之女，于西行妖满开之时，即幽明境分开之时，为其魂魄，安息于白玉楼中，将西行妖之花封印作");
put("D8", "普京与克林顿,没有达成，因为普通物理不允许司马迁和孙权不是一路人，听了松江府的宋江说来说去不明白是还是不是");
put("D9", "非UGC，仅用于betterread文插图的点赞功能,subtype=1");
put("D10", "起点孙悟空和刘邦都去了云南打猎，回来时候路过牛家村，看到满天繁星，想起了孙权");

匹配的本质是找到相似性，而计算机运算离不开数字化数值化，所以文本相似性需要数字化的表示，可以是基于字符的编码、可以基于最简单元素集合的相似性、可以基于句子的特征向量化、可以基于词的向量化，甚至把句子用矩阵表示，因此产生了诸如词袋模型、TF-IDF、LSA、LDA、N-gram、主题模型、词向量（word2vec等）、ESim、BERT等语言模型。大师Ullman的《大数据-互联网大规模数据挖掘与分布式处理》 书中列举各种距离算法，欧几里得、Jacard、海明(汉明)距离、莱文斯基距离、余弦距离、超平面等。我这里从实用角度看，近考虑并比较了基于字符的编辑距离、最长公共子串、基于特征向量的TF-IDF+余弦距离、SimHash+海明距离等实现分别对比下效果，涉及到分词组件Ansj、HanLp、少量BERT语义等部分知识

编辑距离（Edit Distance）

WikiPedia：编辑距离，即Edit Distance，是衡量两个字符串相似度的方法。它表示从一个字符串转换为另一个字符串所需的最少单字符编辑操作次数，这些操作包括插入、删除或替换，编辑距离也叫Levenshtein距离。
学计算机的可能大多第一反应是这个算法，下面代码levenshteinSimCalc方法所示，直接采用Apache Common Text的库实现，当然时间/空间复杂度m*n等不是本文讨论重点。
上面 C1行和D1行，相差末尾两个标点符号，所以得到的Levenshtein相似度0.96是相似度的，但可惜的是匹配C2和D2以及C3和D3就有问题了，因为C2和D2基本是部分顺序不同，C3则拆分为D3和D4，用编辑距离显然匹配不到，不满足需求

最长公共子串（LCS）

最长公共子串（Longest Common Substring），不过这里严格来说是这里使用的是最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列中取出尽可能多的公共子元素，按照它们在原序列排列的先后次序排列得到（即寻找公共子序列），子序列不必是连续的，和编辑距离一样都属于动态规划算法
C2/D2匹配，用Jarcard相似度可以解决，但对于中文需要分词，否则如果默认单字分割，不仅失去内容语义，更可能因大量单字重复匹配失效。
LCS就可以很好的兼容C2和D2以及C3和D3的匹配，实际上对于网文段落匹配来说，LCS适合大多数修改类的匹配工作，因为章节编辑变更常见的是字、部分用词、合并拆分段落。可以看到 下文lcsSimCalc方法，将C2/D2，C3/D3都匹配上了，相比Levenshtein则认为不匹配：

1
2
3
4
5
6
7
8
# 距离编辑算法 的 最大相似度
lev:C1 -> D1 similarity: 0.9608
lev:C2 -> D2 similarity: 0.6852
lev:C3 -> D3 similarity: 0.5900
# LCS算法 的 最大相似度
lcs:C1 -> D1 similarity: 1.0000
lcs:C2 -> D2 similarity: 0.8462
lcs:C3 -> D3 similarity: 1.0000

基于分词

遗憾的是，编辑距离或者LCS方法对于C4-C7的匹配无能为力，得到最大相似度都在0.6以下，我希望匹配方案带有一点语义识别能力，可以将剩下几类场景明确是否匹配上。所以，想到了分词后+Jarcard相似度或特征向量可以实现。
比如最简单的词袋模型，BOW全名叫Bag of words，我们分词后再用Jarcard相似度，C5完全可以匹配，甚至C4、C6也能匹配上对应行！即，假设我们使用Lucene的默认一个汉字一个汉字分词StandardAnalyzer 是可以得到跟D5有0.8以上相似度，但是如果同时减少C4/D5的末尾8个字，相似度就不足0.8了， 另外BOW并不能标识出一个段中重点的部分，比如C4和D5都有“蚂蝗” 这个极少见词汇，希望在匹配时候可以为此加分，为此一个改进是TF-IDF（term frequency–inverse document frequency），即词频-逆向文件频率，就可以支持，另一个是分词+SimHash，虽然都和BOW一样只关注词之间的关系， TF-IDF是bow一种，我们且简称为TF-IDF模型
上面描述的是词和文本关系，那么如果想基于词于词之间的语义关系或词句语义/语法等关系如何实现呢，这就是另一种词向量技术，Word Embedding，将词映射到固定维度的实数向量空间中，目前看主要发展出基于统计学和基于上下文两个方向，比如机器学习入门就会提到的2013年诞生的Word2Vec（CBOW和Skip-Gram）、SoftMax、Glove、FastText属于前者， 现在流行的BERT和GPT主要基于上下文，这些并非笔者特长，暂且不深入介绍。

是否需要语义

所以，这里介绍点其他的，比如提两个注意点

  • 匹配更多的判断依据是”长得像“
    上文的C5和D6就会被语义模型认为不匹配的，因为主语和宾语颠倒了，或许如果后续接入语义相似，我们可以通过规则或者调参改变，但是否存在其他情况呢，比如否定之否定或者只是改为反问语气，即便假设人类语言文法是规范的，也存在作家写错字情况，还有更多考虑，比如作家第一遍某段写的是“xxx，我喜欢你”，但后来想想改成“xxx，我不喜欢你”，甚至“xxx，我讨厌你”，语义上都是不相似的，但我们知道有时候女孩子的不喜欢可能是喜欢，讨厌也是喜欢。。。总之调参无尽头，但我们的场景，其实期望的是只要长得像就是相似的，即便是出现上文主宾颠倒、替换，换句话说大多时候我们匹配的不需要word vector/embedding或者sentence vector/embedding的东西，甚至关注“每个单词都是由其周围的单词所定义”对于比较变化意义不大。总之，和语义匹配最大不同是 语义不相似的段可能是被认为匹配的，比如“我明天就出发去北京”和“我后天就出发去北京”，甚至是去“上海”，可能都希望匹配上。
  • 匹配是从本章节各个段落里找到长得最像的
    还是上文C5和D6，我上面说他们是相似的，前提是这个章节变更后没有相似的，如果文本2还有一段 “D9 赵敏说道，是成昆把张无忌打了一顿”，即如果这个章节本来同时就存在这两句类似的话，比如是两个角色对话，一个观点是张无忌打成昆一个是 成昆打张无忌，那显然C5匹配的应该是D9而非D6。即这里不仅仅是相似度，还是匹配的问题，举个例子：
    “我的衣服有一些旧了，我想去商场买一件新衣服”
    ”我的裤子有一些破洞了，我也想去商场买一件新裤子“
    通过大模型或者词向量分析，都可以得到两句有高度相似的结论，但是这两句可能会同时出现在一段二人对话中，不应该认为是匹配的

TF-IDF

基于分词可以解决上面无法匹配C5和D6的问题，如果你也认为词义即语义，那分析词的相似性就是有意义的
TF-IDF模型： 将文本中的每个词的出现频率和文本中其他文档中的出现频率进行权重，并将这些权重组合在一起形成一个向量。夹角就是他们的相似度，这自18世纪就被使用
不论上面词袋模型还是TF-IDF，都是将文本中的每个词视为一个独立的特征，并组合一起为一个高维向量，TF-IDF方法是一种改进的词袋模型（Bag-of-Words）方法，通过结合词频（Term Frequency，TF）和逆文档频率（Inverse Document Frequency，IDF）来评估词汇在文档中的重要性。
笔者过早地看过吴军博士搜索原理系列的TF-IDF计算余弦相似度方法，所以一直是拿来主义，没有思考过为什么TF-IDF+余弦夹角就可以计算出相似度？以及为什么公式需要用log函数？如果你认为只是简单的希望降低权重，那确实错过了“why”，错过理解一些底层的知识。我没有找到使用词频的理论依据，但想来这更可能是一个工程实践结果，因为我们完全可以根据词频构造一篇文章，但是实际结果狗匹配不通。
这种构造同样也适用于下文的SimHash算法， 但SimHash除了可以通过调整顺序构造高度相似文本，还有其他问题，我下文会再指出。
所以，我认为这里前提需要假设文本特征可以通过关键词语反应出来，其次就像可计算理论所追求的，语言可以是一种模型，至少像乔姆斯基体系建立起来的各型文法一样。
当然需要一些限制条件才可以量化和计算，否则就会陷入“狗不是猫的同义词”，但是“猫和狗是相似的”这种纠结里，比如可以像分布式假设所定义的“如果两个词语在不同的文本中出现在相似的上下文中，那么它们的语义应该是相似的”
TF-IDF 就是建立在“对区别文档最有意义的词语应该是那些在文档中出现频率高，而在整个文档集合的其他文档中出现频率少的词语” 假设，这个假设也有不足，因为人类自然语言有时候并不是频率大的词就无用，其次，单词的先后顺序(位置)也很重要，这些是后话，重要的是基于这个假设能否推导出什么。
TF-IDF向量空间是一个把文本文件表示为一系列特征向量的代数模型，TF-IDF和向量空间都是实践先于理论，布尔模型、向量模型等各种经典的信息检索模型都是是早期检索软件系统引入的概念，TF-IDF则是发表后才有信息学的解释，《数学之美》中有信息熵和词频、逆文本频率等论述，我就不重复了，需要说明的是TF-IDF并不是信息熵推导的一个结果，但信息熵的可以解释其合理性，比如相对熵、交叉熵这些重要的概念，因为这里理解的相关性(或者说重要性)其实是建立在文档里的这个词对本次查询能带来多少信息，但我们不需要使用搜索功能，TF-IDF在搜索子串上的不足也就不存在。主要使用TF-IDF进行相似度比较。
进一步可以参考Ullman的《大数据-互联网大规模数据挖掘与分布式处理》，相似性LSH函数族这章。
这里可以看到，似乎只要能够向量化，就可以考虑使用余弦相似度，比如 地理空间相似度，社区相似度等，这其实很符合人类给万物分类的思维，比如生物学上的分类，就会列举出多个特征，只不过是叫LDA或者SVM。
不过单词或者说特征，本质上是一种局部信息，需要记住的是局部基本相似未必全局相似，除了上文提到的单词位置/顺序一类例子，还有一种是语义上的，比如例子：”你们觉得扮演赵敏的人好看吗 / 你们觉得扮演周芷若的人好看吗“，或者“一个十亿维的向量/十亿个一维的向量”，不同的权重甚至不同的分词结果，基于TF-IDF可以得出这两句相似也可能不相似，但语义上基本会认为是不相似的（至少后者如此）。因为这两类句子主语或者重点词语描述的不是一个对象。
但考虑到网文匹配场景，这两种结果都是有可能的

  • 比如作者就是把赵敏写错为周芷若后续修改时，我们认为两段应该匹配
  • 但也有可能这个章节中同时存在这两段，这个时候就不应该匹配上

目前我们没有解决这类场景，只是靠LCS全局最匹配可以避免，后续可能需要借助具备语义匹配的模型结合上下文匹配
最后 基于TF-IDF并不是唯一余弦相似度方案，改进的还有BM25权重、LDA主题模型、词向量模型等的余弦相似度，我们场景基于一个章节，使用BM25大材小用，不过代码里我还是写了一个BM25算法的实现作为参考。TF-IDF方案则分为文本预处理、分词(和词性标注）、词频统计与向量转换、余弦计算三个步骤：

分词

中文分词（chinese word segment，cws）常见的几个问题是：歧义（真歧义、组合歧义、交集歧义）、未登录词（新词）、分词方案不唯一（上海虹桥机场）。网文段落匹配其实不需要考虑歧义一词多义类，只要文字同就认为相似， 未登录词是需要重点考虑的。
因为歧义和分词方法不唯一，所以完美分词是难的，比如基于词典“普京和川普通话”，我们词典很可能就有普京/普京和川/川普，当然这里不考虑作家把“四”写成了“和”， 其次即便达到人类的语言感知级别，完美分词也是不存在的，比如有名的“下雨天留客天留人不留”，本身就包含两种分词结果，而且对应两种截然相反的含义。不过这里还好只要相似，不需要智能的判断语义相似与否。
词典匹配的分词方法可以分为：正向和逆向；根据词的匹配策略可以分为：最长词优先和最短词优先。具体地，常见的基于词典匹配的分词方法：
完全切分匹配、正向最长匹配、逆向最长匹配、正向最小匹配、逆向最小匹配、双向最长匹配，产生了HMM（viterbi decode）、MEMM（viterbi decode）、Linear + CRF、MLP + softmax、深度模型+ CRF等分词算法，具体可以参考宗成庆老师的《自然语言理解》
IKanalyzer、Ansj_seg、jcseg、HanLP 是当前比较流行且实用的Java分词组件，具体可以参考官网，这里总结下笔者使用感受：

  • IKanalyzer
    基于“正向迭代最细粒度切分算法”，笔者自接触Lucene到ES用的最多中文分词组件，使用和配置都比较方便，代码简单。尤其适合搜索“索引要做到最细颗粒度切分尽可能多的词，检索要做到最大颗粒切分（当然也有最多）”场景，但分词能力受限于字典，适合用于内容搜索，或相对文字规范用词正确的内容分词，对于现代互联网用词日渐随意和口语化不适合，对于用户评论以及表情包，尤其是我们面对的场景，网文里作家创造各种奇奇怪怪的人物名字、地理名字、社会机关名字等新名词必然频出。
  • Ansj_seg
    HanLP之前，笔者用的第二多的是Ansj_seg，功能非常丰富，源于中科院的 ictclas 中文分词算法，支持基于字典的DicAnalysis和CRF模型NlpAnalysis分词，前者适合搜索建立索引，NlpAnalysis支持发现新词，非常适合我们的场景。
    举个例子：“美猴王跟着孙菩提学习了三百六十天”，因为IK词库有美猴王没有孙菩提，所以分词结果是“美猴王/跟着/孙/菩提/学习/了/三百/六十/天”，Ansj_seg虽然没有收录美猴王和孙菩提，但是根据core词典里“跟”作为介词可能性更大以及BEMS标注，认为“美猴王”切分的可能性较大，所以正确的识别出来“美猴王/跟着/孙菩提/学习/了/三百六十/天”，可以说非常适合了。
    但NlpAnalysis似乎不适合搜索场景使用，尤其是NlpAnalysis和ictclas 一样支持自定义词库有限，但优先还是使用自带core字典收录词（笔者经验教训是搜索时宁用IKanalyzer不用Ansj_seg）如果增加自定义，需要自己训练模型
  • FudanNLP 看了下源码，可能不适合正是环境中大规模的去使用。
  • HanLP 可能是目前功能最丰富的中文自然语言处理工具包，内置如CRF分词、HMM分词等，具体可以参考官网介绍。

下面代码里我分别用Ansj_seg和HanLP分词组件实现不同算法作为对比，二者各自的NLP分词器都具备一定的发现新词能力，代码较多，我上传到github上了，移步这里
上面代码除ED(LD)、LCS、基于Ansj的TF-IDF向量实现、HanLP+Simhash的实现，后者是DeepSeek给的一个词向量方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public static void main(String[] args) throws Exception {
    log.info("----main-----");
    TFIDFByLucene.init("ansj", "nlp_ansj");
    lcsSimCalc(text1, text2);
    levenshteinSimCalc(text1, text2);
    tfidfSimCalc(text1, text2);
    hanlpSimCalc(text1, text2);
}

public static void dloopBestMatchFunc(String tag, Map<String, String> text1, Map<String, String> text2,
        BiFunction<String, String, Double> func) throws Exception {
    for (String key1 : text1.keySet()) {
        String bestMatch = "-1";
        double bestScore = -1.0;
        for (String key2 : text2.keySet()) {
            double score = func.apply(text1.get(key1), text2.get(key2));
            if (score > bestScore) {
                bestScore = score;
                bestMatch = key2;
            }
        }
        System.out.println(String.format("%s:%s -> %s similarity: %.4f", tag, key1, bestMatch, bestScore));
    }
    System.out.println("------------");
}
public static void hanlpSimCalc(Map<String, String> text1, Map<String, String> text2) throws Exception {
    dloopBestMatchFunc("hanlp", text1, text2, (line1, line2) -> {
        SimHash hs1 = HanLpSimilarity.simHash(line1);
        SimHash hs2 = HanLpSimilarity.simHash(line2);
        double score = hs1.getSemblance(hs2);
        return score;
    });
}

public static void lcsSimCalc(Map<String, String> text1, Map<String, String> text2) throws Exception {
    dloopBestMatchFunc("lcs", text1, text2, (line1, line2) -> {
        return lcsSimilarity(line1, line2);
    });
}

public static void levenshteinSimCalc(Map<String, String> text1, Map<String, String> text2) throws Exception {
    dloopBestMatchFunc("lev", text1, text2, (line1, line2) -> {
        return levenshteinSimilarity(line1, line2);
    });
}

public static void tfidfSimCalc(Map<String, String> text1, Map<String, String> text2) throws Exception {
    Map<String, Map<WordInfo, Double>> tfIdf1 = TFIDF.create(text1, ANALYZER, WRDFILTER);
    Map<String, Map<WordInfo, Double>> tfIdf2 = TFIDF.create(text2, ANALYZER, WRDFILTER);
    String prefx = "TFIDF";
    Map<String, Integer> weights = TFIDFByLucene.WeightsMap;
    if (null != weights && !weights.isEmpty()) {
        tfIdf1.values().forEach(ent -> reWeight(ent, weights));
        tfIdf2.values().forEach(ent -> reWeight(ent, weights));
    }
    
    for (String key1 : tfIdf1.keySet()) {
        String bestMatch = "-1";
        double bestScore = -1.0;
        for (String key2 : tfIdf2.keySet()) {
            double score = Cosine.cosineSimilarity(tfIdf1.get(key1), tfIdf2.get(key2));
            if (score > bestScore) {
                bestScore = score;
                bestMatch = key2;
            }
        }
        System.out.println(String.format("%s: %s -> %s with similarity: %.4f", prefx, key1, bestMatch, bestScore));
    }
}
private static void reWeight(Map<WordInfo, Double> words, Map<String, Integer> weights) {
    words.entrySet().forEach(ent -> {
        Integer weit = weights.get(ent.getKey().getType());
        if (null != weit) {
            ent.setValue(ent.getValue() * weit);
        }
    });
}

private static WordAnalyzer<WordInfo> ANALYZER = new WordAnalyzer<WordInfo>() {
    @Override
    public List<WordInfo> split(String text) {
        return TFIDFByLucene.splitWords(text);
    }
};
private static Predicate<WordInfo> WRDFILTER = new Predicate<WordInfo>() {
    @Override
    public boolean test(WordInfo wd) {
        return !TFIDFByLucene.EXCLUDE_TYPE.contains(wd.getType());
    }
};

public static double levenshteinSimilarity(String s1, String s2) {
    if (StringUtils.isEmpty(s1) || StringUtils.isEmpty(s2)) {
        return 0d;
    }
    return apacheLevenshtein(s1, s2);
}

public static double lcsSimilarity(String s1, String s2) {
    int lcsth = new LongestCommonSubsequence().apply(s1, s2);
    if (lcsth > 8) {
        return lcsth * 1d / Math.min(s1.length(), s2.length());
    }
    return lcsth * 1d / Math.max(s1.length(), s2.length());
}

public static double apacheLevenshtein(String s1, String s2) {
    return 1.0d - LevenshteinDistance.getDefaultInstance().apply(s1, s2) * 1.0d / Math.max(s1.length(), s2.length());
}

对于 上面 C4/D5，如果把“美猴王”改为“孙悟空”，我用一些语义相似度供应商有的判定 90.75%相似度，也有97%，后者我认为略高了，但显然都比只是简单的使用 ED、Levenstein、LDA/TF-IDF分析都要准确
但如果我把D5中的“孙悟空”改为“美猴王”之后，相似度竟然从90.75%变为 4.75%，这显然不是一个合适的算法。因为看过《西游记》都知道美猴王就是孙悟空另一种称呼，”自学”和“学习”也算同义词，而且即便不考虑同义词，相似度降到5%是不稳定的。我们期望的是这里不会仅仅因改了人物别名就变得匹配不上
或许使用这类自然语言理解工具需要更多的训练和理解同义词，当然也可以使用同义词发现工具计算词向量得到同义词， 总之首先需要分词组件Ansj和Hanlp支持同义词，比如这里“美猴王”这个词条都不在二者同义词库，所以需要加入进去（hanlp：data/dictionary/synonym/CoreSynonym.txt， ansj：/library/synonyms.dic），其次配置停止词，有些比如“了”之类的词过滤掉，可以配置各自的stopword，Ansj默认stop word较少，可以酌情增减，不过这不是本文重点，不过需要提醒的是，Ansj的默认配置，会把动词过滤掉，需要从stop.dic删除”v nature” 这行配置。HanLP本身具备同义词库，但是过于丰富以至于可能在比较相似性时失真。
总的来说是：

  • HanLp的同义词，为了比较相似度，需要我们在分词后，换成同义词列表中第一个词，保持 一致
  • Ansj的同义词， 本文逆文档率是通过Lucene实现，所以开始选择Ansj的Lucene插件，但是后来发现，Ansj近义词插件实际在创建索引时会取出全部匹配的同义词写入到索引，这导致IDF失真，所以需要做些改动，如下面代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
org.ansj.lucene.util.AnsjTokenizer
if (synonyms != null) {
    for (SynonymsRecgnition sr : synonyms) {
//                parse.recognition(sr);
        for (Term term : terms) {
            SmartForest<List<String>> branch = SynonymsLibrary.get().getBranch(term.getName());
            if (branch != null && branch.getStatus() > 1) {
                List<String> syns = branch.getParam();
                if (syns != null) {
                    String synName = syns.get(0);
                    // term.setSynonyms(syns);
                    term.setName(synName);
                    term.setRealName(synName);
                }
            }
        }
    }
}

// 而HanLP则是在解析词列表时候，再过一遍同义词词典，如果是名词，则取出同义词第一个
if ("n".equals(nature)) {
    SynonymItem synciters = CoreSynonymDictionary.get(word);
    if (null != synciters && null !=synciters.synonymList && synciters.synonymList.size() >0) {
        word = synciters.synonymList.get(0).realWord;
    }
}

即需要把AnsjTokenizer parse方法parse.recognition改成替换同义词列表第一个。同样的HanLp可以在分词后再逐个通过CoreSynonymDictionary替换（也可以这里限制仅为名词或成语时同义词生效）
总之设置同义词之后，可以看到相似度有不少提升，但这么做不是没有副作用的，因为其同义词可能存在文本中，影响TF-IDF值。上面列举的C1/C2之外大部分是例外情况，真实匹配遇到大部分还是可以通过LCS+TF-IDF匹配上的，这里只是分析下几个低于0.8相似度的原因。
比如上面C8和D9通过simhash/TFIDF都可以得到接近0.9的相似度，效果不错，不过TFIDF即使用Ansj分词，并不稳定，比如我把“goodread”替换为“烂番茄” 得到的相似度降到0.3了，这是因为替换为“烂番茄”后，分词由”goodread/文插图“变成了“烂番/茄文/插图”, 一拆为三且都是名词有二倍的权重。
分词不理想是因为“烂番茄”不在Ansj的词典中， NlpAnalysis使用的就是crfmodel训练数据，逐个切分字符后，同隐含马尔可夫模型类问题一样，使用Viterbi算法，从CRF模型数据逐字计算BEMS状态转移概率，计算出
番/文/图各自的tag为E，即对应结束状态，所以分词成三份。而“goodread文插图”则在CRF进行vterbi之前，goodread已经被识别为一个英文单词作为一个Element，所以“文”对应的标签是B，后续“插”无法作为E，而“图”可以，所以分成了”goodread/文插图“:

1
2
3
4
5
6
hanlp+simhash+同义词
  “非ugc/仅/用于/goodread文/插画/的/点赞/效用/subtype/1”
  “非ugc/仅/用于/烂/番茄/文/插画/的/点赞/效用/subtype/1”
Ansj_seg+tfidf
  “非ugc/仅/用于/goodread/文插图/的/点赞/功能/subtype/1”
  “非ugc/仅/用于/烂番/茄文/插图/的/点赞/功能/subtype/1”

所以tfidf得到相似度较低，相比之下，HanLP+Simhash看起来较为稳定，始终只切出了“插图”，虽然结果相对较好，但是却是错误的，这里其实就可以看出其将C7与D3认为最匹配，效果最差，具体下文Simhash部分分析一下。
这里试了下如果给名词/人名权重2，可以得到不错效果，大多超过0.8相似度。但其实也并不合适，比如西游记前几章或者拜师这里，每段频繁出现人名，像上面hanlp+simhash C9匹配到D1(但也和hash有关，下文提及)

基于Lucene的TFIDF

  • 如果你不了解Lucene或TFIDF，我在blogcode提供了一个纯内存的TFIDF和BM25实现，这里使用Lucene是希望ByteBuffersDirectory减少堆内存使用，因为试下来大量比较耗内存或者cpu，而耗内存导致高频GC导致cpu较高，基于Lucene试下来损耗少
  • 另外一个问题是，如果章节的段非常少，比如1至n段， 也就是本次只有1至n个文本，那可能很多词会出现在至少n-1个文本中，也就意味着这些词的逆文档率为0，即cossine后可能一直是0，也即永不相似，应避免

TFIDF+余弦总结

  • 分词选择
    不考虑加入到词典的话，Ansj_seg分词 “锦苑中学”/”文插图”一定程度可以识别出来，HanLP则较大概率识别两个，虽然hanlp考虑的多，支持多种分词，但Ansj_seg训练自己的CRF模型也较为简单，我最终选择了Ansj_seg，开源CRF++训练
  • 文本影响
    TFIDF显然受段增减影响，从而影响余弦距离计算，即假设去掉相同段落，影响了idf，从而影响相似度，但删减几段对于大部分词影响微小，而hanlp+simhash不受影响
  • 基于CRF，词语稍微变化或之前有错别字/语法错误，容易直接影响分词结果
  • Simhash或TFIDF都直接受分词影响，同样一段文字分词结果不同直接影响相似度，尤其是上面使用了CRF技术(甚至大部分基于LSTM/HMM思想)的分词
  • 但发现和维护新词，确实有不小的代价
  • 可以看到含有仿古文，分词困难，直接导致相似度判定分歧大，效果差，这或许是因为古汉语语法规范但是含义不规范，尤其是是一词多义，比如上面C6和D7， ”归于“这里可以理解和”安息于“同义。（但实际上，即便最先进的语义判定可能相似度较低，也应归于“匹配”）

Simhash

Simhash是Charikar 在2002年提出来的，参考 《Similarity estimation techniques from rounding algorithms》，谷歌网页去重可能就是参考这里工程化地实现，笔者前面也介绍过：开发常见的Hash函数(三)-Minhash_Simhash，一般基于分词的Simhash过程如下，这里参考知名网站给的实现，我后面介绍下这里错误的几个地方：

  • 分词，去掉停用词，确定词的权重(权重表示词对文档的重要程度，可以用词频)
  • 哈希，将每个词映射为向量，要求每个词映射后的向量随机分布，且不同词对应的向量不同，因此使用一般的哈希方法即可
  • 加权，将每个词的哈希签名h看做01串，设词的权重为w，则签名的第k位加权为h(k) = h(k)==1?w:-w
  • 合并，将文档中所有词的加权签名按位累加
  • 降维，h(k) = h(k)>0:1?0

需要指出的是谷歌的Simhash判定相似度方案是未被证明过的，笔者未找到，倒是找到论文是统计Simhash计算相似度的误差分析。但不能不说的是，Simhash一定从海明距离获取许多灵感，在此之前，像余弦特征描述音乐，描述相貌匹配度，海明距离描述指纹相似性等均有大量应用。
但Simhash确实有理论支撑的，Johnson–Lindenstrauss引理，学习机器学习应该了解这块基础理论：

1
2
3
4
5
Johnson–Lindenstrauss引理是一个关于降维的著名定理...这个定理告诉我们:
一个高维空间中的点集，可以被线性地镶嵌到低维空间中，同时其空间结构只遭受比较小的形变
约翰逊-林登斯特劳斯定理的证明，还说明了如何用随机投影法明确地求出这个变换，所用的算法只需要随机多项式时间。
当然，降维不是免费的：
如果要求形变很少的话，代价是被嵌入的低维空间维数不能很低；反之亦然，如果要求将点集嵌入很低维的空间，那么就不能很好地控制结构形变的程度。

更有趣可以参考“科学空间”的几篇文章：

简单理解为，对于词向量而言，Simhash是一个欧氏空间向量降维的结果，尽管是有损的。
本文使用的HanLP+Simhash部分的代码其实是从deepseek得到的示例，看起来代码出处是这里
https://cloud.tencent.com/developer/article/1043655， 笔者做了些调整，作为对比列出。
不过原代码因为考虑到需要支持128位或更多，所以使用了BigInteger实现，笔者提供了另一个基于64bit的实现:QuickSimHash， 实际测下来当使用64bit时，计算精确度表现不会差于deepseek提供的这个算法，但性能更是快了60-70倍。

为什么Simhash词的权重不宜过高

但Simhash变现的稳定性也是它的问题所在，即比如可以对某一类名词统一设置权重，但是不能像tf-idf一样灵活的根据词频设置权重–那么，可否修改代码，查询词频来tf或idf设置权重？
Simhash也可以跟VSM一样基于特征项在文档中的重要程度分配权重，一般分配分配方式比较固定，如果想反应不同的单词作为特征的不同的重要度，可以考虑动态规则（如tfidf值）。有个知名去重应用是这么做的，但TFIDF值作为参考设置权重需要注意权重相差过大，可能是有问题的，尤其是比如词频导致某一类词权重是其他一百倍，余弦方法可以很快较低影响，但对于Simhash则其他100词带来的影响可以忽略！比如64-bit的simhash时，输入词“美猴王”权重给了100，得到simhash：sim-A即我们知道simhash每次实际只是根据现有64个int正负值确定加减1翻位，也就意味着权重100导致这64个int数组值已经是+100或-100了，这意味着再输入99次任意字符，这些int数组正负不变！，即此时的simhash和sim-A海明距离依旧是0!
举个例子更直观理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static long computeSimHashFromString(List<String> shingles) {
    int v[] = new int[HASH_SIZE];
    for (String shingle : shingles) {
        byte[] bytes = shingle.getBytes();
        long longHash = FPGenerator.std64.fp(bytes, 0, bytes.length);
        for (int i = 0; i < HASH_SIZE; ++i) {
            boolean bitSet = ((longHash >> i) & 1L) == 1L;
            v[i] += (bitSet) ? 1 : -1;
        }
    }
    long simhash = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
        if (v[i] > 0) {
            simhash |= (1L << i);
        }
    }
    return simhash;
}

上面代码里数组v就是64个平面投影，也是加减weight权重的数组，极端情况，比如下面是我使用500个连续的“he”作为输入，进行64位simhash得到结果，500,-500….这些是最后一轮时64个特征(维度)对应的数值：

1
12017435215498645308:[-500, -500, 500, 500, 500, 500, -500, -500, 500, 500, 500, 500, -500, -500, -500, -500, 500, -500, -500, -500, 500, -500, -500, -500, 500, 500, -500, 500, -500, -500, 500, -500, -500, -500, -500, 500, -500, 500, -500, 500, 500, -500, -500, -500, -500, -500, -500, 500, -500, 500, 500, -500, -500, -500, 500, 500, -500, 500, 500, -500, -500, 500, -500, 500]

最终64位的Simhash值就是根据上面大于0小于0设置1/0值并逆序。所以不难理解，最终结果非0则必是正500或负500，这意味着什么呢？意味着之后再继续跟任意500个任意长度的字符串都不会影响其最终Simhash值为当前值
所以可以构建两个任意比如1千个汉字2个为一组，加在500个“he”之后，他们Simhash值是一样的，但是内容确实一半完全不一样！
那么非极端情况会怎样？
下面是我从西游记某章切分2500多个词作为输入，基于Apache codec的murmur hash64后得到的simhash的最终weight数组：

1
[176, 192, 124, -62, 322, 152, 60, -74, -594, 96, -144, 206, 84, -164, -168, -48, -602, -118, -84, -102, 122, 384, -260, 428, 28, -112, -420, -64, -110, 218, -68, 552, 156, 62, -40, 438, 200, 146, 58, 574, 210, 54, -452, 28, -54, -290, -200, 114, 50, -138, -264, -68, -108, 20, -206, -282, -150, 742, 126, -228, 58, 400, -264, -32]

Simhash算法常规每次增减1，从这个数组可以看到，最小的weight[i]是20，假设再继续输入字符串，幸运的话，至少需要 20 次输入才能造成1个bit变化，最少再有32次输入造成2个位反转…
这是理想情况，实际我测试了5000次下来，每次从中文汉字中随机选一个字符加入，知道增加至1000个汉字，观察下来平均是第327个字才稳定在2bit不同，而前1000字稳定在5bit不同。
所以我的建议是，使用64位的Simhash时：

  • Simhash输入列表不应过大，过大可能导致不准确，hamming distance也需要限制大小，具体看经验值了。推荐是7，但是3以内也可能不可信
  • 某一个词分配权重/次数不应过大。如上面权重100，表示后面可能再输入99次都不会改变一个bit值

hash算法影响结果

HanLP+Simhash 实际跑出来结果是 C7和D3最匹配而不是D8，下面是hanlp分词结果(重复是因为配了权重X2)，这里看到有同义词转换，前面提到归一化的同义词不会低于原有相似，但是看下面结果不难看出C7/D8应该更相似, 二者Jacard相似度接近0.6，而C7和D3的jacard相似度0.2不到，可以说差之千里了。当然是受hash算法的结果在0/1选择超平面影响导致（整体结果导致如此，但去掉D3中四个“孙悟空”，相似度确实降了0.3了），上面示例SimHash使用的哈希算法其实是Python的默认hash算法，使用还是上个世纪哈希常用的“大质数”-1000003，而FastSimhash方法则能匹配到D8， 这也验证了实验数据所表明的Simhash在小文本输入存在误差不准确的问题。

1
2
3
c7 = ("普京", "普京", "与", "克林顿", "克林顿", "没有", "参与", "进来", "因为", "锦苑", "锦苑", "中学","中学", "司马迁", "司马迁", "和", "孙权", "孙权", "不再", "来", "玩","你", "说", "是", "也", "不是", "宋江", "宋江", "去", "了", "松江府", "松江府", "还", "没", "来得及", "说", "一首");
d8 = ("普京", "普京", "与", "克林顿", "克林顿", "没有", "达成", "因为", "普通", "情理","情理", "不", "允许", "司马迁", "司马迁", "和", "孙权", "孙权", "不是", "一路人","一路人", "听","了", "松江府","松江府", "的", "宋江说来说去", "宋江说来说去", "不", "明白", "是", "还是", "不是");
d3 = ("孙悟空","孙悟空","每天","和","门生","门生","们","待","在","一起","打扫","院子","院子","养花","养花","修树","修树","挑水","捡","柴","学","经论","经论","道","不知不觉","过去","了","七","年","时间","时间","一","天","菩提","老祖","老祖","对","孙悟空","孙悟空","说");

上面是分词+权重的结果。
所以最终没有选择Simhash作为相似度比较方案

效果/总结

  • 每天作家修改内容，影响的评论大概2-3万，使用编辑距离计算相似度算法，导致相似度匹配较低而无法匹配段，而删除的评论大约每天7500+，在增加LCS/TFIDF算法之后，每天大约挽回6300条评论，剩下占比较高的还是段删除、改动较大。使用TFIDF效果不稳定，6300条中大部分是LCS匹配的，
  • 新词发现或者基于BERT做匹配是后续努力的方向

** 遵循CC协议，转载请标注来源 **