Efficient and Robust Music Identification With Weighted Finite-State Transducers

Mehryar Mohri, Eugene Weinstein, Pedro J. Moreno

Research output: Contribution to journalArticlepeer-review


We present an approach to music identification based on weighted finite-state transducers and Gaussian mixture models, inspired by techniques used in large-vocabulary speech recognition. Our modeling approach is based on learning a set of elementary music sounds in a fully unsupervised manner. While the space of possible music sound sequences is very large, our method enables the construction of a compact and efficient representation for the song collection using finite-state transducers. This paper gives a novel and substantially faster algorithm for the construction of factor transducers, the key representation of song snippets supporting our music identification technique. The complexity of our algorithm is linear with respect to the size of the suffix automaton constructed. Our experiments further show that it helps speed up the construction of the weighted suffix automaton in our task by a factor of 17 with respect to our previous method using the intermediate steps of determinization and minimization. We show that, using these techniques, a large-scale music identification system can be constructed for a database of over 15 000 songs while achieving an identification accuracy of 99.4% on undistorted test data, and performing robustly in the presence of noise and distortions.

Original languageEnglish (US)
Pages (from-to)197-207
Number of pages11
JournalIEEE Transactions on Audio, Speech and Language Processing
Issue number1
StatePublished - Jan 2010


  • Content-based information retrieval
  • factor automata
  • finite-state transducers
  • music identification
  • suffix automata

ASJC Scopus subject areas

  • Acoustics and Ultrasonics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient and Robust Music Identification With Weighted Finite-State Transducers'. Together they form a unique fingerprint.

Cite this