徐凱，沙瀛，李陽，單既喜，王曉巖

1.江西農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院，南昌 330045

2.中國科學(xué)院信息工程研究所，北京 100093

3.中國科學(xué)院計(jì)算技術(shù)研究所，北京 100190

Twitter中重復(fù)消息的分析和處理

徐凱1，2，沙瀛2，李陽3，單既喜2，王曉巖2

1.江西農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院，南昌 330045

2.中國科學(xué)院信息工程研究所，北京 100093

3.中國科學(xué)院計(jì)算技術(shù)研究所，北京 100190

Twitter已經(jīng)成為微博中的代表性應(yīng)用，但是通過分析發(fā)現(xiàn)twitter上的消息（推文）有很多完全一致或相似，這對(duì)后續(xù)對(duì)推文的分析和存儲(chǔ)都帶來很大的問題。為了處理這些內(nèi)容完全一致或相似的消息（推文），針對(duì)推文特有的短文本的特點(diǎn)，基于規(guī)則處理完全一致的推文，采用simhash的方法來處理相似性的推文。實(shí)驗(yàn)采用實(shí)際抓取的240萬條推文數(shù)據(jù)進(jìn)行分析和處理，分別對(duì)中文和英文的推文重復(fù)情況進(jìn)行了分析，實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)重復(fù)的推文占總推文的10%左右。

推特；微博；Simhash；短文本去重

1 概述

在WEB 2.0的時(shí)代里，用戶之間的交互變得非常廣泛，任何時(shí)間，任何地點(diǎn)的用戶之間都可以進(jìn)行通信。微博把WEB 2.0時(shí)代推向了一個(gè)更加快捷，更加開放的時(shí)代；微博的傳播速度非常快，用戶之間可以互相關(guān)注，微博的信息非常短，每條微博的信息不允許超過140個(gè)字。

Twitter[1]（http：//www.twitter.com）是微博中最具有代表性的平臺(tái)之一。一條消息的發(fā)布，在twitter里面被稱為一條推文，在twitter上，用戶不僅可以發(fā)布推文，用戶之間還可以互相關(guān)注，如果你被別人關(guān)注了，那么這些關(guān)注你的人就叫做你的跟隨者，如果你發(fā)布一條推文，那么你的跟隨者可以在他們自己的twitter主頁面看到你的推文，并對(duì)他們感興趣的推文進(jìn)行回復(fù)；反之，如果你關(guān)注了別人，那么他們發(fā)布的推文你同樣可以在自己的twitter主頁面看到，你同樣可以對(duì)自己感興趣的推文進(jìn)行回復(fù)。

Twitter中用戶除了可以對(duì)自己感興趣的推文進(jìn)行回復(fù)，還可以對(duì)該推文進(jìn)行轉(zhuǎn)發(fā)[2]，也就是說一條相同的推文被其他感興趣的用戶重新發(fā)布一次；這個(gè)過程好比一棵樹的數(shù)據(jù)結(jié)構(gòu)，從根節(jié)點(diǎn)一直向后發(fā)展，最終推文所描述的事情變成了熱點(diǎn)，有的時(shí)候一條推文可以在幾分鐘內(nèi)被轉(zhuǎn)發(fā)幾百萬次。

如此多的轉(zhuǎn)發(fā)可以讓一件事迅速變成熱點(diǎn)；但造成了大量重復(fù)的消息，不僅給系統(tǒng)帶來了沉重的負(fù)擔(dān)，而且給推文的閱讀者帶來了一定的麻煩，浪費(fèi)了大量時(shí)間。

為此，本文提出一種方法來處理這些大量重復(fù)相似的推文，twitter中重復(fù)相似的推文一般有兩種形式，一種是官方的轉(zhuǎn)發(fā)方式，另一種是非官方的轉(zhuǎn)發(fā)方式。

官方轉(zhuǎn)發(fā)方式的推文可以快速轉(zhuǎn)發(fā)別人的推文，但是不允許用戶修改推文的內(nèi)容。

