近似重复检测:怎样找出几乎一样的文本
抓来的评论和新闻里,很多条只差几个字。这篇讲怎样给两段文字有多像打分,怎样在几万条里把近似重复找出来归成组,这些办法从哪来,各学科怎么用,想深入该读哪几篇论文。
假设你在研究一座古镇的口碑,从几家点评网站和旅游论坛抓了两万条游客评论。细读下去,有不少条几乎一样。有人把同一条评论在几个网站各发一遍,有的推广文案改了几个字又发了几十次,一篇游记被转来转去,只换了标题。这些近似重复留在材料里,一种说法会被当成很多人的意见,词频和情绪的比例都跟着偏。
近似重复检测(near-duplicate detection)要做两件事。一是给两段文字有多像打个分,二是在成千上万条里把分数高的那些对找出来,再归成组。打分有个朴素的办法,是把每段文字切成交叠的小片,看两边有多少片是共同的。
相像度 = 两段共有的片数 ÷ 两段合起来一共有几种片
下面的例子是编的。A 是【古城夜景很美值得去】,B 是【古城夜景很美值得再去】。按相邻两个字切片,A 从【古城】【城夜】切到【得去】,共 8 片,B 切出 9 片。两边共有的是前 7 片,合起来一共 10 种,相像度是 7 ÷ 10 = 0.7。完全一样的两段得 1,没有一片相同的得 0。难处在数量上,两万条评论两两相比,要比将近两亿对。
从查抄袭到给几十亿网页去重
Brin、Davis 和 García-Molina 1995 年考虑的是数字图书馆里的版权。文档成了电子版,容易被复制,版权也更容易被侵犯。论文提出先把文档登记下来,再查出新文档里整篇或部分抄来的内容,并做了一个原型系统 COPS(Brin 等,1995)。
Broder 1997 年的论文把【大体相同】变成了能算的数。文档里连续的一小段叫 shingle(瓦片),上面那个比值就是论文定义的 resemblance(相像度);分母换成其中一篇自己的片数,得到 containment(包含度),看一篇是否大体包含在另一篇里。论文指出,常用的字符串距离通常要拿两篇全文来比,文档一多,这样两两比就做不到,所以给每篇各留一份大小固定的样本,拿两份样本就能估出相像度。论文用 AltaVista 搜索引擎从网上抓来的 3000 多万份文档试了这个办法,按相像度 50% 归组,得到 360 万个组,其中 210 万个组里全是一模一样的文档,其余 150 万个组共 700 万份,相同的和相近的混在一起(Broder,1997)。这次归组的详情写在 Broder 等人同年的另一篇论文里,他们设想的用途包括过滤网页搜索结果和找出侵犯知识产权的行为(Broder 等,1997)。
样本让每一对比得快了,要比的对数却没少。Indyk 和 Motwani 1998 年研究近似最近邻搜索,也就是在一大堆数据里找出和查询对象最接近的那一个,允许有一点误差。论文指出,数据的维数一高,已有的办法比起拿查询对象挨个去比,好不了多少。论文引入 locality-sensitive hashing(局部敏感哈希)。哈希是把任意长的内容算成一个定长的值,局部敏感哈希要做到,两个对象离得近,算出同一个值的机会就远大于离得远的两个,查的时候只细看和查询对象撞在一起的那些。论文也提到它可以用在信息检索和快速聚类上(Indyk 与 Motwani,1998)。
Charikar 2002 年把局部敏感哈希定义为一族哈希函数,两样东西算出同一个值的概率正好等于它们的相似度,并据此造出一种给向量用的方案,可以估计两个向量的余弦相似度(Charikar,2002)。这个办法后来叫 simhash(相似哈希)。2006 年,Henzinger 在 16 亿个不同网页上把它和 Broder 等人的办法放在一起比,两种办法找同一网站内的近似重复都不理想,找不同网站之间的都很准;总的来看,Charikar 的办法找出的对里有 50% 确实是近似重复,Broder 等人的办法是 38%(Henzinger,2006)。Manku、Jain 和 Das Sarma 2007 年讲了 simhash 在网页抓取中的用法。MD5 这类加密哈希,两篇文档差一个字节,算出的值就完全不同;simhash 先把网页变成一组带权重的特征,再压成一个指纹,相似的文档得到的指纹只差几位。论文说,80 亿个网页用 64 位的指纹就够了,新抓来一个网页,只要查有没有旧指纹和它相差不超过 3 位(Manku 等,2007)。
这些办法比的都是字面。两条评论意思一样而用词全换了,切片对不上,指纹也差得远。按意思比,要先把每句话变成一串数字,也就是句子向量,详见语义相似度那一篇。Reimers 和 Gurevych 2019 年的 Sentence-BERT(句子向量模型)论文算过一笔账,在 1 万个句子里找出最相似的一对,用 BERT(一种预训练语言模型)把两句成对送进去比,要算约 5000 万次、约 65 小时,先给每句算出向量再比,大约 5 秒(Reimers 与 Gurevych,2019)。
近几年,去重又用在了训练语言模型上。Lee 等人 2022 年发现,已有的训练语料里有许多近似重复的样本和很长的重复片段,C4 语料里有一句 61 个词的英文句子重复了 6 万多次,在这类语料上训练的模型,不加提示生成的文字有超过 1% 是从训练语料原样照抄的。去重以后,模型吐出背过的文字的次数降到十分之一,达到同样或更高的准确率所需的训练步数也更少(Lee 等,2022)。2023 年,Abbas 等人提出 SemDeDup(语义去重),用预训练模型的向量找出意思相近、又不完全相同的语义重复,在 LAION 数据集的一个子集上删掉一半数据,性能损失很小,训练时间差不多减半(Abbas 等,2023)。
| 年份 | 谁 | 留下了什么 |
|---|---|---|
| 1995 | Brin、Davis 与 García-Molina | 登记文档,查整篇或部分的复制 |
| 1997 | Broder | 切片算相像度,每篇只留一份小样本 |
| 1997 | Broder 等 | 把网上字面相似的文档归成组 |
| 1998 | Indyk 与 Motwani | 局部敏感哈希,不必两两全比 |
| 2002 | Charikar | 能估计余弦相似度的哈希 |
| 2007 | Manku 等 | 用 64 位指纹在几十亿网页里查重 |
| 2019 | Reimers 与 Gurevych | 先算句子向量,再按意思比 |
| 2022 | Lee 等 | 给语言模型的训练语料去重 |
| 2023 | Abbas 等 | 用向量删掉语义重复 |
评论、意见和帖子里的重复
旅游研究里,António、Correia 和 Perdigão Ribeiro 2023 年专门研究 TripAdvisor(猫途鹰)上的重复评论。他们抓取了葡萄牙科英布拉和西班牙萨拉曼卡这两座世界遗产城市的评论,每座城市取十个最热门的景点,时间是 2017 到 2018 年,共 8638 条,语言有英语、葡萄牙语和西班牙语。两年里,科英布拉有 60 个用户、萨拉曼卡有 64 个用户给同一个景点发过不止一条评论。他们从字面重复和意思相近两方面去找,归纳出三种动机,分别是享乐、实用,以及发布出了问题或忘了自己评过。文章提醒研究者,重复会让研究结果走样,用评论做研究要先去掉重复和近似重复(António 等,2023)。
公共政策研究里,一批几乎一样的意见本身就是研究对象。在美国的行政规章制定中,有一种意见成批出现,由组织发起,成员和支持者提交,内容相同或近似重复,Balla 等人称之为大规模意见运动。他们研究了环境保护署 2012 到 2017 年间 22 项规章制定中的 1049 场这类运动,发现该机构回应意见时会提到它们,引用的比例却低于其他意见;最后的规章大多没有照意见要求的方向改,对这些运动尤其如此(Balla 等,2022)。Linder 等人用找出相似文字片段的算法比较美国各州议会的 50 万份法案,州与州之间重用文字的多少和政策扩散网络里的联系相关(Linder 等,2020)。
Zhang 等人 2013 年从新浪微博抓取数据,用改进的局部敏感哈希找出重复的微博,借此认出抄别人内容的潜在垃圾账号。论文的出发点是,微博已是舆情挖掘和群体行为研究的重要材料来源,垃圾信息可能大大影响分析结果(Zhang 等,2013)。
想深入可以读这几篇
- Broder(1997)On the resemblance and containment of documents,九页,相像度、包含度和切片的定义都在这里,例子是一句 a rose is a rose is a rose。
- Henzinger(2006)Finding near-duplicate web pages: a large-scale evaluation of algorithms,想知道切片和 simhash 两种办法在哪儿不灵,读这篇。
- Manku、Jain 与 Das Sarma(2007)Detecting near-duplicates for web crawling,一步步写了 simhash 怎样算出指纹,也讲了怎样在几十亿个指纹里快速找出只差几位的那些。
- Leskovec、Rajaraman 与 Ullman(2014)Mining of Massive Datasets,教材,第三章叫 Finding Similar Items(找出相似的东西),书里讲了局部敏感哈希的技巧。
- Kim 与 Park(2026)A Survey of Text Deduplication: From Syntactic Matching to Semantic Understanding,综述,把重复分成完全相同、近似和语义三类,从切片和局部敏感哈希一直讲到用向量和大语言模型去重。
TATOOLS 里的去重雷达和重复内容合并
TATOOLS 的【文本相似度去重雷达】按意思比较每条文本,用词不同也可能判为重复。交给它的可以是问卷开放题的回答和游客评论,也可以是政策文件的段落或论坛帖子。报告给出重复率和高相似度的文本对,把相似的文本归成组,列出每组的条数、代表文本和平均相似度。它的同义改写嫌疑模式还会逐词标出两条文本改在哪里。
【重复内容合并】给出一份合并方案,每组保留一条代表文本,其余标为并入,报告上写着合并后还剩多少条,原文不改也不删。