一种图文组合相似度算法的设计与优化

鲜翠琼 秦学 朱道恒 操淑敏

摘  要：包含文字和图片的文档作为信息的一种载体，能够极大地丰富信息的表现形式。针对传统计算图文相似度的算法效率不高的问题，提出一种图文组合相似度算法。将Jaccard相似系数引入余弦相似度，通过加权计算两文本的相似度，然后用感知哈希算法计算文档中图片相似度并找出最大值，再计算单个文档中所有图片相似度均值，与文本相似度加权求得文档的图文相似度。最后通过一个文档相似度查重系统验证了该算法能准确高效地完成文档之间相似度的量化，且优化后的相似度算法能够极大提高该系统的运行效率。

关键词：余弦相似度算法;Jaccard相似系数;感知哈希算法;文本相似度

中圖分类号：TP391.1     文献标识码：A

Abstract： As a carrier of information， documents containing both text and graphics can greatly enrich information. In view of the inconsistency of traditional algorithms for calculating similarity between graphics and text， this paper proposes a similarity algorithm for combining graphics and text. Jaccard similarity coefficient is introduced into cosine similarity， and the similarity of two kinds of text are calculated by weighting. Then， the graphic similarity in the document is calculated through PHash algorithm and the maximum value is derived. After that， the average similarity of all the graphics is calculated in a single document， and weighted with the text similarity， thus to obtain the similarity of both graphics and text of document. Finally， a document similarity check system is used to verify that the algorithm accurately and efficiently quantifies the similarity between documents， and the optimized similarity algorithm greatly improves the efficiency of the system.

Keywords： cosine similarity algorithm; Jaccard similarity coefficient; PHash similarity; text similarity

1   引言（Introduction）

文本相似度分析是中文信息处理领域的一种基础技术，凡是在处理中文信息处理的领域都有其身影。机器翻译领域，文本相似度可作为翻译准确度的衡量原则[1];搜索引擎领域，文本相似度算法是其核心;自动问答领域，文本相似度更是匹配回答与提问的重要技术[2];在论文查重领域，文本相似度研究更是系统检测学术不端行为的唯一手段;在文本聚类领域，文本相似度也是聚类表中的重要参考[3];在新闻推荐、关联词推荐等智能精准推荐领域，文本相似度研究更是其基础工作[4]。而在计算机视觉领域，图像相似度度量是一个基础问题，它在图像分类、图像检索、图像匹配、模式识别和目标检测等多方面都有十分广泛的应用。因此，对图像文本相似度度量的研究在诸多领域都有非常重要的意义。

2   相关算法（Correlation algorithm）

2.1   余弦相似度

余弦相似度又称为余弦相似性，是通过测量两个向量的夹角的余弦值来度量它们之间的相似性。利用两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。

将一个字符串通过分词工具分成一个个词语项，将这些词语，映射到向量空间，形成字符串和向量数据的映射关系。利用词语词频映射字符串向量。通过计算对应向量的余弦值来表示两个文本字符串在统计学方法中的相似度。

3.3   算法优化

上述算法是将所有图片依次与其他图片对比，对比完成后才处理结果，这样在图片重复度较高时会增加很多额外开销。故在图1所示的比较算法的10和11行间增加一个判断语句，其余部分不变，如图2所示。

改进算法后系统运行效率大幅提升，但仍受限于文档中相似图片的顺序及数量。分析模块调用算法，发现每组数据中只有几十到几百张图片，但图片计算次数从几百到几十万次。比较算法每计算一次就要对图片进行一次PHash处理，单次PHash处理很快，但几十万次PHash处理就会大大增加程序运行时间。故考虑在图片相似度计算发生前完成所有图片的PHash处理，并将处理好的Hash指纹存储起来。计算图片相似度时不再调用Phash算法对图片进行DCT等计算，直接读取已经计算好的图片Hash指纹。进一步优化比较算法如图3所示。

4  实验验证与分析（Experimental verification and analysis）

4.1   系统设计

设计一种文档相似度查询系统，应用到判定作业是否抄袭的场景。系统主要包含六个模块：文件导入模块、文本相似度模块、图片相似度模块、比较模块、输出模块、可视化界面模块，如图4所示。系统可自动识别txt文档编码格式，自动分离Word中图片和文字信息，然后按前面介绍的方法对图片和文字分别计算相似度，加权求出文档整体相似度，最后将全部比较数据输入本地csv文档中。此外可视化界面让用户使用时更加方便，只需把待比较文件放入同一文件夹下，将路径传入程序，便能自动计算文件夹内所有文档的相似度，最后将结果导入到csv文件。

