Форум программистов, компьютерный форум, киберфорум
Наши страницы
Assembler, MASM, TASM
Войти
Регистрация
Восстановить пароль
 
R71MT
3242 / 1110 / 264
Регистрация: 29.07.2014
Сообщений: 2,122
Записей в блоге: 4
#1

Обзор алгоритмов сжатия - Assembler

26.08.2016, 22:34. Просмотров 1249. Ответов 5
Метки нет (Все метки)

Пролог
-----------------


Однажды понадобилось мне зашить внешний файл в свою программу, чтобы он не таскал везде свою задницу вместе с исполняемым файлом. Я сделал это через команду "INCBIN" (для фасма FILE), но на выходе получил исполняемый файл неимоверных размеров. Тогда возникла идея прошить в программу упакованый/внешний файл, но для этого нужно было добавить в программу ещё и декодер, который распаковал-бы его. Готовые пакеры не подходили мне тем, что я не знал алгоритмов по которому они пакуют, и пришлось писать свой архиватор.

За время поисков набрал кучу инфы по этой теме, с которой хотелось-бы поделиться с Вами. Статья расчитана на тех, кто хотел-бы освоить тему сжатия информации, но уровень знаний не позволяет им самостоятельно разобраться в куче математических формул и непонятных терминов. Не знаю: правильно я понял всё/это или нет, но главное - положительный результат, который в данном случае я получил. Буду использовать FASM, редактор HxD, ну и виндовый CALC в инженерном виде.


Введение
-----------------


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

Степень избыточности привязана к типу данных:
Код
............ 1. Видео - максимальная избыточность;
---------------------------------------------------------------------------
00006960  2F 00 00 00 01 00 00 0E A9 00 00 00 01 00 00 0E  /.......©.......
00006970  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......
00006980  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......
00006990  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......

............ 2. Графика - средняя избыточность;
---------------------------------------------------------------------------
00007C30  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C40  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C50  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C60  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя

............ 3. Текст - минимальная избыточность;
---------------------------------------------------------------------------
00000000  CB E5 EE ED E8 E4 20 D4 E8 EB E0 F2 EE E2 2E 20  Леонид Филатов. 
00000010  CF F0 EE 20 D4 E5 E4 EE F2 E0 2D F1 F2 F0 E5 EB  Про Федота-стрел
00000020  FC F6 E0 20 09 0D 0A D1 CA C0 C7 CA C0 20 C4 CB  ьца ...СКАЗКА ДЛ
00000030  DF 20 D2 C5 C0 D2 D0 C0 20 0D 0A 0D 0A 20 20 20  Я ТЕАТРА ....
Очевидно, что для сжатия разных типов информации нужны и разные алгоритмы сжатия. К примеру, у видео- и графики просматриваются цепочки повторяющихся байт, которые можно закодировать в формате "Байт->Повторов", хотя с текстом такой фокус уже не пройдёт.

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

- Алгоритм "RLE" (Run-Length-Encoding);
- Алгоритм "LZ" (Лемпеля-Зива);
- Алгоритм "Хаффмана".

Для всех систем сжатия требуется 2 алгоритма: компрессии на стороне источника, и декомпрессии у её получателя. Обычно, эти алгоритмы ассиметричны во-времени, т.к. алгоритм кодирования имеет право быть довольно медленным, в то время как декодер должен быть быстрым, чтобы удовлетворять требованиям пользователя. Рассмотрим в двух-словах основные различия этих алгоритмов.

Алгоритм RLE:
^^^^^^^^^^^^^^^^^^^^

- Кодирование цепочек одинаковых байт.
Для этой цели применяют байт-маркеры. Цепочки не одинаковых байт, вообще никак не кодируются, и передаются в открытом виде. К примеру, маркер [09h,38h] заставит декодер отправить на выход 9 восьмёрок, и т.д. Алгоритм даёт хорошие результаты при кодировании видео- и графики.


Алгоритм LZ:
^^^^^^^^^^^^^^^^^^^^

