一種高效的文本信息查重算法

一種高效的文本信息查重算法

0適當(dāng)刪除重復(fù)信息隨著電子商務(wù)的發(fā)展，網(wǎng)絡(luò)中充滿了越來越多的信息。考慮到自己的利益，許多公司經(jīng)常使用各種手段發(fā)布大量重復(fù)信息（或類似信息）。這些重復(fù)發(fā)布的信息會(huì)造成各商家在網(wǎng)絡(luò)廣告方面投入與產(chǎn)出的不公平。為此,我們需要通過各種途徑準(zhǔn)確高效地查找、歸類這些信息并予以適當(dāng)處理。目前在各個(gè)商業(yè)化的電子商務(wù)網(wǎng)站中,大多數(shù)信息的發(fā)布是需要人工審核的。通常,審核員需要通過一定的記憶,把重復(fù)信息找到,然后予以刪除。這種傳統(tǒng)的方法存在兩個(gè)缺陷:其一,每天成千上萬的數(shù)據(jù),通過大量的勞動(dòng)密集型投入,致使審核成本劇增;其二,通過這種方法也不能有效地刪除重復(fù)信息。如果我們能找到一種合理的算法把類似的信息歸并在一起排序,將會(huì)極大地提高信息審核員的勞動(dòng)效率和降低審核成本。但是,大規(guī)模的文本相似比較,是相當(dāng)耗時(shí)的,在實(shí)時(shí)環(huán)境下,甚至是根本無法忍受的。如果每千條信息比較需要花費(fèi)一分鐘的時(shí)間,這就違背我們的意圖了。尤其是在一個(gè)基于Web的應(yīng)用,這樣的性能將會(huì)把WebServer拖跨。我們需要尋求一個(gè)效率更高的算法,以解決重復(fù)信息(或相似信息)的歸類排序問題。1有條件進(jìn)入實(shí)驗(yàn)對(duì)象把“選取”打造成“個(gè)人成本”文本信息的相似性常常用俄國(guó)科學(xué)家VladimirLevenshtein在1965年提出的Levenshtein距離來衡量。根據(jù)Levenshtein距離可以計(jì)算將一個(gè)短語轉(zhuǎn)化成另一個(gè)短語時(shí)所需執(zhí)行的插入、刪除和置換的次數(shù)。比如,要將“good”變成“goods”,只需要輸入一個(gè)字符(“s”),因此它們之間的距離是“1”。四個(gè)字母中取一個(gè)就是25%(距離通常相對(duì)于短語來計(jì)算),采用這種方法的CAT工具用75%來表示這兩個(gè)詞之間的相似性。該算法主要應(yīng)用于DNA分析、拼字檢查、語音辨識(shí)和抄襲偵測(cè)等。該算法比較適合英語之類的拉丁語系而不適合中文。另外,該算法的性能也有問題。筆者測(cè)試過,選擇了1000條常規(guī)的商業(yè)信息,第一條和其他999條信息比較,發(fā)現(xiàn)需要將近1秒的時(shí)間。如果要做相互比較,基本是行不通了。盡管Levenshtein有一些改進(jìn)的算法,但是從性能上來說,在最糟糕的情況下仍然表現(xiàn)出一樣的算法復(fù)雜度。2算法的時(shí)間復(fù)雜度假如兩個(gè)具有足夠長(zhǎng)度的字符串s1,s2是相似的,那么s1的部分內(nèi)容必定出現(xiàn)在s2中。即:..s1≌s2,則{s1(0)|s1(1)|s1(2)|s1(3)…|s1(n)}∈s2,其中s1(0)、s1(1)、s1(2)、s1(3)、…、s1(n)是s1的子串。假設(shè)1由于我們只需把相似的信息歸類在一起供人工審核,故不必考慮兩個(gè)字符串是否完成相同的問題,當(dāng)s1中有k(k<<n)個(gè)子串存在于s2中,即可認(rèn)為該兩字符串是相似的,可以在排序上把他們歸并在一起?，F(xiàn)在分析該算法的時(shí)間復(fù)雜度,定義問題如下:有N{N1,N2…Nn}條中文文本信息,所有文本的平均長(zhǎng)度m,通過相互比較,把類似的文本信息分組排列成一組。如果被判定是重復(fù)的信息,不再參與接下去的相互比較。例如,當(dāng)N1和N2…Nn比較,得到2條與其相似信息(N2,N3),那么接下去的比較應(yīng)該是N4與N5…Nn。以此類推,直到所有的比較結(jié)束?？梢愿话愕孛枥L這個(gè)比較行為:初始條件:參與比較的文本信息集合為N={N1,N2,…,Nn},比較結(jié)果集合為P。1)N1與{N2,N3…Nn}比較得到與N1相似的文本信息加入比較結(jié)果集合P;2)N=N-P,返回步驟1,直到N=Φ由于不同的文本信息集合所比較的結(jié)果P是不固定的,可能是P=N,也可能是P=Φ。在此,僅討論最壞的情況下的算法時(shí)間復(fù)雜度問題,即N{N1,N2,…,Nn}沒有任何的一條信息是重復(fù)的。則:1)模式串長(zhǎng)度(即字符串的切分長(zhǎng)度)為L(zhǎng),則si與sj比較的時(shí)間復(fù)雜度為0((m+L)k),其中k為sj中參與比較的子串個(gè)數(shù);2)n條文本信息相互比較的次數(shù)為n-1,n-2,…,1,比較的總次數(shù)為n(n-1)/2。整個(gè)算法的時(shí)間復(fù)雜度為O(kn(m+L)(n-1)/2)。其中,關(guān)于字符串模式匹配的算法,可以采用KMP字符串模式匹配算法,該算法的時(shí)間復(fù)雜度約為O(m+L),m和L分別是存儲(chǔ)文本和模式串?dāng)?shù)組的最大索引。3模型生成和算法根據(jù)以上理論模型,在生產(chǎn)實(shí)際中,我們要解決以下問題:1)如何切分被比較的字符串,即L的長(zhǎng)度怎么確定;2)如何確定假設(shè)1中的k值。經(jīng)過多次測(cè)試,發(fā)現(xiàn)當(dāng)L=14、k=10時(shí),既能滿足較高的性能要求,又能保證較高的正確率(可達(dá)到90%以上)。具體做法如下:初始條件:參與比較的文本信息集合為N={N1,N2,…,Nn},比較結(jié)果集合為P。1)把整個(gè)電子商務(wù)的Web網(wǎng)頁(yè)過濾掉所有HTML標(biāo)記和ASCII碼符號(hào),得到一個(gè)比較干凈的不影響內(nèi)容含義的文本信息集;2)當(dāng)Nj與Ni比較時(shí)(j≠i且1≤j≤n),Ni作為待比較的字符串,把Nj劃成10個(gè)模式串(Nj1,Nj2,Nj3,Nj4,Nj5,Nj6,Nj7,Nj8,Nj9,Nj10),如果文本長(zhǎng)度大于14,則截去多余部分,采用KMP算法進(jìn)行比較;3)將與Ni相似的文本信息加入比較結(jié)果集合P;4)N=N-P,返回步驟2,直到N=Φ4編碼與實(shí)現(xiàn)下面給出該算法的基于java語言實(shí)現(xiàn)的代碼:5基于lenshte算法的查重算法該算法是針對(duì)某電子商務(wù)網(wǎng)站而研究的。測(cè)試表明,信息數(shù)量在100-1000條時(shí),該算法十分有效,1000條的文本信息相互比較可控制在2秒之內(nèi)。信息數(shù)量超過1000條后,計(jì)算時(shí)間會(huì)大幅度上升,當(dāng)達(dá)到2000條時(shí),計(jì)算時(shí)間約為1分鐘;同時(shí)信息數(shù)量若小于100條,亦不能體現(xiàn)出該算法的優(yōu)勢(shì)。對(duì)于精度而言,可以通過調(diào)整sampleLength,samplingCount,minMatches來達(dá)到目的。但該算法對(duì)于過短信息(少于1