非官方的轉(zhuǎn)發(fā)方式是用戶自己定義了一些好用的，被大多數(shù)人認(rèn)可的轉(zhuǎn)發(fā)格式，通過使用這些轉(zhuǎn)發(fā)格式，轉(zhuǎn)發(fā)者可以復(fù)制感興趣的別人的推文，經(jīng)過一些小小的修改然后發(fā)布出去，正是因?yàn)檫@些小小的修改，使得這些推文和原始作者的推文產(chǎn)生了不同，但其實(shí)這些推文所表達(dá)的意思都是一樣的。

實(shí)驗(yàn)過程如下：

（1）分析數(shù)據(jù)，總結(jié)出官方和非官方的轉(zhuǎn)發(fā)格式。

（2）建立官方格式的正則表達(dá)式，提取出官方格式轉(zhuǎn)發(fā)的推文，通過字符串比較的方法得出相同的推文。

（3）建立非官方格式的正則表達(dá)式，對(duì)推文進(jìn)行預(yù)處理，然后通過基于simhash[3-5]的方法來得出每條推文的指紋，比較這些指紋的海明距離來得出推文的相似性。

本文對(duì)抓取的240萬條推文數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，本文中僅對(duì)中文和英文的推文進(jìn)行實(shí)驗(yàn)，經(jīng)過實(shí)驗(yàn)處理，其中中文的推文46萬條，英文的推文170萬條。發(fā)現(xiàn)重復(fù)相似的推文占總推文的10%左右。

2 基本概念及相關(guān)工作

判斷推文是否相同的最簡單的辦法是，對(duì)推文進(jìn)行兩兩比較，對(duì)兩條推文每個(gè)字符進(jìn)行逐個(gè)比較，如果全部的字符都相同的話那么這兩條推文就是相同的，但是這個(gè)辦法只能判斷完全相同的推文；正如前面所說的，twitter中很多的用戶使用的并不是官方的轉(zhuǎn)發(fā)功能，這導(dǎo)致被轉(zhuǎn)發(fā)的推文可能是用戶經(jīng)過復(fù)制和修改后的推文，這種推文和原創(chuàng)推文相似，但是不相同。

需要判斷文本相似的算法，判斷文本相似的算法有很多，如，Bloom Filter[6]去重算法，shingling去重算法[7-8]，曹鵬等[9]在他們的論文中介紹了通過統(tǒng)計(jì)字符類型算法和最短編輯距離算法[10]相結(jié)合的方法來解決文本之間的相似性，首先通過統(tǒng)計(jì)字符類型算法，把每條消息轉(zhuǎn)換成一個(gè)向量，然后通過余弦定律[11]計(jì)算兩個(gè)向量之間的距離，得出消息（推文）之間的距離，為了確保結(jié)果的精確性，提出再計(jì)算一次消息的最短編輯距離，最后把兩個(gè)算法得到的距離相加，得到兩個(gè)消息（推文）的距離，設(shè)置一個(gè)閥值，如果最終距離小于這個(gè)閥值，那么消息（推文）相似。

文本相似度比較還有一種方法，即Simhash，Simhash是google專門為它的搜索引擎發(fā)明的文本相似度計(jì)算方法，google每天需要抓取處理的文檔是上百億的，這些新抓取的文檔中很多都是和以前存儲(chǔ)在數(shù)據(jù)庫中的相同或者相似的，為了準(zhǔn)確高效地對(duì)重復(fù)的文檔進(jìn)行去重操作，這就是Simhash。

Simhash的主要思想是：降低文本向量的維度，將高維度的文本向量的維度降低到一個(gè)m（本文中m取64）位的一個(gè)整數(shù)中，這個(gè)整數(shù)稱為指紋，每個(gè)指紋代表一個(gè)文檔，最后計(jì)算兩個(gè)文檔的相似度就是計(jì)算它們對(duì)應(yīng)的指紋相似度，指紋之間的差異位個(gè)數(shù)稱為海明距離。

Simhash的好處在于它高效的處理速度，由于Simhash對(duì)哈希函數(shù)的要求比較高（哈希函數(shù)的碰撞率越低，Simhash的準(zhǔn)確度越高），本文中引入google的哈希函數(shù)cityhash（http：//code.google.com/p/cityhash/），該哈希函數(shù)能快速生成一個(gè)64位的簽名。

