オンライン文法圧縮
スポンサーリンク
概要
- 論文の詳細を見る
文字列を文脈自由文法 (CFG) で圧縮するアルゴリズムは,その CFG を簡潔データ構造などを用いて符号化したものを出力とする.これまでは,CFG を陽に構築したあとに符号化を行わなければならず,時間的にも領域的にもコストが掛かっていた.本研究では,はじめてのオンラインアルゴリズムを提案する.このアルゴリズムが出力する符号サイズは,CFG の表現長の情報理論的下限と漸近的に等しい.
- 2013-10-30
著者
関連論文
- データ圧縮による大規模情報検索の実現と関連情報マイニングへの応用 テキストの特徴をつかまえる圧縮技術
- 長いパターンを検出するための文法圧縮に基づく索引構造
- Edit-Sensitive Parsingを用いた文法圧縮に基づく省スペースな索引構造 (特集 「脳科学と知識処理」および一般)
- 圧縮アルゴリズムLCA法の改良と実験による評価
- 圧縮アルゴリズムLCA法の改良と実装 (特集 「人と技術とAI」および一般)
- 圧縮パターン照合の改良 (テーマ:特集「ウェブデータの知的処理」および一般)
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- A Searchable Compressed Edit-Sensitive Parsing (Mathematical Foundations and Applications of Computer Science and Algorithms)
- 文法型圧縮法の全二分木表現による符号化とランダムアクセス手法の提案
- オンライン文法圧縮