使用simhash计算文本相似度

梦里梦外; 2023-07-02 11:23 20阅读 0赞

[1. 使用simhash计算文本相似度][1. _simhash]  
[2. 使用余弦相似度计算文本相似度][2.]  
[3. 使用编辑距离计算文本相似度][3.]  
[4. jaccard系数计算文本相似度][4. jaccard]

--------------------

文本相似度计算常用于网页去重以及NLP里文本分析等场景。文本相似度，可以分为两种，一种是**字面相似度**，另一种是**语义相似度**。本文记录的是文本的字面相似度的计算及实现，语义相似度计算则需要海量数据去计算语义值，较为复杂。

最常用的且最简单的两种文本相似检测方法：**局部敏感hash、余弦相似度**

### 1.局部敏感hash(LSH) ###

使用一种hash算法，对你于相似的文本得到近似的hash值。LSH的实现方式有多种，常用的就是simhash。

计算出simhash值后，再计算hash值的汉明距离，即可得到文本的相似性。

**汉明距离：**

> 定义：两个长度相同的字符串对应位字符不同的个数

两个关键点：

*  长度相同
 *  对应位字符不同

这里的长度相同并不是指输入的字符串长度相同，而是指经过计算后得到的hash字符的长度（一般固定为64位）。

#### 1.1 使用汉明距离计算文本相似性步骤 ####

主要的6个步骤为：**分词、hash、加权、合并、降维、计算汉明距离**，前5个步骤本质上是simhash算法的流程，思路很简单易懂。

*  **分词**  
    分词工具有很多，例如Ansj、JieBa、HanLP等等，本文使用的 是HanLP。  
    为了减小无关词的影响（降噪），可以将标点等过滤掉，并移除停用词，只留下有意义的词语。
 *  **hash（64位）**  
    使用`MurmurHash3.hash64(byte[] data)`来得到词语的hash值。需要注意的是它返回的是Long类型，如果转换为二进制表示后不足64位，需要在补齐64位（高位补0）
 *  **加权**  
    **词频**是衡量一个词语在句子中的常用方法之一，除此之外还有TF-IDF、词语的情感色彩值等等，本文使用词频作为词语的权重。
 *  **合并**  
    对每个词语计算到的加权后的hash值按位求和
 *  **降维**  
    对求和后的数据进行降维，即对于每一位，大于0的位变为1，小于0的位变为0，得到一个二进制数（或者字符串），即为最终的simhash值。
 *  **计算汉明距离**  
    对以上步骤得到的两个simhash值计算其汉明距离，即统计两个64位的二进制数中对应位不同的个数（异或后1的个数），最终得到汉明距离。**一般根据经验值，汉明距离小于等于3的即可认为相似**。

汉明距离为一个整数，似乎不能很直观的反应两个文本的相似度（0 ~ 1），所以这里通过实验的方法找了条类似正态分布的函数来将汉明距离转化为一个0~1之间的数来表示相似度，更直观一些，方程如下：

y = 1 2 π ⋅ 0.16 e ( − ( 0.01 x − 0.01 ) 2 2 ⋅ 0.045 9 2 ) y=\\frac\{1\}\{\\sqrt\{2\\pi\\cdot0.16\}\}e^\{\\left(-\\frac\{\\left(0.01x-0.01\\right)^\{2\}\}\{2\\cdot0.0459^\{2\}\}\\right)\} y=2π⋅0.161e(−2⋅0.04592(0.01x−0.01)2)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d4Z3hncA_size_16_color_FFFFFF_t_70_pic_center]

#### 1.2 使用汉明距离计算文本相似性举例 ####

待比较文本：

s1：今天天气不错！
    	s2：今天天气真好！

