文字列組み合わせ論による情報学へのアプローチ

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

「回文の数学的性質の解明」に加え、「アーベル文字列の性質解明」に取り組んだ。連長圧縮文字列上でのアーベル文字列の性質の計算を行うアルゴリズムを提案した．２つの文字列がアーベル同値であるとは、一方の文字列がもう一方の文字列の順列になっていることである。アーベル同値は音楽の性質分類や遺伝子の類似指標等に用いられるため、様々な研究がなされている。また、連長圧縮（RLE）とは文字とその繰り返しの回数で文字列を圧縮表現する手法であり、同じ文字の繰り返しの多い文字列に対しては、高い圧縮率が得られる。連長圧縮は実データに対しても多く用いられており、連長圧縮で圧縮した文字列上で動作する文字列アルゴリズムの開発が数多く行われている。本研究では，連長圧縮文字列上で、アーベル平方を O(nm) 時間、アーベル周期を O(nm) 時間、最長共通アーベル文字列を O(nm^2) 時間で計算するアルゴリズムを提案した。この成果をまとめた論文は国際会議 IWOCA 2017 に採択された。また，国際論文誌 Journal of Discrete Algorothmsの特集号（Special Issue for extended IWOCA 2017 paper） にも投稿済みである。さらに，k-Abelian 文字列の研究も行った。２つの文字列が k-Abelian 同値であるとは、長さ k 部分文字列の出現回数が等しいことである。文字列学の第一人者である Maxime Crochmore 氏と Golnaz Badkobeh 氏 (University of Warwick)との共同研究として，k-Abealin 同値の判定を既存研究よりも小さい領域で計算するアルゴリズムの構築に取り組んでおり、今後随時発表を行う予定である。