# Сжатие файлов вейвлетами

Файл `messageText.txt` содержит сгенерированные текст `Lorem ipsum dolor sit amet...`, который более-менее похож на реальный текст.

При его размере в 0.5Мб все вариации в режиме: прочитать файл, закодировать, раскодировать; отработали за разумное время (с учётом того, что при запуске выполнялись не только эти действия, а ещё сбор неокотрой статистики).

Однако даже на содержимом, которое очень похоже на текст, ошибка декодирования получилась в лучшем случае **~60%**

<pre>
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| File | Factor | Stub (adapted) | Normalize | Wavelet | Errors | Bytes | Err, % | Runtime, ms |
+==================+========+====================+===========+===================+===========+===========+========+=============+
| messageText.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 1/1 | 260117 | 437050 | 59.52 | 197 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.061133 ( true) | true | BiOrthogonal 1/1 | 260117 | 437050 | 59.52 | 246 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | true | Haar | 260117 | 437050 | 59.52 | 465 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.999543 ( true) | true | Haar | 260117 | 437050 | 59.52 | 616 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | true | Haar | 260117 | 437050 | 59.52 | 627 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | false | BiOrthogonal 1/1 | 260716 | 437050 | 59.65 | 307 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 59.484221 ( true) | false | BiOrthogonal 1/1 | 260716 | 437050 | 59.65 | 420 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 72.206343 ( true) | false | Haar | 260716 | 437050 | 59.65 | 555 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | false | Haar | 260716 | 437050 | 59.65 | 615 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 9.491311 ( true) | false | Haar | 260716 | 437050 | 59.65 | 668 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | false | Haar | 260716 | 437050 | 59.65 | 693 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 82.344180 ( true) | false | Haar | 260716 | 437050 | 59.65 | 768 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 1/3 | 261438 | 437050 | 59.82 | 238 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.517610 ( true) | true | BiOrthogonal 1/3 | 261438 | 437050 | 59.82 | 288 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| messageText.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 3/1 | 261443 | 437050 | 59.82 | 185 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
</pre>

Вейвлеты хорошо работают для сжатия изображения, потому что "в целом" для изображения верно, что соседние пиксели слабо отличаются, например, по значению в канале яркости, из-за чего разница значений в этих каналах будет незначительной и ей можно будет просто пренебречь.

Как и в изображении, каждый символ текста кодируется байтом, значение которого лежит в отрезке $[-128, 127]$, поэтому эти значения надо нормировать на отрезок $[0, 1]$, иначе разница соседних значений будет "слабо-ограниченной" (на самом деле, запускались тесты в том числе и с ненормированными данными (параметр `Normalize = false`), но как видно из таблицы они находятся в основном ниже, чем тесты с нормированными данными).

Для того, чтобы содержимое можно было сжать в 2 раза, значения, получающиеся в правой части в результате вейвлет-разложения стоит считать равными, чтобы их можно было не хранить в сжатом виде вообще. За это отвечает параметр `Stub`, который заменяет все знчаения в правой части вейвлет-преобразования на соответствующее значение. Это значение может быть подставлено в 2х режимах: константа (я выбрал 0) и адаптивный подбор. В адаптивном подборе пробовалось считать средние, минимальные/максимальные, медианные, ..., но на практике разница не была заметна совсем (в плане количества ошибок).

Дополнительно, было ещё построено распределение значений правой части вейвлет-преобразования для нормированных данных из самого успешного (по количеству ошибок) тесту. Распределение масштабировано в 2х вариантах с точностью: до десятых, до сотых. Из графиков ниже видно, что распределение ни эскспоненциалное (а хотелось бы), ни даже нормальное (потому что есть всплески на "больших" раницах).

<pre>
+------------+----------------------------------------------------------------------------------+
| Difference | Distribution |
+------------+----------------------------------------------------------------------------------+
| 0.00 | ████████████████████████████████████████████████████████████████████████ |
| 0.10 | ████████████████████████████████████████████████████████████████████████████████ |
| 0.20 | ███████████████████ |
| 0.30 | ███████████████████████████ |
| 0.40 | █████████████████████████████ |
| 0.50 | █████████████████████████████ |
| 0.60 | ████ |
| 0.70 | █ |
+------------+----------------------------------------------------------------------------------+
</pre>

