Friday, November 21, 2014

Find chorus section in lyrics

I did a simple algorithm to find the chorus section of a song. There are several assumptions for this algorithm:

1. the processing lyrics should be complete, which means there is no abbreviation like "repeat 2 times chorus" etc.
2. the lyrics should be pre-processed by segmenting sections with blank line.
3. the chorus parts should be generally the same.

There are three steps in the algorithm:

1. calculate phrase-level similarity matrix, and it's lag-time form,
2. find repetitive sections which are the consecutive horizontal lines in the matrix,
3. group these repetitive sections.

Let's start!

1. Phrase-level similarity matrix
The similarity metric is defined as:$$metric=\frac{intersection\,words\,number}{largest\,word\,number\,of\,two\,phrases}$$And the similarity is:$$similarity=\left\{\begin{matrix} 0 & \mathrm{if} & metric < 0.8 \\ 1 & \mathrm{if} & metric \ge 0.8. \end{matrix}\right.$$Applying this similarity with each phrase pair in lyrics, we get the similarity matrix:
Fig. 1 phrase-level similarity matrix
Then we transform it to the lag-time form:
Fig. 2 lag-time form similarity matrix
It's quite clear that the horizontal lines represent the repetitive sections in lyrics, and the discrete points represent the repetitive phrases. Due to the variations between some repetitive sections (which breaks the third assumption), some points are not consecutive. We are going to deal with this problem afterwards.

2. Find the repetitive sections
Finding the repetitive sections is simple. At this stage, we only consider the consecutive horizontal lines. The number of the beginning and the ending phrase of repetitive sections are stored in the below matrix. Mind that we unwrap each horizontal line by adding the lag-time to its $x$ coordinates. The (gene) means generative section which can be considered as the parent section generating the horizontal lines in Fig. 2.

Table.1 beginning and ending phrases of horizontal lines
begin end begin (gene) end (gene)
repetition 1 43 50 34 41
repetition 2 34 41 17 24
repetition 3 43 50 17 24

By observing this table, we found that these three repetitions belong to the same group because they share either the repetitive section or the generative section. So in next step, we mange to group these repetitions and re-search missing segment.

3. Group repetitive sections
Alter grouping the repetitive sections and re-searching the missing sections, we end up with four group:

Table.2 after grouping and re-searching missing segment
begin end
group 1 17 24
34 41
43 50
group 2 1 15
group 3 26 32
group 4 52 64

Until now, it seems our job is done. But remember we said that we were going to deal with the discrete points in Fig. 2. Now we can be sure that these points are in our group 2, 3 or 4 and that also means one or several these groups belong to group 1 (remember we said these discrete points stand for the variation of repetitive section?). So we can set up a rule to re-group further the groups in Table. 2. For example, we could do the pair comparison of the first three words in the first lines of two groups.

1 comment: