Основы алгоритма сжатия JPEG - Программирование от RIN.RU

Программирование

ПОИСК

Главная / Алгоритмы / Сжатие информации и кодирование /

8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга

Основы алгоритма сжатия JPEG - Программирование от RIN.RU

Основы алгоритма сжатия JPEG

Алгоритм JPEG можно разделить на несколько этапов

Подготовка
ДКП (Дискретно Косинусоидальное Преобразование)
Квантование
Вторичное сжатие

Этап 0. Подготовка

Нужно преобразовать изображение в вид яркость/цветность, можно использовать цветовую схему YCbCr (YUV), вот формулы перевода:

Y = 0.299*R + 0.578*G + 0.114*B
Cb = 0.1678*R - 0.3313*G + 0.5*B
Cr = 0.5*R - 0.4187*G + 0.0813*B

Y нужно сохранить без изменений, его можно сжать любым алгоритмом без потери данных.

Теперь я попятаюсь объяснить как сжать Cb и Cr

Этап 1. ДКП

Следует создать ДКП матрицу, используя эту формулу

DCT_ij = 1/sqr(N), если i=0
DCT_ij = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0
N = 8, 0 < i < 7 , 0 < j < 7

в результате имеем:

|.353553 .353553 .353553 .353553 .353553 .353553 .353553 .353553|
|.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -.490246|
|.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 .461366|
DCT = |.414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -.414486|
|.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 .351435|
|.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -.274673|
|.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 .187195|
|.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -.092414|

например, нам нужно сжать следующий фрагмент изображения:

| 95 88 88 87 95 88 95 95|
|143 144 151 151 153 170 183 181|
|153 151 162 166 162 151 126 117|
IMG = |143 144 133 130 143 153 159 175|
|123 112 116 130 143 147 162 189|
|133 151 162 166 170 188 166 128|
|160 168 166 159 135 101 93 98|
|154 155 153 144 126 106 118 133|
|-33 -40 -40 -41 -33 -40 -33 -33|
| 15 16 23 23 25 42 55 53|
| 25 23 34 38 34 23 -2 -11|
IMG = | 15 16 5 2 15 25 31 47|
| -5 -16 -12 2 15 19 34 61|
| 5 23 34 38 42 60 38 0|
| 32 40 38 31 7 -27 -35 -30|
| 26 27 25 16 -2 -22 -10 5|

Вот формула, по которой производится ДКП: RES*IMG*DCT^T

Для начала нужно посчитать промежуточную матрицу: TMP = IMG*DCT^T

|-103 -3 1 2 4 0 -1 5|
| 89 -40 12 -2 -7 5 1 0|
| 57 31 -30 6 2 0 5 0|
TMP = | 55 -28 24 1 0 -8 0 0|
| 32 -60 18 -1 14 0 -8 1|
| 84 -11 -37 17 -24 4 0 -4|
| 19 81 -16 -20 8 -3 4 0|
| 22 40 11 -22 8 0 -3 2|

Затем умножаем ее на ДКП матрицу: RES = TMP*DCT

| 91 3 -5 -6 2 0 1|
|-38 -57 9 17 -2 2 2|
|-80 58 0 -18 4 3 4|
RES = |-52 -36 -11 13 -9 3 0|
|-86 -40 44 -7 17 -6 4|
|-62 64 -13 -1 3 -8 0|
|-16 14 -35 17 -11 2 -1|
|-53 32 -9 -8 22 0 2|

Этап 2. Квантование

На этом этапе мы посчитаем матрицу квантования, используя этот псевдо код:

for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
Q[i][j] = 1+((1+i+j)*q);
}

где q - это коэффициент качества, от него зависит степень потери качества сжатого изображения

Для q = 2 имеем матрицу квантования:

| 3 5 7 9 11 13 15 17|
| 5 7 9 11 13 15 17 19|
| 7 9 11 13 15 17 19 21|
Q = | 9 11 13 15 17 19 21 23|
|11 13 15 17 19 21 23 25|
|13 15 17 19 21 23 25 27|
|15 17 19 21 23 25 27 29|
|17 19 21 23 25 27 29 31|

Теперь нужно каждое число в матрице квантования разделить на число в соответствущей позиции в матрице RES, в результате получим:

