最先端文字列アルゴリズム理論に基づく巨大データ解析技法

点击翻译按钮获取中文摘要

前から読んでも後ろから読んでも同じ文字列を回文という。文字列から回文構造を発見する問題は特に生物情報科学の分野で重要視され、盛んに研究されている。本研究期間においては、文字列中の回文構造を効率よく検出するためのデータ構造・アルゴリズムの開発を主として行った。他にも文字列圧縮アルゴリズムの性能に関する研究などを行い、以下の６つの成果を得た。１つ目の成果は、入力文字列に対して特定の編集操作が許された設定において、ユニーク回文部分文字列を計算するアルゴリズムの提案である。ユニーク回文部分文字列とは、文字列中にちょうど一度だけ出現する回文である。本成果は国際会議 SPIRE 2021 に採択されており、さらにその結果を応用した研究成果は国際会議 IWOCA 2022 に投稿された。２つ目の成果は、双方向マクロスキームと呼ばれる文字列圧縮形式に対する圧縮性能限界の解明である。３つ目の成果は、LZEnd 圧縮と呼ばれる文字列圧縮手法の圧縮性能に関する新たな結果の証明である。文字列圧縮手法の性能を比較・解析する研究は文字列圧縮研究の分野で近年盛んに行われており、特に２つ目の成果は同分野で注目されていた未解決問題のひとつを解決したものである。２つ目と３つ目の成果は国際会議 SPIRE 2021 に採択されている。４つ目の成果は、RePair という文字列圧縮手法の圧縮性能に関する新たな結果の証明である。５つ目の成果は、デカルト木部分列照合問題と呼ばれる緩和された部分列照合問題に対するアルゴリズムの提案である。６つ目の成果は、圧縮表現された文字列上で、その文字列中に存在しない不在文字列を計算するアルゴリズムの提案である。上記３つの成果はいずれも国際会議 CPM 2022 に採択されている。