Системы сжатия данных.
Программное Обеспечение:
Утилиты резервного копирования.
Архиваторы.
3. Программы динамического сжатия.
Необходимость архивации файлов:
1) физическая порча магнитных носителей (например, МД)
2) неправильная корректировка (или случайное уничтожение файлов)
3) разрушение файла вирусом.
Для резервного копирования файлов можно использовать команды CОРY или XCOPY, BACKUP и RESTORE операционной системы MS DOS.
Это простое копирование без уменьшения объема исходных файлов.
Специальные программы - архиваторы - позволяют сэкономить место и объединять группы совместно используемых файлов в один архивный файл.
СЖАТИЕ = МОДЕЛИОВАНИЕ + КОДИРОВАНИЕ
Сжатие информации представляет собой процесс обработки символов некоторого сообщения и перевода этих символов в некоторые коды.
При просмотре обрабатываемого сообщения алгоритм сжатия реализует два почти независимых друг от друга процесса:
- поддерживает модель обрабатываемого сообщения;
- на основании модели кодирует очередной фрагмент сообщения;
Термины:
1. Сжатие информации – процесс сокращения количества битов, необходимых для хранения некоторого объема информации;
2. Сжатие без потерь – информация, восстановленная из сжатого состояния, в точности соответствует исходной (до начала сжатия).
3. Сжатие с потерями – информация, восстановленная после сжатия, только частично соответствует исходной (применяется при обработке изображений и звука).
Обычно весь процесс сжатия ошибочно отождествляется только с процессом кодирования, в то время как кодирование представляет собой только часть процесса сжатия, взаимодействующую с моделью данных.
Используя один и тот же метод кодирования, можно совершенно по-разному строить модель сжимаемых данных. При этом результат сжатия будет отличаться для различных методов моделирования.
Wисх. > Wрез.
Первые работы по сжатию информации (~ в конце 40-х гг. 20 века) велись до появления ЭВМ.
Сейчас теория информации развивается параллельно с программированием.
Рассмотрим один из первых алгоритмов эффективного кодирования информации, предложенного Д.А. Хаффманом в 1952 г.
Идея алгоритма: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью появления присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.
Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н дерево).
Термины:
1. Граф -совокупность множества узлов и множества дуг, направленных от одного узла к другому.
2. Дерево -граф, обладающий следующими свойствами:
а) ни в один из узлов не входит более одной дуги (то есть отсутствуют циклы)
б) только в один узел не входит ни одной дуги, он называется корнем дерева;
в) перемещаясь по дугам от корня, можно попасть в любой узел.
3. 
|
4. 
Двоичное дерево - дерево, у которого из всех узлов, кроме листьев, выходит по две дуги.
5. Дерево кодирования Хаффмана (H - дерево) - двоичное дерево, у которого каждый узел имеет вес, и вес родителя равен суммарному весу его детей.
6. Входной алфавит - множество символов, входящих в сообщение.
Алгоритм построения H-дерева:
1. 
Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. 
Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
5. Одной дуге выходящей из родителя, ставится в соответствие бит 1, а другой - бит 0.
6.
 |
Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Архиваторы
Архиватор 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.
Версии архиваторов
PKZIP, LHA
1. Архиваторы
CHARK-С.Чернивецкий
BSA,
RAR
2. PKWARE: PK*3,5a35
PKZIP кодирование
PKUNZIP декодирование
3.. LHA (Harvyasu Yoshi Zaki)
4. ARJ (A rc. R obert J ung)
ARJ<команда> [{ / | -}<ключ> ]
командная строка
[ -| +| < версия >]…]
<имя_архива>[.ARJ]
[ имя_базавого_каталога]
[ < | имя_списка>:<имя_пути>|< произвольное_имя>…]
< команды >: ключ
a:!
b:
j:
e:
ARJ a arc –jm
ARJ a arc
e
-e
/