大型音乐哼唱检索系统中的近似匹配算法及性能评测  

Evaluation of approximate match algorithms in large query by humming music retrieval systems

作　　者：刘怡[1] 郝云飞[1] 

机构地区：[1]中国人民大学信息学院,北京100872

出　　处：《湖南科技大学学报（自然科学版）》2009年第1期81-86,共6页Journal of Hunan University of Science And Technology：Natural Science Edition

基　　金：教育部规划基金项目(05JAZH022)

摘　　要：研究了大型音乐哼唱检索系统中采用的近似匹配算法的性能问题,为了支持对于多种近似匹配算法的比较研究,开发了一个独立于算法的测试平台.所研究的基本算法包括后缀树、隐马尔科夫模型(HMM)、编辑距离、动态时间规整(DTW)和单侧连续匹配(OSCM)方法,用于测试的音乐数据库包括72000首音乐片段.通过构造1500个不同类型错误的查询方法,对其中3类方法算法进行了大量实验,分析评价了它们的性能.实验结果表明,基于单侧连续匹配的算法不仅查询速度快,而且在用户哼唱只包含与旋律轮廓方向相同的错误时,查询的准确率是100%,在用户哼唱包含两个以内与旋律轮廓方向相反的错误时,前10位的命中率也在90%左右,是适用于大型哼唱检索系统的查询算法.图11,表1,参8.This paper describes a study of the performance of approximate match algorithms in large query by humming music retrieval systems. An algorithm-independent test platform was developed in order to support comparative studies of various approximate match algorithms. The basic algorithms studied Suffix-tree, Hidden Markov Medels （HHM）, Edit Distance, Dynamic Time Wrapping （DTW） and One Side Consecutive Match （OSCM）, and the test music database includes 72 000 music pieces. Through large number of experiments using generated 1 500 queries with different errors, the performances of three different kinds of above approximate match algorithms were evaluated. The experiment results indicate that, OSCM algorithm can get fastest response time; and when query only including the error with same direction of melody contour, top -1 success rate is 100%; when query including tow error with contrary direction of melody contour, top -10 success rate is 90%. Therefore, OSCM algorithm is fittest large query by humming music retrieval systems.

关 键 词：哼唱检索 近似匹配 编辑距离 后缀树 动态时间规整 单侧连续匹配 性能评测 

分 类 号：TP37[自动化与计算机技术—计算机系统结构] TP311.134.3[自动化与计算机技术—计算机科学与技术]