九州大学学術情報リポジトリ
Kyushu University Institutional Repository
文字列索引の省領域化とパターン発見の効率化のた めの組み合わせ論的アプローチ
藤重, 雄大
https://doi.org/10.15017/4060184
出版情報：Kyushu University, 2019, 博士（情報科学）, 課程博士 バージョン：
権利関係：
（別紙様式２）
氏 名 ： 藤重 雄大
論 文 名 ： Combinatorial Approaches for Compact String Indexing and
Efficient Pattern Discovery
(文字列索引の省領域化とパターン発見の効率化のための組み合わせ論的アプローチ)
区 分 ： 甲
論 文 内 容 の 要 旨
近年のネットワークの普及に加え，センサ技術の発達やモバイル端末の普及により，大規模かつ 多様なデータが産出され続けている．このような大規模なデータには，社会や経済などの問題を解 決し得る情報が潜んでおり，その利活用が世界中で注目を集めている．ところが，これらのデータ の多くは定まった形式をもたないため，定型データを対象に発展してきた従来のデータ解析技術の適用 が困難であり，非定型データのための新しいデータ解析技術の確立が急務である．非定型データは，陽 に構造を持たない記号の列，すなわち文字列と捉えることができるため，本研究では，文字列を扱うデ ータ処理技術の効率化に挑む．この効率化には，通常のアルゴリズムとデータ構造に関する知識に加え，
文字列データが潜在的にもつ組み合わせ的性質の活用が必須である．例えば，著名なKMPパタン照合ア ルゴリズムは，パタンの周期性に関する性質に基づく．また，重要な部分文字列索引として知られる接 尾辞木とDAWGは，入力文字列の部分文字列上に導入された同値関係 ≡L, ≡R に基づく．
本研究では，文字列の組み合わせ的性質の活用により，(A) 索引構造の高速な構築・省領域化と(B) パ タン発見アルゴリズムの効率化の研究を行った．
(A) では， (A-1) DAWG構 築 ア ル ゴ リ ズ ム の 高 速 化 ，(A-2) DAWGの 省 領 域 化 ，(A-3) 頻出部分文 字列パタン列挙のための索引構造の省領域化に 取 り 組 ん だ ．(A-1) に つ い て は ， 整 数 ア ル フ ァ ベ ッ ト 上 の 入 力 文 字 列 に 対 す る 世 界 初 の 線 形 時 間DAWG構 築 ア ル ゴ リ ズ ム の 開 発 に 成 功 し た ．こ の 成 果 は ， 接 尾 辞 木 とDAWGを 基 礎 付 け る 同値関係≡L, ≡Rのあいだに成り立つ性質の究明によるもので ある．双 方 向 部 分 文 字 列 索 引 と し て 知 ら れ る affix tree に つ い て も 同 じ 性 質 を 用 い て 線 形 時 間 構 築 ア ル ゴ リ ズ ム を 示 し た ．
(A-2) に つ い て は ， 部 分 文 字 列 探 索 に お け る ク エ リ 文 字 列 は 十 分 短 い と い う 実 用 的 観 点 か ら ， 長 さ k 以 下 の ク エ リ 文 字 列 に 対 し て 正 し く 動 作 す る 部 分 文 字 列 索 引 と し て ，k-truncated DAWG を 定 義 し ， そ の オ ン ラ イ ン 構 築 ア ル ゴ リ ズ ム を 開 発 し た ．DAWGの サ イ ズ は 入 力 文 字 列 n に 関 し て 線 形 で あ る の に 対 し ，k-truncated DAWG の サ イ ズ は O(|Subk| + k) と な る ．こ こ で ，|Subk| は 入 力 文 字 列 中 の 長 さ k の 部 分 文 字 列 の 異 な り 数 を 表 す ． ま た ， 本 研 究 に お い て |Subk| ≤ kγ を 示 し た ． こ こ で ， γ は 最 小 の 文 字 列 ア ト ラ ク タ の サ イ ズ で あ り ， あ ら ゆ る 辞 書 式 圧 縮 手 法 の 圧 縮 サ イ ズ の 下 界 と な る こ と が 知 ら れ て い る ．し た が っ て ，入 力 文 字 列 が 十 分 高 い 圧 縮 率 で 圧 縮 可 能 な と き ， k-truncated DAWGは DAWG に 対 し て 小 さ く な る ．
(A-3) については，頻出部分文字列パタン列挙問題の変種のための索引構造の省領域化に成功した．
頻出部分文字列パタン列挙問題とは，文書(文字列)の有限集合 D と正整数 d が与えられて， d 個以 上の文書に生起する文字列をすべて列挙する問題である．本研究では，その変種として，ク エ リ 文 字 列 p を 部 分 文 字 列 と し て 含 み ，か つ ，文字列の包含関係に関して極大な文 字 列 の み を 列 挙 す る 問 題 に 取 り 組 み ，O(nlog|D|) 領 域・O(|p| + o·loglog|D|) ク エ リ 応 答 時 間 の 索 引 構 造 を 開 発 し た ．こ こ で ， n は D 中 の 文 字 列 長 の 総 和 ，o は 解 の サ イ ズ で あ る ．こ の 結 果 は ，Nishimoto ら の 先 行 研 究 を ， 領 域 ・ ク エ リ 応 答 時 間 と も に 大 幅 に 改 善 し て い る ．
(B) で は ， 入 力 文 字 列 に 含 ま れ る 組 み 合 わ せ 的 オ ブ ジ ェ ク ト(combinatorial objects)を 列 挙 す る 問 題 に 取 り 組 ん だ ．組 み 合 わ せ 的 オ ブ ジ ェ ク ト と し て ，(B-1) 長 さ 制 約 付 き ギ ャ ッ プ 付 き 回 文 と ， (B-2) 極 大 反 復 の ２ つ を 取 り 上 げ た ． 長 さ 制 約 付 き ギ ャ ッ プ 付 き 回 文 と は ， 回 文 の 中 央 に ギ ャ ッ プ を 許 し た も の で あ り ，形 式 的 に は ，vuvR と 表 せ る 文 字 列 で ，gmi n ≤ |u| ≤ gm a x, u[1] ≠ u[|v|], |v| ≥ ami n
と い う 制 約 を 満 た す も の を 指 す ． ま た ， 文 字 列 w の 極 大 反 復 と は ，w[i..j] が 反 復 文 字 列 と な る よ う な 区 間 I=[i, j] (1 ≤ i ≤ j ≤ |w|) の う ち 区 間 の 包 含 関 係 に 関 し て 極 大 な も の を い い ， 文 字 列 x が 反 復 文 字 列 で あ る と は x = ye と な る 文 字 列 y と 有 理 数 e ≥ 2 が 存 在 す る と き を い う ．
(B-1) の 列 挙 に 関 し て は ，先 行 研 究 と し て Kolpakov と Kucherov の O(nlogσ + occ) 時 間・O(n) 領 域 で 動 作 す る オ フ ラ イ ン ア ル ゴ リ ズ ム が 知 ら れ て い る ． 本 研 究 で は ，O(n ((gma x − gmi n) / am i n + logσ) + occ) 時 間 で 動 作 す る オ ン ラ イ ン ア ル ゴ リ ズ ム を 開 発 し た ． ここで，σ はアルファベットサ イズ，occ は出力の個数である．(gma x − gmi n) / ami n∈ O(logσ) であるとき，計算時間は先 行 研 究 の オ フ ラ イ ン ア ル ゴ リ ズ ム と 同 等 で あ る ．
一 方 ，(B-2) の 列 挙 に 関 し て は ，先 行 研 究 と し て ，順 序 付 き ア ル フ ァ ベ ッ ト 上 の 長 さ n の 文 字 列 に 対 し て O(n A(n)) 時 間 ・O(n) 領 域 で 動 作 す る Crochemore ら の ア ル ゴ リ ズ ム が 知 ら れ て い る ． こ こ で ，A は 逆 ア ッ カ ー マ ン 関 数 で あ る ． 長 さ n の 任 意 の 文 字 列 に 含 ま れ る 極 大 反 復 の 個 数 は n 未 満 で あ る こ と が 知 ら れ て い る が ，本 研 究 で は ，ま ず ，入 力 文 字 列 の 連 長 圧 縮 サ イ ズ m に 着 目 し ，新 た な 上 界 2m を 示 し た ．こ こ で ，連 長 圧 縮 と は 文 字 列 中 に 連 続 し て 出 現 す る 文 字 を そ の 文 字 と 連 続 長 の 対 で 置 き 換 え る 圧 縮 法 を い う ．次 に ，連 長 圧 縮 形 式 で 与 え ら れ た 入 力 文 字 列 に 対 し て 極 大 反 復 を O(m A(m)) 時 間 ・O(m) 領 域 で 列 挙 す る ア ル ゴ リ ズ ム を 開 発 し た ． 連 長 圧 縮 は O(n) 時 間 ・O(m) 追 加 領 域 で 行 う こ と が で き ， か つ ， m ≤ n が 常 に 成 り 立 つ こ と か ら ， 連 長 圧 縮 後 に 提 案 ア ル ゴ リ ズ ム を 適 用 す る 手 法 は ， 先 行 研 究 と 同 等 ま た は 高 速 ・ 省 領 域 で あ る ．
