Twitter中近似重复消息的判定方法研究

曹 鹏，李静远，满 彤，刘 悦，程学旗

(1. 中国科学院 计算技术研究所 网络重点实验室，北京 100190;2. 中国科学院 研究生院，北京 100190)

1 概述

随着Web2.0的出现以及迅猛发展，社交类网站的概念渐渐深入人心，随之而产生了“微博客(Microblog)”的概念。微博客是一种非正式的迷你型博客，是最近新兴起的Web2.0的一个表现形式，是一种可以即时发布消息的系统。微博客的最大的特点是消息的集成化和API的开放化。用户可以通过移动设备、IM软件(Gtalk、MSN、QQ、Skype等)和外部API接口等途径发布消息。例如，自2006年以来利用无线通信技术，Twitter用户无需输入手机号码，就可以通过客户端在微博客上发布信息。微博客的另一个特点是其消息相对比较短小，每次最多能够发送140个字符的短文本，因此一般发布的消息只能是只言片语。

Twitter[1]是国外的一个社交网站，也是微博客中比较有代表性的实例之一。目前，Twitter的使用非常火爆，用户数量高居国内外各种微博客系统之首。根据2010年末Twitter官方博客上的权威资料，当前Twitter用户已超过1.6亿，且仍然以每天30万新用户的数量增长；同时，Twitter服务器的月访问请求超过190亿次[2]。

在Twitter中，用户之间可能建立的好友关系称为“追随关系”，即一个用户可以根据兴趣选择自己愿意关注的人而“追随”他；当然，同时他自己也可能被其他一些用户追随。用户可以随时以消息形式发送一些内容，就像发送手机短信一样，所以类似Twitter这样的微博服务又被称为互联网上的短信平台。一个用户发出的信息对他的所有“追随者(Follower)”都是公开的。因此，如果一个用户写了一条消息(称为Tweet)，他的所有追随者都可以看到，并且他们可以回复这个人的消息，而被回复的人同样可以看到别人回复他的消息。于是，用户之间可能针对一个话题展开激烈的讨论，正如我们日常生活的对话一样，消息会越积累越多。一个用户在Twitter中所写的消息，系统会自动地让他的追随者知道，这属于一种“推送”的方式。另外，作为一个Twitter用户,他一般会经常关注自己所追随的人，回复他们所发的消息。因此Twitter为用户之间信息交流提供了一个基础的平台。

Twitter中除了好友关系和消息回复关系以外，还有消息的转发关系。也就是说，同一个内容的消息，可以在好友之间进行转发(Retweet)。正是通过这种方便且简单的转发方式，Twitter可以令一条消息在数分钟内在数百万用户间大范围传播。

然而，在对Twitter的调研过程中我们发现，用户在发送消息的时候，往往会完全复制别人的消息，或者经过少量的修改后(添加、修改、删除部分字符)，作为自己的消息而再次发送出去。于是在Twitter中往往存在大量内容相同或者相似的消息，本文中称其为近似重复信息(Near Duplicate Message)。在单纯考虑消息种类的时候，经过转发的和少量修改的消息会有很大的重复，而内容重复的消息往往是没有意义的。例如，Twitter的用户往往会发现，因为存在大量的重复消息，自己阅读到的消息数量很多，但真正得到的信息量却很有限。比如自2010年5月份以来，Twitter中关于“世博会(World Expo)”的消息相对较多，而真正原创的消息数量却有限，大部分都是用户之间来回转发的消息。大量重复消息的存在对用户的影响往往是灾难性的： 它们白白浪费了用户的时间和精力，降低了用户的使用热情。去掉这种大量重复的消息，不但可以减轻系统存储的负担，而且可以提高用户阅读、理解和分析消息内容的效率，从而提高用户的使用热情。因此，提出一种微博客系统上近似重复信息的高效判定方法是十分重要而有意义的。

本文分析了Twitter系统中消息转发现象。从大量存在的转发消息中提取出一些固定的程式化的词法结构特征，并据此归纳出一定规则。然后，按照这些规则预处理Twitter中的消息，得到和系统无关的“原始消息”文本(真正被转发的消息内容)。在此基础上，提出针对Twitter消息的字符串近似匹配算法，以计算两条消息的距离，从而决定它们是否近似重复。

接下来的章节安排如下： 本文第2节介绍消息去重的相关工作和基本方法；第3节阐述Twitter上消息去重的特殊性以及本文所采用的方法；第4节给出实验结果；第5节展望并讨论Twitter上重复消息的判定方法发展的可能方向；第6节是结论。

