如何捕获相似基因（两个相似哈希算法分析）

如何捕获相似基因（两个相似哈希算法分析）

普通的哈希函数具有如下特点

1. 可将任意长度的输入映射为固定长度的输出
2. 不同的输入较大概率映射为不同的输出

可见，普通的哈希算法得到的输出（哈希值）可以很好判定两个文本是否相同。即哈希值虽然抛弃了文本的原始内容，但其继承了输入文本的某种基因，能够精确表达文本的内容。

所谓相似哈希，就是一个特殊的映射函数，具有如下特点

1. 可将任意长度的输入映射为固定长度的输出
2. 相似的输入具有相同或相似的输出

与普通哈希算法不同，相似哈希算法继承了原输入文本更多的基因——相似基因。下面来介绍simhash算法。来看算法是如何捕获相似基因的。后面会介绍LSH算法，可以看出其捕获相似基因的方法是类似的。

以文本信息为例，simhash算法的大体思路是：

1. 将文本分词
2. 统计每个词出现的次数，假设有n个词
3. 设定一个普通hash函数，能将词映射为一个固定长度（假设32bit）的数字，此处称为摘要
4. 计算每个词的摘要。生成n个摘要（每个摘要为一个32bit数字）。
5. 我们计算出的输入文本的相似哈希值也是一个32bit数字，这个数字的每一个二进制位是由步骤4计算出的n个摘要决定的。于是n个摘要对每一个二进制位进行了一次投票。少数服从多数。比如，当n个摘要对相似哈希的第1个二进制位进行投票，其中有m个摘要第一个二进制位为1，n-m个摘要的第一个二进制位为0，则当m>n-m时，则相似哈希的第1个二进制位为1，m<=n-m时为0。

经过如上5步，可以得到一个相似哈希值，还可以在第5步投票的时候考虑每个词出现的频次。即频次高的数字摘要投票的结果要加倍考虑，倍数就是词的频次。

通过分析simhash算法可以得到捕获相似基因的思路

1. 将输入进行合理分割

• 每个分割单元基本不变，具有独立的含义（每个词有独立的含义，变一个字可能整个意义都变了）
• 输入的变化是分割单元的变化（若输入文本发生相似变化，也是个别词不一样）

2. 对分割单元进行频次统计，频次越高的分割单元相似基因越强
3. 采用投票方式找出最强的相似基因作为相似哈希

其中最重要的两个步骤是合理分割变化单元和利用变化单元的统计特征。几乎所有的相似哈希算法都是应用了这两个步骤。下面简述一下LSH算法，可以看到其也是利用上述两个步骤完成相似基因的捕获的。

还是以文本信息为例，LSH算法的思路如下：

1. 将输入进行分词
2. 生成n种不同的将词映射到一个数字的映射方法。
3. 针对n种映射方法的第i(i=1,...,n)种，进行如下计算
4. 将输入文本的所有词输入第i种映射，每个词计算出一个映射值
5. 取所有映射值的最小值作为第i种映射方法计算出的输入文本映射值
6. 通过步骤3可计算出n个文本映射值。将这n个文本映射值作为文本的相似基因。

分析如上步骤，可以看出其也是对输入信息进行了合理的分割。由于n中映射方法完全是随机的，则每种映射方法所得到的文本映射值相当于从分词中的随机获取一个词。两个相似文本通常是存在大量相同词语的，仅有少数词语不同的。如果进行随机抽取，抽取到相同部分词语的概率会比不同词语的概率大。故其也是利用到了分割单元的统计信息进行相似基因的获取的。