| -=RUS=- | Дата: Четверг, 06.11.2014, 18:57 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 352
Статус: Offline
| (ZIP.doc)
┌───────────────────────────────────────────────┐
│ │
│ Д О К У М Е Н Т А Ц И Я │
│ │
│ к пакету программ │
│ │
│ BKZIP и BKUNZIP │
│ │
│ (пособие для начинающих архивариусов) │
│ │
│ версия март 1992 г. │
│ │
└───────────────────────────────────────────────┘
Введение
¯¯¯¯¯¯¯¯
Пакет разработал Милюков А.В. В основу были положены идеи
достаточно известного пользователям IBM PC/XT/AT пакета PKZIP.
Из известных автору разработок - COMP2 В.Бабкина, FAST ARCHIVES
и ARCHIV.AW5 Войлукова А. ни одна программа не способна серьезно
сжимать исполняемые файлы системных программ и текстовые блоки.
Причина этого кроется в том, что с точки зрения архиватора
такие файлы являются случайным набором байт. Естественно, что
редкий отладчик или компилятор содержит подряд несколько одина-
ковых байтов, которые могут быть заменены одним с занесением
адреса этой замены в таблицу,(а именно так или почти так работа-
ют вышеназванные программы). Поэтому ситуация, когда размер слу-
жебной информации, введенной в файл после его сжатия, больше
экономии от самого сжатия, типична. На практике сложно найти и в
тексте строку одинаковых байт, если, конечно, это не пробелы или
псевдографика.
Вообще говоря,возникает проблема правильного выбора алгоритма
сжатия, который позволил бы снизить требования к содержимому
файла. Автору известны несколько видов - метод Хоффмана (коды
переменной длины), методы Лемпеля-Зива (поиск подстрок), различ-
ные префиксные и словарные способы кодирования. Простейший спо-
соб словарного сжатия автор использовал в компиляторе MAWR. Не-
трудно заметить, что такой алгоритм предполагает знание прибли-
женного состава файла и если текст не содержит операторов Ассем-
блера, то он несжимаем таким способом.
Методы, использующие поиск одинаковых строк для их последую-
щей замены, обычно требуют создания обширных таблиц частот пов-
торения байтов и их комбинаций, а также требуют значительного
времени, что нельзя не учесть.
Автором ведется в этом направлении работа, результатом кото-
рой может стать создание хорошего архиватора. Пока же, учитывая
наибольшую потребность в быстром сжатии, был разработан метод,
компромиссный во многих отношениях.
Сжатие по методу Хоффмана
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
По виду упаковки метод является модификацией Хоффмана.
Ближайший его "родственник"- код RADIX50. В последнем, как легко
видеть, старшие биты в слове часто не заполнены, и его разряд-
ность постоянна- около пяти. В коде Хоффмана в слове может быть
закодировано до 16 байтов. Например, имея текст БУБУБУ-БУБУБУ и
согласившись обозначать Б=01 У=10 -=11, мы имеем право на его
битовый образ 01100110011011011001100110. Читая биты слева
направо, можно определить конец одного и начало другого кода.
При таком коде текст 13Х8=104 бита сжат до 26 бит. Важным явля-
ется то, что не нужно разбиение кода на слова и байты: это бито-
вый поток. Закономерен вопрос - кто дал нам право назначить
такие коды байтам и как быть в случае, когда букв больше? Ответ
лежит на поверхности: для различения двух символов достаточно 1
бит информации, четырех - 2 бита и т.д. независимо от кодов этих
символов. Если число разных символов не равно 2 в степени N, то
коды части из них могут быть короче остальных. Например, файл
содержит байты от 0 до 12, от 40 до 177 и буквы У и Ж. Для рас-
познания кодов до 177 может потребоваться 8-разрядный код, тогда
как буквы У и Ж потребуют только 2-разрядный. Он должен будет
отличаться первым битом от основной группы, второй укажет одну
из возможных букв. Весьма наглядно представление кодов всех
символов файла в виде древовидной структуры, где листьями будут
символы,а ветви и развилки изображают связь кодов этих символов.
┬ Это вершина дерева
│
1 ┌┴┐ 0
┌────────────┤■├──────────────┐
│ └─┘ │
1 ┌┴┐ 0 1 ┌┴┐ 0
┌────┤■├────┐ ┌──────┤■├──────┐
│ └─┘ │ │ └─┘ │
│ 1 ┌┴┐ 0 1 ┌┴┐ 0 1 ┌┴┐ 0
│ ┌──┤■├──┐ ┌──┤■├──┐ ┌──┤■├──┐
│ │ └─┘ │ │ └─┘ │ │ └─┘ │
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
│М│ │И│ │Л│ │Ю│ │К│ │О│ │В│
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘
Чтобы при помощи дерева получить код Хоффмана, например бук-
Вы К, нужно добраться до неё от вершины, запоминая при этом
попутные биты 0/1. Легко видеть, что: 11=М 101=И 100=Л 011=Ю и
так далее.
Наоборот, получив из массива кодов Хоффмана три нулевых бита
подряд, можно быть уверенным в том, что исходный текст содержал
символ В. Этот пример иллюстрирует основу метода – нахождение
кода для символа и символа по коду. Очевидно, что количество и
состав символов в файле не повлияют на алгоритм, но дерево изме-
нится. Автор счёл весьма удобным составлять всякий раз полное,
то есть содержащее все 256 листа дерево, удаляя затем из него
все, относящееся к ненайденным в файле символам.
Тогда для двух разных файлов поиск кодов Хоффмана будет про-
ходить одинаково, но удаление коснется разных символов (листьев
дерева). Естественно, что алгоритм сжатия и распаковки будет не-
изменен от файла к файлу. Эти соображения обусловили выбор заго-
ловка файла-архива: достаточно сохранить сведения об отсутствую-
щих в данном файле символах, чтобы при разархивировании восста-
новить дерево, использованное при сжатии файла. Далее, как по-
казано в примере, анализируя бит за битом сжатый файл, можно
восстановить его содержимое.
Некоторую трудность представляет размещение дерева в памяти,
но это преодолимо, если использовать подобие File Allocation
Table IBM PC: пусть вершина хранит адрес двух отходящих ветвей,
те, соответственно, своих дочерних и так далее, а листья пометим
установленным знаковым битом(все ссылки имеют адреса 0...77777).
Тогда зная, например, что файл не содержит букву Ъ, мы отыщем в
структуре дерева слово 100377 и ссылку на него заменим на эле-
мент из противоположной ветви. Это может быть тоже лист дерева
или его ветвь. Такие действия правомерны потому, что отсутствие
одного из выбираемых путей (ветвей или листьев) делает ненужным
выбор и соответственно код Хоффмена станет на 1 бит короче.
После удаления лишних элементов дерево способно стать ключём
к кодированию и декодированию файла.
Более детальные комментарии и исходные тексты пакета Вы може-
те получить, обратившись через редакцию журнала "Вычислительная
техника и её применение" к автору - Милюкову Александру
Васильевичу.
Основные характеристики BKZIP:
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
адрес загрузки 1000
длина 1166
Основные характеристики BKUNZIP:
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
адрес загрузки 1000
длина 776
ДИРЕКТИВЫ:
¯¯¯¯¯¯¯¯¯¯
L - чтение файла с ленты в ОЗУ экрана по имени. Ошибка чтения
вызывает повтор. Выход - СТОП
Программа BKZIP требует загрузки исходного файла, а BKUNZIP-
файла с расширением .ZIP
После успешной загрузки программа преобразует файл в нужный
формат. Это сопровождается появлением внизу экрана кодовых
таблиц и звуком, число которых равно длине файла в килобайтах.
По окончании преобразования программа ждет нажатия клавиши.
<пробел> - запись файла-результата на ленту. BKUNZIP заполня-
ет пробелами расширение имени файла, BKZIP вставляет в имя рас-
ширение .ZIP, адрес файла на запись 6/10 тыс. восьм.
BKUNZIP позволяет также запустить исполняемый файл с началь-
ного адреса. После распаковки и, возможно, записи на ленту можно
по директиве G указать адрес, куда будет перенесен файл перед
запуском. Управление будет передано по этому же адресу. Пересе-
чение адресов файла с самим собой нежелательно.
Предложения и замечания по работе пакета направляйте:
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
117490 г.МОСКВА, ул.ДОНСКАЯ, 6.
арендное предприятие "ЭЛЕКТРОНИКА-КЦ"
проезд: ст.метро ОКТЯБРЬСКАЯ т.238-26-02
|
| |
| |
.