4.2   测试结果分析

选四组数据（一组人工制造的有特殊相似度分布的数据加三组真实作业数据）进行测试。第一组为两份不同的文档分别去除图片和保留图片放入待查重目录进行查重测试，产生特殊相似度分布的结果，方便检查程序能否正常工作。另三组为实验报告合集，导入系统得到测试结果如表2—表5所示。

取第二组数据的测试结果作准确性测试如图5所示，得对比详情如图6所示。

从图中看出，经组合算法加权后的值更加光滑地表现了相似度分布，且处于各算法的中间值，趋于稳定。从结果判断具有极高相似度的数据量较小，随数据量的增大，相似度在小范围内迅速下降，最后趋于平缓，符合实际情况。经过人工比对加权相似度超过80%的99条比对结果，发现大部分内容几乎完全相同。在总加权相似度低于0.8但图片相似度等其他三条相似度中两条值偏高的文档中，部分内容也存在删减性雷同。故实际使用时，判定抄袭的具体阈值还需实际作业类型来确定。一个字数量庞大的作业，经系统测试，当加权相似度大于80%，或其他几项文本相似度大于95%或图片相似度大于90%才判定为抄袭的原则下，判定结果99.9%是准确的。

4.3   算法优化后的测试结果

算法优化后再次测试上述四组数据，优化前后运行时间对比如图7—图10所示。

从图7至图10可知，系统经过优化后，图片处理次数从几十万次降至几百次，极大地缩短了系统的运算耗时。虽然会增加几十万次的读取操作，但这个代价完全不值一提。测试数据整体运行效率明显提高，验证了改进算法的有效性。

5   结论（Conclusion）

针对传统计算图文相似度的算法效率低的问题，本文提出一种图文组合相似度算法。通过将Jaccard相似系数引入余弦相似度通过加权计算文本间的相似度，再与PHash算法求得的图片相似度均值加权后得到全文相似度，并对组合相似度算法作出优化。最后在一个文档相似度查重系统中验证了该算法的准确性和可行性，并且运行相似度优化算法后，系统整体运行效率得到极大提升。未来可以考虑引入词频权重

库来提高计算准确率，以及将系统部署在云服务器实现“云查重”来提升查询效率。

参考文献（References）

[1] 杨立波.基于CFN的相似度计算在实例机器翻译中的应用[J].电脑开发与应用，2011，24（06）：58-60.

[2] 宋万鹏.短文本相似度计算在用户交互式问答系统中的应用[D].中国科学技术大学，2010.

[3] 孙爽.基于语义相似度的文本聚类算法的研究[D].南京航空航天大学，2007.

[4] 田军霞.基于短文本处理算法优化的文本信息推荐系统的设计与实现[D].北京交通大学，2017.

[5] 金宇.基于常规水质参数的供水管网特征污染物分类方法研究[D].浙江大学，2017.

[6] 张猛，李玲娟.基于改进的Jaccard相似系数矩阵的社团划分算法[J].南京邮电大学学报（自然科学版），2018，38（06）：96-102.

[7] 金希茜.基于语义相似度的中文文本相似度算法研究[D].浙江工业大学，2009.

[8] 文心灵.方向离散余弦变换和方向离散小波变换及其在超声图像中的应用[D].北京交通大学，2008.

[9] 唐菲骏.基于VC-1视频标准的离散余弦变换实现及验证[D].西安科技大学，2012.

[10] Quyet Thang Dang， Trung Huy Phan. Determining Restricted Damerau-Levenshtein Edit-Distance of Two Languages by Extended Automata[P]. Computing and Communication Technologies， Research， Innovation， and Vision for the Future （RIVF）， 2010 IEEE RIVF International Conference on， 2010.

[11] F. Tichy， W. The string-to-string correction problem with block moves[J]. ACM Transactions on Computer Systems， 1984， 2（4）： 309-312.

[12] Anas M Al-Oraiqat， Natalya S. Kostyukova A Modified Image Comparison Algorithm Using Histogram Features[J]. ResearchGate， 2013， 4（1）： 152-156.

[13] 龚成清.基于Java的相似图片搜索[J].電脑开发与应用，2012，25（10）：13-15.

作者简介：

鲜翠琼（1993-），女，硕士生.研究领域：数据挖掘与分析.

秦   学（1980-），男，博士，副教授.研究领域：大数据环境下的电子政务.

朱道恒（1992-），男，硕士生.研究领域：语义Web，数据挖掘.

操淑敏（1996-），女，硕士生.研究领域：数据挖掘与分析.