| 30 0 0 0 0 0 0 0|
| -7 8 1 1 0 0 0 0|
|-11 6 0 1 0 0 0 0|
A = | -5 -3 0 0 0 0 0 0|
| -7 -3 2 0 0 0 0 0|
| -4 4 0 0 0 0 0 0|
| -1 0 1 0 0 0 0 0|
| -3 1 0 0 0 0 0 0|

Kак вы видите здесь имеется довольно много нулей, мы получим наиболее длинную последовательность нулей, если будем использовать следущий алгоритм:

+----+----+----+----+----+----+----+----+
| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |
+----+----+----+----+----+----+----+----+
| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |
+----+----+----+----+----+----+----+----+
| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |
+----+----+----+----+----+----+----+----+
| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |
+----+----+----+----+----+----+----+----+
| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |
+----+----+----+----+----+----+----+----+
| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |
+----+----+----+----+----+----+----+----+
| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |
+----+----+----+----+----+----+----+----+
| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |
+----+----+----+----+----+----+----+----+

Итак у нас получилась последовательность:

30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Для большего сжатия можно перед первым этапом JPEG можно провести субдискретизацию, или другими словами уменьшить частоту изображения, идея очень проста:

К примеру у нас есть следующая последовательность (Cb или Cr)

11 42 200 123 56 32 125 234 12 24 34 78 145 134 245 101

Если будем использовать субдискретизацию 4:1:1 результирующая последовательность будет:

11 123 125 24 145 101

а если использовать 4:2:2

11 234 245

а для восстановления последовательности нужно интерполироать

Этап 3. Вторичное сжатиe

На этом этапе можно применить следующие алгоритмя

7bit RLE
LZW с кодом переменной длинны
Адаптированное кодирование Хаффмана

7bit RLE

Этот алгоритм очень прост.

Если у нас есть последовательнось одинаковых байтов, то нужно установить последний бит в 0, посчитать количество байт и записать в оставшиеся биты.

Если у нас последоваетльность различных байт, то нужно установить последний быт в 1, посчитать количество байт и записать его в оставшиеся биты. Для нашей поледовательности получится:

133 30 0 -7 -11 8 | 2 0 | 135 1 6 -5 -7 -3 0 1 | 3 0 | 135 1 0 -3 -4 -1 4 2
11 0 | 131 -3 1 1 | 27 0

Итак, мы сжали 64 байта в 34

LZW с кодом переменной длиины

Этот алгоритм основан на динамически формируемом словаре, который состоит из различных строк. Строки заменяются кодами переменной длины. Вот этапы этого алгоритма:

Инициализуем словарь. В нашем случае числами в диапазоне [0;255].
BITS = 9, MAX = 2^BITS = 512
STRING = первый символ
Пока не кончились символы:
CHARACTER = взять символ из данных
Если STRING+CHARACTER есть в словаре, тогда STRING = STRING+CHARACTER, иначе выдать код для STRING, добавить STRING+CHARACTER в словарь, если количество строк в словаре > MAX-1, тогда у величиваем BITS и вычисляем заново MAX=2^BITS, STRING=CHARACTER
переход на 3
выдать код для STRING

Теперь нам нужно сжать нашу последовательность, но сперва прибавим ко всем значениям 128, чтобы сделать их положительными

158 128 121 117 136 128 128 129 134 123 121 125 128 129 128 128 128 129 128
125 124 127 132 130 128 128 128 128 128 128 128 128 128 128 128 125 129 129
128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128
128 128 128 128 128 128 128 128

STRING=158

CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (158) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 121
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (128) и добавить STRING+CHARACTER в словарь, STRING = 121
CHARACTER = 117
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (121) и добавить STRING+CHARACTER в словарь, STRING = 117
CHARACTER = 136
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (117) и добавить STRING+CHARACTER в словарь, STRING = 136
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (136) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (128) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 129
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (128) и добавить STRING+CHARACTER в словарь, STRING = 129
CHARACTER = 134
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (129) и добавить STRING+CHARACTER в словарь, STRING = 134
CHARACTER = 123
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (134) и добавить STRING+CHARACTER в словарь, STRING = 123
CHARACTER = 121
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (123) и добавить STRING+CHARACTER в словарь, STRING = 121
CHARACTER = 125
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (121) и добавить STRING+CHARACTER в словарь, STRING = 125
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (125) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 129
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (262) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (261) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 129
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 125
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (268) и добавить STRING+CHARACTER в словарь, STRING = 125
CHARACTER = 124
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (125) и добавить STRING+CHARACTER в словарь, STRING = 124
CHARACTER = 127
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (124) и добавить STRING+CHARACTER в словарь, STRING = 127
CHARACTER = 132
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (127) и добавить STRING+CHARACTER в словарь, STRING = 132
CHARACTER = 130
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (132) и добавить STRING+CHARACTER в словарь, STRING = 130
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (130) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (269) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (276) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 125
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (276) и добавить STRING+CHARACTER в словарь, STRING = 125
CHARACTER = 129
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (125) и добавить STRING+CHARACTER в словарь, STRING = 129
CHARACTER = 129
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (129) и добавить STRING+CHARACTER в словарь, STRING = 129
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (129) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (277) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (282) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (283) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (284) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = EOS (конец данных)

Мы достигли конца данных, нужно выдать код для STRING (261) и вот нажа сжатая строка

158 128 121 117 136 128 128 129 134 123 121 125 262 261 268 125 124 127 132
130 269 276 276 125 129 129 277 282 283 284

У нас было 9 бит на код и мы сжали 64 байта в 35 (31*9/8)

Вот алгоритм разпаковки:

Инициализуем словарь. Это числа в интервале [0;255].
BITS = 9, MAX = 2^BITS = 512
считываем OLD_CODE
выписываем OLD_CODE
Пока не кончились коды:
считываем NEW_CODE
если NEW_CODE отсутствует в словаре тогда STRING = трансляция OLD_CODE,
STRING = STRING+CHARACTER, иначе STRING = трансляция NEW_CODE
выписываем STRING
CHARACTER = первый символ в STRING
добавить OLD_CODE+CHARACTER в словарь
Если количество строк в словаре > MAX-1, тогда увеличиваем BITS, и вычисляем заново MAX=2^BITS
OLD_CODE = NEW_CODE
идем на 4

Теперь давайте распакуем нашу последовательность

OLD_CODE = 158
ouput 158

