中斷點認知之重覆樣式搜尋演算法

本篇論文提出一新的演算法Greepie，目的為找出音樂物件中所有的非不重要重複片段(nontrivial repeating patterns)，非不重要重覆片段可加以應用，例如：音樂資料庫中的搜尋技術。目前在音樂分類、摘要等相關領域中，H.L.C.演算法為最多引用之作法，本篇論文所提演算法之效能比H.L.C.演算法高，且論文顯示H.L.C.演算法在找最大長度之非不重要重覆片段上不完整。最後，論文使用時間複雜度(Time Complexity)的運算比較兩者之效能差異，並說明比較結果。

關鍵字

重覆片段；重要重覆片段；非不重要重覆片段；字串結合法

並列摘要

This thesis introduces an innovative algorithm to obtain all meaningful nontrivial repeating patterns in music objects. This algorithm extracts so-called significant nontrivial repeating patterns from a melody music object. In addition, the proposed approach also discovers all nontrivial repeating patterns using a “gap-recognized" string-join algorithm during searching. By recognizing the gaps between the consecutive patterns, this algorithm reduces the number of the comparing the position of the repeating patterns. This paper discovers that there exists error for finding the longest repeating patterns of an existing baseline algorithm, which is called H.L.C. algorithm. Computing the results of the complexity illustrate a significant performance improvement using the proposed algorithm in comparison of the H.L.C. algorithm.

並列關鍵字

repeating pattern ； string-join ； non-trivial repeating patterns ； trivial repeating patterns ； gap

參考文獻

[2]. Barlow H, and Morgenstern S, A dictionary of musical themes, Crown, New York, 1975

[6]. Hsu JL, Liu CC, and Chen ALP, “Discovering non-trivial repeating patterns in music data,” IEEE Trans Multimedia 3(3):311–325, 2001

[9]. Lin D-I, and Kedem Z, “Pincer-search: an efficient algorithm for discovering the maximum frequent set,” IEEE Trans Knowl Data Eng 14(3):553–566, 2002

[11]. Kassler M “Toward musical information retrieval,” Perspect New Music 4(2):59–67, 1966

[15]. Kang YK, Kim YS, and Ku KI, “Extracting theme melodies by using a graphical clustering algorithm for content-based MIR,” In Proceedings of the 5th East-European conference on advances in databases and information systems (ADBIS), Springer-Verlag, London, pp 84–97, 2001

國際替代計量

中斷點認知之重覆樣式搜尋演算法

未授權

主題瀏覽