Download Implementation of DCA Compression Method

40
CHAPTER 4. IMPLEMENTATION
size
3B
item
“DCA”
4B
original length
4B
CRC32
*
*
antidictionary
compressed data
description
text identificator to unambiguously identify DCA compressed file
length of the original input text, this length is important
when decompressing data to determine end of the decompression process
cyclic redundancy check of the original data, it is computed
and checked during decompression
antidictionary representation as specified in Section 4.5
data with bits erased using DCA compression
Table 4.2: Compressed file format
Example 4.1
Let’s suppose that we have an antidictionary AD built over string “01010101”, AD =
{00, 11}. If we encodeded it using 2+2 representation, we would get antidictionary size
|AD| = 2 ∗ k = 10 bits, as the trie has k = 5 nodes. It is easy to see, that the text “010”
generates the same antidictionary, while it needs only 3 bits for coding the generating
text and a few bits for coding the text length.
Two promising ways of generating text Ty were found. The first uses compression transducer processing input text Tx avoiding loops, that don’t bring new nodes into suffix
trie. The second walks back from the stopping pair using transitions and suffix links
in inversed directions until it walks through all nodes. Both methods may not work on
general suffix tries, rather on the non-pruned constructed from a real text string, but this
needs more experiments.
Disadvantage of this representation is slower decompression, because we need to build
the antidictionary first from text Ty , also the decompressor must use the same method
as compressor to reconstruct the antidictionary. Another problem could be complexity
of constructing text Ty in compression process. Still antidictionary representation using
a generating text looks promising.
4.6
Compressed File Format
To be able to store the files compressed using DCA, a compressed file format had to be
developed. The proposed file format is similar to the one used by gzip and contains only
the necessary fields, targeting it to representing files compressed by static compression
scheme. CRC32 is used to check integrity of the decompressed data. See Table 4.2.