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 }