*  **分词**  
    分词时过滤掉标点符号。
    
        [今天, 天气, 不错]
        
          [今天, 天气, 真好]
 *  **hash（64位）**
    
    “今天天气不错！”分词后hash结果：
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">word</th> 
       <th>hash</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">天气</td> 
       <td>1000011110110011101100010101001101011111101101011101001110101010</td> 
      </tr> 
      <tr> 
       <td align="center">今天</td> 
       <td>0001111100111100111101110100100001010001011111001000100100110011</td> 
      </tr> 
      <tr> 
       <td align="center">不错</td> 
       <td>0010000001000111010010010000010101101111000111010101101011010111</td> 
      </tr> 
     </tbody> 
    </table>
    
    “今天天气真好！”分词后hash结果：
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">word</th> 
       <th>hash</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">今天</td> 
       <td>0001111100111100111101110100100001010001011111001000100100110011</td> 
      </tr> 
      <tr> 
       <td align="center">天气</td> 
       <td>1000011110110011101100010101001101011111101101011101001110101010</td> 
      </tr> 
      <tr> 
       <td align="center">真好</td> 
       <td>1111000111100001100011010011001111011110100000000011110011101011</td> 
      </tr> 
     </tbody> 
    </table>
 *  **加权**
    
    “今天天气不错！”hash加权结果：
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">word</th> 
       <th>hash</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">天气</td> 
       <td>1000011110110011101100010101001101011111101101011101001110101010</td> 
      </tr> 
      <tr> 
       <td align="center">今天</td> 
       <td>0001111100111100111101110100100001010001011111001000100100110011</td> 
      </tr> 
      <tr> 
       <td align="center">不错</td> 
       <td>0010000001000111010010010000010101101111000111010101101011010111</td> 
      </tr> 
     </tbody> 
    </table>
    
    “今天天气真好！”hash加权结果：
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">word</th> 
       <th>hash</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">今天</td> 
       <td>0001111100111100111101110100100001010001011111001000100100110011</td> 
      </tr> 
      <tr> 
       <td align="center">天气</td> 
       <td>1000011110110011101100010101001101011111101101011101001110101010</td> 
      </tr> 
      <tr> 
       <td align="center">真好</td> 
       <td>1111000111100001100011010011001111011110100000000011110011101011</td> 
      </tr> 
     </tbody> 
    </table>
    
    权重都为1，所以没变化。
 *  **合并**
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">sentence</th> 
       <th>hash</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">今天天气不错</td> 
       <td>-1-3-1-1-1111-1-111-11111111-1-1-13-31-3-1-1-1-11-33-111113-1-11313-3111-311-3111-111-1-131</td> 
      </tr> 
      <tr> 
       <td align="center">今天天气真好</td> 
       <td>1-1-11-11131-131-1-1-113-111-11-13-31-11-1-311-13-3311111-111-11-3-11-1-111-1-111-13-11-331</td> 
      </tr> 
     </tbody> 
    </table>
 *  **降维**
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">sentence</th> 
       <th>hash</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">今天天气不错</td> 
       <td>0000011100110111111100010100000101011111001111011101101110110011</td> 
      </tr> 
      <tr> 
       <td align="center">今天天气真好</td> 
       <td>1001011110110001101101010101001101011111101101001001100110101011</td> 
      </tr> 
     </tbody> 
    </table>
 *  **计算汉明距离**

计算以上两个二禁止字符串中对应位不同的位数：

0000011100110111111100010100000101011111001111011101101110110011

1001011110110001101101010101001101011111101101001001100110101011

共有16处不同，所以汉明距离为16，转化为相似度位0.004799039154476354。可以看出不是很准确。

#### 1.3 汉明距离计算相似性存在的问题 ####

通过上边的举例也可以看出，两个相似的句子：

s1：今天天气不错！
    	s2：今天天气真好！

得出的汉明距离居然有16，相似度仅仅位0.004。

造成这种问题的原因是：利用局部hash+汉明距离计算相似度时，只适用于长文本，对短文本的判别效果不是很好。

现在输入两个较长的文本进行测试：

以下两个样本摘自一段豆瓣对《爱情公寓5》的影评，其中样本一和二是相似的，样本三和一、二是不相似的。

样本一(s1)：

