SOFSEM 2016

Compacting a Dynamic Edit Distance
Table by RLE Compression
Heikki Hyyrö (University of Tampere, Finland)
Shunsuke Inenaga (Kyushu University, Japan)Kyushu University, Japan

Kyushu University, Japan

Kyushu U.

Kyushu U.

Kyushu University, Japan
Itoshima Peninsula

Kyushu U.

糸島
String Island

String Comparison
Problem 1 (Edit Distance)

Input: two strings A and B
Output: the edit distance ed(A, B)
between A and B
ed(A, B) is the minimum number ofedit operations (insertion, deletion,substitution of a single character)which transforms A to B (or vice versa).

Dynamic Programming (DP)

Let m = |A| & n = |B|. Let D be a table of size(m+1) × (n+1) s.t. D[i, j] = ed(A[1..i], B[1..j]),

The fundamental way to compute D[m, n] =ed(A, B) is DP with the following recurrence:

D[i, 0] = i for 1 ≤ i ≤ m,
D[0, j] = j for 1 ≤ j ≤ n,
D[i, j] = min{ D[i, j-1]+1, D[i-1, j]+1,D[i-1, j-1] + δ(A[i], B[j]) },where δ(A[i], B[j]) = 1 if A[i] ≠ B[j],δ(A[i], B[j]) = 0 if A[i] = B[j].

Dynamic Programming (DP)DBa t c c g a ttg
A catat

0 1 2 3 4 5 6 71234567

A = tgcatat
B = atccgat

D[i, 0] = i for 1 ≤ i ≤ m
D[0, j] = j for 1 ≤ j ≤ nDynamic Programming (DP)DBa t c c g a ttg
A catat

0
1
23
4
5
6
7

1
1233
4
562
123434532223445433234555433345665443445765543

A = tgcatat
B = atccgat
D[i, j] = min{ D[i, j-1]+1,D[i-1, j]+1,D[i-1, j-1] +1}

Dynamic Programming (DP)DBa t c c g a ttg
A catat

0
1234
56
7

1
12
334562
12343
4
532
2
2
3
4
4
54
3
32
3
4
5554
33
3
4
5665443
4457655434

A = tgcatat
B = atccgat
D[i, j] = min{ D[i, j-1]+1,D[i-1, j]+1,D[i-1, j-1] +1}

Dynamic Programming (DP)D

Ba t c c g a ttgA catat

012345671123345621234345322234454332345554333456654434457655434

A = tgcatat
B = atccgat
D[i, j] = min{ D[i, j-1]+1,D[i-1, j]+1,D[i-1, j-1] }Dynamic Programming (DP)D

Ba t c c g a ttgA catat0123456711233456212343453222344543323455543334566544344576554344A = tgcatat
B = atccgat
D[i, j] = min{ D[i, j-1]+1,D[i-1, j]+1,D[i-1, j-1] }O(mn) total timeCyclic Rotation of String

For 1 ≤ j ≤ n, let Bj = B[j..n]B[1..j-1],i.e., Bj is the j-th cyclic rotation of B.
E.g.) If B = SOFSEM, then• B1 = SOFSEM• B2 = OFSEMS• B3 = FSEMSO• B4 = SEMSOF• B5 = EMSOFS• B6 = MSOFSE

Cyclic String Comparison
Problem 2 (Cyclic Edit Distance)

Input: two strings A and B
Output: the edit distance ed(A, Bj)
for A and all rotations B1, …, Bn of B.
Motivation in bioinformatics (some biologicalsequences are circular).
 Naïve approach takes O(mn) time for eachrotation Bj. So, overall it takes O(mn2) time.
 Any better solution?
Right Increment Is Easy
B[1..5]Aagcta012345c112234a212333g
321234B[1..5]B[1]t432223a543332Aagcta012345c112234a2
12333g321234

New values are only at the last column.
⇒ Right increment takes O(m) time.

t432223a543332c654343

Left Decrement Is NOT as Easy
B[1..5]B[1]Aagcta012345c112234a2
12333g321234t432223a543332

B[2..5]B[1]c654343Aagcta012345a10
1234g
2
10
123t
32
1112a43222
1

When the left-most character is deleted,different values can propagate to all columns!

c543232

Algorithms for Left Decrements
Algorithms
Landau et al. (1998)

Left decr. time SpaceO(m + n)O(mn)Schmidt (1998)

O(m + n)O(mn)Kim & Park (2004)

