Information extraction from the web using a search engine Citation for published version (apa)

A = [a
i j
] of words. For A we have max(l
1
, l
2
) ≤ l ≤ l
1
+ l
2
. Of this matrix, the ith

---

5.2 Extracting Lyrics from the Web
101
row is denoted by A
i◦
and the jth column is denoted by A
◦ j
. The upper row A
1◦
consists of the source string S
1
with possibly empty strings inserted and the lower
row A
2◦
consists of the destination string S
2
with possibly empty strings inserted.
An empty string or gap in an alignment is denoted by an asterisk (*), assuming that
this character does not appear as a word in the lyrics.
Each column A
◦ j
in the alignment corresponds to either a deletion, an insertion,
a substitution, or a match. Gaps in the upper row A
1◦
correspond to insertions in
S
1
, and gaps in the lower row A
2◦
correspond to deletions in S
1
. There is at most
one gap in each column. If there are no gaps in a given column, then this position
either corresponds to a match (if both characters in that column are identical) or a
substitution (otherwise).
As a primary objective, the goal is to maximize the number of matches, and,
as a secondary objective, to minimize the number of mismatches. To realize this,
we use the following recurrence relation. We compute the dynamic programming
table to align S
1
and S
2
using the following recurrence relation.
D(i, j) =







− j
if i = 0
−i
if j = 0
max { D(i − 1, j) − 1, D(i, j − 1) − 1,
D(i − 1, j − 1) + t(i, j) }
otherwise
(5.5)
with
t(i, j) =
½
M
if S
1
(i) = S
2
( j)
−1 if S
1
(i) 6= S
2
( j),
where S
i
( j) now denotes the jth word in the ith text fragment. Hence, all
insertions, deletions and substitutions receive a weight −1, while a match receives
a weight M. Now, M must be chosen large enough such that each alignment with a
maximum score has a maximum number of matches. In a worst-case situation, an
alignment with a single match in the lower-left or upper-right corner of the dynamic
programming table must still get a larger score than an alignment with no matches
and max(l
1
, l
2
) mismatches. Consequently, it must hold that M − (l
1
− 1) − (l
2
−
1) > − max(l
1
, l
2
), which is equivalent to M > min(l
1
, l
2
) − 2. Hence, choosing
M = min(l
1
, l
2
) gives the desired result.
Multiple alignments with maximum D(l
1
, l
2
) may occur. To get the matches as
much as possible in the first part of the alignment, we give preference to insertions
and deletions when tracing back.
Combining Single Alignments
We use the above dynamic programming approach to align the different text frag-
ments on a word-by-word basis. Suppose that the remaining set of text fragments is

---

102
given by P