2 基本概念和相关工作

消息的本质就是字符串。因此最简单直接的消息重复判定规则是对两条消息进行全文匹配，即如果两条消息完全相同，则认为是重复的。这种方法的特点是实现简单，只需要对字符串排序；但是其缺点也相当明显的： 两条消息内容绝对相同，对文本要求太敏感、鲁棒性差。因为完全相同的两条消息在Twitter系统中几乎是不存在的。一般地，Twitter用户总会在原始消息上添加、删除、修改部分内容，这种简单的方法并不能鉴别出这样的重复消息。所以本文更关心近似重复消息，而不仅仅是完全重复消息。

判定近似重复消息的一般方法是对每个消息进行压缩，压缩的信息称为指纹(Fingerprint)，然后利用指纹比较消息是否相同。指纹方法是一种普遍的方法，它的本质是利用哈希(Hash)进行文本压缩，判断重复性。文献[3]对网络文档(网页)进行查重。作者采取了多指纹的方法，即每个文档有若干个指纹，如果两个文档相同的指纹数达到一个预先给定的阈值，则认为它们是相同的。如果允许误判，还有经典的Bloom-filter[4]方法可以用来进行查重，但它不仅限于消息查重领域。

文献[5]中提出的Simhash给出了在规模上百万的网页中查找重复消息的一个有效方法。Simhash是一种文档指纹算法，它有如下性质： 两个近似文档的指纹(两个整数)只差几个数据位(bit)[6]。这样，相当于把文档映射为整数，文档的相似度对应为整数的接近。这种方法对哈希函数的选择要求比较高。

另外一种消息去重的直接想法是在消息中提取关键词，如果关键词的集合基本相同则认为它们重复。更为深入的方法是提取出文档的摘要，根据语义的信息判断文档的相似度。这种方法在消息聚类领域使用得比较广泛。但是，它的缺点是涉及到的技术比较复杂，例如，自然语言理解、关键词提取、摘要抽取等等，因此实现难度大、复杂度比较高，效率也相对较低。而且这种方法比较适合分析较长的文本，例如普通的文章，因为它们往往具有比较完备的结构、语法和语义信息。但是，Twitter中的消息都是140个字符以内的短文本，文本内容和语法结构通常并不很规范，甚至还可能包括众多用户自定义的符号和标记，因此很难提取适当的关键词，抽取摘要就更加困难。因此，Twitter中的近似重复消息判定也不能采取这种方法。

3 Twitter上近似重复消息的判定方法

3.1 Twitter中转发消息的特点

登录Twitter，用户会发现，有很多消息是非常相似的。这些消息通常可以看作同一内容在好友之间的转发。系统本身在用户转发消息时会给消息加上一些特殊的字符(如@、RT等)，另外，用户回复某条消息时，系统同样会加上固定模式的字符，这些都对转发消息的识别提供了便利条件，为顺利找到“原创消息”提供了帮助。但对于“原创消息”，Twitter系统并不会在消息中加入特殊字符，因此，必须利用字符串本身的特性进行近似重复消息的判定。

Twitter对于用户消息的转发，在消息的语法结构本身并没有十分明确和严格的定义。但是，根据文献[7]，以及对实际采集到的消息的观察，我们发现，Twitter系统中转发的消息通常包含如表1中所述特征(一般“@”符号的后面是用户名)。

表1 Twitter转发消息的特征

这些转发消息特征的位置以及具体样式并不是一成不变的。例如，假设用户名为A的用户发了一条消息，内容为hello，而用户名为B的用户转发了A的消息,按照上述的符号说明，转发的消息可能具有如下格式：

B:RT:@A:hello

B:retweeting @A: hello

B:retweet @A:hello

B:hello(via@A)

B:RT(via @A):hello

B:hello thx@A

B:r@A:hello

事实上，Twitter系统本身并不强制约定用户转发消息的格式，以上格式只是比较常见的。实际的情况千变万化。例如，转发消息可能在“@用户名”后面缺少冒号，消息中可能有大量空白字符，此外，有些用户在转发消息时，甚至会修改消息的内容。这些都给对消息的预处理带来了困难。

3.2 Twitter中消息预处理

对于一个转发消息，我们考虑的对象是被转发的“原始消息”，所以按照3.1节所述规则，需要对消息进行一些预处理，把消息中的转发特征字符串过滤掉。

