很多時候，走在路上，突然聽到一段熟悉的音樂，但是怎麼想也想不起來這首歌到底叫什麼名字、到底是誰唱的；又或是聽到了一首好聽的歌，因為從未聽過，也不知道要從何處找起這首歌的資訊，這時候我們可依賴旋律辨識系統來幫助使用者找出歌曲資訊。
一個旋律辨識系統有三個要素：要查詢的歌曲 (input query)、歌曲資料庫(song database)、以及有效率的比對方式 (method for comparison)。對使用者而言，Query by Singing/Humming (QBSH) 可謂最方便的查詢方式，使用者只需對著麥克風哼唱未知歌曲的旋律，而系統會自動把輸入與資料庫比對，再從中找出最佳答案。
在過去，張智星教授 (國立臺灣大學及前國立清華大學) 及其團隊對此問題的研究有良好的解決方式，其方法為將查詢歌曲的旋律轉成pitch vector、將資料庫中的每首歌曲轉成note vector，再利用線性伸縮 (linear scaling) 將查詢歌曲和資料庫中的每一首歌去做比較，算出最接近的旋律，用此方法可以迅速的得到答案，並擁有不錯的辨識率。
本論文的目標是在此基礎上再加以加速。我們加入後綴樹 (suffix tree) 的概念，希望以此對資料庫的歌曲進行篩選，而線性伸縮則只對被挑選出來的歌曲進行，進而達到加速的概念。實驗結果顯示我們的系統除了能有預期的加速效果外，更意外地能使辨識率有些微的提高。

Sometimes, we may hear a familiar song on the street but we do not know what the name it is or who the singer is. Or, we may hear a good melody, but we do not know how to find further information of the song since we have never heard this song before. In these situations, one may use a melody recognition system to help.
A melody recognition system has three main components: (1) an input query, (2) a database of songs, and (3) method for comparison. Perhaps the most user-friendly form of input query is by singing and humming (QBSH), where a user sings or hums a melody with a microphone, and then the input data is transformed to a suitable format for comparison with the database to be performed. In the past, Jyh-Shing Jang (formerly with National Tsing Hua University, and now with National Taiwan University) and his team have designed a system that has high recognition rate to solving this problem. The idea is to change the input to a pitch vector, change the database to a note vector, and use linear scaling method to compare the input with every song in the database. After that, the most song with the highest score is reported to the user. Their system performs with good efficiency and achieves high recognition rate.
In this thesis, we attempt to further improve the above performance. Instead of comparing all songs in the database with the input query using linear scaling, we use suffix tree of the songs in the database as a filter to obtain a few candidate songs that are most likely to be a match with the input query. After that, only these candidate songs will be matched, carefully, with the linear scaling method. Experimental results show that this new approach not only speeds up the overall algorithm, but, to our surprise, also improves slightly the recognition rate.

Abstract ……………………………………………………………………………..2
Table of Contents ……………………………………………………………………..4
Figure List …………………………………………………………………………..5
Table List ……………………………………………………………………………6
Chapter 1 Introduction ……………………………………………………………...7
Chapter 2 Related Work ……………………………………………………………..10
2.1 Ghias et al.’s Approach ………………………………………………….10
2.2 Knopke and Jürgensen’s Work ……………………………………..11
2.3 Jang’s Approach …………………………………………………….12
Chapter 3 Methods ……………..……………………………………………………14
3.1 Ghias et al.’s Melody Representation ......………………………………...15
3.2 Suffix Tree and Generalized Suffix Tree ………………………………...15
3.3 Our Proposed Method ….……………………………………………….17
Chapter 4 Experimental Results …………………………………….. ……………..19
4.1 Execution Time …………………………………………………………..19
4.2 Recognition Rate …………………………………………………………19
Chapter 5 Conclusion and Future Work ……………………………………………24
References …………………………………………………………………………25

[1] A. Ghias, J. Logan, D. Chamberlin, and B.C. Smith. “Query by Humming –– Musical Information Retrieval in an Audio Database,” in Proceedings of ACM Multimedia, 1995.
[2] R.J. McNab, L. A. Smith, I. H. Witten, C. L. Henderson, and S. J. Cunningham. “Toward the Digital Music Library: Tune Retrieval from Acoustic Input,” in Proceedings of ACM Digital Libraries, pp. 11–18, 1996.
[3] J.S.R. Jang and M.Y. Gao. “A Query-by-Singing System based on Dynamic Programming,” in Proceedings of International Workshop on Intelligent System Resolutions, pp. 85–89, 2000.
[4] J.S.R. Jang, H.R. Lee, and M.Y. Kao. “Content-based Music Retrieval Using Linear Scaling and Branch-and-Bound Tree Search,” in Proceedings of IEEE International Conference on Multimedia and Expo, 2001.
[5] R.A. Baeza-Yates and C.H. Perleberg. “Fast and Practical Approximate String Matching,” in Proceedings of Combinatorial Pattern Matching, pp. 185–192, 1992.
[6] I. Knopke and F. Jürgensen. “A System for Identifying Common Melodic Phrases in the Masses of Palestrina,” Journal of New Music Research, vol. 38, pp. 171-181, 2009.
[7] I. Knopke. “The Perlhumdrum and Perllilypond Toolkits for Symbolic Music Information Retrieval,” in Proceedings of International Symposium on Music Information Retrieval, pp. 147–152, 2008.
[8] Online link at http://mirlab.org/jang/books/audioSignalProcessing/
[9] E. Ukkonen. “On-Line Construction of Suffix Trees,” Algorithmica, vol. 14, no. 3, pp. 249–260, 1995.
[10] E.M. McCreight. “A Space-Economical Suffix Tree Construction Algorithm,” Journal of the ACM, vol. 23, no. 2, pp.262–272, 1976.
[11] M. Nelson. “Fast String Searching with Suffix Trees”, 1996. Online link at http://marknelson.us/1996/08/01/suffix-trees/
[12] D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.