A Dynamic Edit Distance Table

A Dynamic Edit Distance Table
Sung-Ryul Kim and Kunsoo Park
CPM2000, LNCS 1848, pp. 60-68, 2000
Edit distance （編集距離）
文字列 x[1...n] を文字列 y[1...n] へ変換する
ために要する最小コスト d
各操作のコスト置換 = 削除 = 挿入 = 1
CARRIAGE
1
MARRIAGE
k=2
MASSAGE
3
編集距離
Dynamic Programming
a
b
b
b
1
1
2
1
D(i, j) = min{D(i-1, j-1)+ij, D(i-1, j)+1, D(i, j-1)+1}
n
D
m
a
b
a
b
b
a
b
b
0
1
2
3
4
5
6
7
8
b
1
1
1
2
3
4
5
6
7
b
2
2
1
2
2
3
4
5
6
a
3
2
2
1
2
3
3
4
5
b
4
3
2
2
1
2
3
3
4
a
5
4
3
2
2
2
2
3
4
b
6
5
4
3
2
2
3
2
3
b
7
6
5
4
3
2
3
3
2
a
8
7
6
5
4
3
2
3
3
b
9
8
7
6
5
4
3
2
3
O(mn)
DPによるEDの求め方
論文の主張
A と B の Edit distance が与えられたとき・・・
A と B’ (B’=aB) ・・・ incremental
A と B’ (bB’=B) ・・・ decremental
の Edit distance を求める！
D
O(mn)
等価な情報
を保持
Dの差分表現
DR
O(mn)
D’
O(m＋n)
DR’
論文の主張
Dの差分表現
DR(i, j).L = D(i, j)  D(i, j 1)
D
b
1
1
1
2
3
4
5
6
7
b
2
2
1
2
2
3
4
5
6
a
3
2
2
1
2
3
3
4
5
b
4
3
2
2
1
2
3
3
4
a
5
4
3
2
2
2
2
3
4
b
6
5
4
3
2
2
3
2
3
b
7
6
5
4
3
2
3
3
2
a
8
7
6
5
4
3
2
3
3
b
9
8
7
6
5
4
3
2
3
DR.L
DR.U
b
b
a
b
a
b
b
a
b
a
b
a
b
b
a
b
b
0 0 -1 -1 -1 -1 -1 -1 -1
0 -1 0 -1 -1 -1 -1 -1 -1
1 1 -1 0 -1 -1 -1 -1 -1
1 0 1 -1 0 -1 -1 -1 -1
1 1 1 1 0 0 -1 -1 -1
1 1 0 1 0 1 1 -1 -1
1 1 1 0 1 -1 0 1 -1
1 1 1 1 1 1 -1 0 1
a
b
a
b
b
a
b
b
0
1
2
3
4
5
6
7
8
DR(i, j).U = D(i, j)  D(i 1, j)
b
b
a
0
-1
-1
-1
-1
-1
-1
-1
1
0
0
-1
-1
-1
-1
-1
0
1
-1
0
0
-1
-1
-1
DR.UL
b
b
a
b
a
b
b
a
b
a
b
a
b
b
a
b
b
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
a
b
a
b
b
a
b
b
b
a
b
b
a
b
1 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 1 1
-1 1 0 1 1 1
-1 0 0 0 1 1
0 -1 1 0 -1 1
-1 0 -1 1 0 -1
-1 0 -1 -1 1 0
DR(i, j).UL = D(i, j)  D(i 1, j 1)
= DR(i, j).U + DR(i 1, j).L
Dの差分表現
アイデア
DR.U
b
0 -1 -1 -1 -1 -1 -1 -1
0 1 -1 -1 -1 -1 -1 -1
1 -1 1 -1 -1 -1 -1 -1
1 1 -1 1 -1 -1 -1 -1
1 1 1 0 1 -1 -1 -1
1 1 1 0 1 1 -1 -1
1 1 1 1 -1 1 1 -1
1 1 1 1 1 -1 1 1
a
b
a
b
b
a
b
b
0 0 -1 -1 -1 -1 -1 -1 -1
0 -1 0 -1 -1 -1 -1 -1 -1
1 1 -1 0 -1 -1 -1 -1 -1
1 0 1 -1 0 -1 -1 -1 -1
1 1 1 1 0 0 -1 -1 -1
1 1 0 1 0 1 1 -1 -1
1 1 1 0 1 -1 0 1 -1
1 1 1 1 1 1 -1 0 1
b
a
b
DR.L
b
b
a
0
-1
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
1
0
0
-1
-1
-1
-1
-1
0
1
-1
0
0
-1
-1
-1
DR'.U
b
a
b
a
b
b
a
b
b
DR'.L
a
b
a
b
b
a
b
b
a
b
a
a
b
b
b
b
a
a
b
b
1 1 1 1 1
1 1 1 1 1
-1 1 1 1 1
1 -1 1 1 1
0 0 -1 1 1
-1 1 -1 -1 1
-1 -1 1 -1 -1
-1 -1 -1 1 -1
DR’
a
b
a
b
b
a
b
b
b
a
b
b
a
a
b
b
b
b
a
a
b
b
1 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 1 1
-1 1 0 1 1 1
-1 0 0 0 1 1
0 -1 1 0 -1 1
-1 0 -1 1 0 -1
-1 0 -1 -1 1 0
DR
a
b
a
b
b
a
b
b
a
b
a
b
b
a
b
b
b
a
b
a
b
b
a
b
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
b
a
b
a
b
b
a
b
-1 0 0 0 0 0 0 0
-1 0 -1 0 0 0 0 0
-1 0 0 -1 0 0 0 0
0 -1 0 0 -1 0 0 0
0 -1 0 0 0 -1 0 0
0 0 -1 0 0 -1 0 0
0 0 0 -1 0 0 -1 0
0 0 0 -1 0 0 0 -1
ちょっとちがう
基本的アイデア
Change Table
D'
a
b
a
b
b
a
b
b
0
1
2
3
4
5
6
7
8
b
1
1
1
2
3
4
5
6
7
a
2
1
2
1
2
3
4
5
6
b
3
2
1
2
1
2
3
4
5
Ch
a
b
a
b
b
a
b
b
-1
0
1
1
1
1
1
1
1
a
4
3
2
1
2
2
2
3
4
b
5
4
3
2
1
2
3
2
3
b
6
5
4
3
2
1
2
3
2
a
7
6
5
4
3
2
1
2
3
b
8
7
6
5
4
3
2
1
2
D
a
b
a
b
b
a
b
b
b a b a b b a b
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
0 0 -1 -1 -1 -1 -1 -1
0 0 0 -1 -1 -1 -1 -1
1 0 0 0 -1 -1 -1 -1
1 0 0 0 0 -1 -1 -1
1 1 0 0 0 -1 -1 -1
1 1 1 0 0 0 -1 -1
1 1 1 0 0 0 0 -1
0
1
2
3
4
5
6
7
8
b
1
1
1
2
3
4
5
6
7
b
2
2
1
2
2
3
4
5
6
a
3
2
2
1
2
3
3
4
5
b
4
3
2
2
1
2
3
3
4
a
5
4
3
2
2
2
2
3
4
b
6
5
4
3
2
2
3
2
3
b
7
6
5
4
3
2
3
3
2
a
8
7
6
5
4
3
2
3
3
b
9
8
7
6
5
4
3
2
3
O(m+n)
Affected entry
Ch(i, j) = D’(i, j)  D(i, j +1)
ココの値が等しくない
Change table
論文の概要
decremental (bB’=B)の場合のみ
•
•
•
•
•
補題１ Chの最上段と最左列の値
補題２ Ch(i, j)のとり得る値の範囲
補題３ Chテーブルの 1 の階段
補題４ Chテーブルの 1 の階段
補題５ DR上の影響される場所(affected
entry)
• 補題６ ChテーブルとDRテーブルの関係
• （隠れ補題） DRからDR’の計算方法
• 提案アルゴリズム
論文の概要
補題１
1. Ch(0, j) = 1 for all 0  j  n
2. Ch(i, 0) = 0 for all 1  i  k1
ただし k は A[k]=B[1] を満たす最小の値
3. Ch(i, 0) = 1 for all k  i  m
Ch
a
b
a
b
b
a
b
b
b b a b a b b a b
-1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1
1 0 0 -1 -1 -1 -1 -1 -1
1 0 0 0 -1 -1 -1 -1 -1
1 1 0 0 0 -1 -1 -1 -1
1 1 0 0 0 0 -1 -1 -1
1 1 1 0 0 0 -1 -1 -1
1 1 1 1 0 0 0 -1 -1
1 1 1 1 0 0 0 0 -1
補題１
証明
(1)は自明．
(2)(3)は…
D’
a
b
a
b
c
a
b
b
0
1
2
3
4
5
6
7
8
D’ D
D
a
b
a
b
c
a
b
b
0
1
2
3
4
5
6
7
8
c
1
1
2
3
4
4
5
6
7
a
b
a
b
c
a
b
b
-1
0
0
0
0
1
1
1
1
証明
補題２
Ch(i, j) がとり得る値は
min{ Ch(i1, j1), Ch(i1, j), Ch(i, j1) }
から
max{ Ch(i1, j1), Ch(i1, j), Ch(i, j1) }
の範囲である。
(i1, j1)
(i1, j)
(i, j1)
(i, j)
補題２
証明
DとD’の関係から直接的にChの範囲を調べる．
D(i, j +1) = min{ D(i 1, j)+ i, j+1 , D(i 1, j +1)+1, D(i, j)+1}
・・・(2)
D(i 1, j) + Ch(i 1, j 1) +i, j+1
D’(i, j) = min
D(i 1, j + 1) + Ch(i 1, j) +1
・・・(3)
D(i, j) + Ch(i, j1) +1
(2)の１が最小と仮定する．
i) (3)の1 が最小→ Ch(i, j ) = Ch(i 1, j 1).
ii) (3)の2 が最小→
Ch(i, j )  min{Ch(i 1, j 1), Ch(i 1, j ), Ch(i, j 1)},
Ch(i, j )  max{Ch(i 1, j 1), Ch(i 1, j ), Ch(i, j 1)}.
iii) (3)の3 が最小→ ii)と同様．
証明
補題３と４
補題３
0  i  m について， f (i) = j と定義する．
ただし， j は Ch(i, j) = 1 を満たす最小の値である．
このときすべての f (i)  j’ n について
Ch(i, j’ ) = 1
が成り立つ．また 1  i  m について
f (i)  f (i1) .
補題４
0  j  n について， g( j ) = i と定義する．
ただし， i は Ch(i, j) = 1 を満たす最小の値である．
このときすべての g( j )  i’ m について
Ch(i’, j ) = 1
が成り立つ．また 1  j  n について
g( j )  g( j 1) .
補題３および補題４
証明
補題１と補題２から帰納法によって証明される．
-1
0
1
1
1
O(mn)
Ch
-1
0
0
1
1
-1
-1
0
1
1
-1
-1
0
-1
1
等価な情報
を保持
-1
-1
-1
-1
0
-1
0
-1
-1
-1
f
g
O(m+n)
証明
補題５
•Ch(i1, j1), Ch(i1, j), Ch(i, j1) が異なるとき
Ch(i, j) は affected という．
•Ch(i, j) が affected のとき DR’(i, j) は affected という．
補題５
DR’(i, j) が affected でないならば，
DR’(i, j) = DR(i, j + 1)
が成り立つ．
Affected な（更新されうる）DR(i, j )のエントリ数は
O(m+n)
補題５
証明
DR’(i, j) が affected でないならば，
Ch(i1, j1), Ch(i1, j), Ch(i, j1)
は等しい．よって，
DR’(i, j).U = D’(i, j)  D’(i 1, j)
= D(i, j + 1) + Ch(i, j)
 ( D(i 1, j + 1) + Ch(i 1, j) )
