用于哼唱识别精确匹配的线性伸缩动态规划算法  

Linear scaling based dynamic programming algorithm for accurate matching in QBH

作　　者：曹文晓[1,2] 刘轶[1,2] 郑方 蒋丹宁[3] 秦勇 

机构地区：[1]清华大学信息技术研究院语音和语言技术中心,北京100084 [2]清华信息科学技术国家实验室技术创新与开发部,语音和语言技术中心,北京100084 [3]IBM中国研究中心,北京100094

出　　处：《清华大学学报（自然科学版）》2009年第S1期1402-1407,共6页Journal of Tsinghua University(Science and Technology)

基　　金：IBM与清华大学合作项目(2007-2008)

摘　　要：提出一种用于哼唱识别精确匹配的线性伸缩动态规划算法。该算法将哼唱旋律切割成句子,对每一句子进行线性伸缩匹配,同时在句子层次进行动态规划获得最优路径。该算法更有效地利用了哼唱语音的分段特性并克服了动态规划在长路径搜索时可能丢失全局最优路径的缺点。在含5 223首M ID I的数据库上同等条件下该算法正确率分别比线性伸缩、动态规划及递归匹配方法提高10.5%、6.0%和2.8%。该算法具有更高的准确率和更小的时间复杂度,是一种更有效的精确匹配算法。A linear scaling(LS) based dynamic programming(DP) algorithm was developed for accurate matching of queries by humming.The query contours are split into phrases,with the LS match calculated for each phrase.Finally dynamic programming is used to analyze on all the phrases to choose the optimal matching path.The algorithm more efficiently considers the query contours related to the phrases,thus,overcoming the missing-global-optimal-path disadvantage of dynamic programming for long path matching.Tests on a 5 223 MIDI database show that the algorithm outperforms the traditional LS method by 10.5%,the DP method by 6.0% and recursive alignment by 2.8% for the top-1 rate.Thus,the algorithm is more efficient and more accurate while being less expense.

关 键 词：检索机 哼唱识别 精确匹配 线性伸缩 动态规划 

分 类 号：TP391.42[自动化与计算机技术—计算机应用技术]