晉曉琳，張樹武，劉杰

(1.中國(guó)傳媒大學(xué) 信息工程學(xué)院，北京 100024；2. 中國(guó)科學(xué)院自動(dòng)化研究所 數(shù)字內(nèi)容技術(shù)與研究中心，北京 100190；3.北京電影學(xué)院未來(lái)影像高精尖創(chuàng)新中心，北京 100088)

1 引言

在高速發(fā)展的21世紀(jì)，每時(shí)每刻都有大量的信息產(chǎn)生并在互聯(lián)網(wǎng)上快速傳播。數(shù)據(jù)集合規(guī)模已實(shí)現(xiàn)從GB到PB的飛躍，未來(lái)網(wǎng)絡(luò)大數(shù)據(jù)還將實(shí)現(xiàn)近50倍的增長(zhǎng)。IDC《數(shù)字宇宙》的研究報(bào)告表明：2020 年全球新建和復(fù)制的信息量將超過(guò)40ZB，是2012年的12倍；而中國(guó)的數(shù)據(jù)量則會(huì)在2020年超過(guò)8ZB，比2012年增長(zhǎng)22倍。雖然數(shù)據(jù)量的飛速增長(zhǎng)帶來(lái)了大數(shù)據(jù)技術(shù)和服務(wù)市場(chǎng)的繁榮發(fā)展，但面對(duì)海量文本數(shù)據(jù)人們變得越來(lái)越手足無(wú)措，所以人們?cè)絹?lái)越希望能夠在海量文本環(huán)境下快速精確地提取出所需要的信息，從而對(duì)所選信息進(jìn)行后續(xù)處理。為了解決這一問(wèn)題，就需要一個(gè)文本相似性檢測(cè)技術(shù)，使人們能夠快速準(zhǔn)確地從海量數(shù)據(jù)中找到最為相似的文本。

文本相似度算法一直是自然語(yǔ)言處理領(lǐng)域研究的重點(diǎn)之一，國(guó)內(nèi)外學(xué)者也提出了一些解決方案?；诰嚯x的計(jì)算相似度的方法主要有余弦距離[1]、編輯距離[2]、漢明距離、歐幾里得距離。如丁智斌等提出先用VSM向量空間模型進(jìn)行文本向量化[3]，通過(guò)使用余弦相似度和 Jaccard 相似度這兩種基于向量?jī)?nèi)積的方法進(jìn)行相似度計(jì)算。胡維華等利用漢明距離計(jì)算文本相似度[4]，該方法首先采用TF-IDF算法以及《知網(wǎng)》的語(yǔ)義信息來(lái)加強(qiáng)語(yǔ)義信息，然后利用漢明距離計(jì)算文本相似度，避開(kāi)對(duì)高維稀疏矩陣的直接處理并提高了文本計(jì)算的準(zhǔn)確性?；诰嚯x的計(jì)算方法適用于文本數(shù)量較小的情況，在海量文本環(huán)境下，該計(jì)算方法的效率非常低。VSM 向量空間模型(Vector Space Model)是一種基于向量空間的方法，它是由Gerard Salton 等在1969年首先提出的[5] [6]。該模型需要逐個(gè)進(jìn)行向量化，并進(jìn)行余弦計(jì)算，比較消耗CPU處理時(shí)間，所以不適合于海量文本環(huán)境下。Simhash算法是2002年由Google 的Charikar提出的文本指紋算法[7]。該算法主要用來(lái)處理Google網(wǎng)頁(yè)去重問(wèn)題，也是目前主流的海量相似度算法之一[8] [9] [10]。Simhash算法主要通過(guò)指紋間的漢明距離來(lái)比較文本的相似程度，而且其“降維”的思想使得檢測(cè)速度快，常常被用做處理海量文本查找。但該算法的實(shí)質(zhì)是基于哈希的算法，只能得到一個(gè)粗略的相似度篩選，高的相似度并不意味著文本一定相似。