- Кодирование лексических единиц и помещение их в словарь.
За основу взят принцип поиска подстроки-в-строке. Алгоритм имеет буфер, который разделён на две/неравные части. Первая часть представляет из себя собственно буфер данных, а вторая часть - словарь алгоритма. Входной поток читается в буфер (по образу бегущей строки влево), и содержимое буфера сравнивается со-словарём. Каждая фраза словаря кодируется в байт:

|------- Словарь ------|-- Буфер --|---<<---входной поток....

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


Алгоритм Хаффмана:
^^^^^^^^^^^^^^^^^^^^

- Кодирование в виде бинарного древа.
Хаффман пошёл совсем иным путём, и решил съэкономить не то-что на каждом байте, а даже на каждом его бите. Кодер начинает работу с того, что сканирует сразу весь файл, и подсчитывает в нём кол-во вхождений каждого из символов. Так он получает вес каждого байта во-входном потоке данных:

00000000 F0 E0 F1 F1 EC EE F2 F0 E8 EC F1 F2 F0 EE EA F3 рассмотримстроку
--------+------------------------------------------------------------------
Байт | Вес
--------+------
F0h (р) | 3
E0h (а) | 1
F1h (с) | 3
ECh (м) | 2
;....... и т.д.

Теперь, Хаффман сортирует эти веса по-убыванию, в результате чего самые часто/встречающиеся байты выстаиваются в начале древа, и кодируются всего одним битом. Наименее встречающиеся байты будут кодироваться наибольшей разрядной сеткой, за счёт чего возрастает процент сжатия. Для зрительного восприятия это можно представить так.., хотя на самом деле всё чуть/подругому:

вес: 7 6 5 4 3 2 1 0
бит: 0 1 2 3 4 5 6 7

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

Тонкости алгоритма Хаффмана оставим на потом, а пока разберём детали каждого из алгоритмов сжатия, начиная с самого простого: Run-Len-Encoding.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2016, 22:34
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Обзор алгоритмов сжатия (Assembler):

Алгоритм необратимого сжатия данных
Помогите пожалуйста, мне нужно написать программку для необратимого сжатия...

А.В. Максимов Проектирование ассемблерных программ вычислительных алгоритмов
Предлагаю обсудить книгу А.В. Максимов Проектирование ассемблерных программ...

Реализация алгоритмов преобразования строк в численное представление
Нужна помощь в решении задачи. Суть в том, что мало того, что нужно решить, но...

При попытке выполнения сжатия диска система пишет, что доступное для сжатия место — всего лишь 45 МБ
Приветствую. Пытаюсь отделить от диска D (не системный) 50гб памяти. На диске...

Теория Алгоритмов или Путеводитель по созданию простых и эффективных алгоритмов
Я начинаю изучать язык Си, но в целом представляю, что такое алгоритм; могу...

Разработка и отладка алгоритмов и программ с использованием шаблонов классов и алгоритмов библиотеки STL
1. Создать объект-контейнер и заполнить его данными. 2. Просмотреть...

5
R71MT
3242 / 1110 / 264
Регистрация: 29.07.2014
Сообщений: 2,122
Записей в блоге: 4
26.08.2016, 22:39  [ТС] #2

Принцип кодирования по алгоритму RLE
-------------------------------------------------


Имя этого алгоритма переводится как "кодирование последовательностей". Это самый простой из всех методов сжатий. В нём нет словаря и он весьма неэффективен для текста, но вполне может сгодиться для кодирования видео- и графики. Пусть задана такая последовательность байт, которая подлежит сжатию:

Кодируемая строка: -----------------------------------------------
41 41 41 41 42 42 42 42 42 43 43 44 45 46 47 48 AAAABBBBBCCDEFGH

Алгоритм RLE предлагает заменить её структурой, в которой указывается значение кодируемого байта и коэффициент его повторения. Другими словами, нам нужен обычный счётчик повторов. Если для этого счётчика использовать 1 байт, то мы сможем закодировать в нём последовательность из 256 одинаковых элементов. Далее будем называть этот байт - маркером.

Первое, что приходит на ум - это вставлять маркер перед каждой последовательностью, например так:

