哈希排序算法优化

哈希学习在解决大规模数据的近似最近邻搜索问题时，可以获得较好的时间性能，但是如何提高哈希学习的精度，一直是研究人员关注的问题，不仅需要关注在哈希编码过程中原始空间与投影空间之间的相似性保持，还需要关注哈希码的排序问题。

哈希排序指的是在某个距离空间对哈希码进行排序的问题，如最常用的基于汉明距离的二进制哈希码排序。但是，基于汉明距离的二进制码排序无法解决那些与查询点的汉明距离相同的二进制码的排序问题；而且，随着汉明距离的增加，与查询点具有相同汉明距离的二进制码的个数呈指数增长。基于以上弊端，近年来哈希排序得到了人们的关注，主要研究工作集中在基于加权汉明距离和基于非对称距离的哈希排序。以下分别简要介绍基于汉明距离的哈希排序、基于加权汉明距离的哈希排序和基于非对称距离的哈希排序。

一、基于汉明距离的哈希排序

如前所述，二进制哈希通过将每个数据集点映射成紧凑的二进制代码，从而将原始数据空间中的相似数据点映射到汉明距离空间中的相似二进制代码。基于汉明距离的哈希排序返回二进制哈希码空间中与查询点的汉明距离小于某个阈值的数据点，大多数二进制哈希是通过基于汉明距离对实现哈希排序的，如局部敏感哈希、语义哈希、谱散列等。

虽然基于汉明距离的哈希排序以其简单易用得到了广泛的应用，但是在实际应用中存在局限性，例如，局部敏感哈希通常需要较长的代码才能获得良好的精度，但是长代码导致低召回率，基于汉明距离的排序会导致查询时间过长，增加内存占用。此外，由于汉明距离是离散的，在实际应用中存在由于某些数据点与查询点具有相同的汉明距离而难以排序的问题。

二、基于加权汉明距离的哈希排序

针对基于汉明距离的哈希排序难以处理与查询点具有相同汉明距离的数据点的排序问题，为了提高检索精度，人们提出基于加权汉明距离的哈希排序。代表性研究工作包括:X.Zhang等人(2012)提出一种基于主成分分析的哈希码查询敏感排序算法(QsRank)，该算法取目标邻域半径ε以及将查询点的原始特征作为输入，对哈希码空间中邻域半径ε内目标的统计特性进行建模；与基于汉明距离的排序不同，QsRank算法并不直接将查询点压缩为二进制哈希码，造成的信息损失更小，所得到的排序比汉明距离更准确，并且可以灵活性调整精度和效率之间的平衡。L.Zhang等人(2013)提出一种加权汉明距离排序算法(WhRank)，该算法通过给不同的哈希位分配不同等级的权重，以实现更细粒度的排序，从而提高二进制哈希的性能。与QsRank相比，WhRank可应用于目前大多数二进制哈希方法，且不受邻域半径的限制，因而适用性更强。此外，Liu X.等人(2016)提出一种构建具有多视图的多哈希表的通用方法，从哈希比特位和哈希表两个方面考虑生成细粒度的排序结果，一方面弥补了哈希量化导致的部分信息丢失，另一方面自适应地结合来自不同源或视图的辅助信息，能够有效提高搜索性能。(www.xing528.com)

三、基于非对称距离的哈希排序

在大规模检索中，大多数嵌入算法采用的都是基于对称距离的哈希排序方法，但是在实际应用中，非对称距离排序可能产生更高的检索准确率。这方面的研究包括:A.Gordo等人(2014)提出了两种可以广泛应用于二进制嵌入算法的非对称距离，并且证明了这两种算法比对称汉明距离显著提高了检索精度；Yueming Lv等人(2015)提出的非对称哈希方案中，使用紧凑哈希码减少存储需求，使用长哈希码提高检索精度，通过计算查询的长哈希码和存储图像的紧凑哈希码之间的汉明距离实现图像检索，以产生高精度和召回率；此外，Zhenyu Weng等(2016)提出了一种基于超球面的非对称距离检索方法；Yuan Cao等人(2017)提出了两种加权非对称距离算法，即基于Otsu阈值的算法(WoRank)和基于分数计算的算法(WsRank)等。

表7-1从哈希函数、相似性保持、Sgn函数、距离函数、编码方式、监督方式6个方面，对目前代表性的哈希方法进行了总结和归纳。

表7-1　代表性哈希方法

其它关于哈希的研究包括分布式哈希和跨模态哈希等。其中，分布式哈希编码方法的思想是将某种已有的量化或哈希编码方法扩展到分布式环境中，跨模态哈希则研究从多种模态数据中搜索具有相同语义类别的数据。总之，哈希方法的发展体现了从数据独立到数据依赖、从传统的投影加量化到基于深度学习的端到端的方式、从单模态到多模态、从单机到分布式的趋势。