文献

J-GLOBAL ID：201802282820961132   整理番号：18A0731447

高頻度な繰り返し構造を含むテキストに対する省領域な動的索引

著者 (3件)： 西本崇晃 (RIKEN 革新知能統合研究セ) ,  高畠嘉将 (九州工大) ,  田部井靖生 (RIKEN 革新知能統合研究セ)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2018  号： AL-167  ページ： Vol.2018-AL-167,No.1,1-8 (WEB ONLY)  発行年： 2018年03月01日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では高頻度反復テキスト集合用の新しい圧縮動的索引を提案する。シグネチャエンコーディングとは短いパターンに対する検索速度が遅いという欠点を持つ圧縮動的索引である。本論文はシグネチャエンコーディングに枝刈りされた接尾辞木(TST)を組み合わせることで高頻度反復テキスト集合に対して動的な更新操作と高速なパターン検索の両立を可能にし,また,このTST索引と名付けた新しい圧縮動的索引は実験において性能の目覚ましい改善を示した。(著者抄録)

シソーラス用語： *頻度 ,  *逐次検出 ,  *データ ,  *動的系 ,  *索引 ,  ゲーム理論 ,  データ構造 ,  圧縮性
準シソーラス用語： シグネチャエンコーディング ,  *テキストデータ ,  枝刈り【木探索】 ,  接尾辞木

分類 (1件)： 検索技術  (AC06020S)

引用文献 (17件)：

• 1000 Genomes Project Consortium. A map of human genome variation from population-scale sequencing. Nature, Vol. 467, pp. 1061-1073, 2010.
• Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Optimal-time text indexing in BWT-runs bounded space. CoRR, Vol. abs/1705.10382, , 2017.
• Yoshimasa Takabatake, Yasuo Tabei, and Hiroshi Sakamoto. Improved ESP-index: A practical self-index for highly repetitive texts. In Proceedings of the 13th International Symposium on Experimental Algorithms, pp. 338-350, 2014.
• Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Dynamic index and LZ factorization in compressed space. In Proceedings of the 20th Annual Symposium on Prague Stringology Conference, pp. 158-170, 2016.
• Joong Chae Na, Alberto Apostolico, Costas S. Iliopoulos, and Kunsoo Park. Truncated suffix trees and their application to data compression. Theoretical Computer Science, Vol. 304, pp. 87-101, 2003.

タイトルに関連する用語 (2件)： 頻度 ,  索引