微信搖一搖搜歌技術原理分析

1、華北水利水電大學微信搖一搖搜歌技術原理分析姓名： 劉 勇 學號： 201215708 摘要：給出一首歌利用cool edit等多軌錄音和音頻處理軟件得出語譜圖，然后利用傅里葉變換得到語音波形圖，從中找到多個“音樂指紋”p，然后匹配哈希表匹配已知的音樂指紋，如果相同即為同一首歌；而經(jīng)過版本改進之后的Local Sensitive Hash局部敏感哈?；诳焖俳徦阉?，抗噪性更強。關鍵詞：傅里葉變換；音樂指紋；哈希表；局部敏感哈希1、提取音樂指紋首先，一首MP3用cool edit之類的軟件打開將是下圖這樣，以陳百強的情人片段距離，以下波形圖示20秒片段。接下來對這個波形做短時傅里葉變換(SFFT

2、)，可以得到下面這個類似樂譜的圖，叫做譜圖(spectrogram)，縱坐標是頻率，橫坐標是時間。亮的地方代表能量高。每一首樂曲因為樂器、音高不同，所以它們譜圖都不同。哪怕是不同的人用同一伴奏，甚至相同的人分開兩次唱，語譜圖都是有細微差別的，體現(xiàn)在亮的位置不同上。PS: 傅里葉變換是可逆的，也可以將語譜圖轉化為波形放出來聽，這也是現(xiàn)代頻譜作曲流派的方法。既然兩首曲子亮的位置不同，我們就可以根據(jù)亮點來區(qū)分兩首歌一不一樣。如下圖找到譜圖上若干個最亮的點，比如下圖找到了點1，點2，點3。它們的音高記作y1,y2,y3, 點1和點2的橫坐標距離記作dx1, 點2和點3的橫坐標距離記作dx2。我們用向量

3、p=y1,y2,y3,dx1,dx2作為這個片段的特征，我們將p叫做音樂指紋。如果兩首歌的p相同，那么我們就認為這兩首個一樣啦！否則就不一樣。2、音樂指紋匹配哈希表事實上為了穩(wěn)定和抗噪，我們可能會對一首歌提取更多的指紋p，比如100個錄音環(huán)境經(jīng)常會有噪音，如果匹配中了50個以上，我們就認為是同一首歌。而那些不一樣的歌，基本上匹配數(shù)不會超過個位數(shù)。這就是基本原理了，是不是很簡單！當然另一個問題就是大數(shù)據(jù)量了，酷狗的音樂庫動輒上百萬，總不可能對用戶錄制的片段一條一條去匹配吧？所以這里我用的不是逐條匹配，而是哈希表匹配?？偟恼f來就是把每個p映射成不同整數(shù)，比如p=24,8,46,13,29可以映射成

4、14335621。每個p對應著一首歌的某個位置，建庫的時候把所有曲目的指紋都插到這個巨大的哈希表中。如下所示。那么加入我們想查找14335621對應的曲子，就可以一瞬間找到。就像查字典一樣，找到偏旁部首對應的頁數(shù)一樣。這樣即使曲目再多也不怕了。3、局部敏感哈?？乖胄愿鼜?局部敏感哈希LSH在很多應用領域中，我們面對和需要處理的數(shù)據(jù)往往是海量并且具有很高的維度，怎樣快速地從海量的高維數(shù)據(jù)集合中找到與某個數(shù)據(jù)最相似（距離最近）的一個數(shù)據(jù)或多個數(shù)據(jù)成為了一個難點和問題。如果是低維的小數(shù)據(jù)集，我們通過線性查找（Linear Search）就可以容易解決，但如果是對一個海量的高維數(shù)據(jù)集采用線性查找匹配的

5、話，會非常耗時，因此，為了解決該問題，我們需要采用一些類似索引的技術來加快查找過程，通常這類技術稱為最近鄰查找（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的方式我們能夠得到O(1)的查找時間性能，其中關鍵在于選取一個hash function，將原始數(shù)據(jù)映射到相對應的桶內(nèi)（bucket

6、, hash bin），例如對數(shù)據(jù)求模：h = x mod w，w通常為一個素數(shù)。在對數(shù)據(jù)集進行hash 的過程中，會發(fā)生不同的數(shù)據(jù)被映射到了同一個桶中（即發(fā)生了沖突collision），這一般通過再次哈希將數(shù)據(jù)映射到其他空桶內(nèi)來解決。這是普通Hash方法或者叫傳統(tǒng)Hash方法，其與LSH有些不同之處。局部敏感哈希示意圖（from: Piotr Indyk）LSH的基本思想是：將原始數(shù)據(jù)空間中的兩個相鄰數(shù)據(jù)點通過相同的映射或投影變換（projection）后，這兩個數(shù)據(jù)點在新的數(shù)據(jù)空間中仍然相鄰的概率很大，而不相鄰的數(shù)據(jù)點被映射到同一個桶的概率很小。也就是說，如果我們對原始數(shù)據(jù)進行一些hash