3 推文去重

3.1 Twitter消息的官方轉(zhuǎn)發(fā)格式

如表1所示為twitter官方推文的轉(zhuǎn)發(fā)格式，Retweeted by表示轉(zhuǎn)發(fā)符號(hào)，編號(hào)1中，Retweeted by jasongod之前的是推文的內(nèi)容，jasongod表示轉(zhuǎn)發(fā)這條推文人的名字，一般Retweeted by跟隨在推文的末尾，如果還有其他人轉(zhuǎn)發(fā)了這條推文，如編號(hào)2中的推文，該推文首先被用戶renyuan619轉(zhuǎn)發(fā)，然后又被用戶cwxm37轉(zhuǎn)發(fā)，被轉(zhuǎn)發(fā)了2次。

表1 官方轉(zhuǎn)發(fā)格式

3.2 Twitter消息的非官方轉(zhuǎn)發(fā)格式

Twitter中除了有官方的轉(zhuǎn)發(fā)格式還有非官方的轉(zhuǎn)發(fā)格式，這些非官方轉(zhuǎn)發(fā)格式被大多數(shù)用戶所認(rèn)可，經(jīng)過研究分析發(fā)現(xiàn)以下這些常用的非官方推文轉(zhuǎn)發(fā)符號(hào)，如表2所示。

3.3 twitter中推文的預(yù)處理

原始的推文中包含很多額外的特殊符號(hào)，這些特殊符號(hào)有些表示轉(zhuǎn)發(fā)某人的推文，有些表示回復(fù)某人的推文，或者自己發(fā)的推文。例如表3中的推文，這些推文沒有經(jīng)過預(yù)處理。

表2 非官方轉(zhuǎn)發(fā)格式

表3 未經(jīng)預(yù)處理的推文

編號(hào)1的推文中有轉(zhuǎn)發(fā)符號(hào)RT@zhangweiguo：，RT@uponsnow和Retweeted by lyfwww需要去掉。

編號(hào)2推文中的特殊符號(hào)@williamlong有可能是自己發(fā)送的推文，也有可能是回復(fù)別人的話，無論是哪種，需要把它去掉。

這些特殊符號(hào)，可以通過構(gòu)建不同的正則表達(dá)式把它們?nèi)サ?，如?里面的正則表達(dá)式，去掉后推文如表5所示，算法如下：

（1）構(gòu)造指定以上這些轉(zhuǎn)發(fā)符號(hào)格式的字符串正則表達(dá)式，為了提高準(zhǔn)確率，把@用戶名這種正則表達(dá)式所表示的字符串也考慮進(jìn)去。

（2）按照表1中編號(hào)1中表格格式對(duì)應(yīng)的正則表達(dá)式的順序循環(huán)匹配推文，如果匹配成功那么刪除推文中匹配好的正則表達(dá)式對(duì)應(yīng)的字符串，保存推文，匹配下一個(gè)正則表達(dá)式，直到匹配完表格中最后一個(gè)正則表達(dá)式為止。

（3）下一條推文繼續(xù)表1中編號(hào)2中的處理過程，直到所有的推文處理完成。

表4 轉(zhuǎn)發(fā)格式的正則表達(dá)式

3.4 消息去重的方法

在設(shè)計(jì)simhash算法過程中，simhash需要文檔的特征集合，特征集合包括能代表該文檔意思的詞組集合和集合中每個(gè)詞的權(quán)重，為了得到詞組集合，使用中科院的分詞系統(tǒng)ictclass（http：//ictclass.org/），考慮到推文的短文本特點(diǎn)，把分詞后的所有詞都作為特征詞，并對(duì)詞組進(jìn)行去重操作，給每個(gè)詞分配權(quán)重1，例如如下兩條推文：

表5 預(yù)處理后的推文

推文1：毛主席偉大、偉大，偉大。

推文2：毛主席偉大。

