The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
É apresentado um algoritmo de aproximação com uso eficiente de espaço para o problema de compressão baseado em gramática, que solicita que uma determinada string encontre a menor gramática livre de contexto que deriva a string. Para o comprimento de entrada n e um tamanho ideal de CFG g, o algoritmo consome apenas O(g log g) espaço e O(n log*n) tempo para alcançar O((registro*n)registro n) relação de aproximação para a compressão ideal, onde log*n é o número máximo de logaritmos que satisfazem log log
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Hiroshi SAKAMOTO, Shirou MARUYAMA, Takuya KIDA, Shinichi SHIMOZONO, "A Space-Saving Approximation Algorithm for Grammar-Based Compression" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 158-165, February 2009, doi: 10.1587/transinf.E92.D.158.
Abstract: A space-efficient 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. For the input length n and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n)log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.158/_p
Copiar
@ARTICLE{e92-d_2_158,
author={Hiroshi SAKAMOTO, Shirou MARUYAMA, Takuya KIDA, Shinichi SHIMOZONO, },
journal={IEICE TRANSACTIONS on Information},
title={A Space-Saving Approximation Algorithm for Grammar-Based Compression},
year={2009},
volume={E92-D},
number={2},
pages={158-165},
abstract={A space-efficient 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. For the input length n and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n)log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log
keywords={},
doi={10.1587/transinf.E92.D.158},
ISSN={1745-1361},
month={February},}
Copiar
TY - JOUR
TI - A Space-Saving Approximation Algorithm for Grammar-Based Compression
T2 - IEICE TRANSACTIONS on Information
SP - 158
EP - 165
AU - Hiroshi SAKAMOTO
AU - Shirou MARUYAMA
AU - Takuya KIDA
AU - Shinichi SHIMOZONO
PY - 2009
DO - 10.1587/transinf.E92.D.158
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - A space-efficient 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. For the input length n and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n)log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log
ER -