現(xiàn)在使用最多的搜索引擎主要是Elasticsearch和Solr[11][12][13]。Elasticsearch是一個(gè)建立在全文搜索引擎 Apache LuceneTM基礎(chǔ)上的搜索引擎，可以說(shuō)Lucene是當(dāng)今最先進(jìn)、最高效的全功能開(kāi)源搜索引擎框架。它是一個(gè)實(shí)時(shí)分布式的搜索引擎和數(shù)據(jù)分析引擎，能夠進(jìn)行全文檢索，結(jié)構(gòu)化檢索，數(shù)據(jù)分析，可以幫助你用前所未有的速度去處理大規(guī)模數(shù)據(jù)。對(duì)于海量數(shù)據(jù)來(lái)說(shuō)，ES可以自動(dòng)將大規(guī)模數(shù)據(jù)分布到多臺(tái)服務(wù)器上進(jìn)行存儲(chǔ)和檢索，而不需要額外建立數(shù)據(jù)庫(kù)。對(duì)于Solr來(lái)說(shuō)，在建立索引時(shí)，它會(huì)產(chǎn)生io阻塞，查詢性能較差，實(shí)時(shí)索引搜索效率不高。所以海量數(shù)據(jù)進(jìn)行搜索時(shí)，ES更具有優(yōu)勢(shì)。因?yàn)镋S實(shí)時(shí)搜索的優(yōu)點(diǎn)，國(guó)內(nèi)外很多公司都使用該框架作為信息檢工具。例如，Github公司使用Elasticsearch搜索20TB的數(shù)據(jù)，包括13億的文件和 1300億行的代碼；維基百科作為多語(yǔ)言的網(wǎng)絡(luò)百科全書，整個(gè)網(wǎng)站的總編輯次數(shù)已超過(guò)10億次，它使用Elasticsearch來(lái)進(jìn)行全文搜索并高亮顯示關(guān)鍵詞，以及給用戶進(jìn)行搜索推薦等功能；The Guardian是英國(guó)三大綜合性內(nèi)容日?qǐng)?bào)之一，Elasticsearch作為該新聞網(wǎng)站的搜索引擎去記錄用戶行為日志、發(fā)布用戶評(píng)論、進(jìn)行數(shù)據(jù)分析。

在對(duì)海量文本進(jìn)行搜索查詢時(shí)，Elasticsearch能夠分布式實(shí)時(shí)文件存儲(chǔ)，并將每一個(gè)字段都編入索引，使其可以被實(shí)時(shí)搜索。本文選用ES作為文本相似度檢測(cè)的第一步，通過(guò)多個(gè)關(guān)鍵詞的并行搜索來(lái)篩選出候選樣本。余弦相似度算法適合于小樣本集合，因此本文選用TF-IDF作為關(guān)鍵詞提取算法，通過(guò)關(guān)鍵詞作為ES查詢條件在海量文本環(huán)境下快速篩選出可疑候選集，進(jìn)而再用余弦相似度來(lái)進(jìn)一步找到最為相似的文本。

2 關(guān)鍵技術(shù)

2.1 Elasticsearch

Elasticsearch(簡(jiǎn)稱ES)是一個(gè)基于Lucene構(gòu)建的實(shí)時(shí)、分布式、RESTful的搜索引擎。它的高級(jí)之處在于，使用Lucene作為核心來(lái)實(shí)現(xiàn)所有索引和搜索的功能，使得每個(gè)文檔的內(nèi)容都可以被索引、搜索、排序、過(guò)濾。同時(shí)，它還提供了豐富的聚合功能，可以對(duì)數(shù)據(jù)進(jìn)行多維度分析；對(duì)外統(tǒng)一使用REST API接口進(jìn)行溝通，即Client與Server之間使用HTTP協(xié)議通信 ，Elasticsearch的架構(gòu)圖如圖1所示。

圖1 Elasticsearch分布式搜索引擎架構(gòu)圖

