基于多級索引的音頻特征檢索比對算法

葉循澹

摘要 本文通過對有聲內(nèi)容智能質(zhì)檢平臺項目中音頻檢索涉及的哈希算法進(jìn)行研究，在FNV哈希算法基礎(chǔ)上，混合了位移、異或等算法的優(yōu)點(diǎn)，提出了一種FNV混合哈希算法。并且通過對比分析表明，應(yīng)用FNV混合哈希算法對有聲內(nèi)容智能質(zhì)檢項目中的音頻進(jìn)行特征提取和索引建立，能夠有效提高音頻重復(fù)內(nèi)容的檢出效率。

[關(guān)鍵詞]音頻檢索 多級索引 音頻特征 哈希算法

1 引言

移動互聯(lián)網(wǎng)時代，每天都有大量的資訊內(nèi)容不斷地產(chǎn)生和投放。一旦有聲內(nèi)容運(yùn)營平臺出現(xiàn)了內(nèi)容錯誤、內(nèi)容缺字、聲音斷續(xù)、音質(zhì)不清等不良內(nèi)容，會嚴(yán)重影響用戶的體驗和滿意度。因此采用基于內(nèi)容的音頻檢索、音頻轉(zhuǎn)寫等智能化質(zhì)檢手段代人工質(zhì)檢，降低人力成本，提高質(zhì)檢效率是目前內(nèi)容運(yùn)營平臺主要目標(biāo)。

某互聯(lián)網(wǎng)公司為提高內(nèi)容運(yùn)營管理平臺的質(zhì)檢效率，建設(shè)了一套基于音頻智能檢索和音頻智能轉(zhuǎn)寫的有聲內(nèi)容智能質(zhì)檢平臺。其中，音頻檢索是指對音頻數(shù)據(jù)中的特征信息進(jìn)行提取和分析，建立音頻特征索引，快速檢索出音頻數(shù)據(jù)中的重復(fù)內(nèi)容等信息。目前國內(nèi)對基于內(nèi)容的音頻檢索技術(shù)進(jìn)行了大量的研究，其中，如何提取音頻指紋特征實(shí)現(xiàn)對音頻的分類，并建立音頻索引庫是音頻檢索中的重點(diǎn)內(nèi)容，哈希算法是實(shí)現(xiàn)音頻分類的主要技術(shù)手段之一。

本文通過對基于內(nèi)容的音頻檢索中的多級索引算法進(jìn)行研究，對多種哈希算法的性能進(jìn)行了分析對比，包括FNV哈希算法、RS哈希算法等九種哈希算法，并在FNV哈希算法基礎(chǔ)上，混合了位移、異或等算法的優(yōu)點(diǎn)，提出了一種適用于有聲內(nèi)容智能質(zhì)檢平臺的FNV混合哈希算法。

2 哈希算法

本文研究的哈希算法主要應(yīng)用于有聲內(nèi)容智能質(zhì)檢平臺的音頻重復(fù)內(nèi)容檢測場景中，用于根據(jù)提取的音頻特征建立音頻索引目錄。在音頻內(nèi)容檢索中，使用提取音頻特征的方式，對音頻特征進(jìn)行采樣和標(biāo)記，具體是對每10-30秒音頻特征進(jìn)行一次音頻特征的提取。特征的選取，既要保證特征對內(nèi)容的可代表性，又要保證特征的抽取速度。通過對音頻特征進(jìn)行檢索和比對，來進(jìn)行音頻內(nèi)容的重復(fù)性質(zhì)檢。其中，對音頻特征檢索比對的效率，是性能的關(guān)鍵。哈希算法的計算效率和命中率是決定音頻特征檢索比對效率的重要內(nèi)容之一。

哈希算法又稱散列算法，可以將任意長度的二進(jìn)制源數(shù)據(jù)映射為固定長度的二進(jìn)制哈希值。哈希值是一種特別的數(shù)值表示形式，可以檢驗數(shù)據(jù)的完整性，一般用于快速查找算法或加密算法中。本文對常用的幾種哈希算法進(jìn)行了研究分析，主要包括：

2.1 FNV哈希算法

FNV哈希算法全名為Fowler-Noll-Vo算法，是以三位發(fā)明人Glenn Fowler，LandonCurt Noll，Phong Vo的名字來命名的。FNV能在保持較小的沖突率的同時，高速地對大量數(shù)據(jù)進(jìn)行哈希運(yùn)算。它分散度高的特性，使它常被用于相似度較高的字符串的哈希運(yùn)算中，比如URL，hostname，文件名，text，IP地址等。算法描述如下：

hash=0ffset_ basis

for each octet of data to be hashed

hash= hash * FNV_prime

hash= hash xor octet of data

return hash

FNV哈希算法計算耗時少，效率高，但是在數(shù)據(jù)量較大的運(yùn)算場景中，由于缺乏良好的散列分布性能，使其不能夠在音頻等有聲內(nèi)容檢索時對數(shù)據(jù)進(jìn)行準(zhǔn)確定位。

2.2 其它哈希算法

