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

1、WORWOR 格式 1 專業(yè)資料整理 華北水利水電大學 微信搖一搖搜歌技術原理分析 WORWOR 格式 2 專業(yè)資料整理 姓名： 劉勇 學號： 201215708 WORWOR 格式 3 專業(yè)資料整理 摘要：給出一首歌利用 cool edit 等多軌錄音和音頻處理軟件得出語譜圖， 然后利 用傅里葉變換得到語音波形圖，從中找到多個“音樂指紋” p，然后匹配哈希表 匹配已知的音樂指紋，如果相同即為同一首歌；而經(jīng)過版本改進之后的 Local Sensitive Hash 局部敏感哈希基于快速近鄰搜索，抗噪性更強。 關鍵詞：傅里葉變換；音樂指紋；哈希表；局部敏感哈希 1、提取音樂指紋 首先，一首MP3

2、 用cool edit 之類的軟件打開將是下圖這樣，以陳百強的情 人片段距離，以下波形圖示 20秒片段。 WORWOR 格式 4 專業(yè)資料整理 叫做譜圖(spectrogram)，縱坐標是頻率，橫坐標是時間。亮的地方代表能量高。每一首樂曲 因為樂器、 音高不同， 所以它們譜圖都不同。 哪怕是不同的人用同一接下來對這個波形做短時傅里葉變換 (SFFT)，可以得到下面這個類似樂譜的圖， WORWOR 格式 5 專業(yè)資料整理 PS:傅里葉變換是可逆的，也可以將語譜圖轉(zhuǎn)化為波形放出來聽，這也是現(xiàn)代 頻譜作曲流派的方法。 既然兩首曲子亮的位置不同， 我們就可以根據(jù)亮點來區(qū)分兩首歌一不一樣。 如下 圖找到

3、譜圖上若干個最亮的點，比如下圖找到了點 1 ，點2 ，點3。它們的音高 伴奏，甚至相同的人分開兩次唱， 同上。 語譜圖都是有細微差別的， 體現(xiàn)在亮的位置不 WORWOR 格式 6 專業(yè)資料整理 記作y1,y2,y3, 點1和點2的橫坐標距離記作 dx1，點2和點3的橫坐標距 離記作dx2。我們用向量p =y1,y2,y3,dx1,dx2 作為這個片段的特征，我們 將p叫做音樂指紋。如果兩首歌的p相同，那么我們就認為這兩首個一樣啦！否則就不 一樣。 2、音樂指紋匹配哈希表WORWOR 格式 7 專業(yè)資料整理 事實上為了穩(wěn)定和抗噪，我們可能會對一首歌提取更多的指紋 P，比如100 個 錄音環(huán)境經(jīng)常

4、會有噪音， 如果匹配中了 50個以上，我們就認為是同一首歌。而那些不一樣 的歌，基本上匹配數(shù)不會超過個位數(shù)。 這就是基本原理了，是不是很簡單！ 當然另一個問題就是大數(shù)據(jù)量了， 酷狗的音樂庫動輒上百萬， 總不可能對用戶錄制的片段一 條一條去匹配吧？所以這里我用的不是逐條匹配，而是哈希表匹配。 總的說來就是把每個 p映射成不同整數(shù)，比如 p =24,8,46,13,29 可以映射 成14335621。每個p對應著一首歌的某個位置，建庫的時候把所有曲目的指紋都插到這 個巨大的哈希表中。如下所示。 WORWOR 格式 8 專業(yè)資料整理 那么加入我們想查找14335621對應的曲子，就可以一瞬間找到。就

