<テクニカルレポート>
Ο(log n)-Approximation Algorithm for Grammar-Based Compression

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 In the grammar-based compression scheme, a given text string is transformed into a context-free grammar $ G $ such that $ L(G)={ omega } $ and then encoded in an appropriate manner. The compression i...s thus regarded as an optimization ploblem of minimizing the size of $ G $ for a given string $ omega $ of length $ n $. For the APX-hard problem an $ O(log n) $ approximation algorithm with arbitrary string is presented. The previously known best approximation ratio was $ O(sqrt{n/log n}) $[8]続きを見る

本文情報を非表示

trcs201.ps gz 96.5 KB 43  
trcs201 pdf 239 KB 42  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2018.08.31