Elasticsearch進(jìn)行全文檢索有以下流程：(1)建立索引：ES中的索引相當(dāng)于SQL中的一個(gè)數(shù)據(jù)庫(kù)，通過(guò)建立索引名字來(lái)進(jìn)行后續(xù)文檔的搜索、更新及刪除等操作。不同于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)，ES能夠?qū)?shù)據(jù)存儲(chǔ)于一個(gè)或多個(gè)索引中進(jìn)行分布式索引。分布式索引通過(guò)將一個(gè)索引進(jìn)行分片，也就是說(shuō)將一個(gè)索引通過(guò)分片又重新分成一個(gè)個(gè)獨(dú)立的索引。在海量數(shù)據(jù)下，ES正是因?yàn)閷?duì)索引進(jìn)行分片來(lái)分?jǐn)傆布毫?，從而達(dá)到能夠進(jìn)行實(shí)時(shí)快速搜索。在創(chuàng)建索引時(shí)，用戶可指定其分片的數(shù)量，默認(rèn)數(shù)量為5個(gè)。(2)建立映射：在存儲(chǔ)文本之前需要建立映射，ES中使用Mapping來(lái)對(duì)存儲(chǔ)文本進(jìn)行分析。使用者可根據(jù)需要在Mapping中申明字段的數(shù)據(jù)類型、是否建立倒排索引、建立倒排索引時(shí)使用什么分詞器。默認(rèn)情況下，ES會(huì)為所有的string類型數(shù)據(jù)使用standard分詞器來(lái)建立倒排索引。這個(gè)類似于MySQL在db schema。(3)文本存儲(chǔ)：ES是面向文檔型數(shù)據(jù)庫(kù)，一條數(shù)據(jù)在這里就是一個(gè)文檔，用JSON作為文檔序列化的格式。一個(gè)文檔中包含_index、_type、_id、_source等核心元數(shù)據(jù)，其中_index說(shuō)明一個(gè)document屬于哪個(gè)index，這里的index為文本集合建立的索引，索引相當(dāng)于一個(gè)數(shù)據(jù)庫(kù)；_type說(shuō)明document屬于index中的哪個(gè)類別，也就是數(shù)據(jù)庫(kù)中的表；_id代表document的唯一標(biāo)識(shí)，與index和type一起，可以唯一標(biāo)識(shí)和定位一個(gè)document ；_source代表了document中具體包含的內(nèi)容，例如標(biāo)題、關(guān)鍵詞、文本內(nèi)容等信息，也就是數(shù)據(jù)庫(kù)中的字段。一個(gè) ES 集群可以包含多個(gè)索引，也就是說(shuō)索引中包含了很多類型。這些類型中包含了很多的文檔，然后每個(gè)文檔中又包含了很多的字段。(4)文本查詢：ES的查詢語(yǔ)法(query DSL)分為兩部分：query和filter，區(qū)別在于查詢的結(jié)果是要完全匹配還是相關(guān)性匹配。filter查詢考慮的是“文檔中的字段值是否等于給定值”，答案在“是”與“否”中；而query查詢考慮的是“文檔中的字段值與給定值的匹配程度如何”，會(huì)計(jì)算出每份文檔與給定值的相關(guān)性分?jǐn)?shù)，用這個(gè)分?jǐn)?shù)對(duì)匹配了的文檔進(jìn)行相關(guān)性排序。

2.2 余弦相似度

余弦相似度，也稱為余弦距離，是用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小的度量。它是文本相似度計(jì)算比較經(jīng)典和常用的算法之一。如果余弦值越接近1，就表明夾角越接近0度，也就是兩個(gè)向量越相似，這就叫“余弦相似性”。該算法的基本思路是：如果兩個(gè)文本的用詞越相似，它們的內(nèi)容就應(yīng)該越相似。因此，一般通過(guò)詞頻來(lái)計(jì)算它們之間的相似程度。余弦距離計(jì)算相似度主要采用以下步驟：第一步，對(duì)文本進(jìn)行分詞以及去停用詞。對(duì)于短文本，可以直接對(duì)文本進(jìn)行分詞；而對(duì)長(zhǎng)文本來(lái)說(shuō)，則需要進(jìn)行文本關(guān)鍵詞提取；第二步，計(jì)算詞頻。列出文本中所有詞語(yǔ)，如果文本中有該詞語(yǔ)就加1，沒(méi)有出現(xiàn)則為0；第三步，通過(guò)第二步計(jì)算出的詞頻可以生成文本的詞頻向量；第四步，計(jì)算向量之間的余弦距離，值越大就說(shuō)明兩個(gè)文本越相似。文本的向量為多維向量，設(shè)向量A=(A1，A2，，An)，B=(B1，B2，，Bn)，則余弦距離公式如公式1所示：

