Сайт о сжатии  >>  ARCTEST

Сравнительные тесты
    Текстовые файлы
    Текстовые файлы (Mac)
    EXE-файлы
    EXE-файлы (Mac)
    Исполнимые EXE-сжатые
    Аудио: Wav-файлы
    Аудио: Wav-файлы (Mac)
    Графика: TIFF-файлы
    Графика: TIFF-файлы (Mac)
    Разноформатные файлы
    Разноформатные файлы (Mac)
    Файлы демо-игры
    Файлы демо-игры (Mac)
Альтернативные тесты
    Русский текст
    Английский текст
    Исходники
    WinWord-файл
    Excel-файл
    EXE-файл
    Новые тесты
Графические тесты
    Сжатие изображений без потерь
Новости
    Архив новостей
    Архив рассылки
Утилиты
    Просмотра-распаковки
    Идентификации-распаковки
    COM/EXE-распаковки, анализа
    Распаковки инсталляций
    Создания SFX-архивов/инсталляций
    Конвертирования
    Починки архивов
    Поиска
    Универсальные оболочки
    Управления баннерами
    Управления файлами
    Резервного копирования
    Тестирования
    Разные
Файл-менеджеры
    Файл-менеджеры
    Арх.-модули для FAR
    Арх.-модули для Win. Commander
Описания
    Статьи, интервью
    Теория, алгоритмы
    Self-описания архиваторов
    FAQ
    Разное
Линки
    Архиваторные
    COM/EXE/DLL-пакеров
Necromancer's DN
    О программе
    Новости свежих версий
    Архив новостей
Поддержка
   
    Подписка на рассылку новостей
    Архиваторные опросы
    Об авторе
Все о сжатии / arctest. Авторский проект.
---------------------------------------------------------

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


    Алгоритм JPEG можно разделить на несколько этапов:
  1. Подготовка
  2. ДКП (Дискретно Косинусоидальное Преобразование)
  3. Квантование
  4. Вторичное сжатие
Этап 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   = 1/sqr(N), если i=0
       ij

    DCT   = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0
       ij

    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|
                                                                                                       T
    Вот формула, по которой производится ДКП: RES*IMG*DCT
                                                                                                                              T
    Для начала нужно посчитать промежуточную матрицу: TMP = IMG*DCT 
      |-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|

    Как вы видите здесь имеется довольно много нулей, мы получим наиболее длинную последовательность нулей, если будем использовать следующий алгоритм:
     +----+----+----+----+----+----+----+----+
     |  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. Вторичное сжатие

    На этом этапе можно применить следующие алгоритмы:
a) 7bit RLE
b) LZW с кодом переменной длинны
c) Адаптированное кодирование Хаффмана

    a) 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.

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

    Этот алгоритм основан на динамически формируемом словаре, который состоит из различных строк. Строки заменяются кодами переменной длины. Вот этапы этого алгоритма:
  1. Инициализируем словарь. В нашем случае числами в диапазоне [0;255].
    BITS = 9, MAX = 2^BITS = 512;
  2. STRING = первый символ;
  3. Пока не кончились символы:;
  4. CHARACTER = взять символ из данных;
  5. Если STRING+CHARACTER есть в словаре, тогда STRING = STRING+CHARACTER, иначе выдать код для STRING, добавить STRING+CHARACTER в словарь, если количество строк в словаре > MAX-1, тогда увеличиваем BITS и вычисляем заново MAX=2^BITS, STRING=CHARACTER;
  6. Переход на 3;
  7. Выдать код для 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). Вот алгоритм распаковки:
  1. Инициализируем словарь. Это числа в интервале [0;255].
    BITS = 9, MAX = 2^BITS = 512;
  2. Считываем OLD_CODE;
  3. Выписываем OLD_CODE;
  4. Пока не кончились коды:;
  5. Считываем NEW_CODE;
  6. Если NEW_CODE отсутствует в словаре тогда STRING = трансляция OLD_CODE,    STRING = STRING+CHARACTER, иначе STRING = трансляция NEW_CODE;
  7. Выписываем STRING;
  8. CHARACTER = первый символ в STRING;
  9. Добавить OLD_CODE+CHARACTER в словарь;
  10. Если количество строк в словаре > MAX-1, тогда увеличиваем BITS, и вычисляем заново MAX=2^BITS;
  11. OLD_CODE = NEW_CODE;
  12. Идем на 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

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

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

    Этот алгоритм основывается на частотах появления символов, и более часто повторяющийся символ представляется более малым кодом
    Вот алгоритм:
  1. Инициализируем частоты - 1 для каждого символа;
  2. Строим дерево, символы с меньшей частотой мы объединяем в один узел;
  3. Пока есть символы:;
  4. Ищем символ в дереве, если идем направо выдаем 1, иначе 0
    (конечно в битах);
  5. Увеличиваем частоту символа и перестраиваем дерево;
  6. Переходим к 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). Вот и все!

Денис Бухаров (White Eagle)
Россия, Челябинск
Последнее обновление: 12-May-2022

Сайт о сжатии  >>  ARCTEST  >>  Сравнительные тесты  |  Альтернативные тесты  |  Графические тесты  |  Новости  |  Утилиты  |  Файл'менеджеры  |  Описания  |  Линки  |  Necromancer's DN  |  Поддержка

Поиск:
Справка Детальный запрос
Размер сервера: 8069 файлов 1215Мб

Сайт о сжатии >>
  Новинки | О сервере | Статистика

  Книга "Методы сжатия данных" >>
     Универсальные | Изображений | Видео

  Разделы >> Download (статьи+исходники) | Ссылки | Ru.compress | Arctest | Видео | Каталог ссылок | Форум
  Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | А.Филинского | Д.Шкарина | С.Оснача
  Оставьте ваши замечания, предложения, мнения!
  О найденных ошибках пишите на compression_на_graphicon.ru
  © Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин и др., текст, состав., 2001-2003
    Project supported by Graphics & Media Lab

   ЭТОТ ДОКУМЕНТ МОЖНО СКАЧАТЬ C http://www.compression.ru/compression.ru/arctest/descript/jpeg-basis.htm

Rambler's Top100 Рейтинг@Mail.ru