假設(shè)為推文1中的毛主席分配1的權(quán)重，偉大分配3的權(quán)重，那么毛主席在推文1中權(quán)重比率是1/4；推文2中的權(quán)重比率是1/2，這樣就造成simhash后的兩個(gè)推文的指紋偏差較大，但實(shí)際上推文1和推文2表達(dá)的意思是一樣的，綜上考慮把推文中每個(gè)詞的權(quán)重設(shè)置為1。

由于推文通常較短，每個(gè)詞都表示了重要的信息，且彼此之間沒有較明顯的差異性，因此選擇每個(gè)詞的權(quán)重為1，即每個(gè)詞的貢獻(xiàn)都是一樣的。

之后使用cityhash函數(shù)分別計(jì)算每個(gè)詞的簽名（64位的無符號(hào)整數(shù)），cityhash由google提出是一種非加密性質(zhì)的哈希算法，主要面向生成唯一的指紋，該算法源自于murmurhash（https：//sites.google.com/site/murmurhash/）算法的改進(jìn)，64位的cityhash算法不但減少了碰撞率，而且在64位的CPU上進(jìn)行了優(yōu)化，在字符串的移位操作過程中，綜合了字符串的長度因素，函數(shù)接口格式如下所示：

uint64 CityHash64（const char*buf，size_t len）；

接收2個(gè)參數(shù)，第一個(gè)參數(shù)表示需要計(jì)算指紋的字符串內(nèi)容，第二個(gè)參數(shù)表示該字符串的長度，函數(shù)接口返回值是64位的無符號(hào)整數(shù)簽名。

得到每個(gè)推文的指紋之后，就可以進(jìn)行求海明距離，海明距離[12]定義是：兩個(gè)長度相等字符串的海明距離是在相同位置上不同字符的個(gè)數(shù)，也就是將一個(gè)字符串替換成另一個(gè)字符串需要的替換的次數(shù)。在這里把64位整數(shù)的指紋的二進(jìn)制形式來表示這個(gè)字符串。假設(shè)指紋是64位的整數(shù)，那么兩個(gè)64位整數(shù)之間的海明距離就是不同的二進(jìn)制位的個(gè)數(shù)。

不同位的個(gè)數(shù)越多，認(rèn)為兩個(gè)推文之間越不相似，實(shí)驗(yàn)中設(shè)置海明距離為3，這個(gè)閥值來區(qū)分相似的推文和不相似的推文，當(dāng)計(jì)算出來的指紋海明距離大于3認(rèn)為這兩條推文是不相似的，當(dāng)計(jì)算出來的指紋海明距離小于等于3，認(rèn)為推文之間是相似的。

選擇3的原因：實(shí)驗(yàn)中針對(duì)234個(gè)simhash指紋，分別設(shè)置閥值為1到10，對(duì)于每個(gè)閥值，從234個(gè)指紋中隨機(jī)取樣選取一定對(duì)數(shù)的相似的推文，然后進(jìn)行人工標(biāo)示，如果這兩條推文真的相似，那么標(biāo)記1，如果不相似，那么標(biāo)記0，這樣就統(tǒng)計(jì)出閥值從1到10這個(gè)區(qū)間中，真正相似推文的比率，結(jié)果發(fā)現(xiàn)當(dāng)閥值在3的時(shí)候推文的相似性正確率是最大的。

表6 兩條推文

例如：表6中兩條推文經(jīng)過處理后相似。

Simhash去重如圖1所示。

圖1 simhash去重

4 去重及其分析和實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)中使用2012/7/1到2012/8/1日這一個(gè)月采集的大概240萬條的推文，推文的內(nèi)容主要涉及政治和軍事，實(shí)驗(yàn)中中文推文占總推文比率的19%，英文推文占總推文比率的53%，其他語言的推文占總推文比率的28%，可見英文推文的比率是最大的。下面就這些推文展示實(shí)驗(yàn)結(jié)果。

4.1 統(tǒng)計(jì)推文語言分布

分析各種語言在推文中的比例。實(shí)驗(yàn)中過濾推文，只保留英文和中文的推文。英文推文占總推文的比率是最大的。

4.2 推文長度分布統(tǒng)計(jì)

