文献

J-GLOBAL ID：202302279550828640   整理番号：23A0406571

コンパクト非巡回語グラフに基づく連長圧縮Burrows-Wheeler変換の効率良い構築

著者 (5件)： 須江瑞樹 (北大 大学院情報科学院) ,  小林靖明 (北大 大学院情報科学研究院) ,  有村博紀 (北大 大学院情報科学研究院) ,  中島祐人 (九大 大学院システム情報科学研究院) ,  稲永俊介 (九大 大学院システム情報科学研究院)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 122  号： 294(COMP2022 21-32)  ページ： 21-28 (WEB ONLY)  発行年： 2022年11月29日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,反復テキストに対する代表的な圧縮索引であるコンパクト非巡回有向語グラフ(CDAWG)と連長圧縮Burrows-Wheeler変換(Run-length BWT,連長圧縮BWT)の間の効率良い変換について考察する.主結果として,入力として与えられた長さnの読み取り専用テキストとサイズeのCDAWGから,サイズrの連長圧縮BWTをO(e)語の作業領域と時間で構築する効率良いアルゴリズムを与える.これは,入出力の圧縮索引長の和を超えないメモリと時間を使って,CDAWGを連長圧縮BWTに変換する初めてのアルゴリズムである.(著者抄録)

シソーラス用語： データ構造 ,  圧縮 ,  計算機アルゴリズム ,  作業空間 ,  効率 ,  文字列 ,  *データ圧縮 ,  *プログラム変換
準シソーラス用語： ランレングス ,  高効率 ,  索引構造 ,  接尾辞木 ,  変換効率

分類 (1件)： 自然語処理  (JE06000L)

引用文献 (19件)：

• H. Bannai, P. Gawrychowski, S. Inenaga, and M. Takeda. Converting SLP to LZ78 in almost linear time. In Annual Symposium on Combinatorial Pattern Matching, pp. 38-49. Springer, 2013.
• A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M.-T. Chen, and J. Seiferas. The smallest automation recognizing the subwords of a text. TCS, 40:31-55, 1985.
• A. Blumer, J. Blumer, D. Haussler, R. McConnell, and A. Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. JACM, 34(3):578-595, 1987.
• M. Burrows and D. Wheeler. A block-sorting lossless data compression algorithm. In Digital SRC Research Report. Citeseer, 1994.
• P. Ferragina and G. Manzini. Indexing compressed text. Journal of the ACM (JACM), 52(4):552-581, 2005.

タイトルに関連する用語 (4件)： 巡回 ,  グラフ ,  連長圧縮 ,  構築