NEW_CODE = 128
NEW_CODE присутствует в словаре, тогда STRING = 128
выдаем STRING
CHARACTER = 128
добавляем "158 128" в словарь
OLD_CODE = 128
NEW_CODE = 121
NEW_CODE присутствует в словаре, тогда STRING = 121
выдаем STRING
CHARACTER = 121
добавляем "128 121" в словарь
OLD_CODE = 121
NEW_CODE = 117
NEW_CODE присутствует в словаре, тогда STRING = 117
выдаем STRING
CHARACTER = 117
добавляем "121 117" в словарь
OLD_CODE = 117
NEW_CODE = 136
NEW_CODE присутствует в словаре, тогда STRING = 136
выдаем STRING
CHARACTER = 136
добавляем "117 136" в словарь
OLD_CODE = 136
NEW_CODE = 128
NEW_CODE присутствует в словаре, тогда STRING = 128
выдаем STRING
CHARACTER = 128
добавляем "136 128" в словарь
OLD_CODE = 128
NEW_CODE = 128
NEW_CODE присутствует в словаре, тогда STRING = 128
выдаем STRING
CHARACTER = 128
добавляем "128 128" в словарь
OLD_CODE = 128
NEW_CODE = 129
NEW_CODE присутствует в словаре, тогда STRING = 129
выдаем STRING
CHARACTER = 129
добавляем "128 129" в словарь
OLD_CODE = 129
NEW_CODE = 134
NEW_CODE присутствует в словаре, тогда STRING = 134
выдаем STRING
CHARACTER = 134
добавляем "129 134" в словарь
OLD_CODE = 134
NEW_CODE = 123
NEW_CODE присутствует в словаре, тогда STRING = 123
выдаем STRING
CHARACTER = 123
добавляем "134 123" в словарь
OLD_CODE = 123
NEW_CODE = 121
NEW_CODE присутствует в словаре, тогда STRING = 121
выдаем STRING
CHARACTER = 121
добавляем "123 121" в словарь
OLD_CODE = 121
NEW_CODE = 125
NEW_CODE присутствует в словаре, тогда STRING = 125
выдаем STRING
CHARACTER = 125
добавляем "121 125" в словарь
OLD_CODE = 125
NEW_CODE = 262
NEW_CODE присутствует в словаре, тогда STRING = "128 129"
выдаем STRING
CHARACTER = 128
добавляем "125 128" в словарь
OLD_CODE = 262
NEW_CODE = 261
NEW_CODE присутствует в словаре, тогда STRING = "128 128"
выдаем STRING
CHARACTER = 128
добавляем "128 129 128" в словарь
OLD_CODE = 261
NEW_CODE = 268
NEW_CODE присутствует в словаре, тогда STRING = "128 129 128"
выдаем STRING
CHARACTER = 128
добавляем "128 128 128" в словарь
OLD_CODE = 268
NEW_CODE = 125
NEW_CODE присутствует в словаре, тогда STRING = 125
выдаем STRING
CHARACTER = 125
добавляем "128 129 128 125" в словарь
OLD_CODE = 125
NEW_CODE = 124
NEW_CODE присутствует в словаре, тогда STRING = 124
выдаем STRING
CHARACTER = 124
добавляем "125 124" в словарь
OLD_CODE = 124
NEW_CODE = 127
NEW_CODE присутствует в словаре, тогда STRING = 127
выдаем STRING
CHARACTER = 127
добавляем "124 127" в словарь
OLD_CODE = 127
NEW_CODE = 132
NEW_CODE присутствует в словаре, тогда STRING = 132
выдаем STRING
CHARACTER = 132
добавляем "127 132" в словарь
OLD_CODE = 132
NEW_CODE = 130
NEW_CODE присутствует в словаре, тогда STRING = 130
выдаем STRING
CHARACTER = 130
добавляем "132 130" в словарь
OLD_CODE = 130
NEW_CODE = 269
NEW_CODE присутствует в словаре, тогда STRING = "128 128 128"
выдаем STRING
CHARACTER = 128
добавляем "130 128" в словарь
OLD_CODE = 269
NEW_CODE = 276
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128" в словарь
OLD_CODE = 276
NEW_CODE = 276
NEW_CODE присутствует в словаре, тогда STRING = "128 128 128 128"
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128" в словарь
OLD_CODE = 276
NEW_CODE = 125
NEW_CODE присутствует в словаре, тогда STRING = 125
выдаем STRING
CHARACTER = 125
добавляем "128 128 128 128 125" в словарь
OLD_CODE = 125
NEW_CODE = 129
NEW_CODE присутствует в словаре, тогда STRING = 129
выдаем STRING
CHARACTER = 129
добавляем "125 129" в словарь
OLD_CODE = 129
NEW_CODE = 129
NEW_CODE присутствует в словаре, тогда STRING = 129
выдаем STRING
CHARACTER = 129
добавляем "129 129" в словарь
OLD_CODE = 129
NEW_CODE = 277
NEW_CODE присутствует в словаре, тогда STRING = "128 128 128 128 128"
выдаем STRING
CHARACTER = 128
добавляем "129 128" в словарь
OLD_CODE = 277
NEW_CODE = 282
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128 128" в словарь
OLD_CODE = 282
NEW_CODE = 283
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128 128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128 128 128" в словарь
OLD_CODE = 283
NEW_CODE = 284
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128 128 128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128 128 128 128" в словарь
OLD_CODE = 284

Итак у нас искомая последоваетльность, это работает! :)))

Адаптирование кодирование Хаффмана

Этот алгоритм основывается на частотах появления символов, и более часто повторяющийся символ представляется более малым кодом.

Вот алгоритм:

Инициализуем частоты - 1 для каждого символа
Строим дерево, символы с меньшей частотой мы объединяем в один узел
Пока есть символы:
ищем символ в дереве, если идем направо выдаем 1, иначе 0 (конечно в битах)
увеличиваем частоту символа и перестраиваем дерево
переходим к 3

Теперь попытаемя закодировать нашу последовательность, сперва нам нужно добавить128, чтобы сделать все значения положительными:

