一種圖文組合相似度算法的設計與優化

鮮翠瓊 秦學 朱道恒 操淑敏

摘 ?要：包含文字和圖片的文檔作為信息的一種載體，能夠極大地豐富信息的表現形式。針對傳統計算圖文相似度的算法效率不高的問題，提出一種圖文組合相似度算法。將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-），女，碩士生.研究領域：數據挖掘與分析.