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

Search this Article

Author(s)

Abstract

テキストを圧縮する最適化問題に対して,準最適解を保証する省スペースな線形時間アルゴリズムを構築する.アルゴリズムは,高々アルファベットサイズの頂点を持つ平衡二分木上の最近共通祖先を計算し,その情報を用いて,長さ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.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 104(317), 1-7, 2004-09-10

    The Institute of Electronics, Information and Communication Engineers

References:  22

Codes

  • NII Article ID (NAID)
    110003178856
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    7121863
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top