Закодированный вариант:-------------------------------------------
04.41 05.42 02.43 01.44 01.45 01.46 01.47 01.48 .A.B.C.D.E.F.G.H
-----------------------------------
Коэффициент сжатия: 16 (вход) / 16 (выход) = 1% (нет сжатия)

Здесь, маркером является каждый/первый байт пары, который для наглядности я отделил точками. Работающий по такому алгоритму декодер считывает данные с входного потока словами, и использует старший байт в качестве счётчика для младшего байта. Всё идёт отлично до тех пор, пока последовательность не нарушится (..DEFGH). Как только это происходит, нам приходится тратить на каждый байт один маркер, и выигрыш превращается проигрыш.

Чтобы решить эту проблему, условимся считать маркер, как байт со-знаком. Мы будем использовать 7 бит для счётчика (0..127), а 8-ой бит будет флагом. Пусть мы потеряли в длине (127 против 256), зато теперь сможем ответить на два вопроса: байты в строке повторяются, или-же идут в произвольном порядке.

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

Рассмотрим процесс декодирования блока данных, сжатого по алгоритму RLE:

; диапазон: 00h..7Fh = 127 -> счётчик произвольных байт;
; диапазон: 80h..FFh = 127 -> счётчик одинаковых байт.

Кодируемая строка: -----------------------------------------------
41 41 41 41 42 42 42 42 42 43 43 44 45 46 47 48 AAAABBBBBCCDEFGH
Закодированный вариант:-------------------------------------------
84 41 85 42 82 43 05 44 45 46 47 48 „A…B‚C.DEFGH
-----------------------------------
Коэффициент сжатия: 16 / 12 = 1,33%

Декодер начинает чтение данных из сжатого файла и сразу натыкается на первый маркер (в данном случае 84h). Он проверяет его на знак и делает вывод, что дальше идёт одинаковая цепочка байт. На следующем шаге, декодер отнимает константу(80h) от маркера, и получает таким образом длину последовательности (в данном случае 4). Теперь, декодеру остаётся считать следующий байт(41h), как он получает все данные для дешифровки последовательности: "Вывести 4 байта со-значением 41h!"

Так будет продолжаться до тех пор, пока декодер не обнаружит (в примере выше) маркер со-значением(05h). Как уже говорилось, сброшеный/знаковый бит является флагом нарушения последовательности, поэтому декодер просто отправит значение маркера в регистр(СХ), и скопирует СХ-байт (DEFGH) в исходном виде из входного потока данных - в выходной поток.

Таким образом, при удачных обстоятельствах, алгоритм RLE позволяет сжать 127 повторяющихся байт буквально до 2-х байт. Если кодер (в процессе кодирования) обнаружит во-входном потоке цепочку более чем из 127 байт (будь-то одинаковую или нет), то он должен вставить ещё один маркер, указав в нём длину хвоста например так:

130-байтная цепочка нулей: FF 00 83 00
260-байтная цепочка троек: FF 03 FF 03 85 03

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

Для полноты картины приведу простой пример RLE-кодера и декодера, который подведёт черту под вышесказаным. Чтобы весь алгоритм всплыл наружу, в коде нет ни йоты оптимизации. Детали оставлю на любителя:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
; ======= КОДЕР =======
; Кодировать будем блоками по 256-байт. Маркер в AH.
;---------------------------------------------------------------------//
       ;.............
@pack: call  readFile         ; берём в приёмный буфер очередную порцию данных
       mov   cx,255           ; кол-во данных в буфере
       mov   di,outBuff       ; адрес приёмника (для записи в файл)
       mov   si,inBuff        ; адрес источника данных
@find: xor   ah,ah            ; очищаем маркер
       lodsb                  ; берём байт из SI
       cmp   al,byte[si]      ; сравниваем соседние байты
       jnz   @hash            ; нет одинаковой цепочки! (мусор)
 
       call  dubleCount       ; на процедуру подсчёта одинаковой цепочки
       loop  @find            ; поиск сл.цепочки из 256-байтного блока..
 
       cmp   [fSize],0        ; Один блок зашифровали! Конец файла?
       jnz   @pack            ; нет - мотаем..
       jmp   exit             ; да - на выход!
 
