This is a project the implements different compression techniques such as:

• Huffman encoding. Two different implementations - ordinary and adaptive.
• Range (arithmetic) encoding. Four implementations - 32bit and 64 bit. Each of them can be either ordinary or adaptive.
• RLE->BWT->MTF>RLE transformations which are done before actual compression by one of the methods above.
• Several simple models (order0 fixed or adaptive and order1) that can be used with any compression method.
• Compression/decompression can be done in several threads.

This is a command line compressor written in Java. You need Java RTE installed to run this tool.

To run it use this command line: java -jar Huffman.jar

This will show you list of command line parameters like below.

usage: Huffman [-a <<archive> <files...>>] [-b <arg>] [-hf] [-l <archive>] [-o <arg>] [-ra] [-ra32] [-ra64] [-rabit] [-range] [-range32] [-range64]
[-sm] [-t <arg>] [-v] [-x <archive>]
-a <<archive> <files...>>     Add files to archive
-b,--block-size <arg>         Use specified block size
-hf,--huffman                 Use Huffman compression method (default)
-l <archive>                  Display content of archive
-o,--output-dir <arg>         Specifies directory where uncompressed files will be placed.
-ra,--range-adaptive          Use Adaptive Arithmetic Range compression method (default)
-ra32,--range-adaptive32      Use Adaptive Arithmetic Range compression method 32 bit
-ra64,--range-adaptive64      Use Adaptive Arithmetic Range compression method 64 bit
-rabit,--range-bit-adaptive   Use Adaptive Bit Arithmetic Range compression method
-range,--arithmetic           Use Arithmetic Range compression method (default)
-range32,--arithmetic32       Use Arithmetic Range compression method 32 bit
-range64,--arithmetic64       Use Arithmetic Range compression method 64 bit
-sm,--use-stream-mode         Stream mode will be used for files compression. Might reduce compression ratio.
-t,--threads <arg>            Use specified number of threads.
-v,--verbose                  Print more detailed (verbose) information to screen.
-x <archive>                  Extract files with full path

There are three commands: -a, -x, -l, all the other switches are options. All options should be specified before any command.

-a <archive> <inputfiles...> - add files to archive . Input files can contain paths, otherwise they are got from current directory. Paths are not stored into archive at the moment, if two files have the same names they will be added in archive as two separate entities, but will overwrite each other during uncompression.

-x <archive> - uncompresses and extracts files from archive into current directory. Command line parameter -o <output dir> can be used to specify another directory for extracted files.

-l <archive> - lists contents of archive. If option -v ise used together with command -l then list of blocks is shown on the screen in addition to list of files.

Compression method specified in command line is applied to all files being compressed.

-hf and -hfa - Huffman compression method (either original or adaptive) will be used for compression of specified files. With -hf each file will be passed two times. First time is for collecting frequency statistics and second time for actual compression using this statistics. Statistics table will be stored together with compressed data. With -hfa option Adaptive Huffman compression method will be used that does not require storing separate table with frequencies. Both methods have similar compresssion ratio.

-range, -range32, -range64 - use Range (arithmetic) encoding for compression. Algorithms are the same, they differ by bitness of calculations. Due to this they produce different compressed output but have similar compression ratio. -range is now a synonym for -range32 (may change in future).

-ra, -ra32, -r64 - the same as above but adaptive model of order1 is used instead of fixed order0 model. Adaptive order1 model provides slightly better compression ratio.

-rabit - implementation of Range method that processes input stream bit-by-bit. This implementation is simpler than -ra and -range but it is slower. Also it provides slightly worse compression results.

-b - specifies block size to use. Blocks are required for BWT and MTF transformations which provide better compression. Each input file is divided into blocks of specified size and each block will be compressed separately. Block size can be specified in bytes, kilobytes (K) or megabytes (M). Examples: -b2048, -b100000, -b10K, -b128K, -b2M Block size cannot be less than 1000 bytes and greater than 300 000 000 bytes. This option is valid for compression only. Ignored during uncompresion.

-t - specifies number of threads to be used for doing compression or uncompression. Significantly speeds up the process on computers with several CPU units. Multiple threads will be used only if value specified by -t option is greater than 1. Value cannot be greater than 24. Examples: -t0, -t1, -t4,-t10.

-sm - specifies to DO NOT use blocks during compression. Files will be compressed as streams of bytes without using BWT and MTF transformations. Compression will be faster, but compression rate much worse. This option is intended for experimental purposes for example for adding new compresson algorithms which do not support block mode by default. Option is ignored .....

-o - specifies path to directory where to extract files during uncompressing.

-v - turns on verbose mode. Additional information will be printed to console during compression or uncompression.

Улучшения:

• не хранить bytes length #b804d614
• использовать примитивные типы вместо wrapped типов. дает прирост в ~3 раза #c7a57abc
• был написан suffix array за O(n * log n), но на практике дает мало преимуществ, так как до этого RLE сожмет повторяющиеся символы и сравнение строк будет почти за O(1) в реализации на qsort(которая в теории работает за n^2 * log n), так как быстро встретится первый неповторяющийся символ

Источники:

• https://www.youtube.com/watch?v=4n7NPk5lwbI
• https://www.quora.com/Algorithms/How-can-I-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-in-O-n-time-O-n-space
• https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0-%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0
• https://compression.ru/book/pdf/compression_methods_part1_5-7.pdf
• http://mf.grsu.by/UchProc/livak/po/comprsite/theory_bwt.html

Источники:

• https://habr.com/ru/post/141827/
• https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B4%D0%BB%D0%B8%D0%BD_%D1%81%D0%B5%D1%80%D0%B8%D0%B9

• Заменить алгоритм RLE на LZW/LZ77, что даст прирост в качестве сжатия.
• Можно в алгоритме BWT схлопывать 4ки букв в 32bit число. или 8ки букв в 64bit число. тем самым мы ускорим сортировку. Но это только в теории, на практике непонятно. https://www.hindawi.com/journals/js/2018/6908760/

For tests we are going to use Calgary group dataset