基于内容的音频检索技术的优化方法

从高维空间的角度来看，检索过程就是给定任意一个查询点（向量）在数据库中找到与查询接近的点，并能保证以较高的概率返回与查询最接近的点。从概念上讲，这很容易通过穷举法来实现：计算数据库中的所有点与查询之间的距离即可选出最接近的点。然而，如果数据库的规模很大或数据的维数很高时，穷举法的时间代价往往无法接受。因此，需要寻找不依赖于数据库线性搜索的检索方法。

由于索引的复杂度会随着数据维数的增加而呈指数级增长，出现常见的“维度诅咒”问题。而音频数据不仅有维度高的特征，还包含有时序信息。这要求在选择索引算法的时候不仅要解决数据维数高的问题，还要在索引中体现时序性，这进一步增加了音频数据索引构建的难度。

为解决维数诅咒问题，许多学者提出了各种索引构建算法。但提出的算法与顺序扫描的效果相比，提升效率较小。在一定情况下索引算法效率甚至低于顺序扫描。近年来，为了解决高维向量的搜索时空消耗问题，人们开始转换角度，关注近似搜索问题。近似最近邻搜索在大多数情况下具有与确切搜索同样好的结果，尤其是当距离度量标准设计合理，能够准确捕捉用户的需求时，近似搜索在时间复杂度方面的优势更符合应用需求。

早在1998年，Indyk等便提出了局部敏感哈希（locality-sensitive Hashing，LSH）方法，近年来这种方法开始应用于音频信息检索领域。LSH的想法比较简单，如果空间中的两个点距离很近，经过投影操作后，这两个点的投影也会比较靠近。因此，如从许多不同的方向进行投影，并记录与查询“临近”的点，那些在多个投影中与查询“临近”的点，很可能就是在投影前与查询靠近的点。

LSH是近年来比较活跃的研究领域，其在音频检索中的应用研究也引起越来越多的关注。下面对Indyk等提出的LSH进行介绍。(www.xing528.com)

定义函数族ζ=｛g：S→Uk｝，其中g（·）的定义如下所示：

g（·）就是由k个哈希函数组成的哈希函数组。对于一个向量v，利用g（·）中的k个哈希值h1（v），…，hk（v）生成哈希索引键值。从ζ中随机并且独立均匀地选取L个函数g1，…，gL作为哈希函数组，然后利用这一组函数创建对应的哈希索引。

LSH的本质是将一个高维空间的向量量化为一维数值，将每个向量独立地量化L次，并将L个结果全部加入索引中，只要其中的一个能被检索到就能将结果正常检出，从而保证算法有较高的召回率。LSH是一种近似搜索方法，不仅可以应用于音频样例检索，也可以应用于网页检索、图像检索、音乐检索等诸多领域，不同领域应用的差别主要在于特征向量的选取和构建。