; Процедура подсчёта длины неодинаковой последовательности.
; Как найдём одинаковую цепочку - выходим.
; Нужно проверять маркер на переполнение. 
; Как он достигнет(7Fh), вставляем его в выходной поток.
;---------------------------------------------------------------------
@hash: inc   ah               ; считаем в маркер длину цепочки
       cmp   ah,7Fh           ; тест на переполнение
       jz    @sav1            ; вставить, если заполнился!
       lodsb                  ; иначе: возьмём следующий байт с потока(IN)..
       cmp   al,byte[si]      ; сравниваем его с соседним
       je    @sav1            ; одинаковая цепочка! пора на выход.
       loop  @hash            ; иначе: продолжаем считать
 
@sav1: shr   ax,8             ; AL = маркер, AH = 0 (заодно обновили его)
       stosb                  ; вставляем маркер в поток(OUT)!
       push  cx si            ; +
       mov   cx,ax            ; СХ = длина цепочки неодинаковых байт
       sub   si,cx            ; вернём указатель источника назад
       dec   si               ;    ..коррекция.
       rep   movsb            ; скопировать СХ-байт из IN в OUT!
       pop   si cx            ; -
       loop  @find            ; продолжаем сжимать блок..
 
; Процедура "dubleCount", для подсчёта одинаковой цепочки байт.
; С ней дела обстоят проще..
;---------------------------------------------------------------------
dubleCount:
       or    ah,81h           ; взводим старший бит в маркере
@dup:  inc   ah               ; считаем длину одинаковой цепочки
       cmp   ah,0             ; проверка на переполнение маркера!
       jnz   @ok              ; переход, если в маркере есть место
 
       rol   ax,8             ; иначе: AL = маркер, AH = значение байта
       stosw                  ; вставляем маркер и значение, в поток(OUT)
       mov   ah,81h           ; обновляем маркер!
 
@ok:   lodsb                        ; читаем поток(IN)..
       cmp   al,byte[si]      ; сравниваем соседние байты
       jnz   @sav2             ; нет последовательности!
       loop  @dup             ; всё идёт по-плану..
 
@sav2: rol   ax,8             ; цепочка прервалась!
       stosw                  ; вставить маркер,
       ret                    ;    ..и выйти из процедуры.
В своём эксперименте, я таким образом сжал картинку, и командой "incbin" зашил её в тушку программы. Теперь, внутри поместил декодер, который при надобности распаковывал бинарник. Декодер имел приблизительно такой вид:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
; ======= ДЕКОДЕР =======
; Для него принципиально декодировать сразу весь файл (или по 1 байту),
; т.к. маркеры разбросаны по всему телу данных, и мы не знаем - где точно. 
; Зато уверены, что первый байт - эт точно маркер.
;---------------------------------------------------------------------//
       ;.............
       mov   cx,[fSize]       ; длина файла
       mov   si,inBuff        ; источник сжатой информации
       mov   di,outBuff       ; сюда будем распаковывать
       xor   ah,ah            ; AH = 0
 
@find: lodsb                  ; берём очередной маркер из потока(IN)
       test  al,80h           ; проверка знакового бита в маркере
       jnz   @dup             ; переход, если обнаружена одинаковая цепочка!
                              ; иначе..
 
; Декодер не одинаковой последовательности байт
; Сейчас маркер в AX (AH=0), и хранит длину цепочки в явном виде (00..7Fh).
; SI указывает на адрес начала этой цепочки в потоке(IN).
;---------------------------------------------------------------------
       push  cx               ; +
       mov   cx,ax            ; CX = счётчик байт для копирования
       rep   movsb            ; копируем СХ-байт из SI в DI
       pop   cx               ; -  
       jmp   @next            ; прыгаем вниз..
 
