基于多级索引的音频特征检索比对算法

叶循澹

摘要 本文通过对有声内容智能质检平台项目中音频检索涉及的哈希算法进行研究，在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.