简介

最近在看老师写的关于图像检索的一片综述，看到了SimHash，然后又看到了MinHash，网上一搜又出来了局部感知哈希LSH，看着看着又蹦出来个感知哈希，还有个Sim-Min-Hash，脑子已经成了浆糊……看了很久才大概理清了其中一些关系，在此作一下记录。

综合转载以下文章：

十分感谢！

哈希技术概述

在检索技术中，索引一直需要研究的核心技术。当下，索引技术主要分为三类：基于树的索引技术（tree-based index）、基于哈希的索引技术（hashing-based index）与基于词的倒排索引（visual words based inverted index）。

在检索中，需要解决的问题是给定一个查询样本query，返回与此query相似的样本，线性搜索耗时耗力，不能承担此等重任，要想快速找到结果，必须有一种方法可以将搜索空间控制到一个可以接受的范围，哈希在检索中就是承担这样的任务，因而，这些哈希方法一般都是局部敏感（Locality-sensitive）的，即样本越相似，经过哈希后的值越有可能一样。所以，本文中介绍的技术都是局部敏感哈希（Locality Sensitive Hashing，LSH），与hashmap、hashtable等数据结构中的哈希函数有所不同。

哈希技术分类

对于哈希技术，可以按照不同的维度对齐进行划分。

按照其在检索技术中的应用方法来划分，可以分为分层法和哈希码法：

分层法即为在数据查询过程中使用哈希技术在中间添加一层，将数据划分到桶中；在查询时，先对query计算桶标号，找到与query处于同一个桶的所有样本，然后按照样本之间的相似度计算方法（比如欧氏距离、余弦距离等）使用原始数据计算相似度，按照相似度的顺序返回结果，在该方法中，通常是一组或一个哈希函数形成一个表，表内有若干个桶，可以使用多个表来提高查询的准确率，但通常这是以时间为代价的。分层法的示意图如图1所示。在图1中，H1、H2等代表哈希表，g1、g2等代表哈希映射函数。
分层法的代表算法为E2LSH[2]。
哈希码法则是使用哈希码来代替原始数据进行存储，在分层法中，原始数据仍然需要以在第二层被用来计算相似度，而哈希码法不需要，它使用LSH函数直接将原始数据转换为哈希码，在计算相似度的时候使用hamming距离来衡量。转换为哈希码之后的相似度计算非常之快，比如，可以使用64bit整数来存储哈希码，计算相似度只要使用同或操作就可以得到，唰唰唰，非常之快，忍不住用拟声词来表达我对这种速度的难言之喜，还望各位读者海涵。
哈希码法的代表算法有很多，比如KLSH[3]、Semantic Hashing[4]、KSH[5]等。

以我看来，两者的区别在于如下几点：

在对哈希函数的要求上，哈希码方法对哈希函数的要求更高，因为在分层法中，即便哈希没有计算的精确，后面还有原始数据直接计算相似度来保底，得到的结果总不会太差，而哈希码没有后备保底的，胜则胜败则败。
在查询的时间复杂度上，分层法的时间复杂度主要在找到桶后的样本原始数据之间的相似度计算，而哈希码则主要在query的哈希码与所有样本的哈希码之间的hamming距离的相似计算。哈希码法没有太多其他的需要，但分层法中的各个桶之间相对较均衡方能使复杂度降到最低。按照我的经验，在100W的5000维数据中，KSH比E2LSH要快一个数量级。
在哈希函数的使用上，两者使用的哈希函数往往可以互通，E2LSH使用的p-stable LSH函数可以用到哈希码方法上，而KSH等哈希方法也可以用到分层法上去。

按照哈希函数来划分，可以分为无监督和有监督两种：

无监督，哈希函数是基于某种概率理论的，可以达到局部敏感效果。如E2LSH等。
有监督，哈希函数是从数据中学习出来的，如KSH、Semantic Hashing等。

一般来说，有监督算法比无监督算法更加精确，因而也更常用于哈希码法中。

本文中，主要对无监督的哈希算法进行介绍。

LSH简介

在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度，怎样快速地从海量的高维数据集合中找到与某个数据最相似（距离最近）的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集，我们通过线性查找（Linear Search）就可以容易解决，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,AN），例如K-d tree；或近似最近邻查找（Approximate Nearest Neighbor, ANN），例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一类方法。

我们知道，通过建立Hash Table的方式我们能够得到O(1)的查找时间性能，其中关键在于选取一个hash function，将原始数据映射到相对应的桶内（bucket, hash bin），例如对数据求模：$h = x \space mod \space w$，$w$通常为一个素数。在对数据集进行hash 的过程中，会发生不同的数据被映射到了同一个桶中（即发生了冲突collision），这一般通过再次哈希将数据映射到其他空桶内来解决。这是普通Hash方法或者叫传统Hash方法，其与LSH有些不同之处。

LSH的基本思想是：将原始数据空间中的两个相邻数据点通过相同的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。也就是说，如果我们对原始数据进行一些hash映射后，我们希望原先相邻的两个数据能够被hash到相同的桶内，具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后，我们就得到了一个hash table，这些原始数据集被分散到了hash table的桶内，每个桶会落入一些原始数据，属于同一个桶内的数据就有很大可能是相邻的，当然也存在不相邻的数据被hash到了同一个桶内。因此，如果我们能够找到这样一些hash functions，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入相同的桶内的话，那么我们在该数据集合中进行近邻查找就变得容易了，我们只需要将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查询数据相邻的数据。换句话说，我们通过hash function映射变换操作，将原始数据集合分成了多个子集合，而每个子集合中的数据间是相邻的且该子集合中的元素个数较小，因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题，显然计算量下降了很多。

能够使得原本相邻的两个数据点经过hash变换后会落入相同的桶内的哈希函数需要满足以下两个条件：

如果$d(O_1, O_2) < r1$，那么$Pr[h(O_1) = h(O_2)] \geq p_1$
如果$d(O_1, O_2) > r2$，那么$Pr[h(O_1) = h(O_2)] \leq p_2$

其中，$O_1, O_2 \in S$表示两个具有多维属性的数据对象，$d(O_1, O_2)$为2个对象的相异程度，也就是1-相似度。如果对于任意$H$中的函数$h$，满足以上两个条件，这样的一族hash函数$H = \{h : S \to U\}$称为是$(r_1, r_2, p_1, p_2)$敏感的。

使用LSH进行对海量数据建立索引（Hash table）并通过索引来进行近似最近邻查找的过程如下：

离线建立索引
（1）选取满足$(d_1,d_2,p_1,p_2)-sensitive$的LSH hash functions；
（2）根据对查找结果的准确率（即相邻的数据被查找到的概率）确定hash table的个数L，每个table内的hash functions的个数K，以及跟LSH hash function自身有关的参数；
（3）将所有数据经过LSH hash function哈希到相应的桶内，构成了一个或多个hash table；
在线查找
（1）将查询数据经过LSH hash function哈希得到相应的桶号；
（2）将桶号中对应的数据取出；（为了保证查找速度，通常只需要取出前2L个数据即可）；
（3）计算查询数据与这2L个数据之间的相似度或距离，返回最近邻的数据；

LSH在线查找时间由两个部分组成：（1）通过LSH hash functions计算hash值（桶号）的时间；（2）将查询数据与桶内的数据进行比较计算的时间。因此，LSH的查找时间至少是一个sublinear时间。为什么是“至少”？因为我们可以通过对桶内的属于建立索引来加快匹配速度，这时第（2）部分的耗时就从O(N)变成了O(logN)或O(1)（取决于采用的索引方法）。

LSH为我们提供了一种在海量的高维数据集中查找与查询数据点（query data point）近似最相邻的某个或某些数据点。需要注意的是，LSH并不能保证一定能够查找到与query data point最相邻的数据，而是减少需要匹配的数据点个数的同时保证查找到最近邻的数据点的概率很大。

