葉循澹

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

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

1 引言

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

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

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

2 哈希算法

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

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

2.1 FNV哈希算法

FNV哈希算法全名為Fowler-Noll-Vo算法，是以三位發(fā)明人Glenn Fowler，LandonCurt Noll，Phong Vo的名字來(lái)命名的。FNV能在保持較小的沖突率的同時(shí)，高速地對(duì)大量數(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哈希算法計(jì)算耗時(shí)少，效率高，但是在數(shù)據(jù)量較大的運(yùn)算場(chǎng)景中，由于缺乏良好的散列分布性能，使其不能夠在音頻等有聲內(nèi)容檢索時(shí)對(duì)數(shù)據(jù)進(jìn)行準(zhǔn)確定位。

2.2 其它哈希算法

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

2.3 FNV混合哈希算法

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

Charac value<<=X;

hash= Charac value FNV（Charac value）;

return hash;

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

3 性能對(duì)比

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)

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

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

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

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

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

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