Л
Ребенок
ист
дерева - узел, из которого не выходит
ни одной дуги. В паре узлов дерева,
соединенных между собой дугой, тот, из
которого она выходит, называется
родителем, другой же
ребенком. Два узла называются братьями,
если имеют одного и того же родителя.
Д
воичное
дерево - дерево, у которого из всех
узлов, кроме листьев, выходит по две
дуги.Дерево кодирования Хаффмана (H - дерево) - двоичное дерево, у которого каждый узел имеет вес, и вес родителя равен суммарному весу его детей.
Входной алфавит - множество символов, входящих в сообщение.
Алгоритм построения H-дерева:
С
15 7 6 6 5
А Б В Г Д
Исходная таблица частот.
имволы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.В
ыбираются
два свободных узла дерева с наименьшими
весами.Создается их родитель с весом, равным их суммарному весу.
Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
Одной дуге выходящей из родителя, ставится в соответствие бит 1, а другой бит 0.
Ш
А 0
Б 100
В 101
Г 110
Д 111
Коды Хаффмана
аги,
начиная со второго, повторяются до тех
пор, пока в списке свободных узлов не
останется только один свободный узел.
Он и будет считаться корнем дерева.
2. Архиваторы
Архиватор RAR
Разработчик архиватора RAR — челябинский программист Евгений Рошал; в этой статье рассматривается версия 1.53, датированная декабрем 1994 г., но с июня 1995 г. доступна версия 1.54, о которой немного будет сказано в конце. Основной путь распространения RAR, как и большинства других некоммерческих и «слабо коммерческих» продуктов, — глобальные компьютерные сети. Сопровождение и регистрацией пользователей занимается сеть дистрибуторов со штаб-квартирой в Хельсинки и пунктами по всему миру.
Для тех, к кому программа по каким-то причинам попала без документации, скажу, кратко об, условиях, на которых ею можно пользоваться. Бесплатная версия предназначена для ознакомления с продуктом; проработав с ней 40дней, вы обязаны либо стереть со своего компьютера все файлы, относящиеся к RAR, либо зарегистрироваться у одного из, официальных дистрибуторов, внеся установленную плату, (иначе вы становитесь нарушителем лицензионного соглашения). Россиянам проще всего обратиться к Андрею Спасибожко - это единственный дистрибутор на всей территории бывшего СССР. Его почтовый адрес: 454014, Челябинск, а/я 12687;e-mail: andrey@vybor.chel.su; FIDOnet: 2:5010/23.
Зарегистрированному пользователю предоставляются доступ к некоторым дополнительным функциям RAR, стандартные услуги (сопровождение, консультации), право на коммерческое использование архиватора и на получение всех его следующих версий с сохранением регистрации. А теперь — об основных возможностях существующей версии.
Режимы сжатия
Как и многие другие архиваторы, RAR предусматривает различные методы сжатия: можно паковать информацию «на время», можно «на объем», можно выбрать нечто среднее. Всего методов шесть, они нумеруются числами от 0 до 5. Методу 0 соответствует нулевое сжатие (сору), т. е. простое копирование файлов в архив без упаковки, методу 1 — сверхбыстрое (fastest), далее идут быстрое (fast), нормальное (normal), высокое (good) и максимальное (best). Если файлов более одного, архив можно сделать монолитным (solid; другие русские термины — «блочный», «непрерывный», «связанный»).
Идея монолитного архива состоит в том, что файлы, помещаемые в него, сжимаются не по отдельности, а как один большой файл. Если, например, некоторая цепочка символов встречается по одному разу в файлах 1, 2 и 3, то при упаковке в обычный архив она не будет закодирована как повторяющаяся, а при упаковке в монолитный — будет; следовательно, во втором случае получится более высокая степень сжатия.
Наиболее заметного эффекта следует из общих – соображений ожидать при упаковке большого числа сравнительно коротких однотипных файлов. В документации сказано, что монолитный архив может оказаться на 10-60% короче соответствующего обычного. В моих отнюдь не претендующих на полноту экспериментах максимум, правда, не встретился ни разу, но разницу в тридцать с лишним процентов наблюдать приходилось.
Скорость создания (дополнения) и распаковки монолитного архива теоретически не должна существенно отличаться от скорости выполнения аналогичных операций с обычным архивом. Как правило, RAR создает такие архивы чуть медленнее, чем обычные, но иногда (в режиме сверхбыстрого сжатия) на какие-то доли процента быстрее; распаковывает — и быстрее, и медленнее. Впрочем, отличия всегда незначительные.
Два принципиальных недостатка монолитных архивов — это низкая надежность и сложность модификации. Действительно, поскольку они организованы так, что каждый файл используется при сжатии следующих, повреждение какого-то одного файла с высокой вероятностью приведет к потере всего «хвоста» архива, а для удаления или замены файла «хвост» нужно, вообще говоря, полностью распаковать и вновь упаковать (может быть, на чем-то и удастся сэкономить, но не очень существенно). Модификация монолитных архивов поддерживается в RAR только начиная версии 1.52 (август 1994 г.) и, естественно, требует больше и времени, и памяти, чем внесение изменений в обычный архив. Поэтому в документации не рекомендуется создавать архив как монолитный, если его предполагается часто обновлять. А вот для передачи информации подканалам связи, когда на одном конце она пакуется, а на другом сразу же распаковывается, эта разновидность архивов подходит как нельзя лучше.
Порядок, в котором файлы помещаются в монолитный архив, способен влиять на степень сжатия. Стандартно RAR сортирует их по алфавиту расширений независимо от структуры каталогов — так, чтобы формально однотипные файлы всегда шли подряд (исключением являются файлы без расширений, располагающиеся в архиве абсолютно непредсказуемым образом, — видимо, это какая-то недоработка, которую автор программы не стал устранять за ее несущественностью). Однако в последней версии архиватора появился переключатель, отменяющий такую «принудительную оптимизацию», — так ни странно, без нее архив иногда получается чуть-чуть короче. Интересно было бы поэкспериментировать с другими способами упорядочения (скажем, по размеру файла), но соответствующих переключателей в RAR пока нет. Впрочем, заниматься этим можно только из чистого любопытства — вряд ли имеет смысл рассчитывать на сколько-нибудь серьезные достижения.
В процессе подготовки этой статьи я практически не проводила сравнительных тестов. Поэтому сошлюсь на результаты, опубликованные в статье Александра Дегая «Сожми свои данные» («HARD 'n' SOFT», апрель 1994 г.). Из рассмотренных в ней семнадцати архиваторов RAR показал самую высокую степень сжатия в тестах на упаковку большого текстового файла и (в режиме создания монолитного, архива) сложного дерева каталогов, в других тестах (множество текстовых файлов, гипертекст, DBF-файл, графическая информация в форматах BMP и PCX) был не самым первым, но и далеко, не последним. Скорость упаковки и распаковки в режиме нормального сжатия можно охарактеризовать как среднюю — выше, чем у ARJ или LHA, и ниже, чем у PKZIP, а в режиме максимального сжатия, к пожалуй, как низкую — ниже, чем у ARJ.
Что касается разных режимов самого RAR, то они соответствуют своим названиям: упаковка методом 5 — самая плотная и медленная, методом 1 — самая неплотная и быстрая. Однако при включении в рассмотрение монолитных архивов картина отчасти теряет стройность. Так, монолитный архив, созданный методом 1, очень часто оказывается короче обычного, созданного методом 5, — при том, что сжатие занимает в полтора-два раза меньше времени. Правда, использовать монолитные архивы можно не во всех случаях.
Сверхбыстрое сжатие имеет одну замечательную особенность: оно является самым выгодным по времени при архивировании на «медленное» устройство (дискету). В моем эксперименте создание на дискете архива методом 1 заняло меньше времени, чем копирование файлов без сжатия (метод 0), и в точности столько же времени, сколько переписывание их на дискету DOS-командой COPY. Это свойство делает RAR прекрасным средством резервного копирования, поскольку он, как и ARJ, может создавать многотомные архивы, автоматически устанавливая размер тома в зависимости от количества свободного места на дискете (скоростной режим ARJ работает существенно медленнее).
Функциональные возможности
Конечно, набор команд и переключателей в RAR скромнее, чем в ARJ, с которым по этому показателю не может сравниться ни один архиватор. Однако заметим, что в действительности нам нужно не обилие средств управления, а обилие возможностей; понятно, что лучше было бы обеспечивать функциональную полноту программы с помощью небольшого числа команд, — вот только каким образом?
Один из возможных путей — сделать команды более универсальными и повысить их взаимную совместимость. Мне кажется, что соответствующая тенденция определяет многие особенности интерфейса командной строки RAR.
Начну с незначительного примера. Переключатель -f — обновить(freshen), т. е. заменять файлы только на более новые, - совместим в RAR со всеми командами упаковки и распаковки. Правда, отдельная команда f (обновление архива) тоже присутствует (видимо, так удобнее для пользователей, привыкших к ARJ), но необходимости в ней нет, поскольку это — точный эквивалент сочетания с переключателем -f команды а (добавить файлы в архив).
Замечательно организовано в RAR управление длиной томов многотомного архива — она задается либо в тысячах байтов, либо (начиная с версии 1.53) в килобайтах. В результате точность, с которой можно установить размер тома, оказывается, правда, более низкой, чем в ARJ, но достаточной для любых практических целей, а благодаря наличию универсальной краткой инструкции отпадает нужда в типовых сокращениях (таких, как -v360, -vl440 и т. д. в ARJ).
И, несомненно, самым ярким проявлением стремления к сочетаемости «всего со всем» является поддержка любых комбинаций специальных типов архивов. Признаки «монолитный», «многотомный» и «самораспаковывающийся» в RAR независимы; таким образом, он позволяет создать среди прочего и многотомный самораспаковывающийся архив — тип, которого нет больше ни в одном архиваторе. Такие архивы (не забудем, что их можно делать и монолитными) идеально подходят для создания дистрибутивов, и разработчики уже начали активно этим пользоваться.
Очень удачно решена в RAR проблема комментариев с ESG-последовательностями драйвера ANSI.SYS. Проблема эта, согласно документации ARJ, сводится к следующему. Разноцветные комментарии к архиву и отдельным файлам, выводимые на экран с помощью ANSI.SYS, очень привлекательны, но, к сожалению, потенциально опасны. Какой-нибудь зловредный шутник может в этом случае «подложить» в комментарий так называемую «ANSI-бомбу» — переопределить некоторую клавишу, приписав ей в качестве нового значения, скажем, ECHO Y | DEL \*.*. Поэтому на всякий случай в ARJ по умолчанию устанавливается режим игнорирования ESC-последовательностей ANSI.SYS. Что же касается RAR, то он обрабатывает ESC-последовательности сам, причем команды управления экраном выполняются, а команды переназначения клавиш — нет. В результате управление цветом — в вашем распоряжении, а угроза «взрыва бомбы» полностью устраняется. Вдобавок комментарии останутся цветными, даже если не будет загружен ANSI.SYS.
Впрочем, мои собственные попытки создать архив с разноцветным комментарием закончились плачевно, — скорее всего, из-за слабого знания ANSI.SYS. В некоторый момент я умудрилась создать комментарий, который «подвешивал» мою машину, — но только в версии 1.53; версия 1.54 обрабатывает этот комментарий вполне нормально. Кажется, цветной комментарий должен обязательно храниться в файле. Во всяком случае, я так и не научилась вводить ESC-последовательности в режиме комментирования непосредственно из RAR: нажатие клавиши ESC вызывает прекращение ввода комментария, <Alt>+27 тоже. Видимо, здесь есть над чем поработать в следующих версиях
И, наконец, самая примечательная особенность RAR — его оболочка. Введя команду RAR без параметров, вы запускаете архиватор в полноэкранном режиме, работа в котором организована по тому же принципу, что в Norton Commander: можно перемещаться по каталогам, помечать файлы и производить над ними действия, которые приписаны различным функциональным клавишам. В архив вы входите, как в обычный каталог; при этом меняются назначения клавиш и содержание служебной информации на правой панели.
При выполнении различных операций на экран выдается статистическая информация, включая, что очень удобно, предполагаемую продолжительность процесса. Обычно вывод RAR происходит в полноэкранном режиме независимо от того, как была задана операция — в командной строке или в оболочке. Лишь в версии 1.53 появилась дополнительная возможность задать для режима командной строки стандартный вывод на экран, при котором RAR «выглядит» так же, как другие архиваторы.
Возможности работы с RAR-apхивами у оболочки RAR те же, что у командной строки, но она, кроме того, позволяет входить в ARJ-, LHA- и ZIP-архивы, распаковывать их, преобразовывать в самораспаковывающиеся, просматривать файлы, комментировать... Похоже, что своей популярностью RAR обязан в первую очередь именно наличию оболочки.
Версия RAR 1.54
В вышедшей в июне версии 1.54 основных нововведений два: утилита конвертирования RCVT, которая преобразует архивы других форматов в формат RAR и внешние SFX-модули.
Модуль распаковки, или SFX-модуль, присутствует в любом самораспаковывающемся архиве, но RAR 1.54 позволяет вместо обычного SFX-модуля, используемого по умолчанию, подставить другой, обладающий какими-либо специальными свойствами. В составе версии для DOS имеются готовые SFX-модули, позволяющие сформировать обычный самораспаковывающийся архив для OS/2 и инсталляционный архив для DOS.
Пакет RAR 1.54 сам выполнен в виде инсталляционного архива и убедительно демонстрирует возможности создания дистрибутивов на основе RAR. Сценарий инсталляции записывается в комментарий архива и интерпретируется SFX-модулем. Язык сценариев предусматривает интерфейс на основе меню, проверку наличия на диске свободного места, установку в каталог по выбору пользователя, — похоже, в нем есть все, что только может понадобиться.
Сейчас RAR существует в версиях для DOS, OS/2 и для Windows.