分別統(tǒng)計(jì)英文推文和中文推文的長度分布。

圖2是英文推文長度分布圖和中文推文長度分布圖，從圖中可以看出推文長度在140的推文的個(gè)數(shù)是最多的。

圖2 中文/英文推文長度分布圖（未經(jīng)過預(yù)處理）

4.3 預(yù)處理后推文長度的分布

分別統(tǒng)計(jì)預(yù)處理前后中英文推文的長度并比較其變化。

經(jīng)過推文預(yù)處理操作后，重新統(tǒng)計(jì)消息的個(gè)數(shù)隨長度的分布，從圖3～5中可以發(fā)現(xiàn)以下幾點(diǎn)：

（1）預(yù)處理后推文長度在0～20區(qū)間的推文數(shù)量有所增加，說明推文長度在0～20區(qū)間的推文很多被轉(zhuǎn)發(fā)過，短推文轉(zhuǎn)發(fā)很多。

（2）推文長度在140個(gè)字符的推文在預(yù)處理后大量減少，說明這些推文中大部分具備轉(zhuǎn)發(fā)格式，長推文也很多被轉(zhuǎn)發(fā)。

圖3 中文/英文推文長度分布圖（預(yù)處理后）

圖4 預(yù)處理前和預(yù)處理后的英文推文長度分布圖

圖5 預(yù)處理前和預(yù)處理后的中文推文長度分布圖

4.4 推文去重

分別統(tǒng)計(jì)中英文推文的去重比率和重復(fù)推文的重復(fù)次數(shù)分布。

經(jīng)過分析統(tǒng)計(jì)英文推文中相似的推文占英文推文總個(gè)數(shù)的9%，中文推文中相似的推文占中文推文總個(gè)數(shù)的7%，可見推文中消息的重復(fù)比率還是很大的。

圖6 英文推文重復(fù)次數(shù)對(duì)數(shù)分布圖

圖7 中文推文重復(fù)次數(shù)分布圖

圖8 英文用戶推文個(gè)數(shù)統(tǒng)計(jì)對(duì)數(shù)分布圖

圖9 中文用戶推文個(gè)數(shù)統(tǒng)計(jì)對(duì)數(shù)分布圖

如圖6和圖7所示，統(tǒng)計(jì)那些重復(fù)推文的重復(fù)次數(shù)，從圖中可以看出，當(dāng)重復(fù)次數(shù)為1的時(shí)候，推文數(shù)量是最多的，隨著重復(fù)次數(shù)的增加，推文的個(gè)數(shù)迅速減少，可見大多數(shù)推文不是熱點(diǎn)推文。

4.5 用戶發(fā)送消息

分別統(tǒng)計(jì)中英文推文的用戶個(gè)數(shù)和推文個(gè)數(shù)的分布。

從圖8和圖9中可以看出，只發(fā)送了一條推文的用戶是最多的，其次集中在發(fā)送20條推文的用戶也是挺多的，之后發(fā)送了100條以上的用戶非常少，可見twitter中活躍的用戶還是集中在少數(shù)用戶中，大部分用戶還是不活躍的。

5 結(jié)論

本文提出針對(duì)twitter平臺(tái)的消息去重方法，不但可以減輕twitter平臺(tái)存儲(chǔ)消息的壓力，而且給分析twitter消息帶來了方便；對(duì)推文的分析分兩種情況，轉(zhuǎn)發(fā)關(guān)系和相似。對(duì)轉(zhuǎn)發(fā)關(guān)系采用預(yù)處理檢測關(guān)鍵字retweeted的方法，對(duì)相似關(guān)系采用預(yù)處理后simhash的方法。通過實(shí)驗(yàn)證明，simhash能有效處理類似于twitter平臺(tái)上的短消息之間的相似度，實(shí)驗(yàn)中對(duì)采集的240萬條推文數(shù)據(jù)進(jìn)行過濾，分析中文和英文的推文，分別對(duì)中文和英文的推文長度分布、推文去重率、用戶發(fā)送的推文個(gè)數(shù)進(jìn)行統(tǒng)計(jì)。

