文法型圧縮法の全二分木表現による符号化とランダムアクセス手法の提案
スポンサーリンク
概要
- 論文の詳細を見る
本稿では文法型圧縮法によって圧縮された文字列上でランダムアクセスを行う手法について述べる.文法型圧縮法とは与えられた文字列を一意に導出する文脈自由文法 (CFG) を構成し,それを符号化することによって実現する圧縮法ある.そのため,全体を復号せずにランダムアクセスを行うためには CFG の構造を保ったまま符号化を行うことが重要となる.本研究では n 個の変数を持つ CFG に対して,nlogn+2n+o(n) ビット領域で構文木上での操作が可能な符号化法を提案する.この特性とコンパクトな索引付けにより,省主記憶領域で高速なランダムアクセスが実現できることを計算機実験により示す.
- 2011-02-28
著者
-
馬場 雅大
九州大学システム情報科学府
-
岸上 直也
九州工業大学大学院情報工学府
-
丸山 史郎
九州大学大学院システム情報科学府
-
坂本 比呂志
九州工業大学大学院情報工学研究院
-
馬場 雅大
九州大学大学院システム情報科学府
-
坂本 比呂志
九州工業大学
-
坂本 比呂志
九州大学大学院システム情報科学研究院
-
坂本 比呂志
九州大学システム情報科学研究科
-
坂本 比呂志
九州大学大学院 システム情報科学研究院情報理学部門
関連論文
- 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)
- データ圧縮による大規模情報検索の実現と関連情報マイニングへの応用 テキストの特徴をつかまえる圧縮技術
- 有向グラフ上の到達可能性のための索引構造と大規模XMLデータベースへの応用(コンテンツ技術,Web情報システム)
- 有向グラフ上の最短距離の効率的な計算 (「生命情報からの知識発見」及び一般)
- 数値データからの意外な回帰結合ルールの発見
- 長いパターンを検出するための文法圧縮に基づく索引構造
- 全二分木の簡潔な表現
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- 「DAG上の2HOPラベリングの大規模化 (特集 「ウェブマイニング」および一般)
- Edit-Sensitive Parsingを用いた文法圧縮に基づく省スペースな索引構造 (特集 「脳科学と知識処理」および一般)
- 参照構造を持つXML上の高速な到達可能性判定
- 圧縮アルゴリズムLCA法の改良と実験による評価
- 高速な到達可能性判定のための規模耐性の高い索引付け
- DAG上の2HOPラベリングの効率的なメンテナンス (特集 「ウェブマイニング」および一般)
- 圧縮アルゴリズムLCA法の改良と実装 (特集 「人と技術とAI」および一般)
- 有向グラフ上の到達可能性を判定するための索引構造とXMLデータへの応用 (特集 「人と技術とAI」および一般)
- 木構造データに対するカーネル関数の設計と解析
- 圧縮パターン照合の改良 (テーマ:特集「ウェブデータの知的処理」および一般)
- 参照構造を持つXML上の高速な到達可能性判定 (テーマ:特集「ウェブデータの知的処理」および一般)
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- テキストマイニングにおける最適パターン発見
- テキストマイニングにおける最適パターン発見(データ・テキストマイニング)
- ウェブデータマイニング(「データマイニング特集号」)
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- 省スペースな線形時間文法圧縮アルゴリズム
- 決定性有限メモリーオートマトンの学習可能性(計算理論とその応用)
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- A Searchable Compressed Edit-Sensitive Parsing (Mathematical Foundations and Applications of Computer Science and Algorithms)
- 文法型圧縮法の全二分木表現による符号化とランダムアクセス手法の提案
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- 文脈自由文法による圧縮のための省スペースな近似アルゴリズム(文字列アルゴリズム)
- 形式言語の質問学習可能性に関する研究
- 木の変換規則の例からの学習 (小特集 「発見科学」及び一般演題)
- Webマイニング(「テキストマイニング」)
- オンライン文法圧縮
- 圧縮情報処理ノススメ