微信摇一摇搜歌技术原理分析

1、WORWOR 格式 1 专业资料整理 华北水利水电大学 微信摇一摇搜歌技术原理分析 WORWOR 格式 2 专业资料整理 姓名： 刘勇 学号： 201215708 WORWOR 格式 3 专业资料整理 摘要：给出一首歌利用 cool edit 等多轨录音和音频处理软件得出语谱图， 然后利 用傅里叶变换得到语音波形图，从中找到多个“音乐指纹” p，然后匹配哈希表 匹配已知的音乐指纹，如果相同即为同一首歌；而经过版本改进之后的 Local Sensitive Hash 局部敏感哈希基于快速近邻搜索，抗噪性更强。 关键词：傅里叶变换；音乐指纹；哈希表；局部敏感哈希 1、提取音乐指纹 首先，一首MP3

2、 用cool edit 之类的软件打开将是下图这样，以陈百强的情 人片段距离，以下波形图示 20秒片段。 WORWOR 格式 4 专业资料整理 叫做谱图(spectrogram)，纵坐标是频率，横坐标是时间。亮的地方代表能量高。每一首乐曲 因为乐器、 音高不同， 所以它们谱图都不同。 哪怕是不同的人用同一接下来对这个波形做短时傅里叶变换 (SFFT)，可以得到下面这个类似乐谱的图， WORWOR 格式 5 专业资料整理 PS:傅里叶变换是可逆的，也可以将语谱图转化为波形放出来听，这也是现代 频谱作曲流派的方法。 既然两首曲子亮的位置不同， 我们就可以根据亮点来区分两首歌一不一样。 如下 图找到

3、谱图上若干个最亮的点，比如下图找到了点 1 ，点2 ，点3。它们的音高 伴奏，甚至相同的人分开两次唱， 同上。 语谱图都是有细微差别的， 体现在亮的位置不 WORWOR 格式 6 专业资料整理 记作y1,y2,y3, 点1和点2的横坐标距离记作 dx1，点2和点3的横坐标距 离记作dx2。我们用向量p =y1,y2,y3,dx1,dx2 作为这个片段的特征，我们 将p叫做音乐指纹。如果两首歌的p相同，那么我们就认为这两首个一样啦！否则就不 一样。 2、音乐指纹匹配哈希表WORWOR 格式 7 专业资料整理 事实上为了稳定和抗噪，我们可能会对一首歌提取更多的指纹 P，比如100 个 录音环境经常

4、会有噪音， 如果匹配中了 50个以上，我们就认为是同一首歌。而那些不一样 的歌，基本上匹配数不会超过个位数。 这就是基本原理了，是不是很简单！ 当然另一个问题就是大数据量了， 酷狗的音乐库动辄上百万， 总不可能对用户录制的片段一 条一条去匹配吧？所以这里我用的不是逐条匹配，而是哈希表匹配。 总的说来就是把每个 p映射成不同整数，比如 p =24,8,46,13,29 可以映射 成14335621。每个p对应着一首歌的某个位置，建库的时候把所有曲目的指纹都插到这 个巨大的哈希表中。如下所示。 WORWOR 格式 8 专业资料整理 那么加入我们想查找14335621对应的曲子，就可以一瞬间找到。就

5、像查字典一样，找到偏 旁部首对应的页数一样。这样即使曲目再多也不怕了。99999999 loct $on!D I loct a $ongID I loct WORWOR 格式 9 专业资料整理 3、局部敏感哈希抗噪性更强 局部敏感哈希 LSH 在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维 度，怎样快速地从海量的高维数据集合中找到与某个数据最相似 (距离最近) 的一个数据或 多个数据成为了一个难点和问题。 如果是低维的小数据集， 我们通过线性查找(Linear Search )就可以容易解决，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常 耗时，因此，为了解决

