文献

J-GLOBAL ID：202002230770301107   整理番号：20A0529241

交互BWT アルゴリズム的展望【JST・京大機械翻訳】

The Alternating BWT: An algorithmic perspective

著者 (5件)： Giancarlo Raffaele (University of Palermo, Italy) ,  Manzini Giovanni (University of Eastern Piedmont and IIT-CNR Pisa, Italy) ,  Restivo Antonio (University of Palermo, Italy) ,  Rosone Giovanna (University of Pisa, Italy) ,  Sciortino Marinella (University of Palermo, Italy)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 812  ページ： 230-243  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Burrows-Wheeler変換(BWT)はデータ圧縮のために1994年に導入された単語変換である。それは,科学と工学におけるいくつかの分野において重要な応用によって,自己索引化データ構造を設計するための基本的ツールになった。交互変換(ABWT)は,最近Gesselら(2012)に導入されたもう一つの変換であり,Wordに関するCombinoricsの分野で研究されている。それは,通常のものの代わりに交互の語彙的順序を使用することを除いて,BWTに類似している。Giancarloら(2018)の結果に基づいて,BWTとABWTが可逆変換の大きなクラスの一部であることを示した。ここでは,新しい変換ABWTの組合せとアルゴリズム研究を提供した。BWTとABWTの間の深い類似性を証明することにより,上記のクラスにおける唯一のものであることを証明することにより,効率的な反転可能性を保証する新しい概念であるランク変換可能なものであることを証明した。さらに,逆方向探索手順がABWTに効率的に一般化できることを示した。この結果は,ABWTが効率的な圧縮フルテキストインデックスの基礎として使用できることを意味する。最後に,著者らは,ABWTが,交互の語彙の順序に関して単語の最小の周期的回転を見つけるために,線形時間アルゴリズムによって,差分Cover suffixソートアルゴリズム(Kaerkkaeinenら,2006)の組合せを使用することによって,効率的に計算することができることを証明した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  データ構造 ,  語彙 ,  類似性 ,  データ圧縮 ,  単語 ,  被覆
準シソーラス用語： 線形時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (4件)： 交互Burrows-Wheeler変換 ,  ランク反転可能性 ,  差分被覆アルゴリズム ,  Galois語

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： アルゴリズム ,  展望