Compressão gramatical com extração eficiente

Abstract

We present a grammar compressor, called GCX (Grammar Compression modulo X), based on the induced suffix sorting grammar compression technique introduced in GCIS. Our method incorporates the text factorization used by algorithm DC3 to create a context-free grammar that produces the input string. We evaluated the performance of our algorithm using different values of covering X, and we introduce a heuristic based on the average longest common prefix between the rules of the grammar to define this coverage. GCX supports very fast extraction on the encoded grammar without the need to complete decompression. Experiments with real and artificial datasets showed that GCX, compared with GCIS, in most cases, is faster to compress, faster to decompress, have worse compression ratio most often; however, it has an extraction speed approximately 100 times larger. Similar behavior is observed when comparing the performance of GCX with that of RePair.