ZX Review #7-8-9-10 08 ноября 1997

Этюды - Процедура составления оптимальной таблицы символов.

(c) Татаринов М., г.Соликамск

   Хочу  предложить   процедуру,
которая будет  полезна  создате-
лям  компрессоров,  использующих
алгоритм Хаффмана (битовая  ком-
прессия).
   Как известно, подобный  метод
требует наличия справочной  таб-
лицы символов.  Чем  меньше  бу-
дет номер символа в таблице, тем
меньше потребуется бит для коди-
ровки этого символа. Данная про-
цедура  составляет  для  каждого
файла оптимальную таблицу.
   Программа работает  следующим
образом: первым делом  подсчиты-
ваются  коэффициенты  повторения
каждого  символа  в  файле,  за-
тем  коэффициенты сортируются, и
идентификаторы этих  коэффициен-
тов упаковываются в таблицу.
   Программа для работы  требует
буфер, максимальный размер кото-
рого равен 3*256=768 байт (т.е.,
если в файле 256 различных  сим-
волов. 3 - это размер одной  за-
писи в  буфере).  Таблица  будет
записана также в начало буфера.
140.
;Программа для составления
;таблицы
;(C) Mat Software'96

MKTREE    LD      A,#FF
          LD      (TSIZE),A
          LD      D,0
;начальный символ - 0
          LD      IX,(TREE)
;адрес буфера
AG        LD      HL,(RAW)
;адрес файла
          LD      BC,(LEN)
;длина файла
          CALL    ONE
          LD      A,D
          CP      #FF
;все символы проверены?
          JR      NC,SORT
;да - идем на сортировку.
          INC     D
;иначе - повтор для всех 256
          JR      AG
ONE       XOR     A
          LD      (PEP),A
          LD      (PEP+1),A
SEEK      LD      A,(HL)
          CP      D
          JR      NZ,NXT
          PUSH    HL
          LD      HL,(PEP)
          INC     HL
          LD      (PEP),HL
          POP     HL
NXT       LD      A,B
          OR      C
          JR      Z,EOF
          DEC     BC
          INC     HL
          JR      SEEK
EOF       LD      HL,(PEP)
          LD      A,H
          OR      L
          RET     Z
          LD      (IX+0),D
          LD      (IX+1),L
          LD      (IX+2),H
          LD      BC,3
          ADD     IX,BC
          LD      HL,TSIZE
          INC     (HL)
          RET

;Процедура сортировки символов

SORT      LD      A,(TSIZE)
          LD      B,A
PS2       LD      IX,(TREE)
          LD      A,(TSIZE)
          LD      C,A
PS1       LD      D,(IX+2)
          LD      E,(IX+1)
          LD      H,(IX+5)
          LD      L,(IX+4)
          AND     A
          SBC     HL,DE
          JR      C,NOPF
          PUSH    BC
          LD      A,(IX+3)
          LD      B,(IX+0)
          LD      (IX+0),A
          LD      (IX+3),B
          LD      A,(IX+4)
          LD      B,(IX+1)
          LD      (IX+1),A
          LD      (IX+4),B
          LD      A,(IX+5)
          LD      B,(IX+2)
          LD      (IX+2),A
          LD      (IX+5),B
          POP     BC
NOPF      LD      DE,3
          ADD     IX,DE
          DEC     C
          JR      NZ,PS1
          DJNZ    PS2

;формирование таблицы

FORM      LD      A,(TSIZE)
          LD      IX,(TREE)
          LD      HL,(TREE)
          LD      B,A
ALL       LD      A,(IX+3)
          INC     HL
          LD      (HL),A
          LD      DE,3
          ADD     IX,DE
          LD      A,B
;вместо DJNZ!
          AND     A
          RET     Z
          DEC     B
          JR      ALL

;переменные:

RAW       DW  0 ;адрес файла
TREE      DW  0 ;адрес буфера
LEN       DW  0 ;длина файла
PEP       DW  0 ;рабочая пере-
                ;менная
TSIZE     DB  0 ;размер таблицы,
;причем если TSIZE=0, то
;размер - 1 байт.
2
   Теперь немного о странном на-
чальном  значении  TSIZE  -  #FF
(-1). Логичнее, казалось бы, ус-
тановка TSIZE в 0.  Однако, если
в файле будет содержаться макси-
мум - 256 различных символов, то
TSIZE, установленный в 0, на вы-
ходе даст тоже 0, поэтому прихо-
дится так изворачиваться.
   И еще: процедура компрессора,
преобразующая код символа в  его
номер в таблице, тоже может сра-
ботать ошибочно при TSIZE = max,
поэтому придется в ней DJNZ  за-
менить на:

          LD      A,B
          AND     A
          JR      NZ,XXXX

   Это, конечно, если Вы не наш-
ли в вашей процедуре лучший  ме-
тод. А вообще-то можно  обойтись
без ухищрений: надо размер TSIZE
определить не в байт, а в слово.
Тогда, правда, придется  жертво-
вать дополнительной  регистровой
парой, а значит, неизбежны  вся-
кие  PUSH'ы и POP'ы, замедляющие
и без того медленную  программу.
Кстати, о скорости. В моей  про-
цедуре компрессии большую  часть
времени  отнимало    составление
таблицы.  Очень  много   времени
уходит  на  сортировку,  поэтому
метод, предложенный  выше, жела-
тельно заменить на более быстрый
(типа алгоритмов  Шелла  и  "пу-
зырька". Советую прочитать в  ZX
РЕВЮ N5, 1994 статью  о  методах
сортировки).

   Прим. ред.: Одним из  наиболее  быстрых
способов сортировки является  метод  "быс-
трой сортировки Хоара".

          *   *   *