Edit Distance

Edit Distance

• Symbol Substitution:���
• Deletion:���
• Insertion

a

b

b

a

b

c

a

c

b

c

b

a

b

b

a

b

c

a

c

a

c

a

b

b

a

b

c

a

a

a

Edit Distance

• The edit distance between S and T the minimal number of substitutions, deletions, and Insertions required to turn T into S.��

S =�

T = ��ED(S,T) = 3�

a

b

b

a

c

c

b

a

a

c

c

b

c

a

subs

a

b

a

c

c

b

a

del

a

a

c

c

b

a

ins

a

a

c

c

b

c

a

Compute Edit Distance

• Input: two strings S[1..n] and T[1..m]�
• Output: ED(S,T)���
• Idea: dynamic programing!

Dynamic Programing for Edit Distance

S

T

i

j

ED[i,j] = ED( , )

Dynamic Programing for Edit Distance

• Base case 1: i = 0�������
• ED[0,j] = j -> we must make j insertions!��

​

S

T

i

j

Dynamic Programing for Edit Distance

• Base case 2: j = 0�������
• ED[i,0] = i -> we must make i deletions!��

​

S

T

i

j

Dynamic Programing for Edit Distance

• Recursive case. ED[i,j] (i,j >0)��������
• How can be aligned with ? ���

​

S

T

i

j

Dynamic Programing for Edit Distance

• First option: is deleted. How to align the remaining prefixes?��������
• We are left with the task of turning into
• Cost: ED(i-1,j)+1 -> +1 for the deletion!���

​

S

T

i

j

Dynamic Programing for Edit Distance

• Second option: is not deleted, is added to the end of S��������
• We are left with the task of turning into
• Cost: ED(i,j-1) +1 -> +1 for the insertion!���

​

S

T

i

j

Dynamic Programing for Edit Distance

• Last option: is replaced by .��������
• We are left with the task of turning into
• Cost: ED(i-1,j,-1) + HD(S[i],T[j]) -> If = , we changed nothing!���

​

S

T

i

j

Dynamic Programming for Edit Distance

• We covered every possible option, so the final formula is:�� �� ED[i-1,j] + 1�ED[i,j] = min( ED[i,j-1] + 1 )� ED[i-1,j-1] + HD(S[i],T[j])�
• Computation time: O(1) per cell, overall – O(mn).

Bounded Edit Distance

• Input: Two strings S[1..n] and T[1..m] and a parameter k< n�
• Output: YES if ED(S,T) <=k. NO otherwise.��
• Of course, we can do it in O(nm)…�
• Can we do better? What if k is small?

Landau-Vishkin Algorithm

i

Consider a diagonal in the ED dynamic programing table.

Landau-Vishkin Algorithm

0 1 2 3 4 5 6 7

-1

-2

-3

-4

-5

-6

-7

Landau-Vishkin Algorithm

• We will do it using dynamic programing!�
• Set a table LV of size [n+m] x k.�
• LV[d,x] = Hight of lowest cell in diagonal d with value x in the edit distance table�
• Dynamic programing on the dynamic programing!

Landau-Vishkin Algorithm

• Base case: x= 0.�
• Observation: There is only one diagonal that may contain the value 0.

Landau-Vishkin Algorithm

Landau-Vishkin Algorithm

• Why would 0 occur lower on the diagonal?

0

i

i

i-1

i-1

ED(i,i-1)+1 -> at least 1!

ED(i-1,i)+1 -> at least 1!

ED(i-1,i-1)+HD(S[i],T[i]) -> 0 iff ED[i-1,i-1] = 0 and S[i] = T[i]!

Landau-Vishkin Algorithm

• It remains 0 as long as S[1..i] = T[1..i]�
• LCP!!!!!

S

T

Landau-Vishkin Algorithm

• LV(0,0) = LCP(S[1..n],T[1..m])

S

T

Landau-Vishkin Algorithm

• Recursive Step: LV[i,x], x>0. �
• Observation: only diagonals [-x..x] are relevant.

Landau-Vishkin Algorithm

• First, focus on [x,x]�
• Why would x occur lower in the diagonal?

Landau-Vishkin Algorithm

• Why would x occur lower on the diagonal?

x

i

i+x

i+x-1

i-1

ED(i+x,i-1)+1 -> at least x+2!

ED(i+x-1,i)+1 -> can be x if ED(i+x-1,i) = x-1!

ED(i+x-1,i-1)+HD(S[i+x],T[i]) -> is x iff ED[i+x-1,i-1] = x and S[i+x] = T[i]!

We already know the lowest cell in diagonal x-1 with value x-1!

Landau-Vishkin Algorithm

• Can x appear lower?�������
• Only as long as we have equality!�(S[i+x+1] = T[i+1] ….)

x

x-1

i

i+x

i+x-1

i-1

LV[x-1,x-1]

?

i+x+1

i+1

Landau-Vishkin Algorithm

• LV[x,x] = j + LCP(S[j+x+1..n],T[j+1..m])

x-1

x

x

x

S

x+1

j=LV[x-1,x-1]

j

j+x

j+x+1

j+1

Landau-Vishkin Algorithm

• Can x+1 appear lower on diagonal x?

x-1

x

x

x

S

x+1

j=LV[x-1,x-1]

j

j+x

j+x+1

j+1

x

Landau-Vishkin Algorithm

• Recursive Step: LV[d, x], ( d≠x,-x) �
• We can either get x from an adjacent cell with x-1, or with equality

Landau-Vishkin Algorithm

• Why would x occur from an x-1 in adjacent cells?

x

w

y

z

i

i+d

i+d-1

i-1

y=ED(i+d,i-1), y+1 -> relevant if y=x-1

z=ED(i+d-1,i), z+1 -> relevant if z = x-1

w =ED(i+d-1,i-1), +HD(S[i+d],T[i]) -> relevant if w=x-1

We know the lowest cell for every one of these!

Landau-Vishkin Algorithm

• LV[d,x] = j + LCP(S[j+d+1..n],T[j+1..m])

x-1

S

x

j2=LV[d-1,x-1]

j1 +1,

j=max(j2, )

j3+1

j+d

j+d+1

j+1

x-1

j3=LV[d+1,x-1]

x-1

j1=LV[d,x-1]

x

x

x

Landau-Vishkin Algorithm

• LV[d,x] = j + LCP(S[j+d+1..n],T[j+1..m]). Can x appear lower?

x-1

S

x

j2=LV[d-1,x-1]

j1 +1,

j=max(j2, )

j3+1

j+d

j+d+1

j+1

x-1

j3=LV[d+1,x-1]

x-1

j1=LV[d,x-1]

x

x

x

x+1

Landau-Vishkin Algorithm

• The first value lower than x+1 after the x+1 we discovered

v

w

y

z

i

i+d

i+d-1

i-1

Landau-Vishkin Algorithm

• Conclusion: LV[d,x] = j + LCP(S[j+d+1..n],T[j+1..m])�
• j = max (LV[d-1,x-1],LV[d,x-1] +1, LV[d+1,x-1]+1)�
• We can preprocess S,T to execute LCP in O(1)�
• So LV[d,x] is evaluated in O(1) [3 table lookups + LCP]��Complexity: O(n+|LV|).

​

Landau-Vishkin Algorithm