Компрессия программ
Для начала наболевшая тема:
компрессия текста. Практически
идеальным вариантом является
компрессия текста по методу Хаф-
фмана (в чистом виде) - для тек-
стов (больших размеров) данный
метод более прогрессивен, чем
LZSS (про RLE вообще молчу). Про
компрессию Хаффмана и пойдет
речь.
Теория
Тексты обыкновенно пишут ли-
бо на русском, либо на англий-
ском языках, поэтому часто пов-
торяться будут не более 90 (ла-
тинский) или 120-140 букв (рус-
ский). Причем по приблизительным
расчетам 30% из них занимают
очень часто встречающиеся буквы.
Из всего этого следует, что
нам нужно преобразовать алгоритм
компрессии Хаффмана так, чтобы
он работал в этих условиях.
Первое, что нам нужно сде-
лать - составить таблицу по час-
тоте используемых элементов -
массив из 256 байт. На первом
месте должен стоять наиболее ча-
сто встречающийся символ, на по-
следнем - наименее. Примеров
приводить не буду, т.к. сделать
это очень легко.
Итак, массив получен, теперь
самое главное: разрабатываем
формат, в котором будут хранить-
ся данные. Принцип такой: все
числа делятся на 5 групп по чис-
лу битов:
Группа Кол-во битов
1 1
2 2
3 3
4 4-8
Числа с 1-ой по 3-ю группу
кодируются так: сначала идет N
включенных битов - какой номер
группы, столько битов. Затем
идет само число (битов по груп-
пе), причем первое его значение
установлено в 0. (Для более лег-
кого усвоения материала см. ZX-
Ревю 1/95). Пример:
Число 0. Занимает 1 бит: %0.
Число 1-ой группы. Значит, оно
будет выглядеть как %10 - всего
2 бита.
Число 3. Занимает 2 бита:
%11. 2-я группа: %11 01 - четыре
бита. Само число преобразовано
из %11 в %01, чтобы програм-
ма-декомпрессор могла подсчитать
номер группы.
Как видите, чем больше груп-
па, тем меньше выигрыш:
Группа Выигрыш (бит)
1 6
2 4
3 2
Но все равно выигрыш очень
велик. Но если пойти дальше по
этому пути, то 8-битные числа
будут кодировать 16 битами,
7-битные - 14, что нас не устра-
ивает.
Поэтому для 4-8 групп приме-
нен специальный формат: вместо
единиц с номером группы записы-
вается бит = 0 - признак спец-
формата. Затем мы записываем еще
один бит: если он равен 0, то за
ним идет нормальное восьмибитное
число (в случае 6, 7, 8 групп).
Если он равен 1, то за ним идет
5-битовое число (4, 5 группа).
Группа (бит) Выигрыш (бит)
4 +1
5 +1
6 -2
7 -2
8 -2
Пример: число 255. 8-я груп-
па, %11111111. После компрессии:
%00 %11111111 (потеря 2-х байт).
Число 64. 7-я группа, %01000
000. Результат: %00 %01000000
(опять потеря).
Число 8. 4-я группа, %0000100
0. Результат: %01 %01000 (выиг-
рыш 1 бита).
Но ведь чисел с номерами
32 - 255 подавляющее большин-
ство - скажете вы. Вот тут и
дает себя знать алгоритм Хаффма-
на: ведь в таблице мы закодиро-
вали наиболее встречающиеся сим-
волы меньшими кодами, а, особен-
но в текстах, такие символы и
составят у нас большинство (в
русском и английском - гласные,
пробелы).
Алгоритм: декомпрессирующая
программа должна расскомпресси-
ровать код, затем по таблице
найти соответствующий ему сим-
вол.
Пример такого декомпрессора:
(программа сырая, не релоцируе-
мая, не оптимизирована).
Данная программа только осу-
ществляет конвертирование в коды
из компрессированного файла. Вам
нужно писать свою процедуру по-
лучения исходного кода по табли-
це (вычисляется из полученного
кода операциями:
LD L,N ;N-номер кода
LD H,0 ;в двухбайтную форму
LD DE,TABLE ;адрес таблицы
ADD HL,DE ;вычисляем адрес
LD A,(HL) ;получили код
Вход в программу: IY - адрес
компрессированного блока, IX -
адрес, куда происходит деком-
прессия. Формат компрессирован-
ного файла: сначала идут 2 бай-
та - длина файла перед компрес-
сией (сколько всего кодов).140.
ORG 32768
LD E,(IY+0) ;берем длину
LD D,(IY+1)
INC IY
INC IY ;в IY-адрес файла
LD (LONG),DE ;сохраняем длину
LD D,7 ;бит 7.
MAIN CALL GRUPPA ;берем номер группы
CALL PRIEM ;вычисляем код
PUSH BC
LD BC,(LONG)
DEC BC ;уменьшили длину
LD (LONG),BC
LD A,B
OR C
POP BC
JR NZ,MAIN ;в цикл
RET
LONG DW 0 ;сохраняет длину
;увеличение битового адреса
INCBIT PUSH AF ;сохранили A
LD A,D ;номер бита
AND A ;если =0, то
JR Z,NEWBYTE ; переход
DEC A ;уменьшили номер
LD D,A ;в регистр D
POP AF ;восстановили A
RET ;Выход
NEWBYTE LD D,7 ;новый байт.Бит 7
INC IY ;увеличили байтовый
POP AF ; адрес.Восстановили
RET ; A и выход
;проверка бита из адреса
;если бит=0, то в A будет 0, если бит=1,
;то в A будет 255.
GETBIT LD A,#47 ;код BIT 0,A
GETBIT1 PUSH BC ;запомнили BC
LD (BT+1),A ;вставили код
LD A,D
AND A ;если бит 0 ,то
JR Z,PROH ; переход
LD B,A ;счетчик битов
UST LD A,(BT+1) ;устанавливаем
ADD A,8 ; команды BIT 0,A
LD (BT+1),A ; 1,2,3,4,5,6,7
DJNZ UST
PROH LD A,(IY+0) ;берем байт
BT BIT 0,A ;проверяем бит
POP BC ;восстанавливаем BC
IZ DB 0
JR Z,BIT0 ;если бит=0,переход
BIT1 LD A,255 ;бит=1
RET
BIT0 XOR A ;бит=0
RET
;включение бита из адреса
SETBIT PUSH AF ;запомнили A
LD A,#C9 ;используем GETBIT
LD (IZ),A ; из SETBIT:код RET
LD A,#C7 ;код SET 0,A
CALL GETBIT1 ;в A-полученный байт
LD (IY+0),A ;байт в адрес
XOR A ;восстановили
LD (IZ),A ; GETBIT
POP AF ;восстановили A
RET
;получение номера группы
;вход: битовый адрес на указателе группы
GRUPPA CALL GETBIT ;берем бит
AND A ;равен 0 ?
JR Z,GRUP58 ;5-8 битное число
CALL INCBIT ;увеличили адрес
LD C,1 ;счетчик группы
GR1 CALL GETBIT ;взяли бит
AND A ;равен 0 ?
JR Z,GR2 ;если да,пошло число
INC C ;увеличили группу
CALL INCBIT ;увеличили адрес
JR GR1 ;в цикл
GR2 CALL SETBIT ;включили бит(т.к. 1
LD B,C ;бит числа, равный 1
RET ;установлен в 0
GRUP58 CALL INCBIT ;увеличили адрес
CALL GETBIT ;взяли бит
AND A ;равен 0 ?
JR Z,GRUP5 ;5-битное число
GRUP8 CALL INCBIT ;8-битное число
LD B,8 ;группа 8
RET
GRUP5 CALL INCBIT ;увеличили адрес
LD B,5 ;группа 5
RET
;получение числа. B-номер группы
;битовый адрес на числе.
PRIEM XOR A ;обнулили ротируемый
LD (BYTE),A ;байт-приемник
PR CALL GETBIT ;взяли бит
AND A ;если не равен 0, то
CALL NZ,WKL ;включаем бит в BYTE
LD A,(BYTE) ;ротация байта-
RLA ; приемника
LD (BYTE),A
CALL INCBIT ;увеличили адрес
DJNZ PR ;номер группы=циклам
LD (IX+0),A ;получили код
INC IX ;увеличили адрес
RET ; приемника
WKL SCF ;включение бита
RET
BYTE DB 0 ;байт-приемник
2
Из этого вытекает несколько
особенностей компрессии Хаффма-
на:
1. На мелких файлах (по рас-
четам, до 3 Кб) компрессор не
даст выигрыша, так как сама де-
компрессирующая программа будет
довольно большая - нужно сохра-
нить таблицу (уже 256 байт) и
т.д.
2. Чем больше файл и чем
меньше в нем используемых симво-
лов, тем мощнее компрессия.
3. Главная особенность: в от-
личие от других компрессоров
(LZSS, RLE), в компрессированном
файле хранятся не данные, а их
коды!!! Поэтому изменять их ни в
коем случае нельзя. (А вот в
LZSS и, тем более, в RLE, можно:
влез доктором в файл на диске,
поискал свою надпись - может,
она и не скомпрессировалась - и
если нашел, то изменил как нуж-
но. Здесь же вы не только ничего
не найдете, но и еще испортите
ВЕСЬ файл...)
4. Малая скорость декомпрес-
сора (по сравнению с другими
технологиями).
Но это все теория - так что,
кто попробует алгоритм Хаффмана
на практике - напишите в Ревю.
Прим. ред.: Можно значительно сократить
таблицу частот символов, если учесть, что
символы с номерами 32-255 кодируются оди-
наковым числом битов (десятью битами), и,
следовательно, порядок их расположения в
таблице не влияет на размер сжатого файла.
Таким образом, в таблице достаточно хра-
нить лишь 32 наиболее часто используемых
символа.
И еще. Попробуйте реализовать улучшен-
ный алгоритм Хаффмана, в котором кодируют-
ся как отдельные символы, так и наиболее
часто встречающиеся пары символов. Напри-
мер, в тексте на английском языке часто
встречается пара символов "th". Очевид-
но, длина кода, соответствующего этой паре
символов, будет меньше, чем сумма длин ко-
дов символов "t" и "h". За счет этого дос-
тигается превосходство в сжатии.
* * *
(c) Иван Рощин, г.Москва, 1997
Особенности ассемблера
ZX ASM 3.0
При выполнении команды "Load
sts" (в меню Setup) в случае,
если файл с указанным именем не
будет найден, сообщение об ошиб-
ке не выдается.
Если установлен режим Edit
mode = Text, вы лишаетесь воз-
можности доступа ко всем пунктам
меню Run, кроме Inspect, что не
всегда удобно.
Не выдается сообщение об
ошибке при ассемблировании ко-
манды загрузки в однобайтный ре-
гистр двухбайтного числа. Напри-
мер, команда LD B,#1234 будет
ассемблирована как LD B,#34.
ZX ASM почему-то считает, что
регистры HL, IX, IY равноправны,
т.е. в любой команде, использую-
щей HL, можно использовать и ре-
гистры IX, IY. Если в командах
типа LD A,(HL) это действительно
так, то к командам типа ADD HL,
HL и к некоторым другим это не
относится. Поясню сказанное на
примере:
Исходный текст │ Компилируется
───────────────┼──────────────
ADD HL,IX │ ADD HL,HL
SBC HL,IY │ SBC HL,HL
EX DE,IX │ EX DE,HL
Эта ошибка может привести к
крайне неприятной ситуации. На-
пример, вы в своей программе на-
писали ADD HL,IX, забыв, что та-
кой команды нет. Ассемблер так-
же "ничего не заметил", а потом
вы удивляетесь, почему ваша про-
грамма не работает.
В командах, работающих с по-
ловинками индексных регистров,
должны использоваться обозначе-
ния XL,XH,YL,YH. Между тем, STS
в этих же командах использует
обозначения LX,HX,LY,HY.
Некорректно обрабатывается
ситуация, когда вы определяете
переменную с помощью DS, а коли-
чество отводимых под нее байтов
равно нулю. Такой случай может
возникнуть, например, если вы
сначала определили переменную с
помощью DB, а потом решили заме-
нить DB на DS, при этом забыв
заменить 0 на 1:
NAME DB 0 -> NAME DS 0
Если текст программы изменял-
ся с момента последней записи на
диск, ZX ASM перед выполнением
"опасных" операций предложит со-
хранить его. Но как же ZX ASM
определяет, изменялся текст или
нет? Очевидно, просто путем сра-
внения контрольной суммы текста,
находящегося в памяти, и текста,
в последний раз записанного на
диск. Но этот способ в некоторых
случаях дает неправильный ре-
зультат, и ZX ASM считает, что
текст не изменился:
а) LD HL,#1234 LD HL,#3214
DB %01100110 DB %11001100
(т.к. изменение порядка символов
не влияет на контрольную сумму
текста)
б) LD A,5 LD A,4
LD B,6 LD B,7
(т.к. ASC-коды символов "5" и
"6" в сумме равны #35+#36=#6B,
и этой же величине равна сумма
кодов символов "4" и "7").
* * *