常用于缩略图搜索的LSH

常用于缩略图搜索的有三种哈希技术：

平均哈希算法(aHash)

此算法是基于比较灰度图每个像素与平均值来实现的，最适用于缩略图搜索。

步骤：

缩放图片：为了保留结构去掉细节，去除大小、横纵比的差异，把图片统一缩放到8*8，共64个像素。
转化为灰度图：把缩放后的图片转化为256阶的灰度图
计算平均值：计算进行灰度处理后图片的所有像素点的平均值
比较像素灰度值：遍历64个像素，如果大于平均值记录为1，否则为0.
得到信息指纹：组合64个bit位，顺序随意保持一致性即可。
对比指纹：计算两幅图片的汉明距离，汉明距离越大则说明图片越不一致，反之，汉明距离越小则说明图片越相似，当距离为0时，说明完全相同。(通常认为距离>10 就是两张完全不同的图片)

感知哈希算法(pHash)

平均哈希算法过于严格，不够精确，更适合搜索缩略图，为了获得更精确的结果可以选择感知哈希算法，它采用的是DCT(离散余弦变换)来降低频率的方法。

步骤：

缩小图片：32*32是一个较好的大小，这样方便DCT计算
转化为灰度图：把缩放后的图片转化为256阶的灰度图
计算DCT:DCT把图片分离成分率的集合
缩小DCT：DCT是32*32，保留左上角的8*8，这些代表的图片的最低频率
计算平均值：计算缩小DCT后的所有像素点的平均值
进一步减小DCT：大于平均值记录为1，反之记录为0
得到信息指纹：同平均哈希算法
对比指纹：同平均哈希算法

二维图像的DCT变换

二维DCT变换就是将二维图像从空间域转换到频率域。形象的说，就是计算出图像由哪些二维余弦波构成，计算出的结果为$c(u ,v)$, 其中$u$为二维波的水平方向频率，$v$为二维波的垂直方向频率；最终会计算出很多的$c(u,v)$ ; 每一个$c$称为一个DCT系数，代表的是频率为$(u,v)$的二维波的振幅（或者能量），所有这些二维波的叠加就是那个原始的图片。

假设图像为$f(i,j)$，则其DCT变换$F(u,v)$为：

$F(u,v)=c(u)c(v)\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}f(i,j)cos[\frac{(i+0.5)\pi}{N}u]cos[\frac{(j+0.5)\pi}{N}v]$

其中，

