“Fully IncrementalLCS Computation”
15th International Symposium on Fundamentals on Computing Theory (FCT’05),
17-20 August 2005, Luebeck, Germany

Yusuke Ishida, Shunsuke Inenaga, Masayuki Takeda
Kyushu Univ., Japan&Ayumi Shinohara
Tohoku Univ., Japan“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Longest Common Subsequence A string obtained by removing 0 or more characters fromstring A is called a subsequence of A.
 The longest subsequence that occurs in both strings Aand B is called the longest common subsequence(LCS) of A and B.
A: c b a c b a a b a
B: b c d a b aLCS(A,B) = b c a b a

 LCS is a common metric for sequence comparison.

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Dynamic Programming LCS (and its length) of strings A and B can be computedby dynamic programming approach.

if i=0 or j=00,
DP[i, j] =max{DP[i-1, j],DP[i, j-1]}, if A[j]=B[i] and i, j ＞0DP[i-1, j-1] + 1,

if A[j]=B[i] and i, j ＞0

AbcB daba0000000c0011111b0111122a0111223c0122223b0122233“Fully Incremental LCS Computation”

a0122334a0122334b0
122344a0122345O(mn) time & spacen = |A|m = |B|LCS(A,B) = 5
FCT2005 Luebeck, 20.8.2005

Fully Incremental LCS Problem
 Given LCS(A,B) and character c, compute LCS(cA,B),

LCS(Ac,B), LCS(A,cB) and LCS(A,Bc).

 So we are able to e.g. process log files backdating to the past,and compute alignments between suffixes of one and the other.

 Naïve use of DP table takes O(mn) time for computing

LCS(cA,B) and LCS(A,cB) from LCS(A,B).
 More efficiently!?

 Landau et al. presented an algorithm that computes

LCS(cA,B) in O(L) time, where L = LCS(A,B).
 This work: efficient computation for LCS(A,cB),
LCS(Ac,B) and LCS(A,Bc)“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Fully Incremental LCS Problem [cont.]
0a 0aB b 0a 0b b0 01 12 2b0
122O(n)
AbAb a0 0 0
b 0 1 1
a 0 1 2

a b0 0
1 11 2
1 2O(L)a b0 0 0
b 0 0 1B
a 0 1 1b0
1
1AcO(L)a b0 0 0
b 0 0 1
a 0 1 1b c0 0
1 1
1 1O(n)0b 0
Bb a 0b 0“Fully Incremental LCS Computation”

a b0 00 1
1 1
1 2

b0
112FCT2005 Luebeck, 20.8.2005

Fully Incremental LCS Problem [cont.]
Time and Space Comparison (fixed alphabet)Naïve DP

Modified algo. of
Kim & Park

Our algorithm

LCS(cA,B)

O(mn)

O(m+n)O(L)

LCS(Ac,B)

O(m)

O(m)

O(L)

LCS(A,cB)

O(mn)

O(m+n)O(n)LCS(A,Bc)

O(n)

O(n)

O(n)

Total space

O(mn)

O(mn)

O(nL+m)

L = LCS(A,B) < min(m,n)“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Our Approach The algorithm of Laudau et al. computes LCS(cA,B) in

O(L) time.
 Their algorithm does not compute the whole DP matrix –it only considers the set P of partition points.
 Based on their algorithm, we compute LCS(A,cB) inO(n) time by considering partition points only.
 Suppose we have computed DP for strings A and B. Let

us denote by DPBh the DP matrix that is obtained fromDP after we add a new character to the head (left) of B.
 Same for PBh and P.
“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Match Point & Partition Point Pair (i, j) is said to be a match point if A[j] = B[i].
 Pair (i, j) is said to be a partition point

if DP[i, j] = DP[i-1, j] + 1.
Ac b a c b a a b a0 0 0 0 0 0 0 0 0 0Bb0 0 1 1 1 1 1 1 1 1match pointc0 1 1 1 2 2 2 2 2 2partition point

d0 1 1 1 2 2 2 2 2 2

a0 1 1 2 2 2 3 3 3 3

b0 1 2 2 2 3 3 3 4 4

a0 1 2 3 3 3 4 4 4 5“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Match Point & Partition Point [cont.] The set of partition points of DP is denoted by P.
 If (i, j) is a partition point with score v,

we write as P[v, j] = i.

Ac b a c b a a b a0 0 0 0 0 0 0 0 0 0Bb0 0 1 1 1 1 1 1 1 1c0 1 1 1 2 2 2 2 2 2d0 1 1 1 2 2 2 2 2 2

a0 1 1 2 2 2 3 3 3 3b0 1 2 2 2 3 3 3 4 4a0 1 2 3 3 3 4 4 4 5“Fully Incremental LCS Computation”

P[2, 3] = 4
P[4, 7] = 6

FCT2005 Luebeck, 20.8.2005

