An online algorithm for lightweight grammar-based compression (Q1736509): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.3390/a5020214 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2489658791 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 19:05, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An online algorithm for lightweight grammar-based compression |
scientific article |
Statements
An online algorithm for lightweight grammar-based compression (English)
0 references
26 March 2019
0 references
Summary: Grammar-based compression is a well-studied technique to construct a context-free grammar (CFG) deriving a given text uniquely. In this work, we propose an online algorithm for grammar-based compression. Our algorithm guarantees \(O(\log^2n)\)-approximation ratio for the minimum grammar size, where \(n\) is an input size, and it runs in input linear time and output linear space. In addition, we propose a practical encoding, which transforms a restricted CFG into a more compact representation. Experimental results by comparison with standard compressors demonstrate that our algorithm is especially effective for highly repetitive text.
0 references
lossless compression
0 references
grammar-based compression
0 references
online algorithm
0 references
approximation algorithm
0 references