疎な接尾辞木構築のWord RAM上の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2012-10-26
• タイトル: 疎な接尾辞木構築のWord RAM上の高速化
• タイトル / 言語: en
• タイトル: Faster Sparse Suffix Tree Construction on Word RAM
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学工学部
• 著者所属: 株式会社調和技研
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Hokkaido University, Fac. Eng.
• 著者所属(英): en
• 著者所属(英): Chowa Giken Co.
• 著者所属(英): en
• 著者所属(英): Hokkaido University, IST.
• 著者名: 高木, 拓也; 上村, 卓史; 有村, 博紀
• 著者名(英): Takuya, Takagi; Takashi, Uemura; Hiroki, Arimura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 長さ N のテキストの K ≤ N 個の索引点に対する接尾辞木を疎接尾辞木 (sparse suffix tree) といい， O(K) 語の領域しか使用しないため，さまざまな応用に用いられている．上村と有村 (Proc. CPM2011, LNCS 6661, 2011) は，長さ N ビットのハフマン圧縮テキストが入力として与えられたとき，その疎接尾辞木を O(σ) 前処理時間と O(K+σ) 語の領域を用いて，オンライン構築するアルゴリズムを与えている．本稿では，ビット並列計算と簡潔トライ構造からなる詰め込み文字列 (packed string) 技法を用いて，長さ O(N) ビットのハフマン圧縮テキストに対して，疎接尾辞木を O(σ) 前処理時間と O(K+σ) 語の領域を用いて， O(⌈N/w⌉√w+K√w) 時間でオンライン構築するアルゴリズムを与える．ここに， w は計算機のレジスタ長 (ビット) であり， σ は符号中の符号語長さの総和である．これは，疎接尾辞木のオンライン構築で初めて， O(N) 時間より少ない計算時間を達成したアルゴリズムである．提案手法は， K≦O(N/√w) のときに従来手法より高速である．また，一般の有限接頭符号上や，単語アルファベット上の符号化テキストに対しても拡張可能である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present an efficient algorithm on Word RAM for constructing a sparse suffix tree on an encoded text over a regular prefix-code in O(⌈N/w⌉ √w+K√w) time using O(σ)preprocessing and O(K + σ) word space, where N is the length of the text in base letters, K is the length of the text in code words, σ is the size of a base alphabet Σ, σ is the total size of a code alphabet on Σ, and w is a bit-length of a register of Word RAM.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2012-AL-142, 号 9, p. 1-8, 発行日 2012-10-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会