基于指印的音乐检索原理详述
在前面的博客基于指纹的音乐检索中，我们介绍了其基本流程，但是对于检索的具体实现并未做过多介绍，本博客将详细叙述检索的具体原理和实现。
1 搜索引擎的工作原理
在介绍音乐检索的原理之前，我们先介绍一下搜索引擎的工作原理，这是因为音乐检索的工作原理和搜索引擎的工作原理非常类似。
我们使用搜索引擎的时候，通常是这个流程：输入一些关键词，提交给搜索引擎，搜索引擎通过后台分析返回与关键词最相关的网页。这个过程非常快，往往只有几毫米。但是目前互联网上存在的网页总数有数百亿之多，搜索引擎是如何在这么短的时间内找到用户需要的网页的呢？这确实很神奇。
最朴素的方法肯定是一个一个网页进行相似度匹配，每一个文件计算一个相似度，然后对相似度进行排序，返回最相似的网页。但是这也是最笨的方法，这需要每次查询都需要遍历一般所有的网页，复杂度非常高。搜索引擎通过采用一种叫倒排索引的结构避免了朴素的匹配，在此之前我们先介绍一下朴素检索的实现方法。
按照朴素方法，我们需要根据网页文件构造索引，如图一所示。每一个网页都会首先进行分词，然后统计不同词的词频或者其他特征。有了这个索引结构，就可以设计最朴素的搜索引擎。当用户输入的关键词进入搜索引擎之后，就会将关键词进行特征转换，转换成一个带有权值的特征向量，之后就可以和每一个网页的特征向量进行相似度匹配，例如余弦相似性度量等，最后对匹配的结果排序即可。
图一 网页的词组索引结构
倒排索引这个名词听着很玄乎，其实非常容易理解。朴素方法采用网页的索引结构，构造单词的统计信息；倒排索引则相反，以单词为索引结构，构造网页的统计信息，如图二所示。
图二 倒排索引示意图
在倒排索引结构中，每一个单词都对应一个倒排列表，倒排列表记载了出现过某个单词的所有网页的列表和单词在该网页中出现的位置信息或者词频。例如，单词1出现在网页6和10中，词频分别是a1和a2。
搜索引擎在获得用户输入的关键词之后，就查找关键词对应的倒排索引表，然后将多个关键词的倒排索引表求交，获得出现过所有关键词的网页，然后对这些网页进行相似度计算。可以看出，通过采用倒排索引结构，使需要匹配的网页数量急剧减少，因而大大加快了搜索的速度。
上面是最简单的搜索引擎原理，如果大家想深入了解搜索引擎，可以参看《这就是搜索引擎》一书，该书详细介绍了搜索引擎的各个部分和检索原理。下面开始介绍基于指纹的音乐检索原理。
2 基于指纹的音乐检索工作原理
基于指纹的音乐检索工作原理和搜索引擎非常相似，也是构造一个倒排索引结构，不过不是单词的倒排索引，而是指纹的倒排索引。在基于指纹的音乐检索 中，我们介绍了指纹的构造，在此不做过多介绍。指纹可以看做搜索引擎检索中的关键词，但是与关键词不同，每个指纹代表的信息量较少，所以在音乐检索中需要提取非常多的指纹完成单次检索。例如，15s的片段往往需要提取几万个指纹才能查找到正确的音乐。这就意味着搜索引擎几个关键词的单次检索在音乐检索中变成了几万个指纹的单次检索，检索时间大大增加。
每个指纹都是一个整数，根据指纹的构造不同，可能需要24到30位不等，所以可以利用一个int型整数存储每一个指纹。这样所有指纹的空间就限定于一个int型整数所表示的范围，也即0到4G。当音乐库较小时，所有音乐产生的不同指纹数也较少，为了避免空间浪费，存储所有的指纹可以采用散列表形式，如图三所示。
图三 散列表形式的指纹检索结构
当音乐库非常大时，几乎所有的指纹都可能会出现，这时采用散列表结构就没有什么优势，可以直接分配一个大数组来存放所有的指纹，然后每一个指纹都指向一个该指纹对应的倒排列表，如图四所示。在图四中假定每一个指纹的位数是24位，则需要分配一个长度是224的数组，然后每一个指纹都指向一个倒排列表。倒排列表中存储的是音乐id和该指纹在该首音乐中出现的位置。
图四 基于指纹的倒排索引表
获得图四的倒排索引结构之后，检索过程就比较容易了。但是过程却和搜索引擎不同，搜索引擎需要对不同关键词的倒排列表求交集，对交集内的网页进行相似度计算。基于指纹的音乐检索则需要一个间接的匹配过程，匹配过程如下：
- 将客户端传递的音频提取指纹，每个指纹伴随有一个时间属性；
- 对每一个提取的指纹都查找倒排索引表，获得该指纹对应的倒排列表；
- 将倒排列表中每一个音乐对应的时间和提取的指纹对应的时间进行相减，如果时间差大于零，则保存该时间差到图五所示的对应音乐中；
- 对每首歌中的时间差进行排序；
- 统计每首歌中时间差相同的个数，并返回个数最多的音乐。
图五 统计匹配的相似度
基于指纹的音乐检索和搜索引擎相比，复杂度大增，主要体现在两个方面：首先，针对客户端录制的音频，提取的指纹往往上万，而这上万个指纹都需要访问倒排索引表，这意味着一次音乐检索可以完成上万次搜索引擎的检索；其次，由于单次检索需要上万次访问倒排索引表，所以无法对音乐求交，因为求交的结果必然为零，我们只能将倒排列表中对应的音乐时间和提取指纹对应的时间相减，然后统计每一首音乐中不同时间差的个数，然后将个数作为匹配的结果。正是由于上面这两个因素，所以单机上的曲库做得不能太大，并且每一个指纹对应的倒排列表也要限制长度。