文献

J-GLOBAL ID：202102229830664728   整理番号：21A2954395

スライディングウィンドウのためのパリンドロームツリーとその応用【JST・京大機械翻訳】

Palindromic trees for a sliding window and its applications

著者 (8件)： Mieno Takuya (Department of Informatics, Kyushu University, Japan) ,  Mieno Takuya (Japan Society for the Promotion of Science, Japan) ,  Watanabe Kiichi (Department of Informatics, Kyushu University, Japan) ,  Nakashima Yuto (Department of Informatics, Kyushu University, Japan) ,  Inenaga Shunsuke (Department of Informatics, Kyushu University, Japan) ,  Inenaga Shunsuke (PRESTO, Japan Science and Technology Agency, Japan) ,  Bannai Hideo (M&D Data Science Center, Tokyo Medical and Dental University, Japan) ,  Takeda Masayuki (Department of Informatics, Kyushu University, Japan)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 173  ページ： Null  発行年： 2022年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 長さnのストリングSに対するパリンドロームツリー(a.k.a.eertree)は,O(n)空間[RubinchikとShur,2018]を用いて,Sの全ての異なるパリンドロームサブストリングの集合を表す木のようなデータ構造である。Sがサイズσのアルファベット上にあるとき,オンライン方式で与えられ,次に,SのパリンドロームツリーはO(n)空間でO(nlogσ)時間で構築できる。本論文では,この問題のスライディングウィンドウバージョンを考察した:ほとんどのdにおける長さのスライディングウィンドウに対して,著者らは,1≦j-i+1≦dのS上で,あらゆるスライディングウィンドウS[i.j]に対してサイズO(d)のパリンドロームツリーを維持するアルゴリズムの2つのバージョンを提示した。第1版は,O(nlogσ′)時間においてO(d)空間で動作し,そこでは,θ_dが窓における異なる特性の最大数であり,第2のものは(d+2)σ+O(d)空間を有するO(n+dσ)時間において働く。また,スライディングウィンドウに対する最小固有パリンドロームサブストリング(MUPS)と最小存在パリンドローム語(MAPW)の効率的計算に,このアルゴリズムをいかに適用できるかも示した。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  オンラインシステム ,  データ構造 ,  *パリンドローム
準シソーラス用語： *スライディングウィンドウ , 【Automatic Indexing@JST】

著者キーワード (4件)： ストリングアルゴリズム ,  データ構造 ,  パリンドローム ,  スライディングウィンドウ

分類 (2件)： 遺伝子の構造と化学  (EC02020U) ,  分子遺伝学一般  (EC02010J)

タイトルに関連する用語 (2件)： スライディングウィンドウ ,  応用