Воскресенье, 20.08.2017, 14:51

..



Главная Регистрация Вход
Приветствую Вас, Гость · Браузер: « v»
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Всё об «Электроника БК0010(-01), БК0011(М)»! » Программы | Утилиты | ДОСы » Упаковщики (Архиваторы) данных » «ZIP» » «ZIP» [xx.03.92] (Автор: Милюков А.В.)
«ZIP» [xx.03.92]
-=RUS=-Дата: Четверг, 06.11.2014, 18:57 | Сообщение # 1
Генералиссимус
Группа: Администраторы
Сообщений: 350
Репутация: 1
Статус: 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


 
Всё об «Электроника БК0010(-01), БК0011(М)»! » Программы | Утилиты | ДОСы » Упаковщики (Архиваторы) данных » «ZIP» » «ZIP» [xx.03.92] (Автор: Милюков А.В.)
Страница 1 из 11
Поиск:

-=RUS=-
ICQ: 320867225