算法的描述如下： 根据规则，查找@符号的位置，然后提取前后若干个位置的字符，如果可以匹配3.1节中的特征，则删除这些内容。如果有多个@符号，要依次分别处理。但是我们要处理的不仅仅是转发关系，有些消息中包含单独的一个@符号后跟用户名，它并不是转发消息，而是代表针对这个用户发的消息，单独考虑消息内容的时候，这些字符也应删除掉。另外，有的消息中会出现“#”符号，该井号后面紧接的是消息的关键词(或称为话题)，我们认为保留这些内容对消息去重没有影响。总之，经过基于规则的字符串匹配算法，把消息处理成最普通的字符串，这些字符串包含着消息的原始内容。

算法流程：

步骤1 查找第一个没探测到的@符号，如果没有则结束，否则转步骤2。

步骤2 模糊匹配上述的规则，看看@符号前后的部分是否能和规则匹配，这里的匹配允许单词与符号之间出现任意多空白，冒号可有可无。若能匹配规则，转步骤3，否则转步骤1。

步骤3 删除掉匹配规则的部分，消息内容缩短。转步骤1。

这样，我们就获得了“原始消息”。接下来，可以采取一些字符串处理中的经典算法，比较两条消息的相似度。

3.3 Twitter中消息距离的计算

在预处理之后，我们获得的是字符串，计算字符串之间距离，可以用任意经典的方法。本文使用统计字符种类和最短编辑距离两种方法。

3.3.1 统计字符种类

一种常用的给字符串做指纹的方法是统计字符串中每个字符的种类。假设消息的编码方式是Unicode。每个消息的字符对应的是一个16bit的二进制数。由于一般的文本编辑器最小的编辑单位是4个bit。我们把一个16bit的数拆成4组，每组4个bit，则每个组有24=16种；如果再考虑组别的话，每4个bit的可能性有16×4=64种情况。这样

我们可以统计每条消息中这64种情况的出现次数，为每个消息做一个指纹。即使消息不是Unicode编码，我们也可以强行的把消息按Unicode理解，这相当于每64位分为一组。于是，我们可以把所有的消息都按照这种方法解析。

这样对于一个消息M，可以得到向量V=(V1,V2…V64)，其中Vi(1≤i≤64)代表这条消息的二进制表示中第i种情况出现的次数。于是，两个消息的相似度，可以完全转化为两个向量之间的相似度。而向量的相似度通常可以用曼哈顿距离或者余弦距离来计算。

事实上，这种表示方法压缩了字符串，用每个字符出现的次数代替了字符串本身，损失了字符出现的位置信息。因此，对于同一个消息，如果只调换了字符顺序的话，通过这种方式计算出的消息指纹不变。但实际情况中，这种情况往往出现较少。(一个极端的例子是“喜欢”和“欢喜”。)

3.3.2 最短编辑距离

最短编辑距离是一个经典的概念。对一个字符串进行添加一个字符、删除一个字符或修改一个字符定义为进行一次操作。两个字符串的最短编辑距离是指把一个字符串变为另外一个字符串需要的最少操作次数。

求解最小编辑距离是一个可以用动态规划方法解决的经典问题。如果两条消息字符串长度分别为len1,len2, 则计算它们的最短编辑距离的算法复杂度是O(len1×len2)。通常，这样的算法时间复杂度在长文本中是很慢的。但是，针对Twitter系统中消息的长度都小于140个字符这一特性，我们可以使用它来计算消息的距离。

最短编辑距离对字符串的字符顺序比较敏感。因此如果调换了消息中的字符顺序，它们的最短编辑距离差异会比较大。

3.4 Twitter中去除重复消息的方法

由于上节中提到的两种距离计算方法各有利弊，本文采用两种方法叠加来计算消息的距离。假设两个消息字符串之间的曼哈顿距离和最小编辑距离分别为d1和d2。则定义两个消息的距离为D=d1+d2。如果两条消息的距离小于一定的阈值(例如阈值选择5)，则认为消息是近似相同的。

4 Twitter消息采集与去重实验

4.1 数据采集

我们通过约20个Twip API代理，采集了Twitter系统中的将近70 000个用户的约854 629条消息。数据采集的方式是通过浏览Twitter得到一些用户的用户名，利用系统本身提供的API对这些用户、用户的好友、以及好友的好友的消息进行周期性采集。采集时间为2010年4月16日至6月12日。由于上海世界博览会恰好在此期间开幕，我们重点采集了Twitter上与世博会相关的消息，采集时使用的关键词包括“世博”、“expo shanghai”等。

4.2 消息长度分布

