【作者】 刘怡； 郝云飞； 许洁萍；

【Author】 LIU Yi1+, HAO Yun-Fei2, Xu Jie-Ping3 1(Department of Computer Science, Renmin University, Beijing 100872, China) 2(Department of Computer Science, Renmin University, Beijing 100872, China) 3(Department of Computer Science, Renmin University, Beijing 100872, China)

【机构】 中国人民大学信息学院计算机系；

【摘要】 在音乐信息检索领域,近似重复模式的发现是一个重要的研究课题。我们根据乐曲中重复模式的特点,提出了基于二维单侧连续匹配的近似重复模式发现算法,能更准确地发现近似重复模式。由于算法对乐曲采用了n-gram划分,并对划分后的片段建立hash索引,使算法的时间复杂性大大降低,并能在一趟计算过程中发现全部近似重复模式。最后,我们还讨论了如何选取近似重复模式,建立二级音乐数据库的索引机制,进一步提高音乐数据库的查询效率。更多还原

【Abstract】 Repeating patterns discovering is an important problem in music information retrieval. The repeating patterns extracted from music works can be used as the features for music analysis and the index for music retrieval. Since the length of a repeating pattern is much short than that of a music work, and many user’s queries are aimed at repeat patterns, therefore, using repeating patterns as music databases index may improve systems performance greatly. Most previous works on music repeating patterns discovering only focus on exact repeating patterns. But many music segments with a few differences may sound similar, so approximate repeating patterns discovering is more important than exact repeating patterns discovering. The fundamental method of approximate repeating patterns discovering is to find approximate repeating segments in music works. We made a series experiments to study the problem of existing similarity match algorithms and the music similarity of human perceiving. Based the findings of our studies, a new approximate repeating patterns discovering algorithm established on bi-dimensional one side consecutive match is proposed in this paper. In our algorithm, music work is represented by a series of delta pitch and IOI ratio of the notes. The minimal length of the repeating patterns is chose first, and then the series of delta pitch and IOI ratio is segmented into small pieces with n-gram method, here n is the minimal length of the repeating patterns. After that, a hash table is created in memory, using all delta pitches and IOI ratio of the pieces as hash key, and the first position of the pieces in the serial as index items. Finally, for each two pieces in the hash chain which the number of pieces is great than one, the length of bi-dimensional one side consecutive match is counted and the repeating patterns are found. Because of using n-gram method and hash index and considering the situation of notes consecutive match, our new algorithm is more efficient than the existing methods, and it can also discovery approximate repeating patterns more accurately. Moreover, how to select approximate repeating patterns to building two level indexes and improving the query efficiency in music database is discussed in this paper.更多还原