(1)

2.3 TF-IDF

TF-IDF(term frequency-inverse document frequency)是一種用于資訊檢索與資訊探勘的常用加權(quán)技術(shù)[14]。TF-IDF是一種統(tǒng)計(jì)方法，用以評(píng)估一個(gè)詞在一個(gè)文檔集中的某一份文檔的重要程度。TF-IDF主要思想是：如果某個(gè)詞或短語(yǔ)在一篇文章中出現(xiàn)的頻率TF高，并且在其他文章中很少出現(xiàn)，則認(rèn)為此詞或短語(yǔ)在該文章中占有重要位置，而且更能代表該文章的主題。TF-IDF實(shí)際上是：TF * IDF，其中，TF詞頻(Term Frequency)，IDF反文檔頻率(Inverse Document Frequency)。如果一個(gè)詞的TF-IDF的權(quán)重越大說(shuō)明這個(gè)詞匯有很好的辨別能力。某一特定文件內(nèi)的高詞語(yǔ)頻率，以及該詞語(yǔ)在整個(gè)文件集合中的低詞語(yǔ)頻率，可以產(chǎn)生出高權(quán)重的TF-IDF。因此，通過(guò)TF-IDF來(lái)提取文本的關(guān)鍵詞。TF-IDF計(jì)算公式如公式2所示：

(2)

3 分布式海量文本快速相似度檢測(cè)技術(shù)研究改進(jìn)

本文所研究的海量文本快速相似度檢測(cè)主要是使用分布式搜索引擎框架Elasticsearch來(lái)篩選出候選樣本集，然后使用余弦距離來(lái)進(jìn)行最終的相似度比較，最后選出相似度最大的值為所需樣本。分布式搜索框架通過(guò)輸入關(guān)鍵詞來(lái)進(jìn)行文本搜索，搜索出來(lái)的文本都是包含關(guān)鍵詞的文本，所以可以通過(guò)搜索引擎在海量文本下盡可能多的過(guò)濾到無(wú)關(guān)文檔，召回相關(guān)文檔，從而來(lái)加快比較速度。分布式搜索框架只能做到關(guān)鍵詞或者關(guān)鍵句的搜索，也就是說(shuō)只能做到篩選出文本含有搜索關(guān)鍵詞或者句子的文本。如果句子有所改動(dòng)就無(wú)法搜索出來(lái)，所以篩選之后的候選樣本集需要采用精確的相似度算法進(jìn)行更加精確的比對(duì)，最后選出最為相似的文本。

分布式海量文本快速相似度檢測(cè)技術(shù)研究流程如圖2所示，具體步驟如下：

1.首先將海量文本集合存入ES分布式搜索引擎中，并設(shè)置中文分詞器。這樣做主要是可以進(jìn)行詞語(yǔ)對(duì)的搜索，例如，搜索“科學(xué)”，如果設(shè)置分詞器就會(huì)查詢到包含“科學(xué)”的詞的文本，而不會(huì)搜到只包含“科”或“學(xué)”的文本，從而能夠找到更加相關(guān)的文本；

2.通過(guò)特征提取算法TF-IDF來(lái)進(jìn)行文本關(guān)鍵詞的提取，提取的關(guān)鍵詞作為ES搜索引擎的查詢條件。每篇文本選取TF-IDF值高的前20個(gè)關(guān)鍵詞來(lái)表示文本主題意思；

