乐曲近似重复模式的发现及其在音乐数据库检索算法中的应用.pdf

乐曲近似重复模式的发现及其在音乐 数据库检索算法中的应用 刘怡郝云飞许洁萍 中国人民大学信息学院计算机系，北京，100872 摘要：在音乐信息检索领域，近似重复模式的发现是一个重要的研究课题。我们根据乐曲中 重复模式的特点，提出了基于二维单侧连续匹配的近似重复模式发现算法，能更准确地发现近 似重复模式。由于算法对乐曲采用了n．gram划分，并对划分后的片段建立hash索引，使算法 的时问复杂性大大降低，并能在一趟计算过程中发现全部近似重复模式。最后，我们还讨论了 如4-7选取近似重复模式，建立二级音乐教据库的索引机制，进一步提高音乐数据库的查询效率。 关键词：音乐敷据库；基于内容的音乐信．包检索；近似重复模式；模式发现 1．引言 随着计算机网络技术和多媒体处理技术的飞速发展，数字音乐迅速成为Web上的一 种重要的信息资源。对这些资源的使用包括数字图书馆、网上音乐销售、歌厅点歌服务、 个人音乐欣赏、音乐研究等。数字音乐信息广泛应用，使音乐信息检索成为计算机科学中 重要的研究领域，而在美国数字图书馆项目启动之后更成为计算机科学领域的研究热点 之一。 在音乐信息检索领域中，乐曲重复模式的自动发现，不仅对支持各种基于内容的查询 起着非常重要的作用，对乐曲主题分析，情感模式的发现等方面也有重要的意义。因此， 重复模式自动发现方法一直是一个引人注目的研究课题，也是多媒体数据挖掘领域中的重 要课题。 我们在211工程的支持下，进行了音乐信息检索技术的研究，本文所讨论的乐曲近似 霞复模式的笈现算法，则是此项工作的一部分内容。文章的第2节简要介绍了相关的工作 和存在的问题，第3节讨论了近似重复模式的特点和针对这些特点所采取的乐曲抽象表示。 第4节较详细阐述了我们提出的近似重复模式的发现算法，第5节进一步讨论了近似重复 模式在基于哼唱的音乐信息检索中的应用。 2．相关的工作 重复模式发现方法基本、r是将乐曲的抽象表示为音高音长的字符串，再用字符串处理 的方法提取重复模式。至今为止，已有不少沦文讨论了音乐作品中重复模式的发现方法。 资助项目：教育郎2u工程 corn 联系作者：刘怡，E-mail：liuyilee@sohu 414 第一。部分第十四届全国多媒体技术学术会议 这些方法可以分为两类： 第一类是只找出严格重复模式的方法，如：基于后缀树的方法…对作品的音符序列建 立一棵后缀树，树中每一条路径表示了一个模式，每一个页节点表示了模式在作品中的位 置。采用字符串连接(String-join)的方法，将相邻的最小熏复模式连接成更长的重复模式： 中查找重复模式”o““。但这些方法只是找到了严格重复模式，而音乐作品-|『大量存在的是 近似重复模式。 第二类是找}h近似重复模式的方法。文献[6，7]中讨论了不同的采用动态规划的方法， 计算所有可能长度的乐曲序列字符串的编辑距离，根据预定的值，找出近似霓复模式的算 法。这类方法处理时间较长，可达108数量级”J。文献f8]提卅了一种新的方法，在计算编 辑距离时，用忽略音符位序和音符的音长的方法，简化了计算代价，并通过限定模式的晟 大、最小长度的方法和建立Rt树的方法，改进了动态规划的处理时间。1_!=i忽略音符位序和 音长的方式，有时会产生误选，既不是重复模式却当成重复模式选出的情况。例如：乐曲 段塑卫15一I与乐曲段塑3121l，显然不是近似重复的，但如果忽略了音符位序与音长，这 两个乐段就成为近似重复的了。同时，文献[9】所讨论的方法中建立R+树的时问也不容忽视。 3．近似重复模式特点与相应的乐曲抽象表示 在音乐信息检索领域，对乐曲的所有处理，都是对乐曲特征值的处理。本节首先研究 重复模式的特点，将乐曲的音符序列以恰当的形式表示出米。 3．1乐曲中几种不同类型的重复 乐曲中乐段的重复，主要包括以下三粪： (1)模进重复 乐谱段丝3上与乐谱段堑2王从严格意义上讲是不重复的，但这两个序列的音高差、 音长比序列，即乐曲抽象特征的相对表示，是完全。样的，都是(2，2，4)(2，2，4)。 这种重复模式称为模进型重复模式。 (2)扩展重复、紧缩重复