マルチトラック文字列上の順列パターン照合のための省メモリな索引構造
電子情報通信学会コンピュテーション研究会,
信学技報 Vol.COMP2014-15, pp.1-8
(2014)
開催日:
2014年9月2-2日
Abstract / 概要
長さ$n$の文字列$N$個からなる文字列の多重集合をマルチトラック文字列と呼ぶ． 長さがそれぞれ$n$，$m$ である二つのマルチトラック文字列 $\mathcal{T} = \{ t_1,\ldots,t_N \}$ と $\mathcal{P}=\{ p_1,\ldots,p_N \}$が与えられたとき， $\{ p_1, \ldots, p_N \}= \{ t_1[i:i+m-1],\ldots,t_N[i:i+m-1] \}$を満たすすべての位置$i$を返す問題を 順列パターン照合 と呼ぶ． 順列パターン照合問題のためのデータ構造として， $O(n)$領域という省メモリな 縮約マルチトラックポジションヒープ（CMTPH）がある． CMTPHを用いることで，順列パターン照合問題を$O(m^2N^2+occ)$時間で解くことができる． 本研究では，$O(nN)$時間の新しいCMTPH構築アルゴリズムを提案する． また，CMTPHに対して$O(n)$領域のデータ構造を追加することで， 照合時間が$O(max(mN+occ,m^2N^2))$時間で抑えられることを示す．