童学杰 彭绪富

摘要：局部敏感哈希（Locality Sensitive Hashing，LSH）算法，又称局部敏感散列算法，顾名思义，该算法产生的散列值是局部敏感的。对原始内容做微小的修改后，经过LSH算法生成的散列值的变化也是微小的，因此LSH生成的散列值是局部敏感的。这一特性可以运用在论文查重、网页比较、文本比较等需要比较内容相似度的场景上。该文着重研究LSH在文本比较上的实现（Simhash算法）。首先，对给定的文本做分词降噪和加权处理得到带权重的具有给定文本特征的词语，其次，使用哈希算法为每个词语生成对应的哈希值并根据各自的权重形成加权数字串，然后合并所有词语并降维，最后，通过使用海明距离（Hamming Distance）计算生成的两个Simhash的相似度。

关键词：局部敏感；哈希；LSH；Simhash；相似度；查重

中圖分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）10-0162-02

开放科学（资源服务）标识码（OSID）：

1 前言

在做数据分析时，我们常常需要比较两组或多组给定内容之间的差异或者说是相似度的大小。传统的内容比较是直接使用输入的字符串做对比，该方法虽然实现起来十分简单，但是效率极低，无法大规模用于工业生成。相比之下，采用最长公共子序列（Longest Common Subsequence）算法可以达到更好的效果，使用动态规划计算得到编辑距离（levenshtein distance），即两个字符串的相似程度，生物学家可以根据该算法对比DNA的相似度来辅助生物工程研究，但是该算法不能较好的使用在大文本的检索和比较上。通过设计一种特殊性质的算法，即局部敏感哈希算法，可以解决这一问题，并且提高相似度查询的效率。LSH被广泛应用于文本、超媒体等检索领域。

2 分词降噪

分词。所谓的分词主要涉及的是中文（其他亚洲语言比如韩文、日文等也适用），不过拼音语言（比如英语、法语等）的手写体由于分隔不明显，也会导致类似分词的问题，虽然语种不同，但是分词的思想却是一致的。分词在语音识别和翻译等领域应用也十分广泛。近年来，中文分词已经突破了语法语义规则的限制，不再使用传统的基于规则的方法，而是使用统计语言模型来进行自然语言处理。由于基于规则的方法存在严重的性能问题和十分复杂的语义分析，且准确率比较低（大概在70%）等缺陷，其很快被数学中的统计模型代替，该模型不仅具有较高的性能，更重要的是准确率可以达到90%，这是基于规则的方法问世十几年却无法达到的水平。

使用统计模型的公式如下：

P（S）=P（W1，W2，…，Wn） （2.1）

其中，S表示一段子序列，P（S）则表示S在文本（W1，W2，…，Wn）中出现的概率。展开后表示如下：

P（W1，W2，W3，…，Wn）=P（W1）﹒P（W2|W1）﹒P（W3|W1，W2）…P（Wn|W1，W2，…，Wn-1） （2.2）

其中，P（W1）表示第一个词W1出现的概率，P（W2|W1）是在已知第一个词的前提下，第二个词出现的概率，后续依此类推。复杂的分词问题便可以简单化。

降噪。在输入的文本中，并不一定是所有的词或者字都对将要进行的比较有正面作用，比如“的”“地”“得”等和一些副词，这些词语对于理解文本意义会产生负面影响，所以应当去掉。该过程被称为降噪。这时候我们就需要有夹杂着噪音和错误的语料文本，且该语料必须是领域内的，比如搜索的语料应该使用网页的数据，而不是各类规范的日报期刊文章等。

得到具有给定文本特征的带权词语。一般需要表达一篇文章的中心思想时，可能会使用该文章特有的词汇。这些“特有的”词汇就是计算内容相似度的重要依据。通常情况下，应当给文本特有的词语赋权值。比如权值可以从高到低依次为5到1，代表使用该权值的词语在文本中的重要程度，即表达思想的核心程度。如果两篇文章的用词和权值吻合程度比较高，那么就可以肯定这两篇文章的相似度较高。这也是论文查重使用的基本思想。但是仅仅使用这些方法还是远远不够的，譬如：如何快速的比较两段文本？如何确定文本是否相似？计算相似度的依据是什么？这就需要数字化，即把难以处理的文本转换为容易计算的数字。

3 生成加权数字串

为每个词语生成对应的哈希（散列）值。即将给定的特征词语转换为哈希值，并使用生成的哈希值代替原始词语。原始词被映射为较短（比如8位）的固定长度的二进制数值，该值就是我们后续需要计算的哈希值，它是给定的文本特征词语唯一的且十分紧凑的数值表现形式。使用散列函数可以将给定的文本的特征词完整的转化（压缩）成摘要，使得数据量显著减少，并且将数据的格式固定为数字存储，即数字化。计算机对于数字的运算速度要远远高于字符串，因此，数字化不仅方便计算相似度，而且也大大提升了计算能力，是解决实际问题和转化模型最常用的方法。