> 太喜欢短评里的一句话了，如果你带着偏见去看，那你永远都不会满意。  
> 本来影评是没有这段的，但看了一些影评后还是决定再写一下，为什么看了半集或者看了几分钟就来打一星，最可怕的是我看到一个短评说打两星以上都是傻逼，不想多说什么，跟没有教养的人没有讨论的价值。热评里有一篇文章写为什么要喜欢爱情公寓，而不去喜欢其他的喜剧，他列举了很多国内优秀喜剧，并且狠狠的讽刺谩骂了爱情公寓，我告诉你为什么。我出生于00年，一个标准的零零后，那么我从小到大在电视上看过什么喜剧呢?武林外传，爱情公寓，家有儿女，没有了。这就是我们这一代人接触过的喜剧，而我们为什么喜欢爱情公寓，因为我们没有别的喜剧可以喜欢，我同样喜欢武林外传，可爱情公寓的题材与设定更适合我们当时的审美与理解能力，所以爱情公寓才会有了如此多的粉丝，那些无限贬低的人，当时不也是一集集看完的吗  
> 说到抄袭，没得洗，但如果你想发表你的看法应该去前几季，这部剧目前还没有能证明抄袭的证据。美剧和抄袭剧还是有区别，我接触美剧大概是初中，看行尸走肉，血族，看过几集生活大爆炸，也是抄袭的受害者之一，说实话，那时候的我并不喜欢这部剧，因为他太成人化了，有太多我看不懂的段子以及大量成人笑话，别说什么看爱情公寓的人都青春其实都是美剧，一个电视剧哪来什么青春不青春的，就图一乐呵，看着有意思，这把美剧在电视上放，也不一定有多火，但实际上，大部分人在那时候上接触不到美剧的。

样本二(s2)：

> 太喜欢短评里的一句话了，如果你带着偏见去看，那你永远都不会满意。本来影评是没有这段的，但看了一些影评后还是决定再写一下，为什么看了半集或者看了几分钟就来打一星，最可怕的是我看到一个短评说打两星以上都是傻逼，不想多说什么，跟没有教养的人没有讨论的价值。热评里有一篇文章写为什么要喜欢爱情公寓，而不去喜欢其他的喜剧，他列举了很多国内优秀喜剧，并且狠狠的讽刺谩骂了爱情公寓，我告诉你为什么。我出生于00年，一个标准的零零后，那么我从小到大在电视上看过什么喜剧呢?武林外传，爱情公寓，家有儿女，没有了。这就是我们这一代人接触过的喜剧，而我们为什么喜欢爱情公寓，因为我们没有别的喜剧可以喜欢，我同样喜欢武林外传，可爱情公寓的题材与设定更适合我们当时的审美与理解能力，所以爱情公寓才会有了如此多的粉丝，那些无限贬低的人，当时不也是一集集看完的吗？说到抄袭，没得洗，但如果你想发表你的看法应该去前几季，这部剧目前还没有能证明抄袭的证据。美剧和抄袭剧还是有区别，说实话，那时候的我并不喜欢这部剧，因为他太成人化了，有太多我看不懂的段子以及大量成人笑话，别说什么看爱情公寓的人都青春其实都是美剧，一个电视剧哪来什么青春不青春的，就图一乐呵，这把美剧在电视上放，也不一定有多火，但实际上，大部分人在那时候上接触不到美剧的。

样本三(s3)：

