組合せ的文字列分解

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

組合せ的文字列分解

杉本, 志穂

https://doi.org/10.15017/1928634

出版情報：Kyushu University, 2017, 博士（理学）, 課程博士 バージョン：

権利関係：

（別紙様式２）

氏 名 ： 杉本 志穂

論 文 名 ：

Factorizing Strings into Combinatorial Objects

(組合せ的文字列分解)

区 分 ： 甲

論 文 内 容 の 要 旨

文字列分解

(string factorization)

LZ

LZ分解は，「各項が既出」という

Lyndon分解とLZ分解の項数は，文法圧縮における文法サイズの下界を与える

文字列分解の研究は，文字列組合せ論分野と文字列アルゴリズム分野の双方へ貢献することが期待 できる．

本論文では，既存あるいは新たに定義した文字列分解問題に対し，その組合せ的性質を究明し，

効率的なアルゴリズムを開発した．

第 一 に ，逆 向 き

LZ分 解 問 題 お よ び そ の 変 種 に 対 し 省 領 域 な オ ン ラ イ ン ア ル ゴ リ ズ ム を 開 発

LZ

O(n logσ)

n)

Kolpakov-Kucherovア ル ゴ リ ズ ム に 比 べ ， 提 案 ア

O(n log

n )

log σ)ビ ッ ト 領 域 で 動 作 し 省 領 域 で あ る ． こ こ で ， n

LZ

第 二 に ， 項 数 最 小 回 文 分 解 お よ び そ の 変 種 を 求 め る オ ン ラ イ ン ア ル ゴ リ ズ ム を 開 発 し た ． こ こ で ， 項 数 最 小 回 文 分 解 と は ， 「 各 項 が 回 文 」 と い う 制 約 の 下 で 項 数 を 最 小 に す る 分 解 を い う ．本 論 文 で は 項 数 最 小 回 文 分 解 の 一 つ を

O(n log n)

O(n)

NP完 全 で あ る こ と を 示 し た ．

第 三 に ， 閉 文 字 列 分 解 を

O(n)

wが 閉 文 字 列 で あ る と は ， 文 字 列 u

|<|w|） が 存 在 し て ， u

w

2回 を 除 い て w

第 四 に ， ア ー ベ ル 同 値 性 に か か わ る 問 題 を 取 り 上 げ ， 連 長 分 解 を 前 処 理 と し て 用 い る 効 率 的 ア ル ゴ リ ズ ム を 開 発 し た ．文字列

x, y

x

y

(1)アーベル平方を O(mn)

(2)アーベ

O(mn)

n)

n である．これらのアル

O(n

)

m

)/(m-σ )=ω(n)のときには O(σ(m

+n))

(Amir et al. 2014)より高速である．(2)

log log n = ω(m

)

O(n(log log n+log σ))

)

O(σn

)時間アルゴリズム (Grabowski 2015)

n = ω(m)

O(n log

n log

n)

2016)