158 128 121 117 136 128 128 129 134 123 121 125 128 129 128 128 128 129 128
125 124 127 132 130 128 128 128 128 128 128 128 128 128 128 128 125 129 129
128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128
128 128 128 128 128 128 128 128

для упрощения объяснения мы предполагаем, что все возможные символы это:

158 128 121 117 136 129 134 123 125 124 127 132 130
(от 0 до 256 по-настоящему)

итак в начале у нас имеются частоты:

158 - 1, 128 - 1, 121 - 1, 117 - 1, 136 - 1, 129 - 1, 134 - 1, 123 - 1,
125 - 1, 124 - 1, 127 - 1, 132 - 1, 130 - 1
и дерево:

/------------13----------\
I I
/-------8-------\ /----5-----\
I I I I
/---4---\ /---4---\ I /--3--\
I I I I I I I
/-2-\ /-2-\ /-2-\ /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
1 1 1 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=158
для него код будет 1111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/------------14-------------\
I I
/-------8------\ /----6------\
I I I I
/--4--\ /---4---\ /---4---\ I
I I I I I I I
I /-2-\ /-2-\ /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
2 1 1 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 1101
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------15-------------\
I I
/-----8-----\ /------7-------\
I I I I
I /---4---\ /---4---\ /--3--\
I I I I I I I
/-4-\ /-2-\ /-2-\ /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
2 2 1 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=121
для него код будет 1011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------------16----------\
I I
/----8---\ /-------8-------\
I I I I
I /--4--\ /---4---\ /---4---\
I I I I I I I
/-4-\ I /-2-\ /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
2 2 2 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=117
для него код будет 1001
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------------16----------\
I I
I /----------9-----\
I I I
I I /----5-----\
I I I I
/---8---\ /---4---\ I /--3--\
I I I I I I I
/-4-\ /-4-\ /-2-\ /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
2 2 2 2 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=136
для него код будет 0111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------------18-------\
I I
I /----------10-------\
I I I
I I /----6------\
I I I I
/---8---\ /--4--\ /---4---\ I
I I I I I I I
/-4-\ /-4-\ I /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
2 2 2 2 2 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 110
теперь частота CHARACTER будет 3, теперь перестроим дерево
/-------------19-----------\
I I
I /--------12----------\
I I I
I /------8----\ I
I I I I
/--7--\ I /---4---\ /---4---\
I I I I I I I
I /-4-\ /-4-\ /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
3 2 2 2 2 1 1 1 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=129
для него код будет 01011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------20-----------\
I I
I /-----------13--------\
I I I
I /---8----\ /-----5----\
I I I I I
/--7--\ I /--4--\ I /--3--\
I I I I I I I I
I /-4-\ /-4-\ I /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
3 2 2 2 2 2 1 1 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=134
для него код будет 01001
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------21-----------\
I I
I /-----------14--------\
I I I
I I /-----6-----\
I I I I
/--7--\ /---8---\ /---4---\ I
I I I I I I I
I /-4-\ /-4-\ /-4-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
3 2 2 2 2 2 2 1 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=123
для него код будет 00111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------22-----------\
I I
I /-----------15------\
I I I
I I /------7------\
I I I I
/--7--\ /---8---\ /--4--\ /--3--\
I I I I I I I I
I /-4-\ /-4-\ /-4-\ I /-2-\ /-2-\ I
I I I I I I I I I I I I I
3 2 2 2 2 2 2 2 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130

CHARACTER=121
для него код будет 00111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------23-----------\
I I
I /---9-------\
I I I
/-----14----\ I /---5------\
I I I I I
I /---8---\ I I /--3--\
I I I I I I I
/-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
3 3 2 2 2 2 2 2 1 1 1 1 1
128 121 158 117 136 129 134 123 125 124 127 132 130

CHARACTER=125
для него код будет 0011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------24-----------\
I I
I /---10-------\
I I I
/-----14----\ I /---6------\
I I I I I
I /---8---\ I /--4--\ I
I I I I I I I
/-6-\ /-4-\ /-4-\ /-4-\ I /-2-\ /-2-\
I I I I I I I I I I I I I
3 3 2 2 2 2 2 2 2 1 1 1 1
128 121 158 117 136 129 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 111
теперь частота CHARACTER будет 4, теперь перестроим дерево
/--------25-----------\
I I
I /---10-------\
I I I
/-----15----\ I /---6------\
I I I I I
I /---8---\ I /--4--\ I
I I I I I I I
/-7-\ /-4-\ /-4-\ /-4-\ I /-2-\ /-2-\
I I I I I I I I I I I I I
4 3 2 2 2 2 2 2 2 1 1 1 1
128 121 158 117 136 129 134 123 125 124 127 132 130

