文法圧縮を応用したハミング距離の短い文字列列挙アルゴリズム

文法圧縮を応用したハミング距離の短い文字列列挙アルゴリズム

An Enumeration Algorithm of Short Hamming Distance Based on

Grammar Compression

前田幸司

1∗

高畠嘉将

1

田部井靖生

2

坂本比呂志

1

Koji Maeda

1

_{Yoshimasa Takabatake}

1

_{Yasuo Tabei}

2

_{Hiroshi Sakamoto}

1 1

_{九州工業大学 情報工学府}

1

_{Graduate School of Computer Science and Systems Engineering,}

Kyushu Institute of Technology, Japan

2

_PRESTO

_{さきがけ - 独立行政法人科学技術振興機構}

2

_{PRESTO, Japan Science and Technology Agency}

Abstract: We propose an enumeration algorithm of short Hamming distance based on grammar

compression by using split search. Pattern search and frequent pattern discovery using ESP-index[9] have been proposed, but enumeration algorithm of short Hamming distance has not been proposed yet. Using ESP-index and split search, we propose an enumeration algorithm of short Hamming distance. We experiment our algorithm for DNA text and achieve fastar calculate than FM-index[10].

1

はじめに

本論文では，文法圧縮を応用したハミング距離の短 い文字列列挙アルゴリズムを提案する．文法圧縮とは， 与えられた文字列 S を一意に導出する CFG を構築する 圧縮手法である．近年文法圧縮を用いた索引 [1, 2, 3]， 頻出パターン発見 [4] 等の様々な応用が提案されてい る．本稿では文法圧縮の新たな応用として，入力文字 列 S 中に出現する，検索文字列 P とのハミング距離が 短い部分文字列を検索するアルゴリズムを提案する．

2

準備

2.1

文法圧縮

文字の有限集合 Σ の要素からなる文字列全体の集合 を Σ∗と定義する．生成規則 X→ α において X を変 数と呼び，変数の集合を V (G) と表す．生成規則の集 合を辞書 D(G) と呼び，D(G) の生成規則の数を n と する． ∗_{連絡先： 九州工業大学大学院 情報工学府}        〒 820-8502 福岡県飯塚市川津 680 番 4        E-mail: k maeda@donald.ai.kyutech.ac.jp 文法圧縮とは，与えられた文字列 S∈ Σ∗を一意に導 出する CFG G を作る圧縮手法である．このとき G は admissibleであり，一意に文字列を導出する．したがっ て，任意の α∈ (Σ∪V (G))∗において，X → α ∈ D(G) は高々一つしかない．また CFG はチョムスキー標準形 の Straight line program(SLP) に制限し，生成規則は

X → a(a ∈ Σ) もしくは Xk → XiXj(1≤ i, j < k ≤ |V (G)|) である． 例えば入力文字列 S = aabbabab のときの生成規則 と，CFG 木の一例を図 1 に示す．一般に生成規則数が 少なくなるほど圧縮率は高くなるが，生成規則数を最 小にする問題は NP 困難であることが証明されており [5]，Repair[6]，LCA[7] などの文法圧縮アルゴリズムで 近似解を求めるアルゴリズムが複数提案されている．

2.2

ESP-index

ESP-index[9]とは，文法圧縮を用いた索引構造であ る．

2.2.1 Edit Sensitive Parsing(ESP)

ここでは文法圧縮の構文木構築を行う方法について 述べる．

人工知能学会研究会資料 SIG-FPAI-B401-06

A→ aa B→ bb C→ ab D→ AB E→ CC F → DE

B

C

C

F

A

E

D

a

a

b

b

a

b a

b

図 1: CFG の例 長さ u の文字列 S が与えられたとき，連続文字列 xiと，同じ文字の連続を含まない文字列 wiを用いて， Sを S′ = w1, x1, w2, x2, . . . , wk, xk, wk+1に分解する． このとき，w = ∅ の可能性もある．この分割された S′において，xiを Type1，|wi| のうち |wi| ≥ lg∗|w| のものを Type2，Type1 でも Type2 でもないものを Type3とする．ここで lg∗u = {min{i| lg(i)u ≤ 1}}