; Декодер одинаковой цепочки байт
; Здесь тоже-самое, только корректируем длину в маркере,
; читаем следующий байт, и дублируем его в поток(OUT)
;---------------------------------------------------------------------
@dup:  sub   al,80h           ; отнимаем от маркера константу
       push  cx               ; +
       mov   cx,ax            ; СХ = кол-во повторов
       lodsb                  ; берём значение повторяющегося байта
       rep   stosb            ; выводим его СХ-раз!
       pop   cx               ; -
@next: loop  @find            ; продолжаем декодирование потока(IN)..
       ;..........
Нужно сказать, что простой алгоритм дал неплохие результаты. Коэффициент сжатия получился более 6%, и битмап сжался с 40 до 6 килобайт, что меня вполне устроило.
0
gazlan
3139 / 1915 / 311
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
26.08.2016, 23:22 #3

Не по теме:

Оставляя "за кадром" стиль и орфографию...


Рекомендую ознакомиться со статьями на сайте Всё о сжатии данных, изображений и видео, в том числе с превосходным обзором Bell T., Witten I, Cleary J. "Modeling for Text Compression"

Почти все вами сказанное, либо какая-то частность, не дающая верного представления о предмете, либо даже неверно полностью.

Например, большая часть промышленно используемых (BZip, Rar, 7z) методов сжатия (включая мультимедийные) не упомянута вовсе. Ничего о контекстном моделировании, ни слова про lossy и фрактальные алгоритмы.

К вашему посту: "избыточность данных" a) необязательна b) часто намеренна. LZ - это два разных семейства алгоритмов (LZ77 и LZ78), причем, именно им свойственна "асимметричность" по времени/памяти, для большинства других алгоритмов (например, PPM) это не так. В алгоритме Хаффмана дерево не обязательно бинарное (это частный случай), и строится оно в точности обратно написанному вами: от листьев к корню, то есть снизу-вверх, чем и достигается его оптимальность (в отличие от Шеннона-Фано).
0
Kukuxumushu
753 / 476 / 89
Регистрация: 13.06.2015
Сообщений: 1,631
Завершенные тесты: 2
26.08.2016, 23:37 #4
Ох, я думал тут сейчас будет WinRAR на асме))) RLE это же самый примитивнейший алгоритм.
Я ещё в школе когда учился сделал кодек изображений на основе RLE, который разбивал картинку на прямоугольные области с одинаковыми битовыми уровнями R, G и B. Не на асме, конечно. (Второе место в городском конкурсе программистов, между прочим, с ним занял))))
0
R71MT
3242 / 1110 / 264
Регистрация: 29.07.2014
Сообщений: 2,122
Записей в блоге: 4
26.08.2016, 23:59  [ТС] #5
gazlan, спасибо за замечания, но целью было не охватить все алгоритмы сжатия, а рассмотреть именно частный случай, с которым я столкнулся. Это не урок по информатике. А кому нужно, тот сам погуглит и будет разбираться во-всём с нуля. Лично до меня это дошло в таком виде, и я получил какой-то результат.
0
gazlan
3139 / 1915 / 311
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
27.08.2016, 03:25 #6
Цитата Сообщение от Kukuxumushu Посмотреть сообщение
RLE ... примитивнейший алгоритм

Не по теме:

Это иллюзия :-) В то время, как Хаффман, математически, просто инвертор длин кодов (кодового дерева), RLE меняет размерность кодового пространства (сравните, например, с транслитом из кириллицы в латиницу).

И, к слову, Компрессия и декомпрессия RLE + Сжатие данных - тренажеры для изучения алгоритмов сжатия

0
27.08.2016, 03:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2016, 03:25
Привет! Вот еще темы с решениями:

Обзор Other 2.0
О программе, делаю в основном для себя, но если ей будут еще люди пользоваться...

3D обзор
привет всем. парни помогите нахожусь в трудной жизненной ситуации нету даже...

3d обзор помещений
Здравствуйте! Передо мной стоит задача реализовать 3d обзор помещений. Казалось...

3d обзор помещений
Здравствуйте! Передо мной стоит задача реализовать 3d обзор помещений. Казалось...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru