文脈自由文法による圧縮のための省スペースな近似アルゴリズム(<特集>文字列アルゴリズム)
スポンサーリンク
概要
- 論文の詳細を見る
テキストを圧縮する最適化問題に対して,準最適解を保証する省スペースな線形時間アルゴリズムを構築する.アルゴリズムは,高々アルファベットサイズの頂点を持つ,平衡二分木上の最近共通祖先を計算し,その情報を用いて,長さnの任意のテキストを最適な圧縮のサイズg*に対して,高々O((log log g*)log n)倍以内で近似する.アルゴリズムが使用する主記憶領域は,高々O(g*(log log g*)log n)である.
- 社団法人電子情報通信学会の論文
- 2004-01-22
著者
関連論文
- データ圧縮による大規模情報検索の実現と関連情報マイニングへの応用 テキストの特徴をつかまえる圧縮技術
- 有向グラフ上の到達可能性のための索引構造と大規模XMLデータベースへの応用(コンテンツ技術,Web情報システム)
- 長いパターンを検出するための文法圧縮に基づく索引構造
- 参照構造を持つXML上の高速な到達可能性判定
- 圧縮アルゴリズムLCA法の改良と実験による評価
- 木構造データに対するカーネル関数の設計と解析
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- 省スペースな線形時間文法圧縮アルゴリズム
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- A Searchable Compressed Edit-Sensitive Parsing (Mathematical Foundations and Applications of Computer Science and Algorithms)
- 文法型圧縮法の全二分木表現による符号化とランダムアクセス手法の提案
- 文脈自由文法による圧縮のための省スペースな近似アルゴリズム(文字列アルゴリズム)
- 圧縮情報処理ノススメ