隨著數位內容數量的大幅成長，包含聲音、音樂、影像、視訊等多媒體資料，對於數位內容的檢索也變成一個很重要的課題。音樂檢索則是針對音樂部份，使用者透過啍唱、語音與敲擊等不同的方式來選取網路上或資料庫中的歌曲。在目前多媒體數位內容日趨成熟，人們對於資訊需求不再侷限於文字上而已，愈來愈多的圖片、聲音、影像等多媒體將會成為搜尋對象。
目前的音樂檢索均以字串比對為核心，不單單只有精確比對也要允許錯誤比對(近似比對)。但若在資料量大時作比對，會需要大量的計算時間。以精確比對為例子，m為搜尋音符的個數，n為歌曲的音符個數，精確比對的時間複雜度為O(m × n)。
String Matching是很普遍且重要的問題，要在T=t1t2...tn中搜尋字串P=p1p2...pm，P及T有可能是一個檔案中的字元、DNA鹼基對(DNA base pairs)、程式中的一段程式碼、一多邊形的角或是樂譜中的音符及拍子等等。要在T中找尋有符合P字串的位置，也就是F = {i | 1≦i≦n-m+1 , titi+1...ti+m-1 = P}，這類問題最有名的就是Boyer-Moore[13]和Knuth Morris Pratt[14]演算法。
本篇論文採用Fast Text Searching Allowing Errors[6]理論基礎實現硬體的音樂檢索。對於只有Shift、AND、OR的演算法非常適合應用在硬體上面，且對時間複雜度更有大大的改善。當搜尋音符個數為m，歌曲音符個數為n時，時間複雜度為O(n)，和允許錯誤個數d無關；相較於應用在軟體上面時間複雜度是O (d × n)。將整個電路放置在Altera公司的Stratix開發板上，搭配使用者端利用Borland C++ Builder程式開發使用者介面，透過網路便可組成一個完整快速又兼具FPGA特性的音樂檢索系統。

With a great deal growth of digital contents such as media data of voices、musics、images and videos,it becomes an important topic for digital contents retrieval.The music retrieval focuses on the part of musics,and users retrieve songs from internet or database by humming、voicing and keying.In this day,people are no longer restricted to get resources in words with the maturation of media techniques. Accordingly,more and more pictures、voices and images would be objects to be searched.
Music retrieval is based on the core of string matching presently.There are not only exact matching but approximate matching(allowing errors).However,it’s would take large number of time when it proceeds with huge datas.Take exact matching,m denotes the number of querying notes and n denotes the number of music notes,and the time complexity is O(m × n).
String matching is a normal and significant problem. We are searching for the set of starting positions F = {i | 1≦i≦n-m+1 ,titi+1...ti+m-1 = P} for a string P=p1p2...pm inside a large text file T=t1t2...tn.The characters may be English characters in a text file, DNA base pairs, lines of source code, angles between edges in polygons, music notes and tempo in a musical score, and so forth. The two most
famous algorithms for this problem are the Boyer-Moore algorithm [13] and the Knuth Morris Pratt algorithm [14].
This thesis adopts Fast Text Searching Allowing Errors[6] as theorem to achieve music retrieval.It’s very suitable to apply on hardware with Shift、AND、OR algorithm only,and improves time cost significantly.m denotes the number of querying notes and n denotes the number of music notes.The hardware time complexity of the algorithm is O(n) irrelevant to the number of allowing errors(d) while O (d × n) for software.We append our circuits on Stratix development board by Altera corp. accompany with user querying UI(user interface) coded by Borland C++ 6.0 composed with network forms a high-speed FPGA music retrieval system.

