第 5 章 準動的区間最小 ( 最大 ) 値問い合わせ 30
5.5 補題 17 の証明
A′[i]をAiの最小値とする．表A′に対するスパーステーブルSTA′ は，|A′|=mなので，
O(mlogm) = O(n)時間で構築できる．
表Aの各ブロックに対して表引きアルゴリズムを用いる．すなわち，それぞれの1≤ i ≤ mに対して表TLAiを計算する．ただし，素朴に式 (5.4)に基づきTLAiを計算する と合計O(n2)時間必要なので，表Aが±1の制約を満たしていることに注目した工夫を する．それぞれの1≤i≤mに対してAiの正規化ブロックNiを，それぞれの1≤j ≤s に対してNi[j] =Ai[j]−Ai[1]と定義する．表Aのすべてのブロックの正規化ブロックの 集合をN ={Ni : 1≤ i≤m}とする．なお，集合の定義より|N| ≤ mが成り立つこと に注意する．ここで次の命題が成り立つ．
命題 5 ([1]). 長さsの表T1,T2に対して，それぞれの1≤i≤sと定数cに対してT2[i] = T1[i] +cが成り立っているならば，任意の1≤i≤j ≤sに対してrmqT2(i, j) =rmqT1(i, j) が成り立つ．
命題 6 ([1]). |N|=O(√
n)が成り立つ．
証明. 表Aは±1の制約を満たし，ブロックの大きさがs=⌈(log2n)/2⌉であることに注 目すれば，正規化ブロックは2⌈(log2n)/2⌉−1 =O(√
n)通り存在する． 2 すべてのN ∈N に対してTLN を計算するとO(√
n×((log2n)/2)2) =O(n)時間かか る．計算済みのTLN と命題 5を用いることにより，すべての1≤ i≤ mに対してTLAi を線形時間で計算することができる．
すべてのTLAiと，表A′に対するスパーステーブルSTA′が計算されたとすると，rmqA(i1, i2) は高々A′に対するスパーステーブルによるRMQを1回とi1とi2が所属するブロックの 表引きアルゴリズムによるRMQを2回計算することにより，定数時間で計算できる．
補題 19. 準動的±1RMQ問題は事前に最終的な表の大きさnが与えられれば，償却定数 追加時間と最悪定数問い合わせ時間で解ける．
準動的±1RMQのデータ構造Rに対して，大きさをRに追加された要素数とし，容 量をRを最初に作成するときに指定するRに追加される最終的な要素数とする．次に，
事前に容量が与えられなくても，動的配列 [12]と同様に指数的に容量を増やした準動的
±1RMQを作成していくことにより，償却定数追加時間が実現できることを示す．準動 的±1RMQのデータ構造で保持される最終的な表をAとし，その大きさをnとする．最 初は容量0の準動的±1RMQのデータ構造を保持する．それぞれの1≤i≤nに対して，
i回目の追加操作を次のように行う．
(i−1が2のべき乗であるとき)
現在保持している準動的±1RMQのデータ構造を破棄し，新たに容量2iの準動的
±1RMQのデータ構造を作成する．それぞれの1≤j ≤iに対して，A[j]を新しい 準動的±1RMQのデータ構造に追加する．
(それ以外のとき)
現在保持している準動的±1RMQのデータ構造にA[i]を追加する．
i回目の追加操作の時間計算量をciとすると，補題19よりi−1が2のべき乗のときは線 形時間，それ以外のときは償却定数時間なので
∑n i=1
ci ≤n+
⌊log∑2n⌋ j=0
2j
< n+ 2n
= 3n
が成り立つ．そのため，償却定数追加時間で動作することがわかる．また，最悪定数問 い合わせ時間で動作することは自明である．以上より，補題 17は成り立つ．
第 6 章 実験結果
本章では実験結果を述べる．LCSk+に関して，提案手法のAlgorithm 1, 2と既存手法[2, 25]
を比較する．op-LCSk+ に関して，Algorithm 6と栗原ら [27]が提案したO(mnk2logk) 時間アルゴリズムの実行時間を比較する．実験はUbuntu 14.04，Xeon E5-2609，256GB メモリの計算機で行った．アルゴリズムはすべてC++で実装し，-O2の最適化オプショ ンを指定したgcc 4.8.4でコンパイルした．Paveti´cらのアルゴリズムの実装はhttps:
//github.com/fpavetic/lcskppで公開されているものを用いた．Paveti´cら [25]のア ルゴリズムをPˇZˇS，Bensonら [2]のO(mn)時間・O(km)領域アルゴリズムをBLMNS と表記する．
提案手法とPˇZˇS，BLMNSを次の4つの条件の元で比較する．
(1) アルファベットサイズ|Σ|= 4，長さn =m = 1000,2000,· · · ,10000のランダム文 字列においてk = 1,2,3,4のときの実行時間
(2) アルファベットサイズ|Σ|= 1,2,8,16，n =m = 1000,2000,· · · ,10000のランダム 文字列においてk = 3のときの実行時間
(3) アルファベットサイズ|Σ| = 26，n = m = 10000のランダム文字列においてk = 1,2,· · · ,100のときの実行時間
(4) http://www.ncbi.nlm.nih.gov/nuccore/346214858とhttp://www.ncbi.nlm.nih.
gov/nuccore/U38845.1で公開されているDNA配列においてk = 1,2,3,4,5のと きの実行時間
条件(1), (2), (3), (4)の実験結果をそれぞれ図 6.1, 6.2, 6.3, 6.4に示す．
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(a)|Σ|= 4,k= 1
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(b)|Σ|= 4, k= 2
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(c) |Σ|= 4, k= 3
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(d)|Σ|= 4, k= 4
図 6.1: |Σ|= 4のランダム文字列においてk = 1,2,3,4のときのAlgorithm 1, 2，PˇZˇS，
BLMNSの実行時間
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(a)|Σ|= 1,k= 3
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(b)|Σ|= 2, k= 3
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(c) |Σ|= 8, k= 3
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
(d)|Σ|= 16, k= 3
図 6.2: |Σ|= 1,2,8,16のランダム文字列においてk = 3のときのAlgorithm 1, 2，PˇZˇS，
BLMNSの実行時間
0 20 40 60 80 100 k
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Running Time (sec)
Alg. 1
Alg. 2 P
BLMNS
図 6.3: |Σ| = 26, n = m = 10000のランダム文字列においてk = 1,· · · ,100のときの Algorithm 1, 2, PˇZˇS，BLMNSの実行時間
1 2 3 4 5
k 0
1 2 3 4 5
Running Time (sec)
Alg. 1 Alg. 2 PBLMNS
図 6.4: DNA配列におけるAlgorithm 1, 2, PˇZˇS，BLMNSの実行時間
提案アルゴリズムはPˇZˇSと比べてkかアルファベットサイズが小さいとき高速に動作 した．これはPˇZˇSの実行時間は，入力文字列間で一致する長さkの部分文字列の数に 強く依存するが，kや|Σ|が小さいとき，その数が増えるためである．Algorithm 1より Algorithm 2のほうが高速に動作した．これは，Algorithm 1, 2の領域計算量はそれぞれ O(mn),O(km)なので，Algorithm 1におけるキャッシュミス率がAlgorithm 2より高い ためだと考えられる．また，Algorithm 2とBLMNSはほぼ同等の実行時間になった．
op-LCSk+に関して，Algorithm 6と栗原ら[27]が提案したO(mnk2logk)時間アルゴリ ズムの実行時間を比較する．栗原ら [27]のアルゴリズムをKNSと表記する．Algorithm 6 とKNSを次の2つの条件で比較する．
(1) アルファベットΣ = {1,2,· · · ,100}，長さn = m = 1000,2000,· · · ,10000のラン ダム文字列においてk = 2,3,4,5のときの実行時間
(2) アルファベットΣ = {1,2,· · · ,100}，長さn=m = 5000のランダム文字列におい てk = 2,3,· · ·,100のときの実行時間
行った実験の中で，Algorithm 6はΣ ={1,2,· · · ,100},k = 2のときを除き，KNSより 高速に動作した．実験的にもAlgorithm 6はKNSより高速に動作することが確認できた．
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0 50 100 150 200 250 300
Running Time (sec)
Alg. 6 KNS
(a) Σ ={1,2,· · ·,100},k= 2
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0 50 100 150 200 250 300
Running Time (sec)
Alg. 6 KNS
(b) Σ ={1,2,· · ·,100},k= 3
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0 50 100 150 200 250 300
Running Time (sec)
Alg. 6 KNS
(c) Σ ={1,2,· · · ,100},k= 4
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Length
0 50 100 150 200 250 300
Running Time (sec)
Alg. 6 KNS
(d) Σ ={1,2,· · ·,100},k= 5
図 6.5: Σ ={1,2,· · · ,100}のランダム文字列においてk = 2,3,4,5のときのAlgorithm 6, KNSの実行時間
0 20 40 60 80 100
k 0
50 100 150 200 250 300
Running Time (sec)
Alg. 6 KNS
図 6.6: Σ ={1,2,· · · ,100}, n=m= 5000のランダム文字列においてk = 2,· · · ,100の ときのAlgorithm 6，KNSの実行時間
第 7 章 まとめ
本稿では，LCSk+問題とop-LCSk+問題がO(mn)時間で解けることを示した．LCSk+問 題に対しては既存手法 [2, 25]より高速な最悪時間計算量アルゴリズムを提案した．ただ し実験結果は既存手法のほうが概して高速に動作した．op-LCSk+問題に対する提案手法 は，順序同型の性質より単純な動的計画表で解くことができないためLCSk+問題に対す るアルゴリズムより複雑だが，LCSk+ 問題と同じ時間計算量を実現した．提案手法は実 験的にも既存手法より高速に動作した．また，末尾もしくは先頭どちらか一方のみに要 素を追加する操作に対応した，実装が容易な準動的RMQのアルゴリズムを提案した．
今後の課題として，LCSk+ 問題，op-LCSk+ 問題に対してより良い計算量のアルゴリ ズムの開発がある．LCS問題やLCSk問題に対して4人のロシア人の方法（four-Russian technique）を用いてO(mn/logmn)時間で解けることが知られている [15]．4人のロシ ア人の方法がLCSk+問題に対しても適用できればより良い時間計算量のアルゴリズムが 開発できると考えられる．また，第4.2章のop-LCSk+問題に対する省領域アルゴリズム は要素の削除に対応する動的RMQを用いた．動的RMQは保持している表中の任意の 要素の削除と任意の位置への要素の追加に対応しているが，第4.2章のアルゴリズムでは 末尾要素の削除と先頭への要素追加しか行わない．そのため，それらをより効率的に行 えるRMQのデータ構造を開発することにより，より良い時間計算量のアルゴリズムが 実現できると考えられる．
参考文献
[1] M. A. Bender and M. Farach-Colton. The LCA problem revisited. InLATIN 2000, pp. 88–94, 2000.
[2] G. Benson, A. Levy, S. Maimoni, D. Noifeld, and B. Shalom. LCSk: A refined similarity measure. Theoretical Computer Science, 638:11–26, 2016.
[3] L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. In SPIRE 2000, pp. 39–48, 2000.
[4] M. Bouvel, D. Rossin, and S. Vialette. Longest common separable pattern among permutations. In CPM 2007, pp. 316–327, 2007.
[5] G. S. Brodal, P. Davoodi, and S. S. Rao. Path minima queries in dynamic weighted trees. In WADS 2011, pp. 290–301, 2011.
[6] D. Cantone, S. Faro, and M. O. K¨ulekci. An efficient skip-search approach to the order-preserving pattern matching problem. In PSC 2015, pp. 22–35, 2015.
[7] T. Chhabra, S. Faro, M. O. K¨ulekci, and J. Tarhio. Engineering order-preserving pattern matching with SIMD parallelism. Software: Practice and Experience, 2016.
[8] T. Chhabra, M. O. K¨ulekci, and J. Tarhio. Alternative algorithms for order-preserving matching. In PSC 2015, pp. 36–46, 2015.
[9] T. Chhabra and J. Tarhio. A filtration method for order-preserving matching. In-formation Processing Letters, 116(2):71–74, 2016.
[10] S. Cho, J. C. Na, K. Park, and J. S. Sim. A fast algorithm for order-preserving pattern matching. Information Processing Letters, 115(2):397–402, 2015.
[11] R. Cole and R. Hariharan. Dynamic LCA queries on trees. SIAM Journal on Computing, 34(4):894–923, 2005.
[12] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algo-rithms. The MIT Press, 3rd edition, 2009.
[13] M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, A. Langiu, S. P. Pissis, J. Radoszewski, W. Rytter, and T. Wale´n. Order-preserving indexing. Theoretical Computer Science, 638:122–135, 2016.
[14] M. Crochemore and W. Rytter. Jewels of Stringology. World Scientific, 2002.
[15] S. Deorowicz and S. Grabowski. Efficient algorithms for the longest common sub-sequence in k-length substrings. Information Processing Letters, 114(11):634–638, 2014.
[16] S. Faro and M. O. K¨ulekci. Efficient algorithms for the order preserving pattern matching problem. In AAIM 2016, pp. 185–196, 2016.
[17] J. Fischer. Inducing the LCP-array. In WADS 2011, pp. 374–385, 2011.
[18] J. Fischer and V. Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM Journal on Computing, 40(2):465–492, 2011.
[19] D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
[20] M. M. Hasan, A. Islam, M. S. Rahman, and M. Rahman. Order preserving pattern matching revisited. Pattern Recognition Letters, 55:15–21, 2015.
[21] A. Heliou, M. Lonard, L. Mouchard, and M. Salson. Efficient dynamic range mini-mum query. Theoretical Computer Science, 656, Part B:108–117, 2016.
[22] R. Khan, M. Ahmad, and M. Zakarya. Longest common subsequence based algo-rithm for measuring similarity between time series: A new approach. World Applied Sciences Journal, 24(9):1192–1198, 2013.
[23] J. Kim, P. Eades, R. Fleischer, S.-H. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, and T. Tokuyama. Order-preserving matching. Theoretical Computer Science, 525(13):68–79, 2014.
[24] M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, and T. Walen. A linear time algorithm for consecutive permutation pattern matching. Information Processing Letters, 113(12):430–433, 2013.
[25] F. Paveti´c, G. ˇZuˇzi´c, and M. ˇSiki´c. LCSk++: Practical similarity metric for long strings. CoRR, abs/1407.2407, 2014.
[26] I. Sovi´c, M. ˇSiki´c, A. Wilm, S. N. Fenlon, S. Chen, and N. Nagarajan. Fast and sensitive mapping of nanopore sequencing reads with GraphMap. Nature Commu-nications, 7(11307), 2016.
[27] 栗原,成澤,篠原. 順序同型な部分系列を用いた数値列に対する最長共通部分列問題. 電子情報通信学会コンピュテーション研究会，COMP2015-38, pp. 11–20, 2016.
研究業績
国際会議
• Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, and Ayumi Shinohara. Longest common subsequence in at leastk length order-isomorphic substrings. InSOFSEM 2017, pp. 363–374, 2017.
• Yohei Ueki, Kazuyuki Narisawa, and Ayumi Shinohara. A fast order-preserving matching with q-neighborhood filtration using SIMD instructions. In Student Re-search Forum Papers and Posters at SOFSEM 2016, pp. 108–115, 2016.
• Diptarama, Yohei Ueki, Kazuyuki Narisawa, and Ayumi Shinohara. KMP based pattern matching algorithms for multi-track strings. In Student Research Forum Papers and Posters at SOFSEM 2016, pp. 100–107, 2016.
国内会議
• 上木 庸平, 成澤 和志, 篠原 歩．順序保存照合に対する増減フィルタの拡張と高速 な実装．冬のLAシンポジウム，2015．
ポスター
• Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, and Ayumi Shinohara. Order-preserving longest common subsequence. In WTCS 2016, p. 67, 2016.