である．Type1 と Type3 については左優先で２文字 づつペアにして置き換えを行う．Type2 については， alphabet reduction[8]を用いて S = s1, s2, . . . , sk(2≤ |si| ≤ 3) のように分割し，|si| = 2 のとき si= XY か ら ti→ XY が生成され，|si| = 3 のとき si= XY Zか ら ti → Xt′，t′→ Y Z が生成される． 定理 2.1 ESP-index で作られる索引のサイズは n lg u+ n lg n + 2n + o(n lg n)である． 2.2.2 ESP-indexを用いたパターン検索 定理 2.2 S の構文木 Ts構築する際に作られた辞書を 用いて P の構文木 Tpを構築すると，この Tpは先頭 lg∗n + 5文字，末尾 5 文字分を除き，Ts中に含まれる Pの部分の構文木構造と一致する． 定理 2.2 より，文字列 S 中に長さ m のパターン P が 出現するかどうかを判別するには，Ts中に Tpを埋め 込むことができるかを確認すれば良い．(図 2) まず S の構文木 Ts構築する際に作られた辞書を用 いて P の構文木 Tpを構築し，部分木列 Tpの中で符号 化長が最大の部分木をコアとする．その後 Ts中に存在 するコアを探し，Tpと，Tsで抽出されたコアの周辺の 部分木が一致しているかを確認する． 定理 2.3 ESP-index で検索文字列 P の出現位置を求め るのにかかる時間計算量は，(lg lg n)(m+occclg m lg u) lg∗u である．ただし occcは Ts中に存在するコアの個数で ある． 定理 2.4 ESP-index で検索文字列 P の出現位置を求 めるのにかかる領域計算量は，n lg u + n lg n + 2n + o(n lg n)である． 図 2: パターン埋め込み 定理 2.5 ESP-index で部分文字列を復元するのにかか る時間計算量は，(m + lg u) lg lg n である．

2.3

ハミング距離

ハミング距離とは，長さの等しい文字列の中で，対 応する位置にある異なった文字の個数である．例えば， S1= wanderと S2= wonderは 2 番目に位置する文字 が異なっており，ハミング距離は 1 となる．S3= collect と S4= correctは 3 番目と 4 番目に位置する文字が異 なっており，ハミング距離は 2 となる．データ検索にお いて，完全に一致する文字列だけでなく，このような ハミング距離のある文字列も求めることにより，似た ゲノム構造の抽出や，タイポの検出などが可能である．

2.4

複数分類法

提案手法において，ハミング距離の計算量を減らす ために複数分割法を用いた．ここでは文字列 S 中に存 在するハミング距離 d 以下の部分文字列を列挙するア ルゴリズムについて述べる． STEP1 検索文字列 P を，長さ⌊|P |_k ⌋ の k(> d) 個 のブロックに分割し，P1, P2, . . . , Pkとする． STEP2文字列 S 中に存在する Piを検索し，Piの 全ての出現位置を Liに記録する． STEP3 Liに存在する位置 p を取り出し，Lj中に 位置 p− (i − j) × |P |_k (1 ≤ j ≤ i − 1), p + j × |P |_k (i + 1 ≤ j ≤ k) が存在するかを確かめる．このとき， 存在しないブロックの個数が d 個以下だった場合，ハ ミング距離 d 以下になる可能性のある S の部分文字列 として抽出する．すなわちこの操作では，Liの位置 p の周りのブロックが，S の p 番目の周りの部分文字列 と一致しているかを確かめている．この操作を，Li中 に存在する位置 p の全てに対して行う． STEP4 STEP3の操作を L1から順に，Ld+1まで に対して繰り返し行う． (補足) L1に対して STEP3 の動作を行ったとき，P1を 含んでハミング距離 d 以下になる可能性のある S の部