根据各自散列值计算权重并生成加权数字串。权值指的是该特征词在给定的内容中的重要程度，一般权值越大，说明该特征词越重要。权值的确定需要强大的语料和训练，因此，可能同一个应用采用同样的算法，但是如果训练的模型不一样，监督的方式不一样则会导致得到结果的差异非常巨大。比如同一个特征词（Words）在应用A1中的权值为5，记作[Words，5]，但是在另一个应用A2中的权值可能是1，记作[Words，1]，显然该特征词在应用A1中要比A2重要。在计算加权数字串时，按照0为负，1为正来计算权值。假设权值为W，散列值等于1时记作+W，散列值等于0时记作-W。由此计算出一个由+W和-W组成的数字串。例如特征词语“散列值”的权值为5，散列值为01011001（假设压缩后的位数是8位），那么计算加权数字串的过程如下：

-5 +5 -5 +5 +5 -5 -5 +5

再比如，特征词“哈希值”的权值为4，散列值为00101010，那么计算加权数字串的过程如下：

-4-4+4-4+4-4+4-4

4 降维

合并所有特征词语。带运算符号累加所有特征词语对应位的权值，形成新的数字串。假设有哈希值H1和H2，权值W1和W2，其数字串如下：

H1：-W1 +W1 -W1 +W1 +W1 -W1 -W1 +W1 （4.1）

H2：-W2 -W2 +W2 -W2 +W2 -W2 +W2 -W2 （4.2）

则合并公式如下：

-W1-W2 +W1-W2 -W1+W2 +W1-W2 +W1+W2 -W1-W2 -W1+W2 +W1-W2 （4.3）

即第一位W1和第一位W2运算，第二位W1和第二位W2运算，注意所有运算必须带上符号，依次类推。最后得到一个8位（本例假设是8位）的二进制数值，结果如下：

W（-W1-W2） W（+W1-W2） W（-W1+W2） W3（+W1-W2） W（+W1+W2） W（-W1-W2） W（-W1+W2） W（+W1-W2） （4.4）

按照上例中“散列值”和“哈希值”生成的数字串得到如下计算过程：

-5-4 +5-4 -5+4 +5-4 +5+4 -5-4 -5+4 +5-4

由上述过程可得出新的数字串如下所示：

-9+1-1+1+9-9-11

降维。即生成最终的哈希签名。根据给定的公式计算得到合并后的权值，若W小于或者等于0，则该位记为0，若W大于0，则该位记为1。由此可知“散列值”和“哈希值”生成的二进制串如下所示：

01011001

5 计算相似度

使用海明距离（Hamming Distance）计算相似度。在计算机的信息编码中，海明距离可以将给定的编码串进行异或（XOR）运算得到，即给定的兩组编码对应位上不同的位数称为码距，或海明距离。假设有两组8位的编码C1和C2，依次对应为：

C1：0 1 0 1 0 0 1 1

C2：0 0 0 1 0 1 0 1

其中，C1与C2对应位不一致的地方使用黑色粗体标识出来。通过比较不难发现两者共有3处不一致，所以C1与C2的码距为3，即海明距离为3。

海明距离可以表示两组编码之间的差异，常被用于编码的检错和纠错等，也可表示两组编码的相似度。假设C1是我们前面提到的特征词“哈希值”的编码，而C2是特征词“散列值”的编码，那么C1与C2的海明距离则是“哈希值”与“散列值”之间的距离，即两个特征词之间的相似距离。由此，两个中文特征词之间的相似度关系便转化成了两个二进制编码的码距问题。码距越大，说明两者距离越远，相似度越低。如果我们比较的是两篇文章，那么很容易就可以得到两篇文章的相似度，从而可以辅助判断作者是否在文章内使用了过多的引用，甚至是否有抄袭的嫌疑。

6 结语

以局部敏感哈希算法为核心的字符比较算法，利用海明距离计算码长，实现给定两组或多组内容的相似度计算。由于LSH是基于权值空间的算法，因此，在计算之前必须要得到给定特征词的权值，这就涉及了分词和加权，目前被广为接受的分词方法是基于数学中的统计语言模型，加权的难点在于如何确定给定特征词的权值，得到特征词和对应的权值后使用合并降维等方法最终生成给定内容的Simhash。

参考文献：

[1] 吴军.数学之美[M].北京：人民邮电出版社，2014：41-45.

[2] AdityaBhargava. 算法图解[M].北京：人民邮电出版社，2017：178-179.

[3] Richard E.Neapolitan. FoundationsofAlgorithms[M].北京：人民邮电出版社，2016：66-67.

[4] 周志华.机器学习[M]. 北京：清华大学出版社，2016：60-66.

【通联编辑：代影】