在预处理消息之前，得到的消息字符串长度分布如图1所示。

图1 消息长度分布图

可见，由Twitter本身的特征决定了所有的消息都比较短。在120个字符以上的消息数量最多。消息的平均长度只有66.3。对如此短的消息计算最短编辑距离的时间复杂度是可以接受的。

4.3 预处理后的结果

按照3.4节中介绍的方法，对所有消息都进行了预处理。重点看了含有特殊字符(@ rt等)的消息，如图2和图3所示。

由图2、图3可见，消息1是对bestguy说的话，因此需要去掉头部的部分内容；而消息2中的“retweet”一词是消息本身的文本的内容，所以应该保留，不能删掉；消息3结尾的“via”符合预先给出的模式，需要删掉。消息4是既有“RT@”又有“thx@”的情况，同时与两个模式匹配，所以都需要去掉；消息5是“RT”在尾部，而且有两个“@”符号，需要同时处理，另外，消息头部的“thx”属于消息本身的文本内容，不应该删掉；消息6是头部不止有一个“RT@”的情况。可见，我们设计的基于模式规则的消息预处理算法可以正确处理Twitter消息。

4.4 消息去重显示

我们选取了与“世博”相关的消息一共27 599条。找到了一些重复的消息，图4和图5是我们的算法找到的一些近似重复的消息。从图4可以看出，由于用户的转发行为，造成了重复的消息。图5则显示了系统中非用户转发行为产生的另外一类重复消息。明显地，这是一个稍微有一些字符不同的广告。

图2 预处理前的部分消息

图3 预处理后的消息

图4 近似重复的消息-1

图5 近似重复的消息-2

实验表明，对随机抽取的1 000条相关的消息进行去重后，剩余894条，重复消息的比例高达10.6%。抽取比较大规模的“世博”相关的部分27 559条相关的消息进行去重后，剩余16 778条，近似重复消息达到10 781条，占总数的39.1%。对我们采集到的全部“世博”相关消息41 722条执行去重操作，去重后剩余26 427条，重复率占41.2%。可见对消息去重将能够节约很大存储空间。

4.5 消息的重复程度

我们对于“世博”相关的41 722条消息。去重后，一共剩余26 427条。这些条消息平均每条出现1.6次。图6统计了这些消息重复数的分布。从图中我们可以看到，有21 084条消息只出现了一次，占到去重后消息数量的79.8%，而重复数超过10次以上的转发消息只占全部去重后消息的2%。这说明重复或近似重复消息的分布是不均匀的。造成这一现象的原因一方面在于： 对于内容好、质量高的消息，Twitter用户拥有较高的转发热情；另一方面，由于Twitter第三方应用倾向于不遵守Twitter官方的转发协议，导致大量无法被官方数据服务器认定为转发消息、但实际是转发消息的情况出现。

图6 近似重复消息出现次数累积CDF图

4.6 预处理和去重对消息长度分布的影响

在对消息预处理前消息长度的分布如图7所示。“世博”相关消息和全部消息有的分布是一致的。图7和图1有着相似的统计特征，仍然是长消息数比较多，而消息的平均长度比较短。

图7 消息长度—消息数分布图(预处理前)

图8 消息长度—消息数分布图(预处理后)

接着我们对这些消息按照前述规则进行处理，去掉不必要的字符，得到“原始”的消息字符。图8类似于把图7向左平移的结果，因为预处理后，消息长度确实会变短。在其中有三个情况值得关注：

1) 图8较图7陡峭，这说明不遵从官方转发方法的消息，其转发格式自由度很大，这印证了表1中对消息转发多样性的观察结论；

2) 图7中消息长度在130～140字的消息集合在消息去重后操作后，在图8中形态变化不大，只是消息总数略有下降，这说明130字以上的长消息较少存在多次嵌套转发的情况；

3) 有相当一部分用户是属于“空消息”转发的情况，也就是该用户发送的消息的全部内容几乎全满足前述的预处理匹配规则，这样在预处理后，其发送的真正有价值的消息长度为0。

图9为对消息预处理、且合并重复消息后，消息长度与数目的分布关系。预处理和去重后剩余26 427条消息。 具体地，对于近似相同的消息，我们取其平均长度作为消息的长度。这样经过去重后，消息的平均长度为105.2,仍然是120个字符以上的消息数量最多。这说明120个字符以上是同一话题中消息的普遍长度。Twitter对于消息长度的限制，使得除部分“懒用户”(他们发送的消息普遍较短)以外，Twitter用户希望在一条消息中表达尽可能多的内容， 这是消息即使去重后仍然在120个字符以后出现聚集的重要原因之一。

