Comprehensive Overview of Multi-delimiter Data Compression Codes and Key Features
This content showcases the concept of multi-delimiter data compression codes, their application in various algorithms such as arithmetic, finite state entropy, Huffman, and Fibonacci. Key features including compression rate, synchronization, search in compressed files, encoding/decoding speed, and compression efficiency of Fibonacci codes are highlighted. The discussion also touches on the use of delimiters in Fibonacci and multi-delimiter codes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Multi-delimiter data compression codes gor Zavadskyi, Anatoly Anisimov Taras Shevchenko National University of Kyiv, Ukraine
Without delimiters With delimiters Tagged Huffman Huffman ETDC, SCDS Data Finite state entropy compression codes Fibonacci, Arithmetic Multi-delimiter
Key features: compression rate 1.Arithmetic 2.Finite state entropy 3.Huffman 4. Multi-delimiter 5. Fibonacci 6.ETDC, SCDC codes with delimiters
Key features: synchronization Arithmetic, FSE and Huffman codes are not synchronizable Error Tagged Huffman codes, ETDC-codes, SCDC-codes, Fibonacci and multi-delimiter codes contain the synchronization marks Error
Key features: synchronization Bit inversions + + T-Huffman, ETDC,SCDC Fibonacci, Multi-delimiter Bit insertions or deletions T-Huffman, ETDC,SCDC Fibonacci, Multi-delimiter +
Key features: search in compressed file W e h a v e d e v e l o p e d a n e w c l a s s o f v a r i a b l e l e n g t h p r e f i x c o d e s , s o c a l l e d ( ; k ) - c o d e s , w h i c h c a n b e u s e d f o r e f f i c i e n t d a t a c o m p r e s s i o n . efficient Huffman, arithmetic, FSE ETDC, SCDC, Fibonacci, multi-delimiter +
Key features: encoding/decoding speed 1. The byte-by-byte algorithms for ETDC and SCDC codes. 2. Byte decoding algorithms for multi-delimiter codes. 3. Byte decoding algorithms for Fibonacci codes. 4. Huffman and FSE codes. 5. Arithmetic codes.
Fibonacci codes compression efficiency (natural language text compression) Fib3 Fib3 ? Fib2 Fib4 Fib4 Fib2
Delimiters Fibonacci codes Delimiter 111 Sequences 11111 1111 11111 Multi-delimiter codes s Delimiter 0110 , Sequences 011110 + + + 01110 0111110 D2,4
Multi-delimiter codes are not the pattern codes (D2,3) Delimiters 0110, 01110 Codewords of type 1 110, 1110 110, 1110 110, 1110 Codewords of type 2 0110, 01110, 00110, 10110, 001110, 101110, 0101110 etc.
Multi-delimiter code definition Let m1, , mtbe some natural numbers, 0 < m1< < mt 1, , m D Code contains: m t (type 1) - codewords 1 10, , 1 10 m1 mt (type 2) - codewords 01 10, , 01 10 m1 mt Type 2 codeword contains the delimiter only in the end and doesn t contain type 1 codewords as a prefix
Example of the code D2,3 codewords 1101110010110110 delimiters
Adapting codes to a given source probability distribution Number of short codewords Asymptotic density Longer delimiters More delimiters
Natural language text compression rate D2,3,5 D2,3 Fib3 SCDC
MD vs Fibonacci codes: instantaneousness The shortest codeword in Fibm code is the same as a delimiter: 1 1 Thus, Fibonacci codewords can glue into long run of ones Example. Code Fib3 0 1 1 1 1 1 1 1 1 1 1 1 0 Where is the true beginning of a codeword? We should check the sequence of previous bits, in general case infinite. The MD-codewords don t glue , as the delimiter is 01 10 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1, , m D We should check mtbits at the longest for the code . m t
Multi-delimiter codes: completeness and universality Theorem. Each MD-code is uniquely decodable, 1, , m D m t complete and universal in the sense of Elias. Completeness means that no codeword can be added to a code in a way that preserves the uniquely decodability property. Universality means that given any countable set of natural numbers with any monotonically decreasing probability function defined on them, assigning to numbers their codewords gives an expected codeword lengths lying within a constant multiple of the entropy lower bound.
Code : encoding 1, , t m m D = 1, , m m , , J 1 j j numbers that do not belong to t 2 1. Delete the leftmost 1. Not for 01 10 (m2, ,mt) suffixes 2. Each sequence 01 10 01 10 d jd 3. Append the delimiter 01 10 m1 1 1 11 111 111 1111 Example. Encoding to D2. J = {1, 3, 4, } 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1
Fast decoding lookup table (D2,3,5) 11000111 01101011 11001011 01100110 11111000 Text[i] 11000111 01101011 11001011 01100110 10011000 astart g 1 2 0 3 1 x1 1 10 x2 x3 x afin 4 8 8 1 1 10011 10 11001 4 8 8 1 1 1 10 1111110 100 The unpacked lookup table size: 20K The packed version: 10K
Experimental decoding time 10000 8000 SCDC Time, ms 6000 D2,3,5 bitwise D2,3,5 byte-aligned 4000 Fibonacci, byte-aligned 2000 0
Enlarging the dictionary Example: code D2 Decoding 1 2 4 3 8 5 6 16 9 10 12 13 7 110 0110 00110 10110 000110 010110 100110 0000110 0010110 0100110 1000110 1010110 1110110 codeword i Text[i] smaller number shorter codeword Enlarging the dictionary 4 times provides the compression rate 0.1% away from optimal
Conclusion: MD-codes features (vs Fibonacci codes) (i) Adaptability. Varying delimiters we can adapt a multi-delimiter code to a given source probability distribution and an alphabet size. (ii) The better compression rate for natural language text compressing. (iii) The faster byte aligned decoding method. (iv) Instantaneous separation of codeword allowing faster compressed search.
Thank you! ihorza@gmail.com