除FNV哈希算法外，還有一些常用的字符串哈希函數(shù)，像BKDR哈希算法，AP哈希算法，DJB哈希算法，JS哈希算法，RS哈希算法，SDBM哈希算法，PJW哈希算法，ELF哈希算法等等，都是比較經(jīng)典的。這些函數(shù)使用位運(yùn)算使得每一個字符都對最后的函數(shù)值產(chǎn)生影響，并且多以發(fā)明人的名字命名。其中，ELF哈希算法是PJW哈希算法的變形。

2.3 FNV混合哈希算法

本文基于音頻檢索的應(yīng)用場景，對FNV哈希算法進(jìn)行了一定的改進(jìn)，先對哈希值左移X位，然后將結(jié)果與FNV的結(jié)果進(jìn)行異或，具體過程描述如下：

Charac value<<=X;

hash= Charac value FNV（Charac value）;

return hash;

在上述算法中，Charac value為提取的音頻特征值，音頻特征進(jìn)行哈希運(yùn)算后的結(jié)果為，提取的音頻特征值與經(jīng)FNV哈希函數(shù)計算后的音頻特征值相異或的結(jié)果，這種優(yōu)化后的哈希算法為FNV混合哈希算法。

3 性能對比

本章節(jié)對FNV哈希算法、BKDR哈希算法等幾種常見哈希算法，以及改進(jìn)后的FNV混合哈希算法，在同一測試機(jī)，同等數(shù)據(jù)量情況下的消耗時間和命中率進(jìn)行實(shí)驗分析，并對實(shí)驗結(jié)果進(jìn)行了分析說明，具體內(nèi)容如下。

其中，測試機(jī)配置如下：

處理器：英特爾Core i5-6300HQ@2.30GHz四核;

內(nèi)存：16 GB（海力士DDR4 2400MHz）;

主硬盤：三星NVMe MZVLW128（ 128GB/固態(tài)硬盤）。

對358800條二進(jìn)制數(shù)據(jù)進(jìn)行哈希運(yùn)算，結(jié)果如圖1所示。

對1256640條二進(jìn)制數(shù)據(jù)進(jìn)行哈希運(yùn)算，結(jié)果如圖2所示。

對6497400條二進(jìn)制數(shù)據(jù)進(jìn)行哈希運(yùn)算，結(jié)果如圖3所示。

根據(jù)以上圖標(biāo)可以看出，在數(shù)據(jù)量較小的情況下，幾種哈希算法的計算效率和命中率相仿。但是，隨著數(shù)據(jù)量的不斷增加，JsHash、PJW Hash、ELF Hash等幾種哈希算法的命中率明顯下降，無法滿足使用需求;BKBR Hash和SDBM Hash雖然仍保持較高的命中率，但是消耗的時間較長，也不是最優(yōu)算法：而FNV Hash和FNV Mix Hash，一直在保證較高命中率的同時，具有較少的消耗時間。其中，F(xiàn)NV混合哈希算法的計算效率更高。

綜和對比分析幾種哈希算法的消耗時間和命中率，最終選擇消耗時間小段，并且命中率較高的FNV混合哈希算法作為有聲內(nèi)容智能質(zhì)檢項目中的建立音頻特征索引的哈希算法。

4 結(jié)論

本文通過對有聲內(nèi)容智能質(zhì)檢平臺項目中的音頻重復(fù)內(nèi)容檢索算法進(jìn)行研究，對比分析了同等數(shù)據(jù)量情況下，F(xiàn)NV哈希算法、RS哈希算法等多種經(jīng)典哈希算法的消耗時間和命中率。實(shí)驗結(jié)果表明，同等數(shù)據(jù)量條件下，F(xiàn)NV混合哈希算法消耗較少的時間，并且保證了較高的命中率。因此，選取FNV混合哈希算法作為有聲內(nèi)容智能質(zhì)檢平臺中音頻檢索的哈希索引算法。

基于該算法，有聲內(nèi)容智能質(zhì)檢平臺音頻重復(fù)內(nèi)容檢出率高達(dá)99.63%，質(zhì)檢覆蓋率從純?nèi)斯べ|(zhì)檢的15%-20%提升至100%，單位時間內(nèi)單套智能質(zhì)檢引擎相對于人工質(zhì)檢，效率可以提升20倍以上，在保證質(zhì)檢質(zhì)量的前提下，顯著提高了審核效率。

參考文獻(xiàn)

[1]張建華，汪鑫，基于內(nèi)容音頻檢索綜述[J].商情，2012 （02）：215 -217.

[2]陳劍鋒，基于數(shù)字指紋的音頻檢索研究[D].華南理工大學(xué)，2011.

[3]李堅，毛先領(lǐng)，文貴華.基于分形特征的音頻檢索[J].計算機(jī)工程，2008 （11）.

[4]李爽，劉盈.基于內(nèi)容的音頻檢索關(guān)鍵技術(shù)分析[J].電子世界，2017 （18）：123—124.

[5]趙娟，基于內(nèi)容的海量音頻智能檢索與重復(fù)性檢測[D].太原：太原理工大學(xué)，2015.

[6]黃秋蘭，程耀東，陳剛，分布式存儲系統(tǒng)的哈希算法研究[J]，計算機(jī)工程與應(yīng)用，2014，50 （01）：1—4.