$c(u)=\left\{ \begin{aligned} \sqrt{\frac{1}{N}}, u=0 \\ \sqrt{\frac{2}{N}}, u\neq0\\ \end{aligned} \right.$

DCT变换的矩阵形式：

$F=AfA^{T}$

其中，

$A(i,j)=c(i)cos[\frac{(j+0.5)\pi}{N}i]$

差异哈希算法( dHash)

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。

步骤：

缩小图片：收缩到9*8的大小，共72个像素点
转化为灰度图：把缩放后的图片转化为256阶的灰度图
计算差异值：dHash算法工作在相邻像素之间，这样每行9个像素之间产生了8个不同的差异，一共8行，则产生了64个差异值
获得指纹：如果左边像素的灰度值比右边高，则记录为1，否则为0
对比指纹：同平均哈希算法

Python实现

import cv2
import numpy as np
import time
#均值哈希算法
def aHash(img):
    #缩放为8*8
    img=cv2.resize(img,(8,8),interpolation=cv2.INTER_CUBIC)
    #转换为灰度图
    gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    #s为像素和初值为0，hash_str为hash值初值为''
    s=0
    hash_str=''
    #遍历累加求像素和
    for i in range(8):
        for j in range(8):
            s=s+gray[i,j]
            #求平均灰度
    avg=s/64
    #灰度大于平均值为1相反为0生成图片的hash值
    for i in range(8):
        for j in range(8):
            if gray[i,j]>avg:
                hash_str=hash_str+'1'
            else:
                hash_str=hash_str+'0'
    return hash_str
 
#差值感知算法
def dHash(img):
#缩放8*8
    img=cv2.resize(img,(9,8),interpolation=cv2.INTER_CUBIC)
#转换灰度图
    gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    hash_str=''
#每行前一个像素大于后一个像素为1，相反为0，生成哈希
    for i in range(8):
        for j in range(8):
            if gray[i,j]>gray[i,j+1]:
                hash_str=hash_str+'1'
            else:
                hash_str=hash_str+'0'
    return hash_str
 
#Hash值对比
def cmpHash(hash1,hash2):
    n=0
#hash长度不同则返回-1代表传参出错
    if len(hash1)!=len(hash2):
        return -1
#遍历判断
    for i in range(len(hash1)):
#不相等则n计数+1，n最终为相似度
        if hash1[i]!=hash2[i]:
            n=n+1
    return 1 - n / 64
 
def pHash(imgfile):
    img_list=[]
#加载并调整图片为32x32灰度图片
    img=cv2.imread(imgfile, 0)
    img=cv2.resize(img,(64,64),interpolation=cv2.INTER_CUBIC)
 
#创建二维列表
    h, w = img.shape[:2]
    vis0 = np.zeros((h,w), np.float32)
    vis0[:h,:w] = img #填充数据
 
#二维Dct变换
    vis1 = cv2.dct(cv2.dct(vis0))
#cv.SaveImage('a.jpg',cv.fromarray(vis0)) #保存图片
    vis1.resize(32,32)
 
#把二维list变成一维list
    img_list=vis1.flatten()
 
 
#计算均值
    avg = sum(img_list)*1./len(img_list)
    avg_list = ['0' if i>avg else '1' for i in img_list]
 
#得到哈希值
    return ''.join(['%x' % int(''.join(avg_list[x:x+4]),2) for x in range(0,32*32,4)])
 
 
def hammingDist(s1, s2):
#assert len(s1) == len(s2)
    return 1 - sum([ch1 != ch2 for ch1, ch2 in zip(s1, s2)])*1. / (32*32/4)
 
if __name__ == '__main__':
    img1 = cv2.imread("F:\\Humpback Whale\\phash\\4.jpg")
    img2 = cv2.imread("F:\\Humpback Whale\\phash\\2d6610b9.jpg")
    time1 = time.time()
    hash1 = aHash(img1)
    hash2 = aHash(img2)
    n = cmpHash(hash1, hash2)
    print('均值哈希算法相似度：', n, "-----time=", (time.time() - time1))
    time1 = time.time()
    hash1 = dHash(img1)
    hash2 = dHash(img2)
    n = cmpHash(hash1, hash2)
    print('差值哈希算法相似度：', n, "-----time=", (time.time() - time1))
 
    time1 = time.time()
    HASH1=pHash("F:\\Humpback Whale\\phash\\4.jpg")
    HASH2=pHash("F:\\Humpback Whale\\phash\\2d6610b9.jpg")
    out_score = hammingDist(HASH1,HASH2)
    print('感知哈希算法相似度：', out_score, "-----time=", (time.time() - time1))

LSH详细过程，Jaccard距离空间：MinHash

基本概念

shingling: 表示的是对一个文档的转换，可以理解为对一个文档进行切割
minhashing: 将一个大的集合中的元素转换为很多短小的签名，但是保持了这些集合中的元素的相似性
Locality-sensitive hashing: 关注的是签名对可能的相似性

整体架构

一下这个图揭示了Locality Sensitive Hashing 的一个整体结构图。

当接受到文档，或者输入文档之后，我们开始shingling 他们，就是将这个文档切割成一个一个的元素，这些元素是由很多的字符串组成的（由k个字符串组成）
用Minhashing 得到我们集合元素的签名
产生可能的候选对

Shingles

又叫K-shingle、k-gram 。一个文档可以看成是K个字符组成的一个集合。

例如：k=2，doc=adcab，这个集合的2-shingles={ab,ba,ca} 。我们对这个字符串进行划分，得到的是ad dc ca ab，由于集合是唯一性的所以不可能有重复的元素。k=2 其实是一个比较糟糕的选择，我们一般选择K在实际情况中一般会选择9或者10，我们要求这个k一般要大于我们文章中出现的单词的长度。这样的选择会比较合理一些。

Shingles 和相似性

文档如果是相似的，那么他们理论上（intuitively）应该有很多的shingles 是相同的。这里的相似其实是指的是在文本上的相似 text similarity 不涉及到我们说的其他的主题相似等另外一些情况。
交换文档的两个段落只会影响 2k 的shingles 在段落的边界处
e.g. k=3, “The dog which chased the cat” 转换成 “The dog that chased the cat”。
这个时候被替换的3-shingles 就是g_w, wh, whi, hic, ich, ch, and h_c。

MinHashing

在介绍MinHashing 之前我们有必要来介绍一些重要的基本概念。在这里最重要的就是我们的Jaccard Similarity

Jaccard Similarity

Jaccard similarity 指的就是两个集合交集的个数除以两个几何并集的个数。

看下面这个例子我们也可以理解：

在这里有两个集合，交集中元素的个数是3，而并集中元素的个数是8。这个时候我们的Jaccard Similarity 相似度就是3/8

我们来看下面的这个例子来说明我们的列的相似性。

这个很好理解，我们看列的相似性，我们只看含有1 的那些行，所以我们的并集个数就是5，而我们的交集个数就是2 所以相似性就是 0.4。

我们也可以用另一种眼观来看，就是假设只有两列，我们的数据集，也就是说有两个元素，那么行的类型也就是说是有4种就是 A 有B没有或者是A没有B有或者是两个都有或者是两个都没有的情况。

如下图所示：

在这里我们

a 看做是两个元素都具有的属性的个数。
b 就是C1 元素有而C2元素没有的情况的个数。
c 就是C2有而C1元素没有的情况下的个数。
d 就是两个元素都没有的情况下的个数。

所以我们的Jaccard Sim = a/(a+b+c)

定义

minhash 函数 h(c) = 表示的是在某一列中的第一个出现1的那一行的行号,我们用这个行号中第一次出现1的那个行来做我们这个矩阵的那一列的特征值。

如下图所示，这里有一个矩阵

我们对这个矩阵的每一行标注一个号码，就是紫色的这个部分

从这里我们可以看出我们的输入的这个布尔矩阵的可以得到一个特征矩阵

这个时候我们的到的一个签名矩阵，就是这个，输入矩阵的第一个出现1的行数，特征值是3，1，1，2

接下来我们对我们的这个输入矩阵进行重排，得到一个新的矩阵。

我们在对这个输入矩阵进行第三次的重排，这个时候我们又可以得到一个新的特征值
我们对这个矩阵重排之后得到一个新的矩阵，绿色的那个表示重排之后，这个时候它表示的第一排是最后一排，最后一排是第一排的意思。

得到的特征值就是 2，2，1，3。为什么这么做，因为我们可以用这个singnature matrix的相似性（Jaccard similarity）来表示我们的这个input matrix 的相似性。我们来看我们的这个例子，

我们来看我们的第1列和第2列，这个时候我们需要观察的就是我们的input matrix 这个矩阵。这两个样本的相似性我们可以看出来是1/4，根据我们刚才介绍的公式 sim=a/(a+b+c)。我们要比较第一列和第二列，拿出这两列来看，

我们只关注有1 的列

a 的个数是1，并集的个数是4，所以我们得到的是1/4。我们看我们的签名矩阵signature matrix ，第一列和第二列拿出来看，

1
2
3

3 1 
2 2 
1 5

签名的相似性 1/3 ，以此类推我们可以得到我们所求的图中要求的相似性，我们看图中第2列和第3列 Jaccard similarity 就是 1/5，我们签名的相似性就是1/3 。

根据上面我们计算分析的例子发现其实我们可以用signature matrix 中hash值的相似性来表示我们的样本的相似性。这就推理出了我们重要的属性，

对于两个document，在Min-Hashing方法中，它们hash值相等的概率等于它们降维前的Jaccard相似度。

证明：

设有一个词项$x$（就是Signature Matrix中的行），它满足下式：

$\pi(x)=min(\pi(C_1 \cup C_2))$

就是说，词项$x$被置换之后的位置，和$C_1$，$C_2$两列并起来（就是把两列对应位置的值求或）的结果的置换中第一个是1的行的位置相同。那么有下面的式子成立：

$\pi(x)=min(\pi(C_1))\space if \space x \in C_1,or \\ \pi(x)=min(\pi(C_2))\space if \space x \in C_2$

就是说$x$这个词项要么出现在$C_1$中（就是说$C_1$中对应行的值为$1$），要么出现在$C_2$中，或者都出现。这个应该很好理解，因为那个$1$肯定是从$C_1$，$C_2$中来的。

那么词项$x$同时出现在$C_1$，$C_2$中（就是$C_1$，$C_2$中词项$x$对应的行处的值是$1$）的概率，就等于$x$属于$C_1$与$C_2$的交集的概率，这也很好理解，属于它们的交集，就是同时出现了嘛。那么现在问题是：已知$x$属于$C_1$与$C_2$的并集，那么$x$属于$C_1$与$C_2$的交集的概率是多少？其实也很好算，就是看看它的交集有多大，并集有多大，那么$x$属于并集的概率就是交集的大小比上并集的大小，而交集的大小比上并集的大小，不就是Jaccard相似度吗？于是有下式：

$Pr[min(\pi(C_1))=min(\pi(C_2))] = |C_1 \cap C_2|/|C_1 \cup C_2|=sim(C_1, C_2)$

又因为当初我们的hash function就是

$h_{\pi}(C)=min_{\pi}(C)$

往上式代入，

$Pr[h_{\pi}(C_1)=h_{\pi}(C_2)]=sim(C_1,C_2)$

签名的相似性

这里说的就是我们上面这张图片上显示的在最左边的这个列的Jaccard Similarity 必须和我们的签名的相似性保持比较接近。怎么能做到保持比较接近呢，当然就是我们的签名的矩阵越长越好了。

Minhashing的执行

虽然刚才讲了一堆废话，介绍了我们Minhash 算法以及对应的函数的映射规则，但是一般来说基本上上面等于废话，白说。创造LSH的时候就是为了能够处理大数据，上面的那个只能针对数据集比较小的情况才考虑。

如果情况变了呢？假设如下的情况，

如果我们有 10亿行这么多的数据，这个时候我们按照上面的方式来玩，显然是行不通的。把10亿行数据放到内存中排序，这样显然是不科学的。有的人写代码不仅是把行考虑进去了，还考虑了矩阵，这就更尴尬了，你不仅考虑了这么多属性，你还要考虑样本？

按照刚才上面说的这些方法来执行的话，容易出现下面的这些问题：

很难对10亿个数据进行排序。
没有这么大的内存空间
容易造成系统奔溃

所以，我们就要换种玩法。我们刚刚说了，要看两个列的相似性我们可以从签名矩阵上来看，签名矩阵的长度越长的话，这样出错的机会或者说相似的机会就比较小。我们没有必要挑选比较所有的行，我们只要保证我们的签名矩阵的长度合理就可以了。

执行对策

所以我们想了下面的这个执行对策：

我们不用对所有的行进行一个随机的排序，我们只需要挑选，我们用100个不同的哈希函数来对我们的行号进行计算就可以得到新的数据，这个数据就代表我们原先的行号变更出来的行号，可以看成是对我们整个矩阵的行进行洗牌。
其实这样的hash函数很难找到，因为可能是会存在hash值的碰撞，但是这个不影响我们这个算法的执行。
这个想法就是把我们选择hash函数对行号做计算，得出来的数字就是相应的排序行号
在这里我们引入一个Slot的值我们把这个值叫做M，M的初始值是无穷大。我们有100个hash函数我们这么来表示我们的hash函数$h_{i}$, $i$的取值是从1 到100 的，我们用hash函数$h_{i}$计算得到一个hash值，如果我们的样本，也就是某一列的某一行是1，而且这个计算出来的Hash值如果比我们的M值要小，那么M就保存着我们计算出来的较小的hash 值，实际上就是我们默认排列出来较小的行号。

算法的具体描述

for each hash function hi  do
	compute hi (r);
for each column c 
	if c has 1 in row r 
		for each hash function hi do
		if hi (r) is smaller than M(i, c) then
			M(i, c) := hi (r);

下面我们来看一个例子

这个是我们的行，以及我们的两列样本的对应属性的情况，我们设置了两个hash 函数来计算我们的signature的签名应该要哪个

$h(x) = x mod 5 \\ g(x) = (2x+1) mod 5$

如果我们按照常规方法来计算的话，我们要对这个行号进行一个排序，然后找到行号第一个为1 的来做我们的特征值，现在换了计算特征值的方法，我们对行号进行hash 不断的替换我们的最小行号达到我们原始的目的，我们设置两个签名的M值都为无限大，这个时候我们计算行号对应的hash值。

这个时候我们看到两个hash 值分别为1和3，他们的对应的原始行也就是第一行的每一列，我们看到只有第一列有元素为1，所以我们要替换的只能是第一列的M值，如上图所示。这个时候我们在依次计算我们的以下几行的hash值。

计算到第二行的时候得到两个hash值分别是2，0。但是我们检查列只有第2列有1，所以比较大小之后替换得到上面的这个结果

接下来我们来查看我们第三行的Hash 值，我们发现计算的是3，2，并且我们两列的值都是为1的这个时候我们就要来看看替换谁，只能替换的结果是越来越小的。 3比sig1和sig2的值都要大，所以我们保留不替换，我们看2比sig1大，所以被替换的就是它。以此类推，我们得到了下面的结果

其次，这样做的目的是因为我们的数据常常是按照我们的列来给出的，而不是按照行来给出的，如果按照行来给出，我们只需要对矩阵进行一次排列即可。

这样之后，我们一般会得到很多的文档，以及文档被划分出来的shingles。

候选签名

我们用上述的这些算法得到的签名其实是一些候选的相似对，对于这些相似的对我们必须要对他们进行一个评估。对于我们的signature matrix 我们必须对这个hash 得到的列在进行Hash ,这个时候要让这些元素映射到不同的bucket中。（注意，这里的hash 函数可以用一些比较传统的hash 函数）这样我们认为这些列映射到我们相同的buckets 中的就是我们的候选的相似的对，或者说是我们候选可能相似的样本。

我们要得到我们的候选签名，这个时候我们就要设置一个阈值threshold，这个阈值必须是小于1的，当我们的相似度超过了这个阈值的时候我们就认为这些候选的签名是相似的

我们来看一下怎么对我们得到的这个Matrix M 进行处理又或者说是怎么对我们的这个signature M进行处理

上面的这个图黄色的部分就是我们的Matrix M，或者说是我们的signature matirx

每一列我们可以看成是一个样本的签名，就是我们图中的粉红色的条形的部分，就是一列，这一列就是我们样本中的一个签名或者说是样本的特征值，指纹，你都可以这么理解。然后把这个矩阵划分成了b 个bands 也就是b个条状。每一条含有r行。

接下来我们要做的就是：

对每一个signature 分段之后的每一个band 计算一个Hash值，然后让它映射到一个长度为k的bucket里面。我们的k要设置的尽量的大一些。这样子是为了减少碰撞的发生。
我们候选的candidate就是我们认为可能相似的样本就是那些列的hash值被映射到同一个bucket 里面的
我们通过调节我们的b以及r能够捕捉到大多数的相似的pair ,但是很难捕捉到不相似的pair

我们发现第二列和第6 列经过计算一个Hash值之后被映射到了同一个桶里面，这个时候我们可以认为这两个band 很有可能是相同的。当然也有极小的概率是发生了碰撞。

是这样的吗？我们来计算一个概率看一看：

假设我们C1和C2有80%的相似度，在这里我们设置一个Matrix M 它有100 行，我们把这个矩阵分成了20 个bands 每一个band 里面都有5 行(r)

这个时候我们来计算一下C1以及C2 在某个特定的band 里面相似的概率，记住我们有5行，每一行相同的情况是 0.8 的概率：

$(0.8)^5 = 0.328$

那么我们是不是可以计算出C1 ，C2 在任何一个band 都不相似的概率就是：

$(1-0.328)^{20} = 0.00035$

这个时候我们可以得到如果我们设置相似度的阈值是80% 那么它的false nagatives 的概率约为1/3000。

我们再看另外的一个例子：

假设我们认为C1，C2的相似度只有40%。注意我们还是认为我们有100行，也就是我们的签名矩阵（signature matrix 或者说是我们的matrix M）有100 行，同样是被分成了20个band，每一个band还是有5行。

这样，如果C1 和C2 在某个特定的band 里面是相同的概率：

$(0.4)^5 = 0.01$

那么在20个band 里面都不相同的概率就是

$(1-0.01)^{20}=0.99^{20} = 0.82$

我们计算一下如果C1，C2在1个band 或者2,3,4，…20 个band里面都相同的概率

$1-0.82<0.2$

我们的false positive 是远小于40%的。所以当我们设定一个阈值，相似度大于阈值的时候，如果列的相似度非常的大，他们在同一个bucket的概率是非常大的。

我们看下面的例子，$s$表示的是相似度，

所以实际的情况就是下面的这个样子，

这个就说明了我们的LSH 如果其中有两个band 被映射到同一个 bucket 我们可以认为这两列就是相似的。说了这么多意思就是尽管我们的文档很大，产生的最后的Matrix M 也很多。但是我们只需要计算一个band .我们就可以大概的预测出我们样本的相似性了。

把上面的过程作一下正式的说明，两个文档被映射到同一个hash bucket中的概率：

对于两个文档的任意一个band来说，这两个band值相同的概率是：$s^r$，其中$s \in [0, 1]$是这两个文档的相似度。
也就是说，这两个band不相同的概率是$1 - s^r$
这两个文档一共存在$b$个band，这$b$个band都不相同的概率是$(1 - s^r)^b$
所以说，这$b$个band至少有一个相同的概率是$1 - (1 - s^r)^b$

这样的方法称为$AND \space then \space OR$，它是先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。

LSH代码

首先我们至少得构建出我们能够比较的样本的特征值，设计出我们的布尔矩阵（Boolean Matrix）。局部敏感哈希的一个优点就是避免两两比较（pairwise comparison），主要的方法就是看最后的band 被映射同一个bucket的话我们就一般认为这两个特征值其实是相似的，或者说在某个概率下是相同的。

首先我们先构建一个数据集，比如说把它叫做dataSet,这个里面有一些特征向量，我们就用之前我们说的下图这个例子来写我们的代码吧。

我们可以设计我们的dataSet 为一个二维的数组，设计我们需要查询的（或者说找到我们的这个待查询的这个数组为它找到和它相似的数据集）数组为一维数组。我们可以给这个查询的数据叫做query. 我们把这个查询的数组设置为一维数组。

我们可以这么来构建我们的数据结构：

dataSet = [[1,1,0,0,0,1,1],[0,0,1,1,1,0,0],[1,0,0,0,0,1,1]]

query = [0,1,1,1,1,0,0]

dataSet.append(query)
#把这个查询的数组加入到我们的整个数据集当中，并且将它转换成矩阵的形式
matrix = np.array(dataSet).T

如果要写成代码，我们可以像下面这样操作。把我们的这些要操作的数据集设置为我们的输入参数来做：

def  get_data(dataSet,query):

    dataSet.append(query)
    matrix = np.array(dataSet).T

得到我们的数据之后，当然就是生成我们的signature matrix ,这个时候当然就是用到我们的minhash 这个函数，对我们的原始矩阵进行一个行的置换，这个时候找到某列的第一个元素为1 的行号作为我们的signature matrix 的特征值。

我们肯定不会直接把这个矩阵放到内存里面排序进行行置换的操作，这样实在是太占内存了，我们介绍过几种方法，对我们的行号进行置换。依次查询即可。

如果我们按照我们之前章节里面的算法的思路就是对行号进行排序，或者说是置换，这个时候我们来查找置换后的行得到的列中第一次出现1的那个行的行号。

#!/usr/bin/env python
# coding=utf-8

from random import shuffle
import numpy as np
import hashlib 

def generateSig(matrix):

    """
    generate the signature value for the signature matrix 

    param matrix: input matrix 

    """

    # 在这里我们得到原始矩阵的行号
    rowSeries= [i for i in range(matrix.shape[0])]

    #在这里我们设置我们的signature签名矩阵的初始值
    result = [-1 for i in range(matrix.shape[1])]

    colcount = 0

# 对行号重新排序
    shuffle(rowSeries)

    for i in range(len(rowSeries)):

        rowIndex = rowSeries.index(i)

        for j in range(matrix.shape[1]):

            if result[j]==-1 and matrix[rowIndex][j]!=0:

                result[j]=rowIndex 
                colcount += 1  

        if colcount == matrix.shape[1]:
            break 

    return result


def genSigMatrix(matrix,k):

    '''
    generate the signature matrix 

    :param matrix : the input matrix 
    :param k : k =n*r n is the number of band
                      r is the number of row in each band 
    '''

    sigMatrix = []

    for i in range(k):
        sig = generateSig(matrix)
        sigMatrix.append(sig)

    return np.array(sigMatrix)

当然我们还有其他的解决办法，比如我们随机选取一行，而不用对我们的整个行进行重拍我们可以向下面这样做。

这个算法的主要思想就是利用随机行数，抽取一行，然后逐列查询，如果改行的这一列元素刚好是1，那么我们就把对应的签名矩阵的列填上我们抽取的行号，不是1的元素的列继续对行遍历，当然我们会删除之前抽取的行号

import numpy as np
import random
import hashlib


def sigGen(matrix):
    """
    * generate the signature vector

    :param matrix: a ndarray var
    :return a signature vector: a list var
    """

    # the row sequence set
    seqSet = [i for i in range(matrix.shape[0])]

    # initialize the sig vector as [-1, -1, ..., -1]
    result = [-1 for i in range(matrix.shape[1])]

    count = 0

    while len(seqSet) > 0:

        # choose a row of matrix randomly
        randomSeq = random.choice(seqSet)

        for i in range(matrix.shape[1]):

            if matrix[randomSeq][i] != 0 and result[i] == -1:
                result[i] = randomSeq
                count += 1
        if count == matrix.shape[1]:
            break

        seqSet.remove(randomSeq)

    # return a list
    return result

此处代码可以参考这里： https://github.com/guoziqingbupt/Locality-sensitive-hashing/blob/master/min_hash.py

通过这一步之后我们得到了我们的signature matrix ，这个时候我们要计算这些signature 是不是能够被映射到同一个bucket 里面。

我们需要把我们的matrix 划分成不同的bands , 每一个band 里面包含有r 行。然后映射到不同的buckets 里面，经过我们的分析，我们知道如果两个签名是相似的，那么他们会被映射到同一个buckets 里面。这个时候我们LSH避免了两两比较，这个时候LSH极大的提高了运算的效率。

def minHash(input_matrix, b, r):
    """

    map the sim vector into same hash bucket
    :param input_matrix:
    :param b: the number of bands
    :param r: the row number of a band
    :return the hash bucket: a dictionary, key is hash value, value is column number
    """

    hashBuckets = {}

    # permute the matrix for n times
    n = b * r

    # generate the sig matrix
    sigMatrix = sigMatrixGen(input_matrix, n)

    # begin and end of band row
    begin, end = 0, r

    # count the number of band level
    count = 0

    while end <= sigMatrix.shape[0]:

        count += 1

        # traverse the column of sig matrix
        for colNum in range(sigMatrix.shape[1]):

            # generate the hash object, we used md5
            hashObj = hashlib.md5()

            # calculate the hash value
            band = str(sigMatrix[begin: begin + r, colNum]) + str(count)
            hashObj.update(band.encode())

            # use hash value as bucket tag
            tag = hashObj.hexdigest()

            # update the dictionary
            if tag not in hashBuckets:
                hashBuckets[tag] = [colNum]
            elif colNum not in hashBuckets[tag]:
                hashBuckets[tag].append(colNum)
        begin += r
        end += r

    # return a dictionary
    return hashBuckets

这里我们有一个技巧，我们可以把我们的桶设置为一般的hash 函数，比如说md5,sha256 等等。

这个时候我们记录列号，我们把hash 值作为我们字典的键，把列号作为值来计算。
一个字典里面如果，一个键对应的元素是大于两个的，我们则认为找到了相似的样本。

欧式空间：p稳定哈希

p稳定分布

定义：一个分布$D$称为$p$稳定分布，如果对于任意$n$个实数$v_1, v_2, \dots, v_n$和符合$D$分布的$n$个独立同分布的随机变量$X_1, X_2, \dots, X_n$，都存在一个$p \geq 0$，使得$\sum_i v_iX_i$和$(\sum_i |v_i|^p)^{1/p}X$具有相同的分布，其中，$X$是一个满足$D$分布的随机变量。

目前，根据相关文献，在$p \in (0, 2]$这个范围内存在稳定分布。我们最常见的是$p = 1$以及$p = 2$时的情况。

$p = 1$时，这个分布就是标准的柯西分布。概率密度函数：$c(x) = \frac{1}{\pi} \frac{1}{1 + x^2}$
$p = 2$时，这个分布就是标准的正态分布。概率密度函数：$c(x) = \frac{1}{\sqrt{2\pi}} e^{-x^2/2}$

当然，$p$值不是仅能取$1$和$2$。$(0, 2]$中的小数也是可以的。p稳定分布有什么作用呢，我们为什么在这里提出来？它有一个重要的应用，就是可以估计给定向量$v$在欧式空间下的$p$范数的长度，也就是$||v||_p$。

可以这样实现：对于一个向量$v$（相当于上面公式中的$(v_1, v_2, \dots, v_n)$），现在从p稳定分布中，随机选取$v$的维度个随机变量（相当于上面公式中的$X_1, X_2, \dots, X_n$）构成向量$a$，计算$a\cdot v = \sum_i v_iX_i$，此时，$a\cdot v$与$||v||_pX$同分布。我们就可以通过多给几个不同的向量$a$，多计算几个$a\cdot v$的值，来估计$||v||_p$的值。

在p稳定的局部敏感hash中，我们将利用$a\cdot v$可以估计$||v||_p$长度的性质来构建hash函数族。具体如下：

将空间中的一条直线分成长度为$r$的，等长的若干段。
通过一种映射函数（也就是我们要用的hash函数），将空间中的点映射到这条直线上，给映射到同一段的点赋予相同的hash值。不难理解，若空间中的两个点距离较近，他们被映射到同一段的概率也就越高。
之前说过，$a\cdot v$可以估计$||v||_p$长度，那么，$(a \cdot v_1 - a \cdot v_2) = a (v_1 - v_2)$也就可以用来估计$||v_1 - v_2||_p$的长度。
综合上面的3条，可以得到这样一个结论：空间中两个点距离：$||v_1 - v_2||_p$，近到一定程度时，应该被hash成同一hash值，而向量点积的性质，正好保持了这种局部敏感性。因此，可以用点积来设计hash函数族。

文献提出了这样一种hash函数族：

$\begin{equation} h_{a, b}(v) = \lfloor\frac{a \cdot v + b}{r}\rfloor \end{equation}$

其中，$b\in(0, r)$是一个随机数，$r$是直线的分段长度，hash函数族的函数是依据$a$,$b$的不同建立的。

可见，若要空间中的两个点$v_1$,$v_2$映射为同一hash值，需要满足的条件为：这两点与$a$的点积加上随机值b的计算结果在同一条线段上。

现在估计一下这个概率。设$c = ||v_1 - v_2||_p$，则$a \cdot v_1 - a \cdot v_2$与$cX$同分布。概率公式如下：

$\begin{equation} p(c) = Pr[h_{a, b}(v_1) = h_{a, b}(v_2)] = \int_{0}^{r} \frac{1}{c} f_p(\frac{t}{c})(1 - \frac{t}{r})dt \end{equation}$

当$r$的值取定的时候，这个公式可以看做是一个仅与$c$的取值相关的函数。$c$越大，函数值越小（碰撞的概率越低）；$c$越小，函数值越大（碰撞的概率越高）。相关的具体证明参见参考文献。

但是关于$r$的取值，在文献中，并没有给出一个确定的值。这需要我们根据$c$与$p$的值来设定。

试想，因为我们设定的LSH是$(r_1, r_2, p_1, p_2)$敏感的，所以，当$r_2 / r_1 = c$的时候（这里的$c$可以看做是一个标准），也就不难推出：$p_1 = p(1), p_2 = p(c)$

文献指出，选取合适的$r$值，能够使得$\rho = \frac{ln(1/p_1)}{ln(1/p_2)}$尽可能地小。这里面的理论非常复杂，所以，在这里，我给出文献的一张图：

这是在L2范数下，$ρ$和最优的$r$的关系，可以看出以下几点信息：

$c$的取值不同时，即便对于相同的$r$，$ρ$也不同
在$r$的取值大于某一点后，$ρ$对$r$的变化不再敏感
虽然从图像的趋势上看，$r$越大，$ρ$越小，但是，$r$的取值也不能太大，否则会导致$p_1$,$p_2$都接近于1，增大搜索时间（我觉得这就导致LSH没意义了）

所以，可见$r$的取值要根据实际情况，自己设定。我有个想法，不知道在具体实施的时候合不合理：可以先确定一下$r_1$,$r_2$的取值，然后选择合适的$r$，使得$p_1$,$p_2$都达到我们的要求即可。

p稳定分布LSH相似性搜索算法

该算法同样是简单的AND then OR的逻辑，与我们上面说的min-hash的思路是一致的。

现在假设$P = Pr[h_{a, b}(v_1) = h_{a, b}(v_2)]$（这个概率可以由上面的积分公式算出），那么，两条数据被认为是近邻的概率是：

$\begin{equation} 1 - (1 - P^k)^L \end{equation}$

构建hash table时，如果把一个函数组对向量的一组hash值$(h_1(v_i), h_2(v_i), \dots , h_k(v_i))$作为hash bucket的标识，有两个缺点：1. 空间复杂度大；2. 不易查找。为了解决这个问题，我们采用如下方法：

先设计两个hash函数：$H_1$，$H_2$：

$H_1$：$Z^k \to \{0, 1, 2, \dots, size - 1\}$，简单说就是把一个$k$个数组成的整数向量映射到hash table的某一个位上，其中size是hash table的长度。
$H_2$：$Z^k \to \{0, 1, 2, \dots, C\}$，$C = 2^{32} - 5$，是一个大素数。

这两个函数具体的算法如下，其中，$r_i, r_i^{‘}$是两个随机整数。

$\begin{equation} H_1(x_1, \dots, x_k) = ((\sum_{i = 1}^{k} r_ix_i) \mod C) \mod size\\ H_2(x_1, \dots, x_k) = (\sum_{i = 1}^{k} r_i^{'}x_i) \mod C \end{equation}$

我们把$H_2$计算的结果成为一个数据向量的“指纹”，这也好理解，它就是由数据向量的$k$个hash值计算得到的。而$H_1$相当于是数据向量的指纹在hash table中的索引，这个算法跟基本的散列表算法是一个思路，不啰嗦了。

通过这两个新建的函数，我们可以将hash table的构建步骤作以下详细说明：

从设计好的LSH函数族中，随机选取$L$组hash函数，每组由$k$个hash函数构成，记为$\{g_1(\cdot), g_2(\cdot), \dots, g_L(\cdot)\}$，其中$g_i(\cdot) = (h_1(\cdot), h_2(\cdot), \dots , h_k(\cdot))$
每个数据向量经过$g_i(\cdot)$被映射成一个整型向量，记为$(x_1, \dots, x_k)$。
将2步生成的$(x_1, \dots, x_k)$通过$H_1, H_2$计算得到两个数值：$index, fp$，前者是hash table的索引，后者是数据向量对应的指纹。这里，为了方便描述这种hash table的结构，我将我们用的hash table的结构画出，如图所示。
若其中有数据向量拥有相同的数据指纹，那么必然会被映射到同一个hash bucket当中

补充：根据读者DawnRanger的提议，用$L$组hash函数计算数据指纹及相应索引的时候，可能出现两个不相近的数据被两组不同的hash函数族映射为相同数据指纹的情况。这显然增加了误报率，所以一种可行的改进方法为：建立$L$个hash表，两个数据只要在任意一个hash表内被映射为相同的指纹，就认为二者是相近的。其实就是多个hash table加上OR策略。

通过上图，就不难理解这里的数据结构了，数据向量由$H_2$生成数据指纹（图中的$fp_{01},fp_{12}$这些），每个数据指纹就是一个hash bucket的标识，存储着对应的数据向量。

可以得到相同$H_1(\cdot)$值的hash bucket我们放在一个链表中，这个链表对应的就是hash table中相应的索引。

经过上述组织后，查询过程如下：

对于查询点query，
使用k个哈希函数计算桶标号的k元组；
对k元组计算H1和H2值，
获取哈希表的H1位置的链表，
在链表中查找H2值，
获取H2值位置上存储的样本
Query与上述样本计算精确的相似度，并排序
按照顺序返回结果。

上述就是E2LSH。

E2LSH方法存在两方面的不足：首先是典型的基于概率模型生成索引编码的结果并不稳定。虽然编码位数增加，但是查询准确率的提高确十分缓慢；其次是需要大量的存储空间，不适合于大规模数据的索引。E2LSH方法的目标是保证查询结果的准确率和查全率，并不关注索引结构需要的存储空间的大小。E2LSH使用多个索引空间以及多次哈希表查询，生成的索引文件的大小是原始数据大小的数十倍甚至数百倍。

p稳定分布哈希码

E2LSH可以说是分层法基于p稳定分布的应用。另一种当然是转换成哈希码，则定义哈希函数如下：

其中，$a$和$v$都是$d$维向量，$a$由正态分布产生。同上，选择$k$个上述的哈希函数，得到一个$k$位的hamming码，按照”哈希技术分类”中描述的技术即可使用该算法。

余弦空间：随机超平面

cosine相似性对应的LSH hash function为：$H(V) = sign(V·R)$，$R$是一个随机向量。$V·R$可以看做是将$V$向$R$上进行投影操作。其是$(d_1,d_2,(180-d_1)180,(180-d_2)/180)-sensitive$的。

当相似性度量是cosine相似性的时候，第一步的hash function是一个叫随机超平面（Random Hyperplanes）的东西，就是说随机生成一些超平面，哈希方法是看一个特征向量对应的点，它是在平台的哪一侧：

这个可以直观地想象一下，假设有两个相交的超平面，把空间分成了4个区域，如果两个特征向量所对应的点在同一域中，那么这两个向量是不是挨得比较近？因此夹角就小，cosine相似度就高。对比一下前面用Jaccard相似度时Signature
Matrix的生成方法，那里是用了三个转换，在这里对应就是用三个随机超平面，生成方法是：对于一个列$C$（这里因为是用cosine相似度，所以列的值就不一定只是0，1了，可以是其它值，一个列就对应一个特征向量），算出该列对应的特征向量的那个点，它是在超平面的哪个侧，从而对于每个超平面，就得到+1或者-1，对于三个超平面，就得到三个值，就相当于把原来7维的数据降到3维，和前面用Jaccard相似度时的情况是不是很像？得到Signature Matrix后，就进行LSH。

曼哈顿距离

曼哈顿距离又称L1范数距离。其具体定义如下：

在$n$维欧式空间$R^n$中任意两点$A=(a_1,a_2,…,a_n)$，$B=(b_1,b_2,…,b_n)$，他们之间的曼哈顿距离为：

$Manhattan(A,B)=\sum_{i=1}^n{|a_i-b_i|}$

对数据集$P$所有的点，令$C$作为所有点中坐标的最大值$m$，也就是上限。下限是$0$，这个很明显。然后就可以把$P$嵌入汉明空间$H^{d’}$。其中$d’=nC$，此处$n$是数据点在原来欧式空间的维度。对于一个点$p=(x_1,x_2,…,x_n)$如果用$H^{d’}$空间的坐标表示就是：

$v(p)=Unary_C(x_1)Unary_C(x_2)...Unary_C(x_n)$

$Unary_C(x)$是一串长度为$C$二进制的汉明码，其意思是前$x$位为$1$，后$C−x$位为$0$。举个例子，$C$若为5，$x$为3，则$Unary_5(3)=11100$。$v(p)$是多个$Unary_C(x)$拼接而成。此时可以发现对于两点$p$,$q$他们之间的曼哈顿距离和通过变换坐标后的汉明距离是一样的。到此处，我们可以针对汉明距离来定义一族哈希函数。

汉明距离下的LSH哈希函数

给定一族哈希函数$H$，对其中任意一个$h∈H$：

$h(p) = \begin{cases} 0, & \text{若v(p)的第$r$ 位为0} \\ 1, & \text{若v(p)的第$r$ 位为1} \\ \end{cases}$

其中$r$是一个从$1$到$d′$之间产生服从均匀分布的随机整数。

对于这个哈希函数我们可以发现若$p$，$q$的曼哈顿距离为$d$，则他们被哈希成相同哈希值的概率为$Pr_H[h(q)=h(p)]=\frac{nC-d}{nC}$，从而这个哈希函数是具有$(r_1,r_2,\frac{nC-r_1}{nC},\frac{nC-r_2}{nC})$敏感性的。

AND&OR理解：

举一个实例帮助理解。

数据点集合$P$由以下6个点构成：
　　 A=(1,1)　　 B=(2,1)　　 C=(1,2)
　　 D=(2,2)　　 E=(4,2)　　 F=(4,3)

可知坐标出现的最大值是$4$，则$C=4$。维度为$2$，则$n=2$，显然$nC=8$。我们进行8位汉明码编码。

$v(A)=10001000v(A)=10001000v(A)=10001000\\ v(B)=11001000v(B)=11001000v(B)=11001000\\ v(C)=10001100v(C)=10001100v(C)=10001100\\ v(D)=11001100v(D)=11001100v(D)=11001100\\ v(E)=11111100v(E)=11111100v(E)=11111100\\ v(F)=11111110v(F)=11111110v(F)=11111110$

若我们现在采用$k=2$，$l=3$生成哈希函数。
$G$由$g_1$，$g_2$，$g_3$构成。每个$g$由它对应的$h_1$,$h_2$构成。
假设有如下结果。
$g_1$分别抽取第2，4位。
$g_2$分别抽取第1，6位。
$g_3$分别抽取第3，8位。
哈希表的分布如下图所示。

若此时我们的查询点$q=(4,4)$，可以计算出$g_1(q)=[1,1]^T$，$g_2(q)=[1,1]^T$，$g_3(q)=[1,1]^T$。则分别取出表1，2，3的11，11，11号哈希桶的数据点与$q$比较。依次是C,D,E,F。算出距离$q$最近的点为F。当然这个例子可能效果不是很明显。原始搜索空间为6个点，现在搜索空间为4个点。对于刚接触LSH的人会有个疑问。如果不同哈希表的数据点重复了怎么办，会不会增加搜索空间的大小。首先要说的是这个概率很小，为什么呢。试想假设两个不同哈希表的哈希桶对$q$的查询有相同点，这意味着在两张哈希表中这个点与$q$都有相同哈希值。如果使用单个哈希函数$q$和此点被哈希到一起的概率为$p_0$。则刚才那个事件发生的概率为$p_0^{2k}$，这个概率是很小的。当然也有很多办法可以解决这个问题。这不是一个大问题。我在实际运用时$k$大概总是取10-20之间的数，$l$大致20-100左右。每次对$q$进行候选点匹配时，候选的样本点数量已经是$P$的十分之一到百分之一了。就好比$P$有10000个数据点，使用暴力匹配要遍历整个数据集，使用LSH可能只要匹配100到1000个点就可以了。而且往往我都能找到最近点。即使找不到最近的，总体成功率也在90%-98%左右。

汉明空间

在对图像进行匹配时，通常是将图像的描述子与数据中的图像描述子进行匹配实现的。在实时应用中，通常是使用二进制描述子，比如BIREF、BRISK、ORB等。对于二进制描述子使用的是Hamming距离。

对于二进制描述子，哈希函数就是直接选择描述子的某一个比特位，通过若干个哈希函数选择出来的位的级联，就形成了一个哈希键了。通过对这个哈希键对数据库中的描述子进行索引，即形成了一个哈希表，选择若干个哈希表来增大找到近似最近邻的概率。

Hamming distance对应的LSH hash function为：$H(V)$ = 向量$V$的第$i$位上的值，其是$(d_1,d_2,1-d_1/d,1-d_2/d)-sensitive$。

LSH应用

LSH的应用场景很多，凡是需要进行大量数据之间的相似度（或距离）计算的地方都可以使用LSH来加快查找匹配速度，下面列举一些应用：

查找网络上的重复网页
互联网上由于各式各样的原因（例如转载、抄袭等）会存在很多重复的网页，因此为了提高搜索引擎的检索质量或避免重复建立索引，需要查找出重复的网页，以便进行一些处理。其大致的过程如下：将互联网的文档用一个集合或词袋向量来表征，然后通过一些hash运算来判断两篇文档之间的相似度，常用的有minhash+LSH、simhash。
查找相似新闻网页或文章
与查找重复网页类似，可以通过hash的方法来判断两篇新闻网页或文章是否相似，只不过在表达新闻网页或文章时利用了它们的特点来建立表征该文档的集合。
图像检索
在图像检索领域，每张图片可以由一个或多个特征向量来表达，为了检索出与查询图片相似的图片集合，我们可以对图片数据库中的所有特征向量建立LSH索引，然后通过查找LSH索引来加快检索速度。目前图像检索技术在最近几年得到了较大的发展，有兴趣的读者可以查看基于内容的图像检索引擎的相关介绍。
音乐检索
对于一段音乐或音频信息，我们提取其音频指纹（Audio Fingerprint）来表征该音频片段，采用音频指纹的好处在于其能够保持对音频发生的一些改变的鲁棒性，例如压缩，不同的歌手录制的同一条歌曲等。为了快速检索到与查询音频或歌曲相似的歌曲，我们可以对数据库中的所有歌曲的音频指纹建立LSH索引，然后通过该索引来加快检索速度。
指纹匹配
一个手指指纹通常由一些细节来表征，通过对比较两个手指指纹的细节的相似度就可以确定两个指纹是否相同或相似。类似于图片和音乐检索，我们可以对这些细节特征建立LSH索引，加快指纹的匹配速度。

sim-hash

Simhash 是一种用单个哈希函数得到文档最小哈希签名的方法，过程为：

将一个$f$维的向量$V$初始化为$0$；$f$位的二进制数$S$初始化为0；
对每一个特征：用传统的 hash 算法对该特征产生一个$f$位的签名$b$。对 $i=1$ 到$f$：
1. 如果$b$的第$i$位为$1$，则$V$的第$i$个元素加上该特征的权重；
2. 否则，$V$的第$i$个元素减去该特征的权重。
如果$V$的第$i$个元素大于$0$，则$S$的第$i$位为$1$，否则为$0$；
输出$S$作为签名。

对两篇文档，它们的 Simhash 值之间不同位的个数越少（即汉明距离越小），它们之间的 Jaccard 相似度越高。

例子

为了便于理解尽量不使用数学公式，分为这几步：

分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5）雇员（3）称（1）内部（2）有（1） 9架（3）飞碟（5）曾（1）看见（3）灰色（4）外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”，把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。

整个过程图为：

大家可能会有疑问，经过这么多步骤搞这么麻烦，不就是为了得到个01字符串吗？我直接把这个文本作为字符串输入，用hash函数生成 0 1 值更简单。其实不是这样的，传统hash函数解决的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远；hashmap也是用于键值对查找，便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hashcode却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。

通过simhash计算结果为：
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为：
1111111111111111111111111111111110001000001100110100111011011110
1010010001111111110010110011101

　　大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hashcode却不能做到，这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明，“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

　　现在通过这样的转换，我们把库里的文本都转换为simhash 代码，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢？难道是比较两个simhash的01有多少个不同吗？对的，其实也就是这样，我们通过汉明距离（Hamming distance）就可以计算出两个simhash到底相似不相似。两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则汉明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。

　　为了高效比较，我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code，然后和内存里的simhash code 进行比较，测试100w次计算在100ms。速度大大提升。

几何意义

这个算法的几何意义非常明了。它首先将每一个特征映射为f维空间的一个向量，这个映射规则具体是怎样并不重要，只要对很多不同的特征来说，它们对所对应的向量是均匀随机分布的，并且对相同的特征来说对应的向量是唯一的就行。比如一个特征的4位hash签名的二进制表示为1010，那么这个特征对应的 4维向量就是(1, -1, 1, -1)T，即hash签名的某一位为1，映射到的向量的对应位就为1，否则为-1。然后，将一个文档中所包含的各个特征对应的向量加权求和，加权的系数等于该特征的权重。得到的和向量即表征了这个文档，我们可以用向量之间的夹角来衡量对应文档之间的相似度。最后，为了得到一个f位的签名，需要进一步将其压缩，如果和向量的某一维大于0，则最终签名的对应位为1，否则为0。这样的压缩相当于只留下了和向量所在的象限这个信息，而64位的签名可以表示多达264个象限，因此只保存所在象限的信息也足够表征一个文档了。

好处

simhash离线计算指纹，方便了大规模数据比较时的消耗，不需要在计算时提取特征进行计算，hash值的可比性很强，只需要比较汉明距离，方便了从海量数据中发掘相似项的实现，试想一个新文档同百万级甚至千万级数据做相似夹角的情况。simhash大大减少了相似项排重的复杂度。

应用

simhash有两个比较典型的应用，一个是网页抓取的排重，一个是检索时相似doc的排重。前者是在大集合中寻找是否具有相似项，后者是对检索的集合进行滤重。

检索集中发现相似项比较简单，就是针对要排重的field离线提取特征，并计算simhash值，然后将检索集中的记录进行两两比较，就是计算汉明距离，两个simhash值异或后求二进制中1的个数就是汉明距离了，这是针对较少的记录。

针对较多的记录，例如抓取时做排重，针对上千万，或数亿的数据，就需要对算法进行改进，因为求simhash的相似性，其实就是计算simhash间的汉明距离。
提到查找算法就不得不提到O(1)的hash表，但是如何让simhash和hash表联系在一起呢？
假如我们认为海明距离在3以内的具有很高的相似性，那样我们就可以用到鸽巢原理，如果将simhash分成4段的话，那么至少有一段完全相等的情况下才能满足海明距离在3以内。同理将simhash分为6段，那么至少要满足三段完全相等，以此类推。

这样我们就可以使用相等的部分做为hash的key，然后将具体的simhash值依次链接到value中，方便计算具体汉明距离。

将64位的二进制串等分成四块
调整上述64位二进制，将任意一块作为前16位，总共有四种组合，生成四份table
采用精确匹配的方式查找前16位
如果样本库中存有2^34（差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本我们可以将这种方法拓展成多种配置，不过，请记住，table的数量与每个table返回的结果呈此消彼长的关系，也就是说，时间效率与空间效率不可兼得，参看下图：

sim-hash与min-hash的比较

sim-hash

Simhash主要做用是使复杂度o(nml)中，使m<<n，即大幅减小搜索空间的作用。例如计算item a的近临(top M)时，只搜索一个特定的近临空间m，而非整个庞大的n空间。

Simhash是通过设计一个hash方法，使要内容相近item生成的hash签名也相近，hash签名的相近程度，也能反映出item间的相似程度。

从降维的脚度看，通过将item预处理为simhash值后，通过计算两者的汉明距离计算相似度。可惜汉明距离并不能完全表征两者的实际相似程度，因而simhash常用于缩小搜索空间，计算item a的top M相似item时，搜索限为汉明距离最近的空间中。例如假设hash在64位，共将有264个hash桶，将所有item预先按hash桶建好索引后，计算item a的top M或满足某域值的相似item时，可从最近的hash桶中搜索，最近的桶为本桶中的其它item，其次为1位不同的其它hash桶，共64个，再次为2位不同的桶，共64*64个…

min-hash

Minhash主要做用是使复杂度o(nml)中，使l<<k，即减小计算两两相似度计算的维数。

由于只取一个hash函数时，只有相等与不等两个结果，对应于原理，也就只有相似与不相似不个结果。取一系列hash函数后，便可以概率性地统计出结果，而取hash函数的个数据，决定将k降维后的维数l，l越大，相似结果与实际相似度越相近，一般10个左右就已经能满足工程需求。

这样数据预处理完后，计算两item间的复杂度，就等于计算最小Minhash相同的概率了。

PS：在工程中，不容易找一系列的hash函数，由hash母函数生成的一系列hash函数可能相关，将降低Minhash的经度。

sim-min-hash

为了减少误报，Sim-min-Hash中采用汉明嵌入进行验证。与视觉单词相关联的汉明签名附加到相应的散列键或sketches。与min-Hash相同的处理流程，在交叉匹配阶段进行具有汉明签名的验证。这种简单的验证将得到的匹配（sketches级别）的数量减少了至少一个数量级，这又降低了将匹配的sketches聚合成图像匹配的复杂性。

这个……还没看懂……