-=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
|
|
| |