Study of index construction and compression algorithms in fully-online setting

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

本研究は，様々な文字列情報学における問題に対し「どのようにすれば完全オンラインへの拡張が可能か？」を明らかにすることを目標としている．特に，(i)文脈性 (ii)完全オンライン性 (iii) 低メモリ性をもつ索引，すなわち「完全オンライン圧縮文字列索引」の構築を目指している．これを実現するためには，圧縮索引の通常オンライン構築アルゴリズムの開発と，その完全オンライン化の二つのステップが必要である．2022年度は機械学習分野において決定木モデルの列挙構造が動的計画法と同様の構造を持つことを見出し，『羅生門集合』と呼ばれる最適決定木とほとんど同じ精度を持つ決定木の集合を構築するアルゴリズムを初めて与えることに成功した．列挙した決定木は特徴量数の指数個存在する可能性があるため，これを保持するためにはよりコンパクトな索引が必要となる．この課題に対して本研究の圧縮索引構造のアイデアを用いることにより解決することに成功した．羅生門集合は機械学習モデルの説明可能性から近年注目されている概念であり，今後決定木以外のモデルへの拡張が考えられる．また昨年度に引き続き，東北大学のDiptarama Hendrian助教授・九州大学の稲永俊介教授らの協力のもと，昨年度おおむね完成していた最近印付き祖先（Nearest Marked Ancestor）クエリ構造を利用する線形サイズ接尾辞木（Linear-size Suffix Tree）の構築アルゴリズムを精査し具体的な手法を与えることに成功した．