A Dynamic Edit Distance Table

Presentation on theme: "A Dynamic Edit Distance Table"— Presentation transcript:

1 A Dynamic Edit Distance Table
Sung-Ryul Kim and Kunsoo Park CPM2000, LNCS 1848, pp , 2000

2 Edit distance （編集距離） 1 3 文字列 x[1...n] を文字列 y[1...n] へ変換する
置換 = 削除 = 挿入 = 1 各操作のコスト CARRIAGE 1 MARRIAGE k = 2 MASSAGE 3 編集距離

3 D(i, j) = min{D(i-1, j-1)+ij, D(i-1, j)+1, D(i, j-1)+1}
Dynamic Programming b b a 1 2 b D(i, j) = min{D(i-1, j-1)+ij, D(i-1, j)+1, D(i, j-1)+1} n O(mn) m DPによるEDの求め方

4 A と B の Edit distance が与えられたとき・・・
論文の主張 A と B の Edit distance が与えられたとき・・・ A と B’ (B’=aB) ・・・ incremental A と B’ (bB’=B) ・・・ decremental の Edit distance を求める！ O(m＋n) D DR Dの差分表現 等価な情報 を保持 O(mn) D’ DR’ 論文の主張

5 Dの差分表現 DR(i, j).L = D(i, j)  D(i, j 1)
DR(i, j).U = D(i, j)  D(i 1, j) DR(i, j).UL = D(i, j)  D(i 1, j 1) = DR(i, j).U + DR(i 1, j).L Dの差分表現

6 アイデア DR’ DR ちょっとちがう 基本的アイデア

7 Ch(i, j) = D’(i, j)  D(i, j +1)
Change Table O(m+n) Affected entry ココの値が等しくない Ch(i, j) = D’(i, j)  D(i, j +1) Change table

8 論文の概要 decremental (bB’=B)の場合のみ 補題１ Chの最上段と最左列の値 補題２ Ch(i, j)のとり得る値の範囲
補題５　DR上の影響される場所(affected entry) 補題６　ChテーブルとDRテーブルの関係 （隠れ補題）　DRからDR’の計算方法 提案アルゴリズム 論文の概要

9 補題１ Ch(0, j) = 1 for all 0  j  n Ch(i, 0) = 0 for all 1  i  k1 ただし k は A[k]=B[1] を満たす最小の値 Ch(i, 0) = 1 for all k  i  m 補題１

10 証明 (1)は自明． (2)(3)は… D’ D D’ D a 1 b 2 3 4 c 5 6 7 8 c 1 a b 2 3 4 5 6
a 1 b 2 3 4 c 5 6 7 8 c 1 a b 2 3 4 5 6 7 8 -1 a b c 1 　証明

11 補題２ 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) 補題２

12 証明 DとD’の関係から直接的にChの範囲を調べる． ・・・(2) ・・・(3) (2)の１が最小と仮定する．
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, j) = min D(i, j) + Ch(i, j1) +1 D(i 1, j + 1) + Ch(i 1, j) +1 D(i 1, j) + Ch(i 1, j 1) +i, j+1 ・・・(3) (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)と同様． 　証明

13 補題３と４ 補題３ 0  i  m について， f (i) = 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) . 補題３および補題４

14 証明 補題１と補題２から帰納法によって証明される． -1 1 O(mn) O(m+n) 等価な情報 を保持 Ch f g 　証明

15 Affected な（更新されうる）DR(i, j )のエントリ数は
補題５ 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) 補題５

16 Ch(i1, j1), Ch(i1, j), Ch(i, j1)
証明 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 　証明

17 DR(i, j + 1).UL + Ch(i1, j1) +i, j+1
補題６ 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テーブル こいつらと DR(i, j+1) が必要！ (i1, j1) (i1, j) (i, j1) (i, j) 補題６

18 証明 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, j) + Ch(i, j1) +1  D(i, j + 1) D(i1, j + 1) + Ch(i1, j) +1  D(i, j + 1) D(i1, j) + Ch(i1, j1) +i, j+1  D(i, j +1) = min DR(i, j + 1).L + Ch(i, j1) +1 DR(i, j + 1).U + Ch(i1, j) +1 DR(i, j + 1).UL + Ch(i1, j1) +i, j+1 　証明

19 隠れ補題 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) 証明 補題５の証明より明らか． 隠れ補題

20 アルゴリズム Chテーブル (i1, j1) (i1, j) (i, j1) (i, j) f と g から求まる！ アルゴリズム