3.將提取的文本關(guān)鍵詞作為ES的查詢條件來(lái)篩選出文本候選樣本。本文從每篇文本提取TF-IDF高的前20個(gè)關(guān)鍵詞中并選取前10個(gè)關(guān)鍵詞作為可以ES的查詢條件，并通過(guò)最少匹配來(lái)選取候選文本；

4.經(jīng)過(guò)召回一定數(shù)量的文本作為候選樣本進(jìn)行余弦相似度計(jì)算。例如全文比對(duì)召回前150個(gè)文本，句子比對(duì)的話召回前200。那么，對(duì)候選文本集合進(jìn)行余弦距離的比較，最后選取文本相似度最大作為相似文本輸出。

圖2 分布式海量文本快速相似度檢測(cè)技術(shù)研究流程框圖

4 實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)數(shù)據(jù)及工具

本實(shí)驗(yàn)選用了THUCNews作為實(shí)驗(yàn)數(shù)據(jù)，總共有836075萬(wàn)條新聞數(shù)據(jù)，數(shù)據(jù)主要分為財(cái)經(jīng)、科技、體育、社會(huì)、教育等十四類新聞。THUCNews是根據(jù)新浪新聞RSS訂閱頻道2005-2011年間的歷史數(shù)據(jù)篩選過(guò)濾生成，均為UTF-8純文本格式。在新聞中同一類型的新聞數(shù)據(jù)之間的特征詞很相似，這也為實(shí)驗(yàn)增加難度。

文本預(yù)處理過(guò)程中，去停用詞表采用的是哈工大的停用詞表；使用jieba分詞來(lái)進(jìn)行文本分詞處理。jieba分詞支持最大概率法(Maximum Probability)，隱式馬爾科夫模型(Hidden Markov Model)，索引模型(QuerySegment)，混合模型(MixSegment)，共四種分詞模式，同時(shí)有詞性標(biāo)注，關(guān)鍵詞提取，支持自定義字典等功能。

實(shí)驗(yàn)運(yùn)行環(huán)境是在CPU為Intel(R)Core(TM)i7- 4790 @3.60GHz，內(nèi)存16GB，操作系統(tǒng)為windows7 64bit，采用Python語(yǔ)言實(shí)現(xiàn)算法，并在Anaconda3自帶的Spyder編譯器上運(yùn)行，分布式搜索引擎選用Elasticsearch 2.3.4版本，IK為搜索引擎的分詞器。

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)分為2個(gè)實(shí)驗(yàn)，其中實(shí)驗(yàn)1主要是通過(guò)文本之間的相似度比較；實(shí)驗(yàn)2是句子與文本之間的相似度比較。為了更加符合實(shí)際環(huán)境，我們從80多萬(wàn)篇文本中隨機(jī)選取500篇新聞文本，并對(duì)其進(jìn)行25%左右的隨機(jī)修改。對(duì)文本的修改主要是對(duì)文本進(jìn)行開(kāi)頭、結(jié)尾、中間的不同程度的刪除、增加和修改，從而更加符合現(xiàn)實(shí)中大多數(shù)相似文本并不是完全相似，都有一下雜質(zhì)的干擾存在。這兩個(gè)實(shí)驗(yàn)主要是通過(guò)修改后的文本和句子，能夠通過(guò)快速精確的找到未修改前的文本以及包含該句子的文本。

實(shí)驗(yàn)1中，主要是修改后的500個(gè)文本在80多萬(wàn)的文本集合中找到對(duì)應(yīng)的文本，從而驗(yàn)證該算法的性能。該實(shí)驗(yàn)通過(guò)Simhash算法、Simhash算法結(jié)合余弦距離以及ES搜索引擎結(jié)合余弦距離的方法進(jìn)行召回率、準(zhǔn)確率以及時(shí)間復(fù)雜度的比較。在ES結(jié)合余弦距離的算法中，輸入10個(gè)關(guān)鍵詞，且最少匹配6個(gè)；然后通過(guò)ES召回前150個(gè)文本，最后用余弦距離與召回的文本進(jìn)行相似度比較，選出最大相似度文本。實(shí)驗(yàn)1結(jié)果如圖3所示：

