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

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

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

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

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

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

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

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

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

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

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

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

1 概述

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

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

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

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

為此，本文提出一種方法來處理這些大量重復(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ā)布出去，正是因為這些小小的修改，使得這些推文和原始作者的推文產(chǎn)生了不同，但其實這些推文所表達的意思都是一樣的。

實驗過程如下：

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

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

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

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

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

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

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

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

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

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

3 推文去重

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

如表1所示為twitter官方推文的轉(zhuǎn)發(fā)格式，Retweeted by表示轉(zhuǎn)發(fā)符號，編號1中，Retweeted by jasongod之前的是推文的內(nèi)容，jasongod表示轉(zhuǎn)發(fā)這條推文人的名字，一般Retweeted by跟隨在推文的末尾，如果還有其他人轉(zhuǎn)發(fā)了這條推文，如編號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ā)符號，如表2所示。

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

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

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

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

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

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

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

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

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

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

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

3.4 消息去重的方法

在設(shè)計simhash算法過程中，simhash需要文檔的特征集合，特征集合包括能代表該文檔意思的詞組集合和集合中每個詞的權(quán)重，為了得到詞組集合，使用中科院的分詞系統(tǒng)ictclass（http：//ictclass.org/），考慮到推文的短文本特點，把分詞后的所有詞都作為特征詞，并對詞組進行去重操作，給每個詞分配權(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后的兩個推文的指紋偏差較大，但實際上推文1和推文2表達的意思是一樣的，綜上考慮把推文中每個詞的權(quán)重設(shè)置為1。

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

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

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

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

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

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

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

表6 兩條推文

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

Simhash去重如圖1所示。

圖1 simhash去重

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 推文去重

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

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

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

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

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

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

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

4.5 用戶發(fā)送消息

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

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

5 結(jié)論

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

[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].計算機與數(shù)字工程，2009，37（1）：15-17.

[9]曹鵬，李靜遠，滿彤，等.Twitter中近似重復(fù)消息的判定方法研究[J].中文信息學(xué)報，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].計算機科學(xué)，2005，32（9）：160-163.

[12]李彬，汪天飛，劉才銘，等.基于相對Hamming距離的Web聚類算法[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)專項（No.XDA06030200）；國家科技支撐計劃（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