省スペースな線形時間文法圧縮アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
テキストを圧縮する最適化問題に対して,準最適解を保証する省スペースな線形時間アルゴリズムを構築する.アルゴリズムは,高々アルファベットサイズの頂点を持つ平衡二分木上の最近共通祖先を計算し,その情報を用いて,長さnの任意のテキストを最適な圧縮のサイズg_*に対して,高々O(log g_* 1og n)倍以内で近似する.アルゴリズムが使用する主記憶領域は,高々O(g_* log g_*)であり,この有効性を実験によって示す.
- 社団法人電子情報通信学会の論文
- 2004-09-10
著者
関連論文
- 分節木と共有文字列で表現される符号上での効率良い圧縮照合アルゴリズム(アルゴリズム理論,情報検索,情報爆発論文)
- VF符号上における圧縮照合アルゴリズム
- データ圧縮による大規模情報検索の実現と関連情報マイニングへの応用 テキストの特徴をつかまえる圧縮技術
- 有向グラフ上の到達可能性のための索引構造と大規模XMLデータベースへの応用(コンテンツ技術,Web情報システム)
- 有向グラフ上の最短距離の効率的な計算 (「生命情報からの知識発見」及び一般)
- 数値データからの意外な回帰結合ルールの発見
- JPEG画像に対する2次元パターンマッチングアルゴリズム(一般セッション1,移動カメラ画像処理におけるパターン認識とメディア理解)
- 分節木と共有文字列で表現される符号上での効率良い圧縮照合アルゴリズム
- D-1-8 部分文字列の出現頻度に基づくVF符号(D-1.コンピュテーション,一般セッション)
- 長いパターンを検出するための文法圧縮に基づく索引構造
- VF符号と算術符号の組合せ手法による圧縮性能の向上について
- VF符号と算術符号の組合せ手法による圧縮性能の向上について
- VF符号と算術符号の組合せ手法による圧縮性能の向上について
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- ウェブ閲覧における効率的なキーワード抽出とその利用
- 4ZK-7 ブラウジング支援のための一覧性の高いキーワードリストの抽出(情報爆発時代におけるテキストデータ処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- プロパティ接尾辞木のオフライン線形時間構築アルゴリズム(構造化文書・XML,データ工学論文)
- D-020 プロパティ接尾辞木 : メタデータ付き系列データのための効率よい索引構造(D分野:データベース)
- プロパティ付き接尾辞木の効率よいオフライン構築について
- LA_002 単語幅を制約した接尾辞木の効率のよい構築アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 文字列パターン照合のための損失のあるデータ圧縮
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- 図書目録カード画像検索システムの改善 : 扱いやすく柔軟なインタフェースへの移行(画像DB, 夏のデータベースワークショップDBWS2005)
- 図書目録カード画像検索システムの改善 : 扱いやすく柔軟なインタフェースへの移行(画像DB, 夏のデータベースワークショップ2005)
- テキストファイルによる図書目録画像データベースの構築と管理
- ＜発表論文＞ＲＦＩＤ技術を用いた図書館自動化への期待 （「ディジタル図書館」ワークショップ第26回）
- RFID技術を用いた図書館自動化への期待
- 仮想的な多重分節木による効率良いAIVF符号
- 仮想的な多重分節木による効率良いAIVF符号
- 「DAG上の2HOPラベリングの大規模化 (特集 「ウェブマイニング」および一般)
- Edit-Sensitive Parsingを用いた文法圧縮に基づく省スペースな索引構造 (特集 「脳科学と知識処理」および一般)
- 参照構造を持つXML上の高速な到達可能性判定
- 圧縮アルゴリズムLCA法の改良と実験による評価
- 高速な到達可能性判定のための規模耐性の高い索引付け
- DAG上の2HOPラベリングの効率的なメンテナンス (特集 「ウェブマイニング」および一般)
- 圧縮アルゴリズムLCA法の改良と実装 (特集 「人と技術とAI」および一般)
- 有向グラフ上の到達可能性を判定するための索引構造とXMLデータへの応用 (特集 「人と技術とAI」および一般)
- 木構造データに対するカーネル関数の設計と解析
- 圧縮パターン照合の改良 (テーマ:特集「ウェブデータの知的処理」および一般)
- 参照構造を持つXML上の高速な到達可能性判定 (テーマ:特集「ウェブデータの知的処理」および一般)
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- テキストマイニングにおける最適パターン発見
- テキストマイニングにおける最適パターン発見(データ・テキストマイニング)
- ウェブデータマイニング(「データマイニング特集号」)
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- D-019 ビット並列手法に基づく大規模連続ストリームパターン照合(D分野:データベース)
- 生物配列の局所マルチプルアラインメントの計算困難性
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- 位置情報付き個人コンテンツ分類のための線形HMMを用いたイベントクラスタリング (情報論的学習理論と機械学習)
- K語近接相関パタンの高速発見アルゴリズム
- 文字列相関パタンの分類精度最大化問題について
- 省スペースな線形時間文法圧縮アルゴリズム
- DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- Minimum Multiset Covering 問題の近似アルゴリズムについて
- 平面巡回セールスマン問題の高速な近似アルゴリズム
- STVF符号--頻度刈り込み接尾辞木を用いた効率よいVF符号化
- 決定性有限メモリーオートマトンの学習可能性(計算理論とその応用)
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- A Searchable Compressed Edit-Sensitive Parsing (Mathematical Foundations and Applications of Computer Science and Algorithms)
- 効率よいVF符号のためのMDL原理に基づく分節木の訓練手法
- 効率よいVF符号のためのMDL原理に基づく分節木の訓練手法
- LA-007 Arc-annotation付きテキストに対するパターン照合アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 文法型圧縮法の全二分木表現による符号化とランダムアクセス手法の提案
- 位置情報付き個人コンテンツ分類のための線形HMMを用いたイベントクラスタリング(機械学習応用,テキスト・Webマイニング,一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- 1. データストリームのためのマイニング技術(最新!データマイニング手法)
- 誤りを許したVLDCパタン照合アルゴリズム(文字列アルゴリズム)
- 分類階層を考慮したパタン照合アルゴリズム (特集 オントロジー)
- 文脈自由文法による圧縮のための省スペースな近似アルゴリズム(文字列アルゴリズム)
- 形式言語の質問学習可能性に関する研究
- 木の変換規則の例からの学習 (小特集 「発見科学」及び一般演題)
- JPEG画像に対する2次元近似パターンマッチング
- Webマイニング(「テキストマイニング」)
- 非対称で個体差がある関係データ分析のための機会調整型無限関係モデル (情報論的学習理論と機械学習)
- 共有辞書を用いた効率の良い圧縮アルゴリズム
- 非対称で個体差がある関係データ分析のための機会調整型無限関係モデル(ベイズ統計モデル,統計推理,データベース,一般)
- Hough変換を用いた楽曲構造の境界抽出
- 歌唱者の異なる同一楽曲の検索に適した音楽指紋
- 圧縮情報処理ノススメ
- 共有辞書を用いた効率の良い圧縮アルゴリズム(データ処理の効率化,ビッグデータとソーシャルコンピューティング,及び一般)
- A-008 効率よいVF符号化のための分節木を訓練する新手法(アルゴリズム・コンピュテーション(1),A分野:モデル・アルゴリズム・プログラミング)
- 非対称で個体差がある関係データ分析のための機会調整型無限関係モデル