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

葉循澹

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

[關鍵詞]音頻檢索 多級索引 音頻特征 哈希算法

1 引言

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

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

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

2 哈希算法

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

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

2.1 FNV哈希算法

FNV哈希算法全名為Fowler-Noll-Vo算法，是以三位發明人Glenn Fowler，LandonCurt Noll，Phong Vo的名字來命名的。FNV能在保持較小的沖突率的同時，高速地對大量數據進行哈希運算。它分散度高的特性，使它常被用于相似度較高的字符串的哈希運算中，比如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哈希算法計算耗時少，效率高，但是在數據量較大的運算場景中，由于缺乏良好的散列分布性能，使其不能夠在音頻等有聲內容檢索時對數據進行準確定位。

2.2 其它哈希算法

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

2.3 FNV混合哈希算法

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

Charac value<<=X;

hash= Charac value FNV（Charac value）;

return hash;

在上述算法中，Charac value為提取的音頻特征值，音頻特征進行哈希運算后的結果為，提取的音頻特征值與經FNV哈希函數計算后的音頻特征值相異或的結果，這種優化后的哈希算法為FNV混合哈希算法。

3 性能對比

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

其中，測試機配置如下：

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

內存：16 GB（海力士DDR4 2400MHz）;

主硬盤：三星NVMe MZVLW128（ 128GB/固態硬盤）。

對358800條二進制數據進行哈希運算，結果如圖1所示。

對1256640條二進制數據進行哈希運算，結果如圖2所示。

對6497400條二進制數據進行哈希運算，結果如圖3所示。

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

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

4 結論

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

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

參考文獻

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

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

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

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

[5]趙娟，基于內容的海量音頻智能檢索與重復性檢測[D].太原：太原理工大學，2015.

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