[1]Stone B，Williams E.Chirp：Twitter’s developer conference [EB/OL].[2010-04-14].http：//chirp.twitter.com/.

[2]Boyd D，Golder S，Lotan G.Tweet，tweet，retweet：conversational aspects of retweeting on Twitter[C]//Proceedings of the 43rd Hawaii International Conference on System Sciences，2010：1-10.

[3]Manku G S，Jain A，Sarma A D.Detecting near-duplicates for web crawling[C]//Proceedings of the 16th International World Wide Web Conference，Banff，Alberta，Canada，2007.

[4]Charikar M S.Similarity estimation techniques from rounding algorithms[C]//Proceedings of 34th Annual ACM Symposium on Theory of Computing，2002：380-388.

[5]Jiang Qixia，Sun Maosong.Semi-supervised SimHash for efficient document similarity search[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics，2011：93-101.

[6]徐娜，劉四維，汪翔，等.基于Bloom Filter的網(wǎng)頁去重算法[J].微型電腦應(yīng)用，2011，27（3）：48-51.

[7]Broder A Z，Glassman S C，Manasse M S，et al.Syntactic clustering of the Web[J].Computer Networks and ISDN Systems，1997，29（8/13）：1157-1166.

[8]馬成前，毛許光.網(wǎng)頁查重算法Shingling和Simhash研究[J].計(jì)算機(jī)與數(shù)字工程，2009，37（1）：15-17.

[9]曹鵬，李靜遠(yuǎn)，滿彤，等.Twitter中近似重復(fù)消息的判定方法研究[J].中文信息學(xué)報(bào)，2011，25（1）：20-27.

[10]Konstantinidis S.Computing the edit distance of a regular language[J].Information and Computation，2007，205（9）：1307-1316.

[11]張振亞，王進(jìn)，程紅梅，等.基于余弦相似度的文本空間索引方法研究[J].計(jì)算機(jī)科學(xué)，2005，32（9）：160-163.

[12]李彬，汪天飛，劉才銘，等.基于相對(duì)Hamming距離的Web聚類算法[J].計(jì)算機(jī)應(yīng)用，2011，31（5）：1387-1390.

XU Kai1，2,SHAYing2,LI Yang3,SHAN Jixi2,WANG Xiaoyan2

1.School of Computer and Information Engineering,Jiangxi Agricultural University,Nanchang 330045,China
2.Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China
3.Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China

Twitter has become the representative applications of the micro-blog.By analysis on twitter a lot of messages（tweets）are the same or similar.Those messages bring up a trouble on the analysis and message storage,so it is needed to remove those messages which are the same or similar.According to the characteristics of short text on tweets,this paper proposes the following approach.It processes the same tweets based on the specific format,then uses the simhash to process the similar tweets.It uses 240 million tweets crawled on the Internet to experiment.In the experiment it only processes Chinese and English tweets.The repetition messages（tweets）is 10 percent of all the Chinese and English tweets.

twitter;microblog;Simhash;short text duplicate removal

A

TP391.1

10.3778/j.issn.1002-8331.1212-0115

XU Kai,SHAYing,LI Yang,et al.Twitter repeat messages analysis and processing.Computer Engineering and Applications,2014,50（21）：111-115.

國家自然科學(xué)基金（No.61070184）；中國科學(xué)院戰(zhàn)略性科技先導(dǎo)專項(xiàng)（No.XDA06030200）；國家科技支撐計(jì)劃（No.2012BAH46B03）。

徐凱（1989—），男，研究生，研究方向：社交網(wǎng)絡(luò)數(shù)據(jù)采集和傳播路徑分析；沙瀛（1973—），男，博士，副研究員，研究方向：P2P網(wǎng)絡(luò)，網(wǎng)絡(luò)安全，自然語言處理，輿論分析；單既喜（1989—），男，研究生，研究方向：社交網(wǎng)絡(luò)關(guān)系圖；王曉巖（1989—），女，研究生，研究方向：信息安全，社交網(wǎng)絡(luò)。E-mail：331633025@qq.com

2012-12-10

2013-03-11

1002-8331（2014）21-0111-05