夏のLA 2016

連長圧縮に基づく漸増的最長共通部分列アルゴリズム
稲永 俊介 (九州大学)
Heikki Hyyrö (タンペレ大学, フィンランド)

背景

伊都キャンパス

九州大学

背景

糸島
伊都キャンパス

String Island
文字列島

文字列 の編集距離計算
問題 1 (編集距離)

入力: 文字列 A と文字列 B
出力: A と B の編集距離 ed(A, B)



編集距離 ed(A, B) は，文字列 A を B に変換する
編集操作（文字の挿入，削除，置換）の最小回数

動的計画法 (Dynamic Programming)m = |A|, n = |B| とし， (m+1) × (n+1) の表 D をD[i, j] = ed(A[1..i], B[1..j]) と定義する．

以下の式によって D[i, j] を順に埋めていくことで，D[m, n] = ed(A, B) を O(mn) 時間で計算できる．


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]) },ただし δ(A[i], B[j]) = 1 if A[i] ≠ B[j],δ(A[i], B[j]) = 0 if A[i] = B[j].

動的計画法 (Dynamic Programming)
Dtg
A catat

Ba t c c g a t

0 1 2 3 4 5 6 71234567A = tgcatat
B = atccgat
D[i, 0] = i for 1 ≤ i ≤ m
D[0, j] = j for 1 ≤ j ≤ n動的計画法 (Dynamic Programming)
Dtg
A catat

B01234567a t c c g a t
112334562123434532223445433234555433345665443445765543

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)
Dtg
A catatB

01234567a t c c g a t
1123345621234345322234454332345554333456654434457655434A = 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)
Dtg
A catat

B01234567a t c c g a t
1123345621234345322234454332345554333456654434457655434

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)
Dtg
A catatB

0
12
34567a t c c g a t
1
12
3
3
4
562
12
34
3
4
5322234454
332
3455543334566544344576554344

A = tgcatat
B = atccgat
D[i, j] = min{ D[i, j-1]+1,D[i-1, j]+1,D[i-1, j-1] }合計 O(mn) 時間

循環文字列1 ≤ j ≤ n に対して, Bj = B[j..n]B[1..j-1] とする．
すなわち，Bj は B の j 番目の循環文字列である.

循環文字列1 ≤ j ≤ n に対して, Bj = B[j..n]B[1..j-1] とする．
すなわち，Bj は B の j 番目の循環文字列である.
例) 文字列 B = “なつのえるえー” に対して,• B1 = なつのえるえー• B2 = つのえるえーな• B3 = のえるえーなつ• B4 = えるえーなつの• B5 = るえーなつのえ• B6 = えーなつのえる• B7 = ーなつのえるえ循環文字列比較問題 2 (循環文字列の編集距離)

入力: 文字列 A と文字列 B
出力: A と B のすべての循環文字列
B1, …, Bn の編集距離 ed(A, Bj).


動機：生物学的配列の比較など.



素朴な方法では，各循環文字列 Bj に対してO(mn) 時間 ⇒ 合計 O(mn2) 時間かかる.

より効率のよい方法はあるだろうか？

右端の文字追加は簡単
B[1..5]

Aagcta012345c
112234a212333g321234

B[1..5]B[1]t432223a543332Aagcta012345c112234a212333g321234t432223

最後の列の値だけが変化する⇒ 右端の文字追加は O(m) 時間でできる．

a543332c654343

左端の文字削除は簡単ではない
B[1..5]B[1]Aagcta012345c
112234a212333g321234t432223a543332

B[2..5]B[1]c654343Aagcta012345a101234g2
10123t321112

左端の文字を削除すると，最悪の場合には
DP 表の すべての列 に影響が及んでしまう！

a432221c543232

既存手法
アルゴリズムLandau et al. (1998)

左端削除の時間 領域
O(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)

前述のとおり，DP 表をそのまま保持するとO(mn) 時間かかってしまう．



そこで，既存研究では DP 表の非明示的表現(差分表現) を保持し，それを上手く更新している．

提案手法
アルゴリズムLandau et al. (1998)

左端削除の時間 領域
O(m + n)O(mn)Schmidt (1998)

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

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

O(m + n)

O(mn)

提案手法

O(m + n)O(ml + nk)

より省領域な左端削除アルゴリズムを提案する．



ここで，k (≤ m) と l (≤ n) はそれぞれ，文字列 A と B の 連長圧縮 のサイズ．

文字列の連長圧縮 (RLE)

文字列 A 中の同一文字の連続を，その文字の連続長で表現する圧縮法(Run Length Encoding, RLE)．


RLE(A) 中の同一文字の連の個数を，RLE(A) の サイズ という．
例) RLE(aaabbcccccbb) = a3b2c5b2

上の例では，サイズは 4．

m を文字列 A の長さ，k を RLE(A) のサイズとすると，必ず k ≤ m が成り立つ．

連長圧縮文字列の編集距離計算
ed(RLE(A), RLE(B)) の動的計画法の表 D をkl 個のブロックに分割する [Arbel et al. 2002].
bbbcccca a a a b b b b c c c
不一致ブロック

一致ブロック連長圧縮文字列の編集距離計算


ブロックの境界の値だけを陽に保持する⇒ O(ml + nk) 領域で済む.

ブロック内の値は，逐次計算できる．
bbbcccca a a a b b b b c c c境界に含まれるセルの個数はO(ml + nk).

Key Lemmas
動的計画表の差分表現を DR とし，左端文字の削除後の差分表現を DR’ とする．
補題 1 [Hyyrö et al., 2016]
DR’[i, j] ≠ DR[i, j] を満たすセルは表全体で O(m + n) 個しかない．
補題 2
各ブロックの上下左右のそれぞれの境界中には，
DR’[i, j] ≠ DR[i, j] なるセルが O(1) 個しかない．

一致ブロックの処理

動的計画法の表の一致ブロック内では，値は対角線に伝搬する．



よって，その差分表現の一致ブロック内でも，DR’[i, j] ≠ DR[i, j] なる値は，左／上の境界から右／下の境界へと伝搬する．

不一致ブロックの処理

不一致ブロック内では， DR’[i, j] ≠ DR[i, j] を満たすセルのパスは枝分かれする可能性がある．
左／上の境界中の O(1) 個の各始点から，深さ優先探索で DR’[i, j] ≠ DR[i, j] を満たすパスをトレースする.

パスによっては右/下の境界の手前で止まる（バックトラック）

主結果
定理
文字列 A と 文字列 B に対して，以下を満たす
編集距離 ed(A, B) の DP 表の差分表現が存在する．
 O(ml + nk) 領域
 文字列 B の左端文字の削除に対して，O(m + n) 時間で更新可能証明） 前述のアルゴリズムと補題 1, 2 より．

••••

m = |A|n = |B|k = |RLE(A)|l = |RLE(B)|