分文字列は抽出し尽くしている．従って，STEP3 の動 作を L1から順に，Liまで対して行ったとき，P1から Piまでのいずれかのブロックを含んでハミング距離 d 以下になる可能性のある S の部分文字列を抽出し尽く すことができる．以上のことから，STEP3 の操作を L1 から Ld+1まで行ったとき，Ld+2以降に対して STEP3 で得られるハミング距離 d 以下のものは，必ず Piから Pd+1までのいずれかを含んでいるため，すでに抽出さ れている．(P1から Pd+1までのブロックを１つも含ん でいない場合，すでに d + 1 個以上の異なる文字が存在 することが明らか．) 従って，STEP3 の操作を L1か ら Ld+1に対して繰り返し行うことにより，ハミング距 離 d 以下になる可能性のある S の部分文字列をすべて 抽出できる． STEP5 STEP3,4で抽出された位置ではハミング距 離 d 以下になる可能性があるため，STEP3,4 で異なっ た文字が存在していると判明しているブロック Piだけ を１文字ずつ比較していき，正確なハミング距離を求 める． この動作のイメージを図 3 に示す． 図 3: 複数分類法のイメージ

3

提案手法

複数分類法の文字列検索と部分文字列復元を行う動 作を，ESP-index を用いて行うことにより，ハミング 距離 d 以下の部分文字列検索を高速に行う． はじめに入力文字列 S の索引を ESP-index を用いて 作成する．次に，検索文字列 P を長さ⌊|P |_k ⌋ の k 個の ブロック P1, P2, . . . , Pkに分割する．それらのブロック Piの構文木を，S を構築する際にできた辞書を用いて 構築し，出現位置を計算して記録しておく．その後は 複数分類法に従い，ハミング距離 d 以下になる可能性 がある位置を抽出し，抽出されたブロックに関しての み，ESP-index を用いて部分復元を行いながら正確な ハミング距離を求める． 定理 3.1 この手法の時間計算量は

O(lg lg n(m + Σk_iocccilg m lg u) lg∗u + Σki(d−i)occbi+

occelg lg n(m_kd + lg u))である． 証明. １つのブロックの出現位置を計算するのに，定理 2.3より O(lg lg n(m_k+occcilg m lg u) lg∗u)時間掛かる． ブロックの数は k 個であるので，ブロックすべての出現 位置を求めるのに O(lg lg n(m+Σkiocccilg m lg u) lg∗u) 時間掛かる．ここでの occciは，S 中に存在するブロッ クのコアの個数である．各ブロックの出現位置の数を occbi とすると，他のブロックが対応する出現位置を 保持しているかを確認するのに koccbi 回比較を行う． 従って，すべてのブロックに対してその比較を行うと O(Σk_ikoccbi)の計算量が掛かる． ここで，抽出されて残った，ハミング距離 d 以下に なる可能性のある S の部分文字列の数を occeとする． 最後に，ブロックが一致していない部分の S の部分 文字列をすべて復元し，対応する検索文字列のブロ ックと比較する．定理 2.5 より，ブロック１つを復元 するのに O(lg lg nm_k + log u) 掛かり，復元するブロ ックの数は d 個存在するので，O(lg lg n(m_kd + lg u)) である．その操作を occe回繰り返すので，ブロック が一致していない部分の S の部分文字列をすべて復 元し，対応する検索文字列のブロックと比較するのに O(occelg lg n(m_kd + lg u))時間掛かる．従って，全体 として O(lg lg n(m + Σkiocccilg m lg u) lg∗u + Σki(d−

i)occbi+ occelg lg n(m_kd + lg u))の計算時間が掛かる．

4

実験

今回提案したアルゴリズムを実装し，FM-index[10] との計算時間の比較を行った．実験環境は，Intel Xeon CPU E7-8837 2.67GHz/1TB RAM，コンパイラは gcc4.4.7 を用いた．FM-index の実装は [11] を用いた．200MB の DNA データに対し，100 文字から 1000 文字まで 100 文字ごとの長さの検索文字列を，各 1000 個づつ検索し た．また提案手法の複数分類法におけるブロックの個 数は，ESP-index が短い文字列の復元に時間が掛かる ということを考慮し，求めるハミング距離 d を求める のに最低限必要なブロック数である d + 1 とした．ESP-indexの索引サイズは 163.98MB，索引構築にかかった 時間は 60.4948sec である．FM-index の索引サイズは ESP-indexの索引サイズと近い大きさになるようにパ ラメータを調整し 164.63MB，索引構築にかかった時 間は 85.78sec である．各ハミング距離の設定で取得で きた部分文字列の個数を表 1 示す．ハミング距離を 2

