IWOCA 2017 アクセプト (2)

文字列情報学研究室の杉本志穂さん・野田尚貴君の論文が国際会議 IWOCA 2017 にアクセプトされました。

文字列情報学研究室の杉本志穂さん (D3)、野田尚貴君 (執筆時 B4 - 2016年3月卒業) の論文

"Computing Abelian string regularities based on RLE,

Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda."

が国際会議 IWOCA 2017 にアクセプトされました。2つの文字列 x, y について任意の文字の x, y での出現の数が等しいとき、x, y はアーベル同値であるといいます (例えば、aab と aba はアーベル同値)。様々な繰り返し構造に対して、アーベル同値の概念を導入した構造が考えられています。例えば、aabaab のような平方 (square) とよばれる同じ文字列の2回の繰り返しに対して、abaaab のようにアーベル同値な文字列を2つの連結をアーベル平方とよびます。この論文では、入力文字列のアーベル平方とアーベル周期を計算するアルゴリズムを提案してます。また、2つの入力文字列の最長共通アーベル同値部分文字列を計算するアルゴリズムを提案しています。これらのアルゴリズムは、入力文字列の連長圧縮表現 (Run-Length-Encoding) を計算した後に、その圧縮表現上での計算を行う手法になっています。圧縮表現を計算することで計算時間がかかると想像してしまうかもしれませんが、圧縮表現のサイズが入力文字列のサイズになっているときでも既存研究と同等の結果であり、圧縮表現のサイズが小さくなる文字列ほど、理論的に高速な手法であるという結果になっています。
 

IWOCA 2017 は、7月17日~7月21日に、オーストラリアのニューカッスルにて開催されます。