省スペースな線形時間文法圧縮アルゴリズム A Space-Saving Linear-Time Algorithm for Grammar-Based Compression

この論文をさがす

著者

抄録

テキストを圧縮する最適化問題に対して,準最適解を保証する省スペースな線形時間アルゴリズムを構築する.アルゴリズムは,高々アルファベットサイズの頂点を持つ平衡二分木上の最近共通祖先を計算し,その情報を用いて,長さnの任意のテキストを最適な圧縮のサイズg_*に対して,高々O(log g_* 1og n)倍以内で近似する.アルゴリズムが使用する主記憶領域は,高々O(g_* log g_*)であり,この有効性を実験によって示す.

A space-efficient linear-time approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. The algorithm consumes only O(g_* log g_*) space and achieves the worst-case approximation ratio O(log g_* log n), with the size n of an input and the optimum grammar size g_*. Experimental results for typical benchmarks demonstrate that our algorithm is practical and efficient.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 104(317), 1-7, 2004-09-10

    一般社団法人電子情報通信学会

参考文献:  22件中 1-22件 を表示

各種コード

  • NII論文ID(NAID)
    110003178856
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    7121863
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