から 4 までの実験を行い，１つの検索文字列あたりの 検索時間を図 4,5,6 に示す．

表 1: ハミング距離 dist 以下の部分文字列の出現回数 文字列長 dist = 2 dist = 3 dist = 4

100 1717 2213 2962 200 1039 1084 1135 300 1027 1028 1033 400 1026 1040 1052 500 1015 1015 1016 600 1010 1010 1012 700 1017 1017 1018 800 1015 1017 1020 900 1018 1019 1020 1000 1011 1013 1014 よりハミング距離の大きい部分文字列を検索すると， 複数分類法におけるハミング距離の条件を満たす可能 性のある部分文字列の候補が多くなるため，より計算 量が増えるのは明らかである．また提案手法の計算時 間に注目すると，検索文字列の長さが長くなるほど高 速に計算できていることが分かる．これは ESP-index が短い文字列の検索に時間が掛かり，ある程度長い文 字列の方が高速に出現位置を計算できる性質に依るも のだと考えられる．

5

おわりに

本稿では，ESP-index と複数分類法を用い，ハミング 距離 d 以下の部分文字列検索アルゴリズムを提案した． 時間計算量は O(lg lg n(m + Σk iocccilg m lg u) lg∗u + Σk

i(d− i)occbi+ occelg lg n(m_kd + lg u))であり，実験

により FM-index よりも高速に動作することが確認で きた．今後，インフルエンザウイルスの類似度計算な ど，さらに具体的な事例に応用していく． 図 4: ハミング距離 2 の部分文字列の検索時間 図 5: ハミング距離 3 の部分文字列の検索時間 図 6: ハミング距離 4 の部分文字列の検索時間

参考文献

[1] S. Maruyamaa, M. Nakahara, N. Kishiue, H. Sakamoto: ESP-index: A compressed index based on edit-sensitive parsing, J. Discrete

Al-gorithms,Vol. 18,pp. 100–112 (2013)

[2] F.Claude,G.Navarro: Self-indexed grammar-based compression, Fund. in-form.,Vol. 111(3),pp. 313–337(2011)

[3] T.Gagie,P.Gawrychowski,J.Karkkainen,Y.Nekrich,S.Puglisi: A faster grammar-based self-index,

LATA,pp. 240–251(2012)

[4] M. Nakahara, S. Maruyama, T. Kuboyama, H. Sakamoto, Scalable Detection of Frequent Substrings by Grammar-Based Compression

IE-ICE Trans. on Information and

Systems,E96-D(3),pp. 457–464 (2013)

[5] E. Lehman, A. Shelat: Approximation al-gorithms for grammar-based compression. In

SODA pp. 205–212,(2002)

[6] N.J. Larsson and A. Moffat: Offline Dictionary-Based Compression. In DCC, pp. 296–305(1999) [7] S. Maruyama, H. Sakamoto, and M. Takeda: An Online Algorithm for Lightweight Grammar-Based Compression. Algorithms Vol. 5,pp.213– 235(2012)

[8] G. Cormode, S. Muthukrishnan: The string edit distance matching problem with moves, ACM

Transactions on Algorithms,Vol. 3 (1) (2007)

[9] Yoshimasa Takabatake, Yasuo Tabei, and Hiroshi Sakamoto: Improved ESP-index: a practical self-index for highly repetitive texts, In SEA,pp. 338-350 Copenhagen (DEN-MARK)(2014)

[10] Paolo Ferragina and Giovanni Manzini: An ex-perimental study of an opportunistic index In

SODA,pp. 269-278 Washington (USA), 2001