<pre>
+------------+----------------------------------------------------------------------------------+
| Difference | Distribution |
+------------+----------------------------------------------------------------------------------+
| 0.00 | █████████████████████ |
| 0.01 | ████████████████████████████████████████████████████████████████████████████████ |
| 0.02 | ██████████████████████████████████████████████████████████ |
| 0.03 | ████████████████████████████████████████████████████████ |
| 0.04 | ████████████████████████████████████████████████████████ |
| 0.05 | ████████████████████████████████████████ |
| 0.06 | ███████████████████████████████████████████████████████ |
| 0.07 | ████████████████████████████████████████ |
| 0.08 | █████████████████████████████████████████████████████ |
| 0.09 | █████████████████████████████████ |
| 0.10 | █████████████████████████████████ |
| 0.11 | █████████████████████ |
| 0.12 | ████████████████████████████ |
| 0.13 | ███████████████ |
| 0.14 | █████ |
| 0.15 | ███████ |
| 0.16 | ██████ |
| 0.17 | █████ |
| 0.18 | ██████ |
| 0.19 | ██████ |
| 0.20 | ███████ |
| 0.21 | ████████ |
| 0.22 | ███████████ |
| 0.23 | █████████ |
| 0.24 | ████████ |
| 0.25 | ███████████ |
| 0.26 | ██████████ |
| 0.27 | ████████ |
| 0.28 | ███████████ |
| 0.29 | █████████ |
| 0.30 | ████████████ |
| 0.31 | ███████████ |
| 0.32 | █████████ |
| 0.33 | ███████████ |
| 0.34 | ██████████ |
| 0.35 | ████████████ |
| 0.36 | ████████ |
| 0.37 | ███████ |
| 0.38 | ███████ |
| 0.39 | ██████ |
| 0.40 | ████████ |
| 0.41 | ████ |
| 0.42 | █████████████████████ |
| 0.43 | ██████████ |
| 0.44 | ██████████████████████████████ |
| 0.45 | ████████ |
| 0.46 | ███████ |
| 0.47 | ████████ |
| 0.48 | ███ |
| 0.49 | █████████████████████ |
| 0.50 | ████████████ |
| 0.51 | █████████ |
| 0.52 | ███ |
| 0.53 | ████████████████████████████ |
| 0.54 | █████████████████ |
| 0.55 | ████████████ |
| 0.56 | █ |
| 0.57 | █ |
| 0.58 | █ |
| 0.59 | █ |
| 0.60 | █ |
| 0.61 | █ |
| 0.62 | █ |
| 0.63 | █ |
| 0.64 | █ |
| 0.65 | ██ |
| 0.66 | █ |
| 0.67 | █ |
| 0.68 | █ |
| 0.69 | |
| 0.70 | █ |
| 0.71 | |
+------------+----------------------------------------------------------------------------------+
</pre>

Дальше хуже...

Так же тесты запускались для файлов примерно со случайными данными, которые слабо похожи на текст. Результаты этих тестов представлены ниже

Для файла размером 1Мб:

<pre>
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| File | Factor | Stub (adapted) | Normalize | Wavelet | Errors | Bytes | Err, % | Runtime, ms |
+==================+========+====================+===========+===================+===========+===========+========+=============+
| message.txt | 1.00 | 0.000000 (false) | true | Haar | 1041903 | 1250001 | 83.35 | 517 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.000000 (false) | true | Haar | 1041903 | 1250001 | 83.35 | 650 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 1/1 | 1041903 | 1250001 | 83.35 | 664 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.474115 ( true) | true | BiOrthogonal 1/1 | 1041903 | 1250001 | 83.35 | 720 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.572578 ( true) | true | Haar | 1041903 | 1250001 | 83.35 | 999 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.000000 (false) | false | Haar | 1044024 | 1250001 | 83.52 | 565 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 189.346219 ( true) | false | Haar | 1044024 | 1250001 | 83.52 | 568 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.000000 (false) | false | BiOrthogonal 1/1 | 1044024 | 1250001 | 83.52 | 675 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 26.747067 ( true) | false | BiOrthogonal 1/1 | 1044024 | 1250001 | 83.52 | 718 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 196.274310 ( true) | false | Haar | 1044024 | 1250001 | 83.52 | 740 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.000000 (false) | false | Haar | 1044024 | 1250001 | 83.52 | 830 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 211.025841 ( true) | false | Haar | 1044024 | 1250001 | 83.52 | 875 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.117202 ( true) | true | BiOrthogonal 1/3 | 1046057 | 1250001 | 83.68 | 676 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 1/3 | 1046057 | 1250001 | 83.68 | 910 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message.txt | 1.00 | 0.005474 ( true) | true | BiOrthogonal 3/1 | 1046148 | 1250001 | 83.69 | 730 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
</pre>