O(m + n)O(mn)Hyyrö et al. (2015)

O(m + n)O(mn)There are several known solutions for theleft-decrement edit distance problem.

Each solution uses some “indirect” representationof the DP table which requires O(mn) space.
This space consumption is a bottle neck.

Run Length Encoding (RLE)The RLE of a string A is a compressed
representation of A where each maximal“run” a…a of the same character is encoded
by a p, where p is the length of the run.
 E.g.) RLE(aaabbcccccbb) = a3b2c5b2

The size k of RLE(A) is the number of maximal
runs in A.

If m is the length of the original string A,then clearly k ≤ m holds.

DR Tables (Kim & Park 2004)
Let DR be a differential representation ofDP table D for ed(A, B) such that:• DR[i, j].U = D[i, j] – D[i – 1, j] (vertical diff.)• DR[i, j].L = D[i, j] – D[i, j – 1] (horizontal diff.)

DDR.UDR.Lcagtcagtcagt

012341111a11123a10 -1 -1 -1

a0011g22212g111 -1 -1

g00 -1 1c32322c

10110c-1 1 -1 0t

43332t1

1010t-1 00 -1

Property of DR Tables

Let DR and DR’ denote the DR tables fored(A, B) and ed(A, B[2..n]), respectively.
Theorem 1 [Hyyrö et al. 2015]
For each row i of DR’, there are only O(1)column indices j s.t. DR’[i, j].L ≠ DR[i, j].L .

For each column j of DR’, there are onlyO(1) row indices i s.t. DR’[i, j].U ≠ DR[i, j].U .

Edit Distance of RLE strings


The DP and DR tables of ed(RLE(A), RLE(B))
can be divided into kl blocks [Arbel et al. 2002].
a a a a b b b b c c cbbbcccc

Mismatching
BlocksMatchingBlocks

Edit Distance of RLE strings
We explicitly store only the block boundaries ofthe DR tables, using O(ml + nk) space.

Then, the values inside the blocks can becomputed on the fly.
a a a a b b b b c c cbbbcccc

Total numberof cells in blockboundaries areO(ml + nk).

Key Lemma
Lemma 1Each of the top, bottom, left, and rightboundaries of a block of DR contains onlyO(1) cells (i, j) such that DR’[i, j] ≠ DR[i, j].

Proof.
 By Theorem 1.
Black cells arethose whereDR’[i, j] ≠ DR[i, j].

Processing Matching Blocks


In a matching block, the values in the DP tables
D’ and D propagate diagonally.

Thus, the different values of DR propagate
only diagonally, from left/top boundaries tobottom/right boundaries.

Processing Matching Blocks
Lemma 2After the left-most character of B is deleted,
all matching blocks of the DR table can be
updated in a total of O(m + n) time, using
O(ml + nk) space.
Proof.
Moving one step forward in a diagonal pathtakes O(1) time.

The total length of diagonal paths in allmatching blocks is O(m + n).

Processing Mismatching Blocks


In a mismatching block, the different values ofDR’ may diverge.

From each of the O(1) sources in the left/topboundaries, we trace all paths by DFS.

Some path may notreach the right orbottom boundary.

Processing Mismatching Blocks
Lemma 3After the left-most character of B is deleted,
all mismatching blocks of the DR table canbe updated in a total of O(m + n) time,using O(ml + nk) space.
Proof.
We can traverse all the paths of DFS
in time linear in the total length of the paths.
(Details are omitted.)Processing Mismatching Blocks
Lemma 3After the left-most character of B is deleted,
all mismatching blocks of the DR table canbe updated in a total of O(m + n) time,using O(ml + nk) space.
Proof. (Cont.)

The total length of the paths is linear in thenumber of cells where DR’[i, j] ≠ DR[i, j].
It follows from Theorem 1 that there are
only O(m + n) such cells in total.

Putting All Together
Theorem 2 (Main result)
Given an O(ml + nk)-space representationof the DR table for ed(A, B), we can update
it to that for ed(A, B[2..n]) in O(m + n) time.

••••m = |A|n = |B|k = |RLE(A)|l = |RLE(B)|Conclusions and Future Work

We proposed the first space-efficient
left-decremental edit distance algorithm,
which is based on RLE.

Our algorithm can also be applied to theleft-incremental case.

Open questions: Can we extend ouralgorithm to: Weighted edit distance?
 Insertion and deletion at arbitrary
positions?