Robust and Fast Phonetic String Matching Method for Lyric Searching Based on Acoustic Distance

Xin Xu, Tsuneo KatoIEICE 2014 · DOI

Abstract

This paper proposes a robust and fast lyric search method for music information retrieval (MIR). The effectiveness of lyric search systems based on full-text retrieval engines or web search engines is highly compromised when the queries of lyric phrases contain incorrect parts due to mishearing. To improve the robustness of the system, the authors introduce acoustic distance, which is computed based on a confusion matrix of an automatic speech recognition experiment, into Dynamic-Programming (DP)-based phonetic string matching to identify the songs that the misheard lyric phrases refer to. An evaluation experiment verified that the search accuracy is increased by 4.4% compared with the conventional method. Furthermore, in this paper a two-pass search algorithm is proposed to realize real-time execution. The algorithm pre-selects the probable candidates using a rapid index-based search in the first pass and executes a DP-based search process with an adaptive termination strategy in the second pass. Experimental results show that the proposed search method reduced processing time by more than 86.2% compared with the conventional methods for the same search accuracy.

The Challenge of Misheard Lyrics

Have you ever searched for a song using a line you thought you heard, only to have search engines return zero results? This is a common hurdle in Music Information Retrieval (MIR), often referred to as the "mondegreen" problem. Traditional search engines rely on full-text indexing, which fails when phonetic similarity is high but spelling is different (e.g., "Excuse me while I kiss this guy" instead of "the sky").

Analysis of real-world queries reveals that a significant portion of lyric searches contain errors. As shown in the distribution below, only about 21% of queries are perfectly correct, with content-word errors and notation confusion making up the bulk of the issues.

Distribution of error types in lyric queries.

While phonetic string matching using Dynamic Programming (DP) can solve this, it is computationally expensive. Running an exhaustive search across hundreds of thousands of songs in real-time is traditionally too slow for a responsive user experience.

The researchers proposed a dual-pronged approach to make lyric search both robust and fast.

1. Acoustic Distance

Instead of using a simple "edit distance" where every character swap costs the same, the system uses a phoneme confusion matrix derived from Automatic Speech Recognition (ASR) experiments. This matrix quantifies how likely one sound is to be mistaken for another. For example, swapping "k" for "g" has a lower "cost" because they sound similar, whereas swapping "k" for "s" costs more.

2. Two-Pass Search Algorithm

To achieve real-time performance, the system employs a two-pass strategy:

  • Pass 1 (The Filter): The system uses a fast inverted index based on syllable 3-grams. It calculates an approximate acoustic distance to quickly prune the database, narrowing down hundreds of thousands of songs to a few thousand likely candidates.
  • Pass 2 (The Refiner): The system performs a detailed DP-based phonetic match on the candidates. Crucially, it implements an adaptive termination strategy. Candidates are grouped, and if the distance in a group exceeds a threshold ($F_{th}$) based on the best results found so far, the search for that group is aborted early.
The second-pass search algorithm featuring adaptive termination to save processing time.

Key Results and Insights

The evaluation, conducted using real-world queries and a database of up to 50,000 lyrics, yielded several key findings:

  • Accuracy Boost: Using acoustic distance improved the "Top-20" hit rate by 4.4% over standard edit distance.
  • Massive Speedup: The two-pass method (TDPAT) reduced processing time by 86.2% to 96.5% compared to conventional high-speed DP methods. On a standard PC, the system processed queries in roughly 0.23 seconds.
  • Adaptive Efficiency: The researchers discovered that there is no statistical relationship between query length and the DP distance to the correct lyric. This led to the "adaptive threshold" breakthrough, allowing the algorithm to "sense" when it has found the correct match and stop searching the remaining database without losing accuracy.

Conclusion

By prioritizing how words sound over how they are spelled and implementing an intelligent two-pass filtering system, this research provides a viable path for commercial real-time lyric search engines that can handle the nuances of human hearing errors. Future work may involve training the confusion matrix specifically on singing voice data to further refine accuracy.

Summary updated

Abstract

This paper proposes a robust and fast lyric search method for music information retrieval (MIR). The effectiveness of lyric search systems based on full-text retrieval engines or web search engines is highly compromised when the queries of lyric phrases contain incorrect parts due to mishearing. To improve the robustness of the system, the authors introduce acoustic distance, which is computed based on a confusion matrix of an automatic speech recognition experiment, into Dynamic-Programming (DP)-based phonetic string matching to identify the songs that the misheard lyric phrases refer to. An evaluation experiment verified that the search accuracy is increased by 4.4% compared with the conventional method. Furthermore, in this paper a two-pass search algorithm is proposed to realize real-time execution. The algorithm pre-selects the probable candidates using a rapid index-based search in the first pass and executes a DP-based search process with an adaptive termination strategy in the second pass. Experimental results show that the proposed search method reduced processing time by more than 86.2% compared with the conventional methods for the same search accuracy.
BibTeX
@inproceedings{xu2014robust,
  author = {Xin Xu and Tsuneo Kato},
  title = {{Robust and Fast Phonetic String Matching Method for Lyric Searching Based on Acoustic Distance}},
  booktitle = {IEICE},
  year = {2014},
  doi = {10.1587/transinf.2013edp7418},
}
Figure