Database Reference
In-Depth Information
Fig. 10. An example of a translation. By applying the translation to a sequence and
executing
LCSS
for
δ
= 1 we can achieve perfect matching.
pair of elements
positions from each
other (and therefore can be matched by the
LCSS
algorithm if their values
are within
b
i
,a
j
in
A
and
B
that are within
δ
ε
), we create a vertical line segment that is centered at the point
(
b
i
,a
j
) and extends
ε
above and below this point. Since each element in
A
canbematchedwithatmost2
δ
+ 1 elements in
B
, the total number of
such line segments is
O
(
δn
).
A translation
f
c
in one dimension is a function of the form
f
c
(
b
i
)=
c
. Therefore, in the plane we described above,
b
i
+
f
c
(
b
i
) is a line of slope 1.
After translating
B
by
f
c
,anelement
b
i
of
B
canbematchedtoanelement
c
intersects the line segment
a
j
of
A
if and only if the line
f
c
(
x
)=
x
+
((
)).
Therefore each line of slope 1 defines a set of possible matchings between
the elements of sequences
b
i
,a
j
− ε
), (
b
i
,a
j
+
ε
. The number of intersected line seg-
ments is actually an upper bound on the length of the longest common
subsequence because the ordering of the elements is ignored. However, two
different translations can result to different longest common subsequences
only if the respective lines intersect a different set of line segments. For
example, the translations
A
and
B
f
0
(
x
x
f
2
(
x
x
+2 in Figure 10 intersect
different sets of line segments and result to longest common subsequences
of different length.
The following lemma gives a bound on the number of possible different
longest common subsequences by bounding the number of possible different
sets of line segments that are intersected by lines of slope 1.
)=
and
)=
Lemma 2.
Given two one dimensional sequences A, B, there are
O
(
δ
(
n
+
m
))
lines of slope 1 that intersect different sets of line segments.