图9 消息长度分布图(去重后)

4.7 发送消息的用户行为分析

在对消息进行去重前，与关键词“世博”相关的全部41 722条消息中，而它们只涉及到10 614个不同的用户，平均每个用户发送的消息数为3.9条。用户发送消息数量的分布如图10所示，可见大部分用户发送的消息并不多。有4 358的用户只发了一条消息。

图10 消息数—用户数分布

在所有41 722条消息中，用户登录Twitter的方式共有49种。这其中包括Web登录、API登录以及其他各种不同的客户端等，如表2、3所示。我们可以将用户访问Twitter的方式分为Web方式和API方式两大类，其中： Web方式指通过浏览器访问Twitter官方网站，通过官方页面使用Twitter功能；其他方式指通过官方提供的API接口，或通过其他第三方客户端、服务器等间接使用官方API接口的方法。经统计我们发现，约1/3的消息来自于用户直接访问Twitter官方网页，另2/3的消息来自于第三方。

表2 用户登录方式统计

表3 用户登录方式统计(消息重复次数不少于4)

重复次数不少于4次的消息中，3大类访问方式分别占总数的39.43%,14.47%和46.10%，这与不考虑消息重复时访问方式的比例基本一致。而较明显的不同点在于，重复4次以上的消息的长度要大约10个字，这说明长消息更倾向于被复制和转发。所以消息的处理和去重操作对减少数据存储设备负担上效果比想象中更明显一些，这有助于提高系统的效率，更便于分析用户的行为特征。

5 更多应用

基于“发消息相似的用户往往具有相似的爱好和兴趣”这样的信念，我们可以利用这个假设检查用户之间在Twitter中言论的聚集性。事实上，在社会网络普遍地存在社区结构已经成为公认的事实。当然，在重点考察用户言论作的时候，如果通过Twitter中消息的相似性作为“虚拟连边”，而代替用户之间的好友和追随实际关系(Follower, Friend)，显然，这样建立的网络是和我们直观想象上建立的社交网络所不同的。如果把消息的相似度作为边的强度的体现(也就是通常所谓的权值)，这样建立的网络是有权的。另外，把Twitter系统用户之间消息的转发和回复关系作为用户的连边，这样建立的网络又是有向的，对这样建立的网络进行分析，可能得到言论、兴趣和爱好更为相近的用户。

另外，通过对用户转发消息长度真正长度的分析，可以发现所谓发送“垃圾”的用户。

而通过用户访问Twitter方式的分析，可以了解各种客户端的特性，帮助我们有针对性地更好地分析和处理Twitter中的消息。

6 结论

本文提出了一套针对Twitter的近似重复消息判定方法。由于Twitter消息的特殊性，分析其中短小的、结构随意的消息时并不适合采取通用的自然语言处理方法。本文提出了基于字符串的方法，该方法包括两部分：

1) 预处理部分： 根据统计规律产生的规则把消息处理成普通的字符串；

2) 计算距离部分： 采用曼哈顿距离和最短编辑距离的叠加计算两个字符间的距离。

本方法不用进行自然语言理解的复杂计算，具有效率高、效果好、可扩展性强的特点。

在未来的工作中，考虑在预处理部分的规则库中添加新规则。另外，计算距离的方法可以尝试采取其他的距离定义(例如cosine距离等)，计算距离的加权方法也可以进行其他尝试。本文提到的计算消息距离的方法对消息聚类也有帮助。今后，在大规模消息聚类中，还可以考虑采取分布式的方法(例如，分布式K-means聚类)，提高聚类的效率。

[1] Twitter official website [EB/OL]. 2010. URL: http://www.twitter.com/.

[2] B. Stone, E. Williams. Chirp: Twitter’s developer conference [EB/OL]. April 14-15, 2010. URL: http://chirp.twitter.com/.

[3] C. Lyon, R. Barrett, J. Malcolm. A theoretical basis to the automated detection of copying between texts, and its practical implementation in the Ferret plagiarism and collusion detector [C]//Plagiarism, Prevention, Practice and Policies Conference. June, 2004.

[4] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors [J]. Communications of the ACM, 1970, 13(7): 422 426.

[5] M. Charikar. Similarity estimation techniques from rounding algorithms [C]//Proceedings of the 34th Annual Symposium on Theory of Computing, Montr al, Qu b, Canada. May, 2002.

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

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