短文本合并重复（去重）的简单有效做法
2012/6/12
不大合适的SimHash
前些日子看了Charikar SimHash的介绍《Simhash算法原理和网页查重应用》，核心思想是用一个f位的hash值来表示文件的特征值，然后使用hash值之间的Hamming距离来衡量相似性。输入的是一个文档的特征集合，输出的是f位的二进制数S。
于是用来测试短文本（长度在8个中文字符～45个中文字符之间）相似性，做法很简单：
1.将短文本做分词，得到分词数组，数组每一个元素都转为hash字符串。
2.利用simhash算法来计算分词数组的simhash值。
3.利用simhash的similarity算法计算simhash1和simhash2的相似度。
这种做法的缺点是：
1.误判率高。
如下图所示，
SimHash可能不适合做这种短标题的重复度判断，虽然SimHash在空间消耗和计算复杂性方面相对Shingle和BloomFilter占优。
介绍一下2009年2月份我们做Twitter锐推榜时是如何做的
Twitter中对于热门事件的中文表达多种多样，转发时又往往会追加很多格式的各种内容，造成了相似内容的短文本的信息指纹不同，在这种情况下，段国成认为需要先为短文本抽取标签，再通过标签来计算相似度进行锐推合并。
1.短文本抽取标签的方法：
1.1. 剔除所有英文、数字、标点字符；
1.2. 剔除所有Twitter用户名；
1.3.分词，并标注词性，仅保留实体词性，如名词、动词；（技巧一！）
1.4.过滤掉常用实体词（常用实体词是通过对历史锐推训练而得，即建立自己的停止词表）；（技巧二！）
1.5.计算保留实体词的词频，并以此为权重，选择权重大的词语作为标签；
1.6.标签数组长度大于一个阈值（如3），才认为是有信息量的锐推，否则忽略。（技巧三！）
2.合并相似短文本（即我们所说的Retweet）方法：
2.1.以每个标签作为Shingle特征（即核心思想还是“一个数据段分成若干Shingle，每个Shingle计算出一个hash值，然后组成一个以hash值为元素的数组，以此作为特征值或叫信息指纹来表示这个数据段”）；
2.2.以网页去重领域中改进的Shingle方法来进行计算近期内（目的：缩小计算范围）锐推的相似度（Shingle算法的核心思想是将文本相似性问题转换为集合的相似性问题，改进的Shingle方法的时间复杂度近似于线性）；
2.3.对相似程度大于一定阈值的、不同信息指纹的热门锐推，再次扫描出来，将它们的热度进行合并。
以上结果就构成了 @rtmeme 的运算机制。它特别适合处理十几个、几十个汉字的短文本合并重复，适用于微博领域。
也看到有人这么做：先Shingle再SimHash，不知道是否适合海量短文本合并重复，回头试试看。
@郑昀 于北京
推荐阅读：
1、
『我认为腾讯目前的O2O产品其实是没任何借鉴意义的，因为真的做得比较差。但我们也有一点做好的决心。……所以尽管我们在局部解决了闭环的问题，但实际上整个O2O的闭环仍然是遥遥无期的事情。』——《戴志康：让我焦躁并痛苦着的O2O》http://t.cn/zOFL5Cc
2、
#O2O是个伪概念#：知乎O2O系列问答：http://t.cn/SzuEjr ；清科投资集团对O2O的解读：http://t.cn/zOgcikN ；黄绍麟：O2O和无线电子商务是伪概念 http://t.cn/zOfodfZ
3、
推荐阅读：『而Google的#simhash#算法产生的签名，可以用来比较原始内容的相似度时，便很想了解这种神奇的算法的原理。出人意料，这个算法并不深奥，其思想是非常清澈美妙的。』——《Simhash算法原理和网页查重应用》http://t.cn/zOrhqUb
4、
旧文推荐阅读：『我的团长我的团中，学生李梁对龙文章说，我相信你们能战胜日本人，但问题仍然存在。李鸿章们不遗余力地修铁路、办实业，但问题依然存在。 器物上的改变是不会解决问题的。』http://t.cn/zOlg0Kg
赠图一枚：
