微信搖一搖搜歌技術(shù)原理分析

華北水利水電大學(xué)微信搖一搖搜歌技術(shù)原理分析姓名：劉勇學(xué)號(hào)：201215708摘要：給出一首歌利用cooledit等多軌錄音和音頻處理軟件得出語(yǔ)譜圖，然后利用傅里葉變換得到語(yǔ)音波形圖，從中找到多個(gè)“音樂(lè)指紋”p，然后匹配哈希表匹配已知的音樂(lè)指紋，如果相同即為同一首歌；而經(jīng)過(guò)版本改進(jìn)之后的LocalSensitiveHash局部敏感哈?；诳焖俳徦阉鳎乖胄愿鼜?qiáng)。關(guān)鍵詞：傅里葉變換；音樂(lè)指紋；哈希表；局部敏感哈希1、提取音樂(lè)指紋首先，一首MP3用cooledit之類的軟件打開(kāi)將是下圖這樣，以陳百?gòu)?qiáng)的《情人》片段距離，以下波形圖示20秒片段。接下來(lái)對(duì)這個(gè)波形做短時(shí)傅里葉變換(SFFT)，可以得到下面這個(gè)類似樂(lè)譜的圖，叫做譜圖(spectrogram)，縱坐標(biāo)是頻率，橫坐標(biāo)是時(shí)間。亮的地方代表能量高。每一首樂(lè)曲因?yàn)闃?lè)器、音高不同，所以它們譜圖都不同。哪怕是不同的人用同一

伴奏，甚至相同的人分開(kāi)兩次唱，語(yǔ)譜圖都是有細(xì)微差別的，體現(xiàn)在亮的位置不同上。頻譜作曲流派的方法。既然兩首曲子亮的位置不同，我們就可以根據(jù)亮點(diǎn)來(lái)區(qū)分兩首歌一不一樣。如下圖找到譜圖上若十個(gè)最亮的點(diǎn)，比如下圖找到了點(diǎn)1，點(diǎn)2,點(diǎn)3。它們的音高記作y1，y2,y3,點(diǎn)1和點(diǎn)2的橫坐標(biāo)距離記作dxl,點(diǎn)2和點(diǎn)3的橫坐標(biāo)距離記作dx2。我們用向量p=[g1,g2,y3,dx1,dx2]作為這個(gè)片段的特征，我們將p叫做音樂(lè)指紋。如果兩首歌的p相同，那么我們就認(rèn)為這兩首個(gè)一樣啦！否則就不一樣。2、音樂(lè)指紋匹配哈希表

