Skip to content

Latest commit

 

History

History
219 lines (186 loc) · 15.4 KB

README.md

File metadata and controls

219 lines (186 loc) · 15.4 KB

How to use

Compile with maven mvn clean package or download from github and execute the jar
java -jar data-compressor.jar <encode | decode> <input file> <output file>

Project structure

Есть интерфейс Compressor, которые реализуют соответствующие алгоритмы. Все алгоритмы разбиты по пакетам с их названием. Каждый компрессор проверяется на наборе файлов и случайном наборе байт, что он может закодировать и декодировать без ошибок.
Класс DataCompressor включает в себя цепочку компрессоров и поочередно их вызывает.

Algorithm explanation

Сначала был реализован алгоритм Адаптивного Арифметического кодирования. Затем "компрессор" улучшался. В итоге, вся цепочка компрессора состоит из: RLE <-> BWT <-> MTF <-> RLE <-> A0. Стоит заметить, что файл не выгружается целиком в память(во избежание проблем) и каждый следующий алгоритм читает временный файл предыдущего алгоритма. Т.е. данный архиватор является полностью адаптивным.
С итоговым сравнением эффективности разных цепочек алгоритмов вы можете ознакомиться здесь. Ниже будут описаны краткие детали каждого из алгоритмов

Arithmetic coding

Энтропийный алгоритм сжатия, который основан на частоте символов. За основу была взята статья Witten'а. Данный метод основан на целочисленной реализации. Также в данной реализации не передается размер файла, а вводиться дополнительный символ окончания потока(EOF), т.е. расширяется алфавит и число интервалов, на которые делится отрезок. Тем самым делая алгоритм адаптивным. Частота символов вычисляется динамически по их приходу и увеличивает соответствующий счетчик.

Улучшения:

  • использовать примитивные типы вместо wrapped типов. дает прирост в ~3 раза #c7a57abc

Источники:

BWT

Данное преобразование позволяет преобразовать исходный поток в поток повторяющихся подстрок.
Кодирование и декодирование происходит на блоке байт равному 200кБайт

Кодирование:
В данной реализации добавляется искусственно дополнительный символ конца строки(EOF), который является лексикографически большим любого символа. Это позволяет использовать префиксную сортировку, основанную на индексах. В данной реализации использована стандартная сортировка TimSort в Java, которая работает в среднем за O(n), а в худшем за O(n*log n).

Таким образом закодированная строка выглядит следующим образом [data] | first_index | eof_index. firstIndex - это номер исходной строки, eofIndex - индекс символа конца строки. Тем самым мы добавляем дополнительно 2 * 4(на указатели) + 1(на EOF) = 9 байт на каждый блок данных, но это дает нам возможность кодировать за линейное время и не считывать весь файл в память.

Декодирование:
Используется метод вектора обратного преобразования. Работает за линейное время

Улучшения:

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

Источники:

MTF

Алгоритм позволяет после BWT превратить поток в поток повторяющихся байт. Этот подход используется в bzip2. Реализован без каких либо модификаций.

Источники:

Улучшения:

  • использовать примитивные типы вместо wrapped типов. дает прирост в ~3 раза #c7a57abc

RLE

Поточный алгоритм сжатия. Можно сказать, является наивной реализацией алгоритмов семейства LZ*. Он позволяет сжимать повторяющиеся серии символов. Под максимальную длину серии был взят размер 1 байта. Было рассмотрено два варианта реализации:

  1. В первом байте хранить длину и если она отрицательная, то значит следующие n символов не являются серией и мы их просто считываем, если положительная, то будет следовать n повторений следующего символа. Была сделана маленькая оптимизация, что длины повторяющихся цепочек хранились от 2 до 129, так как минимальная цепочка имеет длину 2.
    ABCABCABCDDDFFFFFF -> -9ABCABCABC3D6F

  2. Мы пишем символы и если встретили повторяющиеся, то после них пишем длину еще повторений этих же символов. ABCAAA -> ABCAA1 Это плохо работает только со строками, где много серий длины два, тогда мы каждый раз увеличиваем длину файла на 1 байт(AA -> AA0), но это нивелируется следующими алгоритмами BWT и MTF.

Второй вариант реализации оказался более эффективным.

Этот алгоритм применяется до BWT, чтобы сделать более быструю сортировку впоследствии. И после MTF, так как образуется много нулей после него.

Улучшения:

  • использован подход 2 #e949c158
  • длины серии хранятся от 2 до 257 #e2200a18

Источники:

TODO

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

Performance test results

For tests we are going to use Calgary group dataset

Entropy for files

