Форум - Компрессия программ.

      Компрессия программ

    Для начала наболевшая  тема:
компрессия  текста.  Практически
идеальным  вариантом    является
компрессия текста по методу Хаф-
фмана (в чистом виде) - для тек-
стов (больших  размеров)  данный
метод  более  прогрессивен,  чем
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").

           *   *   *