事實(shí)上為了穩(wěn)定和抗噪，我們可能會(huì)對(duì)一首歌提取更多的指紋P，比如100個(gè)錄音環(huán)境經(jīng)常會(huì)有噪音，如果匹配中了50個(gè)以上，我們就認(rèn)為是同一首歌。而那些不一樣的歌，基本上匹配數(shù)不會(huì)超過(guò)個(gè)位數(shù)。這就是基本原理了，是不是很簡(jiǎn)單！當(dāng)然另一個(gè)問(wèn)題就是大數(shù)據(jù)量了，酷狗的音樂(lè)庫(kù)動(dòng)輒上百萬(wàn)，總不可能對(duì)用戶錄制的片段一條一條去匹配吧？所以這里我用的不是逐條匹配，而是哈希表匹配。總的說(shuō)來(lái)就是把每個(gè)p映射成不同整數(shù)，比如p=[24,8,46,13,29]可以映射成14335621。每個(gè)p對(duì)應(yīng)著一首歌的某個(gè)位置，建庫(kù)的時(shí)候把所有曲目的指紋都插到這個(gè)巨大的哈希表中。如下所示。099999599^onglDloctgsongIDkxt那么加入我們想查找099999599^onglDloctgsongIDkxt3、局部敏感哈希抗噪性更強(qiáng)局部敏感哈希LSH在很多應(yīng)用領(lǐng)域中，我們面對(duì)和需要處理的數(shù)據(jù)往往是海量并且具有很高的維度，怎樣快速地從海量的高維數(shù)據(jù)集合中找到與某個(gè)數(shù)據(jù)最相似(距離最近)的一個(gè)數(shù)據(jù)或多個(gè)數(shù)據(jù)成為了一個(gè)難點(diǎn)和問(wèn)題。如果是低維的小數(shù)據(jù)集，我們通過(guò)線性查找(LinearSearch)就可以容易解決，但如果是對(duì)一個(gè)海量的高維數(shù)據(jù)集采用線性查找匹配的話，會(huì)非常耗時(shí)，因此，為了解決該問(wèn)題，我們需要采用一些類似索引的技術(shù)來(lái)加快查找過(guò)程，通常這類技術(shù)稱為最近鄰查找(NearestNeighbor,AN)，例如K-dtree；或近似最近鄰查找(ApproximateNearestNeighbor,ANN)，例如K-dtreewithBBF,RandomizedKd-trees,HierarchicalK-meansTree。而LSH是ANN中的一類方法。我們知道，通過(guò)建立HashTable的方式我們能夠得到O(1)的查找時(shí)間性能，其中關(guān)鍵在于選取一個(gè)hashfunction，將原始數(shù)據(jù)映射到相對(duì)應(yīng)的桶內(nèi)(bucket,hashbin)，例如對(duì)數(shù)據(jù)求模：h=xmodw，w通常為一個(gè)素?cái)?shù)。在對(duì)數(shù)據(jù)集進(jìn)行hash的過(guò)程中，會(huì)發(fā)生不同的數(shù)據(jù)被映射到了同一個(gè)桶中(即發(fā)生了沖突collision)，這一般通過(guò)再次哈希將數(shù)據(jù)映射到其他空桶內(nèi)來(lái)解決。這是普通Hash方法或者叫傳統(tǒng)Hash方法，其與LSH有些不同之處?！鉖/icvpr1%1I?IF局部敏感哈希示意圖(from:PiotrIndyk)LSH的基本思想是：將原始數(shù)據(jù)空間中的兩個(gè)相鄰數(shù)據(jù)點(diǎn)通過(guò)相同的映射或投影變換(projection)后，這兩個(gè)數(shù)據(jù)點(diǎn)在新的數(shù)據(jù)空間中仍然相鄰的概率很大，而不相鄰的數(shù)據(jù)點(diǎn)被映射到同一個(gè)桶的概率很小。也就是說(shuō)，如果我們對(duì)原始數(shù)據(jù)進(jìn)行一些hash映射后，我們希望原先相鄰的兩個(gè)數(shù)據(jù)能夠被hash到相同的桶內(nèi)，具有相同的桶號(hào)。對(duì)原始數(shù)據(jù)集合中所有的數(shù)據(jù)都進(jìn)行hash映射后，我們就得到了一個(gè)hashtable，這些原始數(shù)據(jù)集被分散到了hashtable的桶內(nèi)，每個(gè)桶會(huì)落入一些原始數(shù)據(jù)，屬于同一個(gè)桶內(nèi)的數(shù)據(jù)就有很大可能是相鄰的，當(dāng)然也存在不相鄰的數(shù)據(jù)被hash到了同一個(gè)桶內(nèi)。因此，如果我們能夠找到這樣一些hashfunctions，使得經(jīng)過(guò)它們的哈希映射變換后，原始空間中相鄰的數(shù)據(jù)落入相同的桶內(nèi)的話，那么我們?cè)谠摂?shù)據(jù)集合中進(jìn)行近鄰查找就變得容易了，我們只需要將查詢數(shù)據(jù)進(jìn)行哈希映射得到其桶號(hào)，然后取出該桶號(hào)對(duì)應(yīng)桶內(nèi)的所有數(shù)據(jù)，再進(jìn)行線性匹配即可查找到與查詢數(shù)據(jù)相鄰的數(shù)據(jù)。換句話說(shuō)，我們通過(guò)hashfunction映射變換操作，將原始數(shù)據(jù)集合分成了多個(gè)子集合，而每個(gè)子集合中的數(shù)據(jù)間是相鄰的且該子集合中的元素個(gè)數(shù)較小，因此將一個(gè)在超大集合內(nèi)查找相鄰元素的問(wèn)題轉(zhuǎn)化為了在一個(gè)很小的集合內(nèi)查找相鄰元素的問(wèn)題，顯然計(jì)算量下降了很多。那具有怎樣特點(diǎn)的hashfunctions才能夠使得原本相鄰的兩個(gè)數(shù)據(jù)點(diǎn)經(jīng)過(guò)hash變換后會(huì)落入相同的桶內(nèi)？這些hashfunction需要滿足以下兩個(gè)條件：如果d(x,y)<di，則h(x)=h(y)的概率至少為pl；如果d(x,y)>d2，則h(x)=h(y)的概率至多為p2；其中d(x,y)表示x和y之間的距離，d1<d2，h(x)和h(y)分別表示對(duì)x和y進(jìn)行hash變換。滿足以上兩個(gè)條件的hashfunctions稱為(d1,d2,p1,p2)-sensitive。而通過(guò)一個(gè)或多個(gè)(d1,d2,p1,p2)-sensitive的hashfunction對(duì)原始數(shù)據(jù)集合進(jìn)行hashing生成一個(gè)或多個(gè)hashtable的過(guò)程稱為L(zhǎng)ocality-sensitiveHashing。使用LSH進(jìn)行對(duì)海量數(shù)據(jù)建立索引（Hashtable）并通過(guò)索引來(lái)進(jìn)行近似最近鄰查找的過(guò)程如下：離線建立索引（1）選取滿足（d1,d2,p1,p2）-sensitive的LSHhashfunctions；（2）根據(jù)對(duì)查找結(jié)果的準(zhǔn)確率（即相鄰的數(shù)據(jù)被查找到的概率）確定hashtable的個(gè)數(shù)L，每個(gè)table內(nèi)的hashfunctions的個(gè)數(shù)K，以及跟LSHhashfunction自身有關(guān)的參數(shù)；（3）將所有數(shù)據(jù)經(jīng)過(guò)LSHhashfunction哈希到相應(yīng)的桶內(nèi)，構(gòu)成了一個(gè)或多個(gè)hashtable；在線查找（1）將查詢數(shù)據(jù)經(jīng)過(guò)LSHhashfunction哈希得到相應(yīng)的桶號(hào)；（2）將桶號(hào)中對(duì)應(yīng)的數(shù)據(jù)取出；（為了保證查找速度，通常只需要取出前2L個(gè)數(shù)據(jù)即可）；（3）計(jì)算查詢數(shù)據(jù)與這2L個(gè)數(shù)據(jù)之間的相似度或距離，返回最近鄰的數(shù)據(jù)；LSH在線查找時(shí)間由兩個(gè)部分組成：（1）通過(guò)LSHhashfunctions計(jì)算hash值（桶號(hào)）的時(shí)間；（2）將查詢數(shù)據(jù)與桶內(nèi)的數(shù)據(jù)進(jìn)行比較計(jì)算的時(shí)間。因此，LSH的查找時(shí)間至少是一個(gè)sublinear時(shí)間。為什么是“至少”？因?yàn)槲覀兛梢酝ㄟ^(guò)對(duì)桶內(nèi)的屬于建立索引來(lái)加快匹配速度，這時(shí)第（2）部分的耗時(shí)就從O（N）變成了O（logN）或O（1）（取決于采用的索引方法）。LSH為我們提供了一種在海量的高維數(shù)據(jù)集中查找與查詢數(shù)據(jù)點(diǎn)（querydatapoint）近似最相鄰的某個(gè)或某些數(shù)據(jù)點(diǎn)。需要注意的是，LSH并不能保證一定能夠查找到與querydatapoint最相鄰的數(shù)據(jù)，而是減少需要匹配的數(shù)據(jù)點(diǎn)個(gè)數(shù)的同時(shí)保證查找到最近鄰的數(shù)據(jù)點(diǎn)的概率很大。音樂(lè)檢索對(duì)于一段音樂(lè)或音頻信息，我們提取其音頻指紋（AudioFingerprint）來(lái)表征該音頻片段，采用音頻指紋的好處在于其能夠保持對(duì)音頻發(fā)生的一些改變的魯棒性，例如壓縮，不同的歌手錄制的同一條歌曲等。為了快速檢索到與查詢音頻或歌曲相似的歌曲，我們可以對(duì)數(shù)據(jù)庫(kù)中的所有歌曲的音頻指紋建立LSH索引，然后通過(guò)該索引來(lái)加快檢索速度。結(jié)語(yǔ)：當(dāng)然實(shí)際上還有很多細(xì)節(jié)需要考慮，我通常用matlab做研究，用C++做實(shí)際系統(tǒng)。由于這是一個(gè)巨大的檢索結(jié)構(gòu)，因此哪怕是1個(gè)字節(jié)乘上100萬(wàn)都是巨大的開(kāi)支。百萬(wàn)首歌構(gòu)建的哈希表內(nèi)存占用甚至可以達(dá)到100Gb。C++在控制內(nèi)存、優(yōu)化速度上非常有優(yōu)勢(shì)。由于STL,BOOST等標(biāo)準(zhǔn)庫(kù)并