Remember Me to One Who Lives There

November 19, 2012 · by Kim Ash · in

One application of dynamic programming is finding the longest common subsequence of two strings. Greg’s example from class applied this principle to sequences of DNA, where it can indicate mutations. I thought it might be interesting to try this with folk songs, which evolve over time and become the basis for other songs.

While I am sure there are better examples, the first one that came to mind was Bob Dylan’s “Girl from the North Country,” which was inspired by the medieval ballad “Scarborough Fair.” Simon and Garfunkel recorded a version of “Scarborough Fair” a few years after Dylan’s composition, so I decided to use those lyrics (minus the Canticle section) alongside Dylan’s for my program.

My program outputs the lyrics from Dylan, Simon and Garfunkel, and the LCS from analyzing the two. The result is a little wacky, but it does sound kind of like old English when you read it aloud. I am curious to try this again with versions of the ballad from different eras.
folk songs and LCS

Note: I found that the library kept cutting off the last “E” in “MINE” at the end of the result unless I added a space to the end of each text file. Here is the Processing code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/*
  Kim Ash
  Makematics - Fall 2012
  folkSongDP - uses dynamic programming to find LCS of 2 folk songs:
  "Scarborough Fair" and Bob Dylan's "Girl from the North Country"
*/
 
import dynamicprogramming.*;
 
String scartext[];  //text of "Scarborough Fair"
String northtext[];  //text of "Girl from the North Country"
String scar;  //composite string of SF lyrics
String north;  //composite string of GNC lyrics
 
LongestCommonSubsequence folkLCS;
 
void setup() {
  size(1040, 900);
  background(255);
  scartext = loadStrings("scarboroughFair.txt");
  northtext = loadStrings("northCountry.txt");
 
  //create composite string of SF lyrics
  for(int i=0; i<scartext.length; i++)  {
    scartext[i] = scartext[i].toUpperCase();
    scar = join(scartext, "\n");
  }
 
  //create composite string of GNC lyrics
  for(int i=0; i<northtext.length; i++)  { 
    northtext[i] = northtext[i].toUpperCase();
    north = join(northtext, "\n");
  }
 
  //find longest common subsequence
  folkLCS = new LongestCommonSubsequence(scar, north);
  println(folkLCS.getLongestCommonSubsequence());
}
 
void draw() 
{
  noStroke();
  fill(#55D3FF, 150);
  rect(0, 0, 560, 900);
  fill(#FFFA55, 150);
  rect(480, 0, 600, 900);
  fill(#8DFF55);
  rect(0, 610, 1040, 300);
 
  fill(0);
  textSize(15);
  text(scar, 40, 30);
  text(north, 600, 30);
  text(folkLCS.getLongestCommonSubsequence(), 20, 640);
}
Tags: , ,