Pattern extraction from music strings is an
important problem. The patterns extracted from music strings can be used as
features for music retrieval or analysis. Previous works on music pattern
extraction only focus on exact repeating patterns. However, music segments with
minor differences may sound similar. The concept of the prototypical melody has
therefore been proposed to represent these similar music segments. In musicology,
the number of music segments that are similar to a prototypical melody implies
the importance degree of the prototypical melody to the music work. In this
paper, a novel approach is developed to extract all the prototypical melodies
in a music work. Our approach considers each music segment as a candidate for
the prototypical melody and uses the edit distance to determine the set of
music segments that are similar to this candidate. A lower bounding mechanism,
which estimates the number of similar music segments for each candidate and
prunes the impossible candidates is designed to speed up the process.
Experiments are performed on a real data set and the results show a significant
improvement of our approach over the existing approaches in the average response
time.