<pre>
+------------+----------------------------------------------------------------------------------+
| Difference | Distribution |
+------------+----------------------------------------------------------------------------------+
| 0.00 | ███████████████████████████████████████████ |
| 0.10 | ██████████████████████████████████████████████████████████████████████████████ |
| 0.20 | ████████████████████████████████████████████████████████████████████████████████ |
| 0.30 | ████████████████████████████ |
| 0.40 | █ |
| 0.50 | █ |
+------------+----------------------------------------------------------------------------------+

+------------+----------------------------------------------------------------------------------+
| Difference | Distribution |
+------------+----------------------------------------------------------------------------------+
| 0.00 | ███████████████████████████████ |
| 0.01 | ███████████████████████████████████████████████████████████████████████ |
| 0.02 | █████████████████████████████████████████████████████████████████████ |
| 0.03 | █████████████████████████████████████████████████████ |
| 0.04 | █████████████████████████████████████████████████████████████ |
| 0.05 | █████████████████████████████████████████████████ |
| 0.06 | ███████████████████████████████████████████████████████ |
| 0.07 | ███████████████████████████████████████████████████ |
| 0.08 | ██████████████████████████████████████ |
| 0.09 | ██████████████████████████████████████████████ |
| 0.10 | ████████████████████████████████████████████ |
| 0.11 | ███████████████████████████████████████████████████████████████ |
| 0.12 | ██████████████████████████████████████████████████████████████████████████ |
| 0.13 | ███████████████████████████████████████████████████████████████ |
| 0.14 | ████████████████████████████████████████████████████████████████████████████████ |
| 0.15 | ████████████████████████████████████████████████████████████ |
| 0.16 | ████████████████████████████████████████████████████████████████████████ |
| 0.17 | ████████████████████████████████████████████████████████████████████ |
| 0.18 | ██████████████████████████████████████████████████ |
| 0.19 | ██████████████████████████████████████████████████████████████ |
| 0.20 | ███████████████████████████████████████████████ |
| 0.21 | ████████████████████████████████████████████████████████████ |
| 0.22 | ████████████████████████████████████████████████████████████████ |
| 0.23 | ████████████████████████████████████████████████ |
| 0.24 | ████████████████████████████████████████████████████████████████ |
| 0.25 | ████████████████████████████████████████████████ |
| 0.26 | █████████████████████████████████████████████████████████████ |
| 0.27 | ██████████████████████████████████████████████████████ |
| 0.28 | ███████████████████████████████ |
| 0.29 | ████████████████████████████ |
| 0.30 | ███████████ |
| 0.31 | ███ |
| 0.32 | |
| 0.33 | |
| 0.34 | |
| 0.35 | |
| 0.36 | █ |
| 0.37 | █ |
| 0.38 | █ |
| 0.39 | █ |
| 0.40 | █ |
| 0.41 | █ |
| 0.42 | █ |
| 0.43 | █ |
| 0.44 | █ |
| 0.45 | █ |
| 0.46 | █ |
| 0.47 | █ |
| 0.48 | █ |
| 0.49 | █ |
| 0.50 | █ |
| 0.51 | █ |
| 0.52 | █ |
| 0.53 | █ |
| 0.54 | |
+------------+----------------------------------------------------------------------------------+
</pre>

Для файла размером 5Мб:

<pre>
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| File | Factor | Stub (adapted) | Normalize | Wavelet | Errors | Bytes | Err, % | Runtime, ms |
+==================+========+====================+===========+===================+===========+===========+========+=============+
| message5.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 1/1 | 4167117 | 5100500 | 81.70 | 2766 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.971433 ( true) | true | BiOrthogonal 1/1 | 4167117 | 5100500 | 81.70 | 2983 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | true | Haar | 4167117 | 5100500 | 81.70 | 3610 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.037613 ( true) | true | Haar | 4167117 | 5100500 | 81.70 | 3768 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | true | Haar | 4167117 | 5100500 | 81.70 | 4512 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | false | BiOrthogonal 1/1 | 4176265 | 5100500 | 81.88 | 2636 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 207.595389 ( true) | false | BiOrthogonal 1/1 | 4176265 | 5100500 | 81.88 | 2933 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | false | Haar | 4176265 | 5100500 | 81.88 | 3572 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 185.319220 ( true) | false | Haar | 4176265 | 5100500 | 81.88 | 3618 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | false | Haar | 4176265 | 5100500 | 81.88 | 3808 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 248.244199 ( true) | false | Haar | 4176265 | 5100500 | 81.88 | 3969 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.275206 ( true) | false | Haar | 4176265 | 5100500 | 81.88 | 4480 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.313541 ( true) | true | BiOrthogonal 1/3 | 4183663 | 5100500 | 82.02 | 4014 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 1/3 | 4183663 | 5100500 | 82.02 | 4162 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
| message5.txt | 1.00 | 0.000000 (false) | true | BiOrthogonal 3/1 | 4183924 | 5100500 | 82.03 | 3590 |
+------------------+--------+--------------------+-----------+-------------------+-----------+-----------+--------+-------------+
</pre>

<pre>
+------------+----------------------------------------------------------------------------------+
| Difference | Distribution |
+------------+----------------------------------------------------------------------------------+
| 0.00 | ████████████████████████████████████████████ |
| 0.10 | ███████████████████████████████████████████████████████████████████████████████ |
| 0.20 | ████████████████████████████████████████████████████████████████████████████████ |
| 0.30 | ████████████████████████████ |
| 0.40 | █ |
| 0.50 | █ |
+------------+----------------------------------------------------------------------------------+

+------------+----------------------------------------------------------------------------------+
| Difference | Distribution |
+------------+----------------------------------------------------------------------------------+
| 0.00 | ███████████████████████████████ |
| 0.01 | ████████████████████████████████████████████████████████████████████████ |
| 0.02 | ██████████████████████████████████████████████████████████████████████ |
| 0.03 | ██████████████████████████████████████████████████████ |
| 0.04 | ██████████████████████████████████████████████████████████████ |
| 0.05 | ██████████████████████████████████████████████████ |
| 0.06 | ███████████████████████████████████████████████████████ |
| 0.07 | ████████████████████████████████████████████████████ |
| 0.08 | ████████████████████████████████████████ |
| 0.09 | ███████████████████████████████████████████████ |
| 0.10 | ████████████████████████████████████████████ |
| 0.11 | ███████████████████████████████████████████████████████████████ |
| 0.12 | ██████████████████████████████████████████████████████████████████████████ |
| 0.13 | ███████████████████████████████████████████████████████████████ |
| 0.14 | ████████████████████████████████████████████████████████████████████████████████ |
| 0.15 | █████████████████████████████████████████████████████████████ |
| 0.16 | ████████████████████████████████████████████████████████████████████████ |
| 0.17 | ████████████████████████████████████████████████████████████████████ |
| 0.18 | █████████████████████████████████████████████████ |
| 0.19 | ██████████████████████████████████████████████████████████████ |
| 0.20 | ███████████████████████████████████████████████ |
| 0.21 | ████████████████████████████████████████████████████████████ |
| 0.22 | ███████████████████████████████████████████████████████████████ |
| 0.23 | ████████████████████████████████████████████████ |
| 0.24 | ███████████████████████████████████████████████████████████████ |
| 0.25 | ███████████████████████████████████████████████ |
| 0.26 | █████████████████████████████████████████████████████████████ |
| 0.27 | █████████████████████████████████████████████████████ |
| 0.28 | ███████████████████████████████ |
| 0.29 | ████████████████████████████ |
| 0.30 | ███████████ |
| 0.31 | ███ |
| 0.32 | |
| 0.33 | |
| 0.34 | |
| 0.35 | |
| 0.36 | █ |
| 0.37 | █ |
| 0.38 | █ |
| 0.39 | █ |
| 0.40 | █ |
| 0.41 | █ |
| 0.42 | █ |
| 0.43 | █ |
| 0.44 | █ |
| 0.45 | █ |
| 0.46 | █ |
| 0.47 | █ |
| 0.48 | █ |
| 0.49 | █ |
| 0.50 | █ |
| 0.51 | █ |
| 0.52 | █ |
| 0.53 | █ |
| 0.54 | |
+------------+----------------------------------------------------------------------------------+
</pre>