5、像查字典一樣，找到偏 旁部首對應的頁數(shù)一樣。這樣即使曲目再多也不怕了。99999999 loct $on!D I loct a $ongID I loct WORWOR 格式 9 專業(yè)資料整理 3、局部敏感哈?？乖胄愿鼜?局部敏感哈希 LSH 在很多應用領域中，我們面對和需要處理的數(shù)據(jù)往往是海量并且具有很高的維 度，怎樣快速地從海量的高維數(shù)據(jù)集合中找到與某個數(shù)據(jù)最相似 (距離最近) 的一個數(shù)據(jù)或 多個數(shù)據(jù)成為了一個難點和問題。 如果是低維的小數(shù)據(jù)集， 我們通過線性查找(Linear Search )就可以容易解決，但如果是對一個海量的高維數(shù)據(jù)集采用線性查找匹配的話，會非常 耗時，因此，為了解決

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 ，將原始數(shù)據(jù)映射到相對應的桶內(nèi)( b

7、ucket, 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有些不同 之處。 WORWOR 格式 10 專業(yè)資料整理 p 局部敏感哈希示意圖(WORWOR 格式 11 專業(yè)資料整理 LSH的基本思想是：將原始數(shù)據(jù)空間中的兩個相鄰數(shù)據(jù)點通過相同的映射或投 影變換(projection )后，這兩個數(shù)據(jù)點在新的數(shù)據(jù)空間中仍然相鄰的概率很大，而

8、不相鄰 的數(shù)據(jù)點被映射到同一個桶的概率很小。 也就是說，如果我們對原始數(shù)據(jù)進行一些 hash映 射后，我們希望原先相鄰的兩個數(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)的話， 那么我們在

9、該數(shù)據(jù)集合中進行近鄰查找就變得容易了， 我們只需要將查詢數(shù)據(jù)進行 哈希映射得到其桶號， 然后取出該桶號對應桶內(nèi)的所有數(shù)據(jù)，再進行線性匹配即可查找到與查 詢數(shù)據(jù)相鄰的數(shù)據(jù)。換句話說，我們通過 hash function 映射變換操作，將原始數(shù)據(jù)集合分成了多個子集合，而每個子集 合中的數(shù)據(jù)間是相鄰的且該子集合中的元素個數(shù)較小， 因此將一個在超大集合內(nèi)查找相鄰元素 的問題轉(zhuǎn)化為了在一個很小的集合內(nèi)查找相鄰元素的問題， 顯然計算量下降了很多。 那具有怎樣特點的 hash functions 才能夠使得原本相鄰的兩個數(shù)據(jù)點經(jīng)過 hash 變換后會落入相同的桶內(nèi)？這些 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 專業(yè)資料整理 滿足以上兩個條件的 hash functions 稱為(d1,d2,p1,p2)-sensitive 。而通過一個或多個 (d1,d2,p1,p2)-sensitive 的hash function 對原始數(shù)據(jù)集合進行 hashing 生成一個或多個 hash table 的過程稱為 Locality-sensitive Hashing 。

11、 使用LSH進行對海量數(shù)據(jù)建立索引（ Hash table ）并通過索引來進行近似最近 鄰查找的過程如下： 1. 離線建立索引 （1 ）選取滿足（d1,d2,p1,p2）-sensitive 的 LSH 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. 在線查

12、找 （1） 將查詢數(shù)據(jù)經(jīng)過 LSH hash function 哈希得到相應的桶號； （2） 將桶號中對應的數(shù)據(jù)取出；（為了保證查找速度，通常只需要取出前 2L 個數(shù)據(jù)即可）； （3 ）計算查詢數(shù)據(jù)與這 2L個數(shù)據(jù)之間的相似度或距離，返回最近鄰的數(shù)據(jù)； LSH在線查找時間由兩個部分組成： （1）通過LSH hash functions 計算hash值（桶號） 的時間； （2）將查詢數(shù)據(jù)與桶內(nèi)的數(shù)據(jù)進行比較計算的時間。因此， LSH的查找時間至少是 一個sublinear 時間。為什么是 “至少”？因為我們可以通 過對桶內(nèi)的屬于建立索引來加快匹配速度，這時第（ 2 ）部分的耗時就從 0（N）變成

13、了 WORWOR 格式 13 專業(yè)資料整理 O（logN）或0（1）（取決于采用的索引方法）。 LSH為我們提供了一種在海量的高維數(shù)據(jù)集中查找與查詢數(shù)據(jù)點（ query data point ）近似最相鄰的某個或某些數(shù)據(jù)點。需要注意的是， LSH并不能保證一定能夠查找到 與query data point 最相鄰的數(shù)據(jù)，而是減少需要匹配的數(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等標準庫并不