6、该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类 技术称为最近邻查找 (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 的方式我们能够得到 0(1)的查找时间性能，其中关键在于 选取一个hash function ，将原始数据映射到相对应的桶内( b

7、ucket, hash bin )，例如对 数据求模：h = x mod w ， w通常为一个素数。在对数据集进行 hash的过程中，会发生不 同的数据被映射到了同一个桶中 (即发生了冲突collision )，这一般通过再次哈希将数据 映射到其他空桶内来解决。 这是普通Hash方法或者叫传统 Hash方法，其与LSH有些不同 之处。 WORWOR 格式 10 专业资料整理 p 局部敏感哈希示意图(WORWOR 格式 11 专业资料整理 LSH的基本思想是：将原始数据空间中的两个相邻数据点通过相同的映射或投 影变换(projection )后，这两个数据点在新的数据空间中仍然相邻的概率很大，而

8、不相邻 的数据点被映射到同一个桶的概率很小。 也就是说，如果我们对原始数据进行一些 hash映 射后，我们希望原先相邻的两个数据能够被 hash至肪目同的 桶内，具有相同的桶号。对原始数据集合中所有的数据都进行 hash映射后，我 们就得到了一个 hash table ，这些原始数据集被分散到了 hash table 的桶内，每个桶会落 入一些原始数据， 属于同一个桶内的数据就有很大可能是相邻的， 当然也存在不相邻的数据 被hash到了同一个桶内。因此，如果我们能够找到这样一 些hash functions ，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入相同的桶 内的话， 那么我们在

9、该数据集合中进行近邻查找就变得容易了， 我们只需要将查询数据进行 哈希映射得到其桶号， 然后取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查 询数据相邻的数据。换句话说，我们通过 hash function 映射变换操作，将原始数据集合分成了多个子集合，而每个子集 合中的数据间是相邻的且该子集合中的元素个数较小， 因此将一个在超大集合内查找相邻元素 的问题转化为了在一个很小的集合内查找相邻元素的问题， 显然计算量下降了很多。 那具有怎样特点的 hash functions 才能够使得原本相邻的两个数据点经过 hash 变换后会落入相同的桶内？这些 hash function 需要满足

10、以下两个条件： 1)如果 d(x,y) ,d2 则 h(x) = h(y) 的概率至多为 p2 ； 其中d(x,y) 表示 x和y之间的距离，di d2 , h(x) 和h(y) 分别表示对x和y进 行hash变换。 WORWOR 格式 12 专业资料整理 满足以上两个条件的 hash functions 称为(d1,d2,p1,p2)-sensitive 。而通过一个或多个 (d1,d2,p1,p2)-sensitive 的hash function 对原始数据集合进行 hashing 生成一个或多个 hash table 的过程称为 Locality-sensitive Hashing 。

11、 使用LSH进行对海量数据建立索引（ Hash table ）并通过索引来进行近似最近 邻查找的过程如下： 1. 离线建立索引 （1 ）选取满足（d1,d2,p1,p2）-sensitive 的 LSH hash functions ； （2 ）根据对查找结果的准确率 （即相邻的数据被查找到的概率） 确定hash table 的个数 L，每个 table 内的 hash functions 的个数 K，以及跟 LSH hash function 自身有关的参数； （3）将所有数据经过 LSH hash function 哈希到相应的桶内，构成了一个或多个 hash table ； 2. 在线查

12、找 （1） 将查询数据经过 LSH hash function 哈希得到相应的桶号； （2） 将桶号中对应的数据取出；（为了保证查找速度，通常只需要取出前 2L 个数据即可）； （3 ）计算查询数据与这 2L个数据之间的相似度或距离，返回最近邻的数据； LSH在线查找时间由两个部分组成： （1）通过LSH hash functions 计算hash值（桶号） 的时间； （2）将查询数据与桶内的数据进行比较计算的时间。因此， LSH的查找时间至少是 一个sublinear 时间。为什么是 “至少”？因为我们可以通 过对桶内的属于建立索引来加快匹配速度，这时第（ 2 ）部分的耗时就从 0（N）变成

13、了 WORWOR 格式 13 专业资料整理 O（logN）或0（1）（取决于采用的索引方法）。 LSH为我们提供了一种在海量的高维数据集中查找与查询数据点（ query data point ）近似最相邻的某个或某些数据点。需要注意的是， LSH并不能保证一定能够查找到 与query data point 最相邻的数据，而是减少需要匹配的数据点个数的同时保证查找到最 近邻的数据点的概率很大。 音乐检索 对于一段音乐或音频信息，我们提取其音频指纹（ Audio Fingerprint ）来表征该 音频片段，采用音频指纹的好处在于其能够保持对音频发生的一些改变的鲁棒 性，例如压缩，不同的歌手录制的同一条歌曲等。 为了快速检索到与查询音频或 歌曲相似的歌曲，我们可以对数据库中的所有歌曲的音频指纹建立 LSH索弓 然后通过该索引来加快检索速度。 结语：当然实际上还有很多细节需要考虑 ，我通常用matlab做研究，用C+做 实际系统。由于这是一个巨大的检索结构， 因此哪怕是1个字节乘上100 万都 是巨大的开支。百万首歌构建的哈希表内存占用甚至可以达到 100Gb 。C+在 控制内存、优化速度上非常有优势。由于 STL, BOOST等标准库并不