圖3 修改文本相似度比較

實(shí)驗(yàn)2中，從文本集合中通過(guò)句子符號(hào)進(jìn)行文本分割，并且在眾多句子集合中隨機(jī)選取68個(gè)句子，并對(duì)句子進(jìn)行一定程度的修改。在對(duì)文本按句子分割時(shí)，會(huì)為每個(gè)句子配上對(duì)應(yīng)的id號(hào)，從而能更好的驗(yàn)證。該實(shí)驗(yàn)的目的主要是通過(guò)修改后的句子來(lái)找到句子所在的文本。該實(shí)驗(yàn)通過(guò)Simhash算法、Simhash算法結(jié)合余弦距離、余弦距離、最長(zhǎng)公共子序列以及ES結(jié)合余弦距離來(lái)進(jìn)行準(zhǔn)確率和時(shí)間復(fù)雜度的比較。在ES結(jié)合余弦距離的算法中，輸入10個(gè)關(guān)鍵詞，且最少匹配6個(gè)，且ES召回前200個(gè)文本。對(duì)召回文本進(jìn)行分句，然后用余弦距離進(jìn)行句子之間的比較，最后選出相似度最大的句子所在文本為最后結(jié)果。實(shí)驗(yàn)2結(jié)果如圖4所示：

圖4 修改句子相似度比較

通過(guò)實(shí)驗(yàn)可知：實(shí)驗(yàn)1中該實(shí)驗(yàn)將Simhash的漢明距離設(shè)為10、16、25，通過(guò)實(shí)驗(yàn)比較發(fā)現(xiàn)閾值為16的準(zhǔn)確率以及召回率最為合適。ES結(jié)合余弦距離方法的召回率和準(zhǔn)確率為100%，運(yùn)行時(shí)間為77.45s；而閾值為16的Simhash算法結(jié)合余弦距離的方法召回率為98.4%，準(zhǔn)確率為96.7%，運(yùn)行時(shí)間為574.38s。對(duì)于修改文本來(lái)說(shuō)，本文方法在準(zhǔn)確率和召回率有很大的提升，而且時(shí)間上也滿足海量文本快速檢測(cè)的要求。在實(shí)驗(yàn)2中，該實(shí)驗(yàn)通過(guò)比較發(fā)現(xiàn)，LCS和余弦距離的方法運(yùn)行時(shí)間太長(zhǎng)，不適合海量文本；只用Simhash算法進(jìn)行相似度雖然比較，時(shí)間上縮短，但是準(zhǔn)確率只有72.06%；Simhash結(jié)合余弦距離與ES結(jié)合余弦距離的方法比較適合海量文本環(huán)境下，其中，兩者在準(zhǔn)確率上都為100%，但是，前者的運(yùn)行時(shí)間是后者的7.4倍，所以分布式搜索引擎結(jié)合余弦距離的方法更加適合海量文本。

5 結(jié)束語(yǔ)

為了滿足海量文本環(huán)境下快速且準(zhǔn)確的找到所需文本，本文提出了基于分布式架構(gòu)的海量文本快速相似度檢測(cè)技術(shù)。本文主要是通過(guò)常用海量文本相似度算法Simhash與分布式搜索引擎ES進(jìn)行比較發(fā)現(xiàn)，分布式搜索引擎在準(zhǔn)確率、召回率以及時(shí)間復(fù)雜度上都更加適合作為海量文本初步篩選算法。該方法比simhash算法能夠更有效的縮小比較范圍來(lái)提高查找速率。對(duì)于分布式搜索引擎來(lái)說(shuō)，準(zhǔn)確率以及召回率的高低取決于查找的關(guān)鍵詞的精確性，所以為了完善本文提出的算法，接下來(lái)需要更加精確的關(guān)鍵詞提取算法來(lái)提取更能代表文本意思的詞語(yǔ)，從而縮小候選文本集來(lái)進(jìn)一步加快比較速度。