整理个带图的回答吧。大概一年前做了一个音乐检索的系统，现在酷狗公司在用，看专利请猛戳
https://www.google.com.hk/patents/CN103853836A?cl=zh&dq=%E9%9F%B3%E4%B9%90%E6%A3%80%E7%B4%A2&hl=zh-CN&sa=X&ei=RUwUVKzeHdHe8AWElICADQ&ved=0CCkQ6AEwAg
去年2月份就看到酷狗发布的需要音乐检索引擎的消息，正好那时比较闲，想想好像可以一试。当然公司为了降低风险，酷狗还找了中大信科院的人，以及其它方面一起竞争开发。竞争是残酷的，当然也许是我花的心思更多一些，外加运气也还不错，酷狗最终采用了我的方案。
那么音乐检索的原理是什么呢？
下面我就为大家介绍！
首先，一首MP3用cool edit之类的软件打开将是下图这样，以陈百强的《情人》片段距离，以下波形图示20秒片段。
![]()
接下来对这个波形做短时傅里叶变换(SFFT)，可以得到下面这个类似乐谱的图，叫做谱图(spectrogram)，纵坐标是频率，横坐标是时间。亮的地方代表能量高。每一首乐曲因为乐器、音高不同，所以它们谱图都不同。哪怕是不同的人用同一伴奏，甚至相同的人分开两次唱，语谱图都是有细微差别的，体现在亮的位置不同上。
![]()
PS: 傅里叶变换是可逆的，也可以将语谱图转化为波形放出来听，这也是现代频谱作曲流派的方法。
既然两首曲子亮的位置不同，我们就可以根据亮点来区分两首歌一不一样。如下图找到谱图上若干个最亮的点，比如下图找到了点1，点2，点3。它们的音高记作y1,y2,y3, 点1和点2的横坐标距离记作dx1, 点2和点3的横坐标距离记作dx2。我们用向量p=[y1,y2,y3,dx1,dx2]作为这个片段的特征，我们将p叫做音乐指纹。如果两首歌的p相同，那么我们就认为这两首个一样啦！否则就不一样！
![]()
事实上为了稳定和抗噪，我们可能会对一首歌提取更多的指纹p，比如100个。录音环境经常会有噪音，如果匹配中了50个以上，我们就认为是同一首歌。而那些不一样的歌，基本上匹配数不会超过个位数。
这就是基本原理了，是不是很简单！
当然另一个问题就是大数据量了，酷狗的音乐库动辄上百万，总不可能对用户录制的片段一条一条去匹配吧？所以这里我用的不是逐条匹配，而是哈希表匹配。总的说来就是把每个p映射成不同整数，比如p=[24,8,46,13,29]可以映射成14335621。每个p对应着一首歌的某个位置，建库的时候把所有曲目的指纹都插到这个巨大的哈希表中。如下所示。
![]()
那么加入我们想查找14335621对应的曲子，就可以一瞬间找到。就像查字典一样，找到偏旁部首对应的页数一样。这样即使曲目再多也不怕了！
当然实际上还有很多细节需要考虑，有很多很多的trick。我通常用matlab做研究，用C++做实际系统。由于这是一个巨大的检索结构，因此哪怕是1个字节乘上100万都是巨大的开支。百万首歌构建的哈希表内存占用甚至可以达到100Gb。C++在控制内存、优化速度上非常有优势。由于STL, BOOST等标准库并不能满足这种特殊需要，在重写了内存池，哈希表等最底层的数据结构，经过8个版本的改进优化后，目前单曲的搜索速度可以在百万级的数据库上小于0.02秒，准确率98%以上！
国内外音乐检索公司包括Shazam公司，Stanford的创业团队Soundhound，国内的音乐雷达等等。音乐雷达的Local Sensitive Hash局部敏感哈希基于快速近邻搜索，抗噪性更强。题主问到了微信摇一摇搜歌，其原理也是基于局部敏感哈希的。其原理是以内存和搜索时间为代价，获得更高的召回率。所以在复杂的环境下，识别效果更好。
总而言之，搜歌的原理并不复杂，维护的大部分时间都在调参优化。工业级的音乐搜索，就看谁的trick用的好，谁的参数用的棒了！
|
转播