CHARACTER=129
для него код будет 1000
теперь частота CHARACTER будет 3, теперь перестроим дерево
/----------26----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-10--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
4 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 5, теперь перестроим дерево
/----------27----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-11--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
5 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 6, теперь перестроим дерево
/----------28----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-12--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
6 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 7, теперь перестроим дерево
/----------29----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-13--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
7 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130

CHARACTER=129
для него код будет 100
теперь частота CHARACTER будет 4, теперь перестроим дерево
/----------30----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-14--\ /---8---\ I /---4---\
I I I I I I I
I /-7-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
7 4 3 2 2 2 2 2 2 1 1 1 1
128 129 121 158 117 136 134 123 125 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 8, теперь перестроим дерево
/----------31----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-15--\ /---8---\ I /---4---\
I I I I I I I
I /-7-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
8 4 3 2 2 2 2 2 2 1 1 1 1
128 129 121 158 117 136 134 123 125 124 127 132 130

CHARACTER=125
для него код будет 0010
теперь частота CHARACTER будет 3, теперь перестроим дерево
/---------32---------------\
I I
I /-------14--------\
I I I
/--18-\ I /----6-----\
I I I I I
I /-10--\ /---8---\ /--4--\ I
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ I /-2-\ /-2-\
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 1 1 1 1
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=124
для него код будет 00101
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------33---------------\
I I
I /-------15--------\
I I I
/--18-\ I /-----7----\
I I I I I
I /-10--\ /---8---\ I /--3--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ I
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 1 1 1
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=127
для него код будет 00011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------34---------------\
I I
I /-------16--------\
I I I
/--18-\ I /-----8--\
I I I I I
I /-10--\ /---8---\ I /--4--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ I /-2-\
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 2 1 1
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=132
для него код будет 00001
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------35---------------\
I I
I /-------17--------\
I I I
/--18-\ I /-----9--\
I I I I I
I /-10--\ /---8---\ I /--5--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ I /-3-\
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 2 2 1
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=130
для него код будет 00000
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------36---------------\
I I
I /-------18--------\
I I I
/--18-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 9, теперь перестроим дерево
/---------37---------------\
I I
I /-------18--------\
I I I
/--19-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
9 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 10, теперь перестроим дерево
/---------38---------------\
I I
I /-------18--------\
I I I
/--20-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
10 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 11, теперь перестроим дерево
/---------39---------------\
I I
I /-------18--------\
I I I
/--21-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
11 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 12, теперь перестроим дерево
/---------40---------------\
I I
I /-------18--------\
I I I
/--22-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
12 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 13, теперь перестроим дерево
/---------41---------------\
I I
I /-------18--------\
I I I
/--23-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
13 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 14, теперь перестроим дерево
/---------42---------------\
I I
I /-------18--------\
I I I
/--24-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
14 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 15, теперь перестроим дерево
/---------43---------------\
I I
I /-------18--------\
I I I
/--25-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
15 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 16, теперь перестроим дерево
/---------44---------------\
I I
I /-------18--------\
I I I
/--26-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
16 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 17, теперь перестроим дерево
/---------45---------------\
I I
I /-------18--------\
I I I
/--27-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
17 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 18, теперь перестроим дерево
/---------46---------------\
I I
I /-------18--------\
I I I
/--28-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
18 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 19, теперь перестроим дерево
/---------47---------------\
I I
I /-------18--------\
I I I
/--29-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130