File name H(X) H(X | X) H(X | XX)
bib 5.2007 3.3641 2.3075
book1 4.5271 3.5845 2.8141
book2 4.7926 3.7452 2.7357
geo 5.6464 4.2642 3.4578
news 5.1896 4.0919 2.9228
obj1 5.9482 3.4636 1.4005
obj2 6.2604 3.8704 2.2654
paper1 4.9830 3.6461 2.3318
paper2 4.6014 3.5224 2.5136
pic 1.2102 0.8237 0.7052
progc 5.1990 3.6034 2.1340
progl 4.7701 3.2116 2.0435
progp 4.8688 3.1875 1.7551
trans 5.5328 3.3548 1.9305

A0

File name Raw size(bytes) Compressed size(bytes) Bits per byte Elapsed time(ms)
bib 111261 72789 5.234 38
book1 768771 436883 4.546 181
book2 610856 364720 4.777 179
geo 102400 72400 5.656 49
news 377109 244471 5.186 122
obj1 21504 16038 5.967 9
obj2 246814 187294 6.071 98
paper1 53161 33120 4.984 14
paper2 82199 47534 4.626 27
pic 513216 74804 1.166 94
progc 39611 25920 5.235 13
progl 71646 42619 4.759 71
progp 49379 30209 4.894 24
trans 93695 64326 5.492 28
total 3141622 1713127 68.593 947

BWT <-> MTF <-> A0

File name Raw size(bytes) Compressed size(bytes) Bits per byte Elapsed time(ms)
bib 111261 31973 2.299 70
book1 768771 278141 2.894 730
book2 610856 189961 2.488 557
geo 102400 67008 5.235 122
news 377109 137605 2.919 960
obj1 21504 11584 4.310 15
obj2 246814 85843 2.782 252
paper1 53161 17975 2.705 27
paper2 82199 27563 2.683 45
pic 513216 63032 0.983 1020
progc 39611 13542 2.735 21
progl 71646 17283 1.930 427
progp 49379 11751 1.904 25
trans 93695 19430 1.659 164
total 3141622 972691 37.525 4435

RLE <-> BWT <-> MTF <-> A0

File name Raw size(bytes) Compressed size(bytes) Bits per byte Elapsed time(ms)
bib 111261 32231 2.318 155
book1 768771 281154 2.926 622
book2 610856 192452 2.520 599
geo 102400 67062 5.239 123
news 377109 138575 2.940 434
obj1 21504 11362 4.227 30
obj2 246814 86322 2.798 236
paper1 53161 18157 2.732 77
paper2 82199 27854 2.711 124
pic 513216 53925 0.841 89
progc 39611 13784 2.784 42
progl 71646 17513 1.956 54
progp 49379 11826 1.916 24
trans 93695 19638 1.677 49
total 3141622 971855 37.583 2658

BWT <-> MTF <-> RLE <-> A0

File name Raw size(bytes) Compressed size(bytes) Bits per byte Elapsed time(ms)
bib 111261 29385 2.113 150
book1 768771 274630 2.858 639
book2 610856 184442 2.416 582
geo 102400 62500 4.883 83
news 377109 133320 2.828 416
obj1 21504 10833 4.030 25
obj2 246814 81723 2.649 224
paper1 53161 17612 2.650 28
paper2 82199 26841 2.612 44
pic 513216 54754 0.854 954
progc 39611 13227 2.671 21
progl 71646 16846 1.881 103
progp 49379 11518 1.866 25
trans 93695 19153 1.635 105
total 3141622 936784 35.946 3399

RLE <-> BWT <-> MTF <-> RLE <-> A0

File name Raw size(bytes) Compressed size(bytes) Bits per byte Elapsed time(ms)
bib 111261 29561 2.126 148
book1 768771 275895 2.871 643
book2 610856 185699 2.432 685
geo 102400 62644 4.894 92
news 377109 134007 2.843 416
obj1 21504 10869 4.044 26
obj2 246814 82106 2.661 406
paper1 53161 17716 2.666 65
paper2 82199 26947 2.623 121
pic 513216 51040 0.796 84
progc 39611 13304 2.687 42
progl 71646 16683 1.863 115
progp 49379 11399 1.847 27
trans 93695 19292 1.647 49
total 3141622 937162 35.998 2919

Overall result

Type Total compressed(bytes) Total bits per byte Total elapsed time(ms) (raw - compressed)/elapsed time ratio
A0 1713127 68.593 947 1508
BWT <-> MTF <-> A0 972691 37.525 4435 489
RLE <-> BWT <-> MTF <-> A0 971855 37.583 2658 816
BWT <-> MTF <-> RLE <-> A0 936784 35.946 3399 648
RLE <-> BWT <-> MTF <-> RLE <-> A0 937162 35.998 2919 755