simhash 性能测试
随便找了 4 篇同一主题的新闻：
| 序号 | 标题 | 备注 |
|---|---|---|
| 0 | 习近平在全国组织部长会议上的讲话 | 2011 年 |
| 1 | 习近平出席全国组织工作会议并发表重要讲话 | 2018 年 |
| 2 | 习近平出席全国组织工作会议并讲话 | 2018 年 |
| 3 | 习近平：切实贯彻落实新时代党的组织路线 全党努力把党建设得更加坚强有力 | 2018 年 |
注：文档 0 是 2011 年的新闻，而文档 1、2、3 都是 2018 年同一通稿的不同转载。
我们可以用「最长公共子串」（LCS）所占比例来估计两篇文档的相似程度：
min{lcs.size / document_1.size, lcs.size / document_2.size}
如果我们分别以「子句」（即以标点符号为切分）「单个汉字」和「词」（做分词处理）为单位计算 simhash ：
| 比较文档 | LCS 占比 | simhash 值距离（子句） | simhash 值距离（字） | simhash 值距离（词） |
|---|---|---|---|---|
| 0 v.s. 1 | 0.0966 | 32 | 8 | 8 |
| 0 v.s. 2 | 0.0966 | 32 | 8 | 7 |
| 0 v.s. 3 | 0.0991 | 32 | 8 | 7 |
| 1 v.s. 2 | 0.9756 | 6 | 0 | 1 |
| 1 v.s. 3 | 0.9552 | 6 | 0 | 1 |
| 2 v.s. 3 | 0.9612 | 2 | 0 | 0 |
可见，更小的粒度（单个汉字）并没有换回更显著的差异。可能是因为以小粒度计算 simhash 时，相同的维度会大幅增加，从而拉低了敏感性。
这也是 simhash 算法的一个缺陷：它并不是映射为一个 0 到 1 之间的「相似概率」，在判定是比较不好把握。虽然好像原论文是希望做成一个这样的概率映射。
下面我们对以上两种指标做敏感性分析。我们在同一样本中分别删去 1、2、4、8、16、32、64 个汉字，然后计算其指标：
| 比较文档 | LCS 占比 | simhash 值距离 |
|---|---|---|
| 0 v.s. 1 | 0.9874581939799331 | 2 |
| 0 v.s. 2 | 0.9871794871794872 | 2 |
| 0 v.s. 4 | 0.9866220735785953 | 3 |
| 0 v.s. 8 | 0.9855072463768116 | 3 |
| 0 v.s. 16 | 0.9832775919732442 | 3 |
| 0 v.s. 32 | 0.9788182831661093 | 1 |
| 0 v.s. 64 | 0.9698996655518395 | 3 |
| 1 v.s. 2 | 0.987454697518818 | 0 |
| 1 v.s. 4 | 0.9868971285196543 | 1 |
| 1 v.s. 8 | 0.985781990521327 | 1 |
| 1 v.s. 16 | 0.9835517145246724 | 1 |
| 1 v.s. 32 | 0.9790911625313633 | 3 |
| 1 v.s. 64 | 0.9701700585447449 | 3 |
| 2 v.s. 4 | 0.9871723368655884 | 1 |
| 2 v.s. 8 | 0.9860568878973787 | 1 |
| 2 v.s. 16 | 0.9838259899609593 | 1 |
| 2 v.s. 32 | 0.9793641940881205 | 3 |
| 2 v.s. 64 | 0.9704406023424428 | 3 |
| 4 v.s. 8 | 0.9866071428571429 | 2 |
| 4 v.s. 16 | 0.984375 | 2 |
| 4 v.s. 32 | 0.9799107142857143 | 4 |
| 4 v.s. 64 | 0.9709821428571429 | 4 |
| 8 v.s. 16 | 0.9854748603351955 | 0 |
| 8 v.s. 32 | 0.9810055865921787 | 2 |
| 8 v.s. 64 | 0.9720670391061452 | 4 |
| 16 v.s. 32 | 0.9832026875699889 | 2 |
| 16 v.s. 64 | 0.9742441209406495 | 4 |
| 32 v.s. 64 | 0.9786276715410573 | 4 |
可见 simhash 对微小差异并不敏感
注：以上是手工删除的结果，删除的是多处连续的小段文字。
下面我们试试随机删除的效果：
| 比较文档 | LCS 占比 | simhash 值距离 |
|---|---|---|
| 0 v.s. 1 | 0.9874581939799331 | 3 |
| 0 v.s. 2 | 0.9871794871794872 | 2 |
| 0 v.s. 4 | 0.9866220735785953 | 3 |
| 0 v.s. 8 | 0.9855072463768116 | 5 |
| 0 v.s. 16 | 0.9832775919732442 | 8 |
| 0 v.s. 32 | 0.9788182831661093 | 9 |
| 0 v.s. 64 | 0.9701783723522854 | 7 |
| 0 v.s. 128 | 0.9531772575250836 | 18 |
| 0 v.s. 256 | 0.9186176142697882 | 21 |
| 0 v.s. 512 | 0.85479375696767 | 33 |
随机删除测试
注：样本文档为 3550 字。
重复测试：
测试 1
测试 2
测试 3
测试 4
测试 5
由上测试可以得到以下经验法则：
- 32 字以下差距的 simhash 距离大概率在 10 以下；
- 512 字以上差距的 simhash 距离大概率在 20 以上；
- 512 字以上差距的 simhash 值区分不明显；
大规模随机测试（从样本文档（3588 字）中随机删除任意个字符，而后计算其与原文档的 simhash 距离）：
横轴是「删除的字符数」，纵轴是「simhash 距离」（为避免作图点重合，y 值都做了漂移）
由上图可以观察到如下经验规律：
- 100 字以内差距（差异小于 3%）的 simhash 距离大概率在 10 以内；
- 600 字以上差距的 simhash 距离与差异量几乎没有相关关系。我们可以计算「 simhash 距离」与「 LCS 占比」的相关系数，为 -0.53；
- 当 simhash 距离大于 20 ，可视为不相似；
如果我们把差异量控制在小范围内，再计算其相关系数，得到如下曲线：
图为：差异在 x 以内的样本的相关系数。x-轴单位为百
可以看到：当我们把差异量控制在 400 字以内（差异小于 11%）时，能得到 80% 以上的相关度。
但实际中，并不会随机删除，而是连续的小段文字删减。下面我们测试一下，以「子句」为单位作少量（20 句以内）、随机删除的效果：
横轴是「删除的字符数」，纵轴是「simhash 距离」（为避免作图点重合，y 值都做了漂移）
我不想说啥了，和「 LCS 占比」的相关系数为 -0.62 。
然后我还不甘心，想着算 simhash 时是以标点符号为分隔切分的。如果用上分词算法会不会好一点呢？接着试了下以「词」为单位的效果：
以「词」为单位的效果，还不如以「子句」为单位。和「 LCS 占比」的相关系数为 -0.34
心塞，这次真的不想说啥了。
实际情况也不会全是块删除，而是点删除与块删除的混合。可以想见，效果应该介于上述两种情况之间。
但反过来看，这个算法对判定相似文本是相当成功的（删掉快 300 个字依旧能保证距离在 4 以内）。好吧，simhash 本来就是为相似文本而生的，你却硬要她去做 MD5 的事情。
以下是垃圾代码，存个档。
require "diff/lcs"
require "simhash"
require 'rmmseg'
class String
RMMSeg::Dictionary.load_dictionaries
def strip_heredoc
self.gsub(/[\t\n\p{Z}]/, '')
end
def random_delete(n)
ary = self.split(/\p{P}/)
n.times do
ary.delete_at(rand(ary.size))
end
ary.delete('')
ary.join("。")
end
def segments()
algor = RMMSeg::Algorithm.new(self)
seg = []
loop do
tok = algor.next_token
break if tok.nil?
seg << tok.text.force_encoding('utf-8')
end
seg
end
end
def lcs_index(seq1, seq2)
return 0 if seq1.empty? or seq2.empty?
lcs = Diff::LCS.LCS(seq1.strip_heredoc, seq2.strip_heredoc)
[lcs.size.to_f / seq1.size, lcs.size.to_f / seq2.size].min
end
def calc(doc, n)
del_doc = doc.random_delete(n)
sim_0 = Simhash.hash(doc.segments) # .split(/[\n\p{P}]/)
sim_n = Simhash.hash(del_doc.segments)
{
count: doc.size - del_doc.size,
lcs: lcs_index(doc, del_doc),
simhash: sim_0.hamming_distance_to(sim_n)
}
end
data = ""
doc = File.open("./sample.txt", "r").read.force_encoding('utf-8')
1000.times do
h = calc(doc, rand(20))
data += "#{h[:count]}\t#{h[:lcs]}\t#{h[:simhash] + rand / 8}\n"
end
File.open("./random_test.txt", "w") { |f| f << data }