CHARACTER=125
для него код будет 1000
теперь частота CHARACTER будет 4, теперь перестроим дерево
/---------48---------------\
I I
I /-------18--------\
I I I
/--30-\ I /-----10---\
I I I I I
I /-11--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 4 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=129
для него код будет 101
теперь частота CHARACTER будет 5, теперь перестроим дерево
/---------49---------------\
I I
I /-------18--------\
I I I
/--31-\ I /-----10---\
I I I I I
I /-12--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 5 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=129
для него код будет 101
теперь частота CHARACTER будет 6, теперь перестроим дерево
/---------50---------------\
I I
I /-------18--------\
I I I
/--32-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 20, теперь перестроим дерево
/---------51---------------\
I I
I /-------18--------\
I I I
/--33-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
20 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 21, теперь перестроим дерево
/---------52---------------\
I I
I /-------18--------\
I I I
/--34-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
21 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 22, теперь перестроим дерево
/---------53---------------\
I I
I /-------18--------\
I I I
/--35-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
22 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 23, теперь перестроим дерево
/---------54---------------\
I I
I /-------18--------\
I I I
/--36-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
23 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 24, теперь перестроим дерево
/---------55---------------\
I I
I /-------18--------\
I I I
/--37-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
24 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 25, теперь перестроим дерево
/---------56---------------\
I I
I /-------18--------\
I I I
/--38-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
25 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 26, теперь перестроим дерево
/---------57---------------\
I I
I /-------18--------\
I I I
/--39-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
26 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 27, теперь перестроим дерево
/---------58---------------\
I I
I /-------18--------\
I I I
/--40-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
27 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 28, теперь перестроим дерево
/---------59---------------\
I I
I /-------18--------\
I I I
/--41-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
28 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 29, теперь перестроим дерево
/---------60---------------\
I I
I /-------18--------\
I I I
/--42-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
29 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 30, теперь перестроим дерево
/---------61---------------\
I I
I /-------18--------\
I I I
/--43-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
30 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 31, теперь перестроим дерево
/---------62---------------\
I I
I /-------18--------\
I I I
/--44-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
31 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 32, теперь перестроим дерево
/---------63---------------\
I I
I /-------18--------\
I I I
/--45-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
32 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 33, теперь перестроим дерево
/---------64---------------\
I I
I /-------18--------\
I I I
/--46-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
33 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 34, теперь перестроим дерево
/---------65---------------\
I I
I /-------18--------\
I I I
/--47-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
34 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 35, теперь перестроим дерево
/---------66---------------\
I I
I /-------18--------\
I I I
/--48-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
35 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 36, теперь перестроим дерево
/---------67---------------\
I I
I /-------18--------\
I I I
/--49-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
36 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 37, теперь перестроим дерево
/---------68---------------\
I I
I /-------18--------\
I I I
/--50-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
37 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 38, теперь перестроим дерево
/---------69---------------\
I I
I /-------18--------\
I I I
/--51-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
38 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 39, теперь перестроим дерево
/---------70---------------\
I I
I /-------18--------\
I I I
/--52-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
39 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 40, теперь перестроим дерево
/---------71---------------\
I I
I /-------18--------\
I I I
/--53-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
40 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 41, теперь перестроим дерево
/---------72---------------\
I I
I /-------18--------\
I I I
/--54-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
41 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 42, теперь перестроим дерево
/---------73---------------\
I I
I /-------18--------\
I I I
/--55-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
42 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 43, теперь перестроим дерево
/---------74---------------\
I I
I /-------18--------\
I I I
/--56-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
43 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 44, теперь перестроим дерево
/---------75---------------\
I I
I /-------18--------\
I I I
/--57-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
44 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 45, теперь перестроим дерево
/---------76---------------\
I I
I /-------18--------\
I I I
/--58-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
45 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 46, теперь перестроим дерево
/---------77---------------\
I I
I /-------18--------\
I I I
/--59-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
46 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130

теперь посмотрим что у нас получилось
/-------\ /-------\ /--------\/-------\/--------\/--------\/--------\ /----
1111 1101 1011 1001 0111 110 01011 01001 00111 00111 0011 111 1000 11 11 11
----\/--------\/--------\/-------\/----------\/----------\/----------\/--
100 11 0010 00101 00011 00001 00000 11 11 11 11 11 11 11 11 11 11 11 1000
-----\/----------\/----------\/----------\/----------\/----------\/---------
101 101 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
\/---------
11 11 11 11

Итак мы сжали 64 байта в 22 (175/8 bits)

Вот и все!

8 Комментарии к статье 8 8 Обсудить в чате