> 爱5可谓后劲十足，被前几集劝退的观众可能会错过很多，豆瓣逐渐升高的评分也证明了爱5得到真正看下去的观众的认可，不在只是搞笑的喜剧可以让人看到演员的演技，也更能体会导演要表达东西  
> 虽然感情戏部分要讲的道理并不复杂，无非是一群年轻人长大后面临的生活困境，信任危机，他们不再只是无忧无虑的年轻人，他们要考虑未来，自己的工作，家庭，梦想，越来越多的压力是每个人成熟的必经之路，爱情公寓现实了许多，你更能找到与自身的相同点，也更愿意去思考  
> 感谢一些网友对我影评的认可，能够在骂声一片的评论区收获赞同是我的荣幸，也有许多持反对意见的朋友提出了质疑与不满，也对我的思考提供了帮助，让我认识到自己观点的不当之处，也试着去理解大家的看法  
> 爱情公寓系列以及这些事情一直存在争议，也很难有个结果，我不希望大家随波逐流，而是应该有自己的思考与认识，无论你对爱情公寓爱不释手还是嗤之以鼻，都不应该被网络的谩骂左右了观点。写这篇影评就是希望大家能够客观冷静的对待这部剧，虽然争吵避免不了，但还是希望大家能够和平探讨，尽量不要用极端的形容或是偷换概念，也请大家尊重每一位观众，我也会积极与大家沟通交流

计算结果如下：  
d(s1,s2)=0  
d(s1,s3)=14  
d(s2,s3)=14

结果还是比较准确的。

另外尝试了其他文本量较大的样本，识别准确率都不错。**因此基于simhash和汉明距离的文本相似性计算适用于文字较多的文本，对短文本的识别是很不准确的。**

**另外，由于任何hash函数都不可避免的存在冲突，所以，也会出现完全不相干的两段文本计算的hash值相同，导致汉明距离很小而误判为相似。**

#### 1.4 simhash关键代码 ####

@Getter
        static class WordTerm extends Term { 
            int frequency;
            long hash;
            List<Integer> weightedHash;
    
            public WordTerm(String word, Nature nature) { 
                super(word, nature);
            }
    
            @Override
            public String toString() { 
                return JSONObject.toJSONString(this);
            }
        }
     private static String simhash(String s) { 
            //分词
            List<Term> segment = segment(s);
            Map<String, WordTerm> wordMap = new HashMap<>();
            //计算词频
            for (Term term : segment) { 
                WordTerm wordTerm = wordMap.get(term.word);
                if (wordTerm == null) { 
                    wordTerm = new WordTerm(term.word, term.nature);
                    //词频
                    wordTerm.frequency = 1;
                    //hash
                    wordTerm.hash = MurmurHash3.hash64(term.word.getBytes());
                    wordMap.put(term.word, wordTerm);
                } else { 
                    wordTerm.frequency += 1;
                }
            }
            //加权hash
            for (Map.Entry<String, WordTerm> wordTermEntry : wordMap.entrySet()) { 
                WordTerm wordTerm = wordTermEntry.getValue();
                int frequency = wordTerm.frequency;
                long hash = wordTerm.hash;
                String hashBinaryString = Long.toBinaryString(hash);
                String[] hashArray = hashBinaryString.split("");
                List<Integer> collect = Lists.newArrayList(hashArray).stream().map(x -> { 
                    if ("0".equals(x)) { 
                        return -frequency;
                    } else return frequency;
                }).collect(Collectors.toList());
                int len = 64 - collect.size();
                for (int i = 0; i < len; i++) { 
                    collect.add(i, -frequency);
                }
                wordTerm.weightedHash = collect;
            }
            //生成64位simhash
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 64; i++) { 
                //合并
                int sum = 0;
                for (Map.Entry<String, WordTerm> wordTermEntry : wordMap.entrySet()) { 
                    WordTerm wordTerm = wordTermEntry.getValue();
                    sum += wordTerm.weightedHash.get(i);
                }
                //降维
                if (sum > 0) { 
                    sb.append(1);
                } else { 
                    sb.append(0);
                }
            }
            return sb.toString();
        }

--------------------

All efforts, only for myself, no longer for others

[1. _simhash]: https://blog.csdn.net/wxgxgp/article/details/104106867
[2.]: https://blog.csdn.net/wxgxgp/article/details/104146034
[3.]: https://blog.csdn.net/wxgxgp/article/details/104184418
[4. jaccard]: https://blog.csdn.net/wxgxgp/article/details/104235559
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d4Z3hncA_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200130153026522.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d4Z3hncA==,size_16,color_FFFFFF,t_70#pic_center