[1]A. Ghias, J. Logan, D. Chamberlain, B. C. Smith,” Query
by humming-musical information retrieval in an audio
database”, ACM Multimedia ’95 San Francisco, 1995.
[2]Chen, A. L. P., M. Chang, J. Chen, J. L. Hsu, C. H. Hsu,
and S. Y. S. Hua, “Query by Music Segments: An
Efficient Approach for Song Retrieval,” in Proc. of
IEEE International Conference on Multimedia and Expo,
2000.
[3]J. Brown and B. Zhang, “Musical frequency tracking
using the methods of conventional and ‘Narrowed’
autocorrelation”. Journal of the Acoustical Society of
America, Volume 89, Number 5, pages 2346-2354,1991.
[4]Park, J. H., and George, K. M.,1999, “Parallel String
Matching Algorithms Based on Dataflow,”Proceedings of
the 32nd Hawaii International Conference on System
Sciences.
[5]Court, T. V., and Herbordt, M. C.,2006, “Families of
FPGA-based accelerators for approximate string
matching,” Microprocessors and Microsystems.
[6]Wu, Sun and Manber, Udi,1992, “Fast Text Searching
Allowing Errors,” Communications of the ACM, Vol. 35,
No.10, pp.83-91.
[7]Jyh-Shing Roger Jang, Hong-Ru Lee, and Chia-Hui Yeh,
2001,“Query by Tapping: A New Paradigm for Content-
based Music Retrieval from Acoustic Input,” Multimedia
Information Retrieval Laboratory Computer Science
Department, National Tsing Hua University, Taiwan, Vol. 8
[8]Sastry, R., Ranganathan, N., and Remedios, K.,
1995, “CASM: A VLSI Chip for Approximate String
Matching,”IEEE Transactions on Pattern Analysis and
Machine Intelligence, Vol. 17, No. 8, pp. 824-830.
[9]Ranganathan, N., and Motamarri, R., 1997, “A VLSI
Architecture for Computing the Optimal Correspondence of
String Subsequences,” Computer Architectures for
Machine Perception,pp. 290-294.
[10]Mukherjee, A., 1989, “Hardware Algorithms for
Determining Similarity Between Two String,” IEEE
Transaction on Computers, Vol. 38, No. 4, pp. 600-603.
[11]Navarro, G., 2001, “A Guided Tour to Approximate
String Matching,” ACM Computer Surveys, Vol. 33, No. 1.
[12]Bazea-Yates, R. A., and Gonnet, G. H., 1992, “A new
approach to text searching,”Communication of the ACM,
Vol. 35, No. 10, pp.74-82.
[13]Boyer, R. and Moore, J., 1977, “A fast string
searching algorithm.” Communication of the ACM, Vol.
20, No. 10, pp.762-772.
[14]Knuth, D. E., Morris, J. H., and Pratt, V. R.,
1977, “Fast pattern matching in strings.” SIAM
Journal on Computing, Vol.6, pp. 323-350.
[15]Ukkonen, E., 1985, “Finding Approximate Patterns in
Strings.,” Journal of Algorithms, Vol. 6, pp. 132-137.
[16]Shang, H., and Merrettal, T. M., 1996, “ Tries for
approximate string matching,” Knowledge and Data
engineering, IEEE Transactions on, Vol. 8,Issue: 4, pp.
540-547.
[17]Shyamala Doraisamy, and Stefan M Rüger, 2001,“An
Approach Towards A Polyphonic Music Retrieval System”,
Dept. of Computing Imperial College,London SW7 2BZ,
Vol.7
[18]Weiner, P., 1973, “Linear pattern matching
algorithms,”In Proceedings of IEEE Symposium on
Switching and Automata Theory, pp. 1-11.
[19]Lemstrom, K., 2000, “String Matching Techniques for
Music Retrieval,” Department of Computer Sciencs
Series of Publication A Report A.
[20]曾元顯, 2000, “ 音樂內容查詢不匹配問題與檢索模式之研究,”輔仁
大學圖書資訊學系 資訊傳播與圖書館學, Vol. 6, No. 4, pp.35-
48.
[21]Mukherjee, A., 1989,“Hardware Algorithms for
Determining Similarity Between Two Strings”, Dept. of
Comput. Sci., Univ. of Central Florida, Orlando, FL,
IEEE TRANSACTIONS ON COMPUTERS, VOL. 38, NO. 4
[22]Stephen Downie, and Prof. Michael Nelson,
2000,“Evaluation of a simple and effective music
information retrieval method”, Middlesex College,
Univ.of Western Ontario,London, Ontario, Canada, Vol.8
[23]J. Stephen Downie, 1999,“Music retrieval as text
retrieval (poster abstract): simple yet effective”,
University of Illinois at Urbana-Champaign501 E. Daniel
St, Champaign IL, Vol.2
[24]陳江村, 2001,“平行處理的音樂比對核心”, 清華大學資訊工程學
系, Vol.45, No.2, No.8, No.9, No.10
[25]Galil, Z., and Park, K., 1990,“An improved algorithm
for approximate string matching”, SIAM Journal on
Computing, Vol.19