7、映射后，我們希望原先相鄰的兩個數(shù)據(jù)能夠被hash到相同的桶內(nèi)，具有相同的桶號。對原始數(shù)據(jù)集合中所有的數(shù)據(jù)都進行hash映射后，我們就得到了一個hash table，這些原始數(shù)據(jù)集被分散到了hash table的桶內(nèi)，每個桶會落入一些原始數(shù)據(jù)，屬于同一個桶內(nèi)的數(shù)據(jù)就有很大可能是相鄰的，當然也存在不相鄰的數(shù)據(jù)被hash到了同一個桶內(nèi)。因此，如果我們能夠找到這樣一些hash functions，使得經(jīng)過它們的哈希映射變換后，原始空間中相鄰的數(shù)據(jù)落入相同的桶內(nèi)的話，那么我們在該數(shù)據(jù)集合中進行近鄰查找就變得容易了，我們只需要將查詢數(shù)據(jù)進行哈希映射得到其桶號，然后取出該桶號對應桶內(nèi)的所有數(shù)據(jù)，再進行線性匹

8、配即可查找到與查詢數(shù)據(jù)相鄰的數(shù)據(jù)。換句話說，我們通過hash function映射變換操作，將原始數(shù)據(jù)集合分成了多個子集合，而每個子集合中的數(shù)據(jù)間是相鄰的且該子集合中的元素個數(shù)較小，因此將一個在超大集合內(nèi)查找相鄰元素的問題轉化為了在一個很小的集合內(nèi)查找相鄰元素的問題，顯然計算量下降了很多。那具有怎樣特點的hash functions才能夠使得原本相鄰的兩個數(shù)據(jù)點經(jīng)過hash變換后會落入相同的桶內(nèi)？這些hash function需要滿足以下兩個條件：1）如果d(x,y) d1， 則h(x) = h(y)的概率至少為p1；2）如果d(x,y) d2， 則h(x) = h(y)的概率至多為p2；其中

9、d(x,y)表示x和y之間的距離，d1 d2， h(x)和h(y)分別表示對x和y進行hash變換。滿足以上兩個條件的hash functions稱為(d1,d2,p1,p2)-sensitive。而通過一個或多個(d1,d2,p1,p2)-sensitive的hash function對原始數(shù)據(jù)集合進行hashing生成一個或多個hash table的過程稱為Locality-sensitive Hashing。使用LSH進行對海量數(shù)據(jù)建立索引（Hash table）并通過索引來進行近似最近鄰查找的過程如下：1. 離線建立索引（1）選取滿足(d1,d2,p1,p2)-sensitive的LS

10、H hash functions；（2）根據(jù)對查找結果的準確率（即相鄰的數(shù)據(jù)被查找到的概率）確定hash table的個數(shù)L，每個table內(nèi)的hash functions的個數(shù)K，以及跟LSH hash function自身有關的參數(shù)；（3）將所有數(shù)據(jù)經(jīng)過LSH hash function哈希到相應的桶內(nèi)，構成了一個或多個hash table；2. 在線查找（1）將查詢數(shù)據(jù)經(jīng)過LSH hash function哈希得到相應的桶號；（2）將桶號中對應的數(shù)據(jù)取出；（為了保證查找速度，通常只需要取出前2L個數(shù)據(jù)即可）；（3）計算查詢數(shù)據(jù)與這2L個數(shù)據(jù)之間的相似度或距離，返回最近鄰的數(shù)據(jù)；LSH在線

11、查找時間由兩個部分組成： （1）通過LSH hash functions計算hash值（桶號）的時間；（2）將查詢數(shù)據(jù)與桶內(nèi)的數(shù)據(jù)進行比較計算的時間。因此，LSH的查找時間至少是一個sublinear時間。為什么是“至少”？因為我們可以通過對桶內(nèi)的屬于建立索引來加快匹配速度，這時第（2）部分的耗時就從O(N)變成了O(logN)或O(1)（取決于采用的索引方法）。LSH為我們提供了一種在海量的高維數(shù)據(jù)集中查找與查詢數(shù)據(jù)點（query data point）近似最相鄰的某個或某些數(shù)據(jù)點。需要注意的是，LSH并不能保證一定能夠查找到與query data point最相鄰的數(shù)據(jù)，而是減少需要匹配的

12、數(shù)據(jù)點個數(shù)的同時保證查找到最近鄰的數(shù)據(jù)點的概率很大。音樂檢索對于一段音樂或音頻信息，我們提取其音頻指紋（Audio Fingerprint）來表征該音頻片段，采用音頻指紋的好處在于其能夠保持對音頻發(fā)生的一些改變的魯棒性，例如壓縮，不同的歌手錄制的同一條歌曲等。為了快速檢索到與查詢音頻或歌曲相似的歌曲，我們可以對數(shù)據(jù)庫中的所有歌曲的音頻指紋建立LSH索引，然后通過該索引來加快檢索速度。結語：當然實際上還有很多細節(jié)需要考慮,我通常用matlab做研究，用C+做實際系統(tǒng)。由于這是一個巨大的檢索結構，因此哪怕是1個字節(jié)乘上100萬都是巨大的開支。百萬首歌構建的哈希表內(nèi)存占用甚至可以達到100Gb。C+在控制內(nèi)存、優(yōu)化速度上非常有優(yōu)勢。由于STL, BOOST等標準