= DR(i, j + 1).U
同様に，
DR’(i, j).L = DR(i, j + 1).L
証明
補題６
DR(i, j + 1).UL + Ch(i1, j1) +i, j+1
Ch(i, j) = min
DR(i, j + 1).U + Ch(i1, j) +1
DR(i, j + 1).L + Ch(i, j1) +1
Chテーブル
(i1, j1)
(i1, j)
(i, j1)
(i, j)
こいつらと
DR(i, j+1)
が必要！
補題６
証明
Ch(i, j) = D’(i, j)  D(i, j + 1)
= min{ D’(i 1, j 1)+ ’i, j , D’(i 1, j )+1, D(i, j 1)+1}
 D(i, j + 1)
= min
D(i1, j) + Ch(i1, j1) +i, j+1  D(i, j +1)
D(i1, j + 1) + Ch(i1, j) +1  D(i, j + 1)
D(i, j) + Ch(i, j1) +1  D(i, j + 1)
= min
DR(i, j + 1).UL + Ch(i1, j1) +i, j+1
DR(i, j + 1).U + Ch(i1, j) +1
DR(i, j + 1).L + Ch(i, j1) +1
証明
隠れ補題
DR’(i, j) が affected ならば，
DR’(i, j).U = DR(i, j + 1).U
+ Ch(i, j)  Ch(i 1, j)
DR’(i, j).L = DR(i, j + 1).L
+ Ch(i, j)  Ch(i, j 1)
証明
補題５の証明より明らか．
隠れ補題
アルゴリズム
Chテーブル
(i1,
j1)
(i1, j)
(i, j1)
(i, j)
f と g から求まる！
アルゴリズム

Download Report