Computing LCS(A,cB)
ADPcB baba000000a000111a000112a000112a000112ADPBhb001122a00
1223c011223b012233a012334bcbB baba0000000a0000111a0000
112a00001
12a0000
112b0
111122a0111223c0122223b012333
3a0123444

 There are no changes to the partition points until the 1stoccurrence of “b” in A.
 All the cells in the 1st row of DPBh after the firstoccurrence of “b” get score 1.
 At most one partition point is eliminated at each column.
“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Eliminated Partition Point Lemma 1. For any column j, there exists row index Ej s.t.

DPBh[i, j] = DP[i, j] + 1 for i < Ej,
DPBh[i, j] = DP[i, j]
for i > Ej.
DPEj

DPBhj
0
122
3
33
45+1Ej=j01233
33345 (Ej, j) is the partition point to be eliminated in DPBh.
“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Eliminated Partition Point [cont.] Lemma 2. Let (Ej-1, j-1) and (Ej, j) be the partition points

eliminated at columns j-1 and j, resp. Let DP[Ej-1, j-1] = v.
Then,
Ej-1 < Ej < PBh[v+1, j-1].
DPDPBhj-1 jv

v-1v

j-1 j

Ej-1
Ejv+1

“Fully Incremental LCS Computation”

PBh[v+1, j-1]

v+1

FCT2005 Luebeck, 20.8.2005

Eliminated Partition Point [cont.] Lemma 3-1. If there is no match point (x, j) such thatPBh[v, j-1] < x < Ej-1,DP

Ej = Ej-1
DPBh

j-1 j
v-2

v-1
v-1

P [v-1, j-1]

j-1 j

PBh[v, j-1]

v-1
v-1v-1no match pointv v
v

v+1“Fully Incremental LCS Computation”

Ej-1 = Ejv
vv v
v+1

FCT2005 Luebeck, 20.8.2005

Eliminated Partition Point [cont.] Lemma 3-2. Otherwise,

Ej = P[v+1, j].

DPDPBhj-1 jv-2

v-1
v-1

v-1

v-1

v-1v

P [v+1, j]

j-1 jv

PBh[v, j-1]

vv

match pointvv v+1v+1“Fully Incremental LCS Computation”

vv+1Ej-1Ejv

v+1v+1v+1

FCT2005 Luebeck, 20.8.2005

Eliminated Partition Point [cont.] Due to Lemma 3-1 and 3-2, the partition points to beeliminated in DPBh can be computed by processing thecolumns of DP from left to right.
 The remaining thing is how to judge whether there exists

a partition point (x, j) such that PBh[v, j-1] < x < Ej-1 ateach column j.
Next Match Table“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Next Match Table NextMatch[i, c] returns the first occurrence of “c” after

position i in string B, if such exists. Otherwise, it returnsnull.
ΣaBbcd0 null 1

24b1 null 3

24c2 null 3 null 4b3 null null null 4d4 null null null null

 Using NextMatch table we can check PBh[v, j-1] < x < Ej-1

in constant time.

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Update Next Match Table When we get a new character to the head of B…
Σabcd0124a0 null 1

24b1 null 324-1aB c

2 null 3 null 4b3 null null null 4d4 null null null null

 For fixed alphabet Σ it takes constant time.
“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Complexity for Computing LCS(A, cB)
 When updating DP to DPBh, at most n partition points

are newly added, and at most n partition points areeliminated.

 Using NextMatch Table, each eliminated partition point

can be found in O(1) time.

 NextMatch table can be updated in O(1) time.
 Conclusion: LCS(A, cB) can be computed from LCS(A,B) in O(n) time.

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Computing LCS(Ac,B) If there exist match points between P[v-1, n] and P[v,n],the uppermost match point becomes the new partition
point of score v at column n+1.
DPnv-1v

match pointv

 Since there are L intervals to be checked at column n+1,

it takes O(L) time (we can use NextMatch table).

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Computing LCS(A,Bc)
 New partition points at row m+1 can be computed in thesame way as the standard DP approach.
DPj-1 jvj-1

vj

 There are n columns to be checked at row m+1.

Therefore O(n) time.

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Update Next Match Table When we get a new character to the tail of B…
Σbcd0 null 124b

1 null 3

24c2 null 3null4b3 null null null 4d4 null null null nullaBΣBaabcd0

5

124b1

5324c2

53null4b35null null

4d4

5null null nulla

5 null null null null

 There can be at most m entries to be updated inNextMatch table. But the amortized time complexity foreach new character is constant.

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005

Conclusion & Future Work Given LCS(A,B), the proposed algorithm computes
 LCS(cA, B) in O(L) time, LCS(Ac, B) in O(L) time, LCS(A, cB) in O(n) time, and LCS(A, Bc) in O(n) time,including (amortized) constant time update of NextMatch.
 Possible future work would be to extend our algorithm tocompressed strings - fully incremental LCS computation
without decompression. Run-length encoding?

“Fully Incremental LCS Computation”

FCT2005 Luebeck, 20.8.2005