去除相似度较高的内容

Question

如何去除相似度较高的内容？可以不择手段！

如下面三条笑话几乎是一样的，只是个别符号和换行不换行的差别。假设现在有30万条数据，其中有几万条是这样具有高相似度的，我要怎么做才能把这些数据筛选出来？

可以不择手段，最好是ＰＨＰ/MySQL，客户端之类的。

哥应邀参加前任婚礼，和一帮陌生人坐一桌， 旁边一哥们问我是新娘什么人？ 我回答，我只是来看一下以前战斗过的地方！ 没想到一桌子的人举起酒杯：
大家都是战友，干杯，多喝点，一会讨论战斗经验！

哥应邀参加前任婚礼，和一帮陌生人坐一桌，旁边一哥们问我：“是新娘什么人？” 我回答，我只是来看一下以前战斗过的地方！
没想到一桌子的人举起酒杯：“大家都是战友，干杯，多喝点，一会讨论战斗经验！”

哥应邀参加前任婚礼，和一帮陌生人坐一桌，旁边一哥们问我是新娘什么人？我回答，我只是来看一下以前战斗过的地方！没想到一桌子的人举起酒杯：大家都是战友，干杯，多喝点，一会讨论战斗经验！

Answer 1

只回答相似度处理

与 similar_text() 函数相比，levenshtein() 函数更快，但similar_text() 函数能通过更少的必需修改次数提供更精确的结果，在追求速度而少精确度，并且字符串长度有限时可以考虑使用 levenshtein() 函数，而且 similar_text() 对中文支持的并不好

最后留一个自己捣鼓的： 通过余弦定理+分词计算文本相似度PHP版

https://github.com/xiaobeicn/text-similarity-php

Answer 2

要求不高的话直接用similar_text吧，DEMO: http://3v4l.org/iBXvC

Answer 3

如果只是多出几个标点符号、换行的话，那可以去掉那些符号、换行，然后比较字符串md5的值。当然，如果文字的顺序变大很大，这个也就不行了

Answer 4

说白了就是文章摘要算法 如果是我的话分词肯定不够 还要上词性分析 留下名词动词做特征能更准一些

我给你一个我认为最靠谱的方案
（1）对文章进行词性划分，只保留动词和名词部分，比如
哥应邀参加前任婚礼，和一帮陌生人坐一桌， 旁边一哥们问我是新娘什么人？ 我回答，我只是来看一下以前战斗过的地方！ 没想到一桌子的人举起酒杯：
大家都是战友，干杯，多喝点，一会讨论战斗经验！

这段文字我认为特征是 婚礼 新娘 战斗 就被 经验 战友
（2）你需要很多的例子，比如10000篇，根据这一万篇，大致推断整个30万文本中所有可能重要的词汇，根据经验这个个词汇表如果不处理会超过10w个
（3）使用特征提取算法精简词汇表，至于怎么特征提取这至少是烟酒生课程才会讲的，都是数学，这样你会把10w个词缩减到3000左右
（4）用这3000个词表示每一个文本，比如w1=[0,0,1,1,.....0,..1,,0...1..0...]我们不考虑词频，这样的数据结构用位图非常容易转化为字符串
（5）使用Hash表对所有文本进行去重
这样的效率是最高的，但是肯定有误差，因为特征提取本身就是信息量减少的过程，来换取最快的速度，但是可以做到任何一个新文本来，分词的过程不计，几乎是O(1)的时间复杂度

Answer 5

再提供一种思路：去掉所有标点符号、空格以及换行符之后用动态规划算法计算“编辑距离/Levenshtein距离”（即把字符串s1经过变换得到s2的最少编辑次数，其中一次编辑可以是添加一个字符、删除一个字符或者修改一个字符）。比较容易实现，效率也不错（大约就是O(N^2)其中N是字符串长度）

这个算法貌似是信息学竞赛的经典算法，搜一下“字符串编辑距离”应该就能找到（维基百科也有），如果不想用库的话可以考虑该方法

Answer 6

我想说的也是编辑距离，楼上已经说了。

Answer 7

http://www.cnblogs.com/liangxiaxu/archive/2012/05/05/2484972.html

Answer 8

余弦定理和simhash都不错，后者是谷歌发明的