Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Архивация данных в MS DOS



 Другие рефераты
Арканоид на Паскале Петр Первый Петр Первый Великий Петр Первый, его наружность, привычки, образ жизни и характер

Архивация данных для MS DOS.


История развития теории сжатия информации    1
Архиваторы MS DOS.     6
  PKZIP     8
  RAR 8
  QUARK     9
  GZIP      10
  ARJZ      10
Сравнение вресий архиваторов MS DOS и Windows.     14
Литература. 15



                  История развития теории сжатия информации


      История развития  MS  DOS  весьма  похожа  на  историю  развития  всех
информационных технологий. Более  того,  концепция  MS  DOS  непосредственно
заимствована из операционной системы UNIX. UNIX, в свою очередь,  базируется
на самых первых операционных системах типа OS/360 и  даже  IBM704.  Основные
алгоритмы архивации данных вначале были опробованы на UNIX, а затем  (иногда
процесс развития тех или иных алгоритмов  осуществлялся  параллельно)  в  MS
DOS. В принципе, большинство  используемых  в  настоящее  время  утилит  для
архивации начали свою жизнь начиная с MS DOS 2.0.
      Итак, в сороковых годах ученые, работающие  в  области  информационных
технологий,  ясно  поняли,  что  можно  разработать  такой  способ  хранения
данных, при котором пространство будет расходоваться  более  экономно.  Клод
Шеннон, изучая нюансы  различий  между  семантикой  (semantics)  (что  некая
сущность значит) и синтаксисом (syntax)  (как  некая  сущность  выражается),
разработал большинство базовых понятий  этой  теории.  Понимание  того,  что
одно  и  то  же  значение  (семантика)  может  быть  реализовано  различными
способами (синтаксис),  приводит  к  закономерному  вопросу:  "Какой  способ
выражения чего-либо является наиболее экономичным?"  Поиск  ответа  на  этот
вопрос  привел  Шеннона  к  мысли  об  энтропии,  которая,   проще   говоря,
соотносится с количеством, содержащейся в файле полезной информации.  Методы
сжатия пытаются увеличивать энтропию файла, то есть уменьшать  длину  файла,
сохраняя при этом всю информацию.
      Однако, Шеннон не был первым, кто задумывался о сущности информации  и
определении ее количества. Первый шаг на этом пути сделал в 1928 г.  Хартли.
Основной полученный им результат можно сформулировать примерно так:  если  в
заданном множестве, содержащем N элементов, выделен некоторый элемент  x,  о
котором известно лишь, что он принадлежит этому множеству, то,  чтобы  найти
x, необходимо получить количество информации, равное  log2  N.  Эту  формулу
обычно называют формулой Хартли.

Формула  Хартли  является  частным  случаем  более  общей  формулы  Шеннона,
позволяющей   найти   количество   информации    в    случайном    сообщении
фиксированного алфавита. Пусть X1, ..., Xn -  символы  этого  алфавита,  P1,
..., Pn -  вероятности  их  появления  в  тексте  сообщения,  тогда  формула
Шеннона принимает вид:
      H = P1*log2(1 / P1) + ... + Pn*log2(1 / Pn),
      где H - количество бит  информации  в  одном  символе  сообщения,  или
энтропия символа сообщения. Это число показывает минимальное  среднее  число
бит,  необходимых  для  представления  одного   символа   алфавита   данного
сообщения.
       В некоторых случаях алфавит сообщения может  быть  неизвестен,  тогда
выдвигаются гипотезы об алфавите  сообщения.  Имея  разные  алфавиты,  можно
достичь разных коэффициентов сжатия.  Например,  текстовый  файл,  если  его
рассматривать как последовательность битов, имеет  энтропию  порядка  0.7  -
0.9, если как последовательность  байтов,  -  0.5  -  0.7,  хотя  популярные
программы сжатия  уменьшают  размеры  текстовых  файлов  до  0.3  -  0.4  от
исходного размера.
      Доказательство Шеннона  не  было  конструктивным,  т.е.  не  содержало
способа  построения  этих  оптимальных   кодов,   а   лишь   показывало   их
существование. До появления работы Шеннона,  кодирование  символов  алфавита
при  передаче  сообщения  по   каналам   связи   осуществлялось   одинаковым
количеством бит, получаемым по формуле  Хартли.  С  появлением  этой  работы
начали  появляться  способы,  кодирующие  символы  разным   числом   бит   в
зависимости от вероятности появления их в тексте. Например, часто  в  файлах
некоторые значения байта встречаются чаще других.  Таким  образом,  за  счет
использования  для  каждого  значения  байта  кода  различной  длины   можно
значительно уменьшить общий размер данных. Эта базовая идея лежит  в  основе
алгоритмов  сжатия  Шеннона-Фано  (Shannon-Fano)   и   Хаффмана   (Huffman).
Подобные алгоритмы выбирают более короткие коды для  часто  встречающихся  и
более длинные для  редко  встречающихся  значений  байта.  Обычно  текстовые
файлы (в которых одни значения байтов повторяются гораздо чаще  других)  они
сжимают довольно хорошо.
      Более тридцати лет алгоритм сжатия Хаффмана и его варианты  оставались
наиболее популярными методами. Однако в 1977 два  исследователя  из  Израиля
предложили совершенно другой подход к этой проблеме. Абрахам Лемпел  и  Якоб
Зив выдвинули идею формирования "словаря" общих последовательностей  данных.
При   этом   сжатие   данных   осуществляется   за   счет   замены   записей
соответствующими кодами из словаря. Существуют два  алгоритма,  в  настоящее
время известные как LZ77 и  LZ78.  Они  уже  не  требуют  включения  словаря
данных в  архив,  так  как  если  вы  формируете  ваш  словарь  определенным
способом, программа декодирования может его восстанавливать  непосредственно
из ваших данных. К сожалению, LZ77 и LZ78 тратят много времени  на  создание
эффективного словаря. Лемпел был приглашен фирмой  Sperry  для  оказания  им
помощи  в  разработке  способа  наиболее  эффективной  упаковки  данных   на
компьютерных лентах. В этой же  фирме  Терри  Велч  (Terry  Welch)  расширил
алгоритм LZ78, создав новый вариант, широко известный, как LZW.
      На  работу  Велча  обратила  внимание  группа  программистов  Unix   и
использовала  его  алгоритм  в  их   приложении   LZW,   получившем   вполне
естественное название compress. Они добавили несколько усовершенствований  и
опубликовали  общедоступную  версию   этой   программы   в   телеконференции
Internet, благодаря чему многие пользователи смогли начать с ней работать.

Популярность  алгоритма  LZW  в  значительной  степени  связана  с   успехом
программы   compress.   Исходный   текст   последней    версии    программы,
осуществляющей как сжатие, так и декомпрессию, занимает  всего  1200  строк.
Ядро кода сжатия занимает не  более  сотни  строк,  а  код  декомпрессии  не
намного больше. Программисты считают, что это облегчает чтение  и  понимание
алгоритма, а также позволяет адаптировать его для самых разных целей.

Алгоритмы LZ-стиля (включая LZW, LZ77, LZ78 и многие другие варианты)  очень
популярны везде, где требуется  универсальное  сжатие.  LZW  используется  в
стандарте модема V.42bis, протоколе передачи данных  ZModem,  форматах  GIF,
TIFF, ARC и других прикладных программах. Другие алгоритмы  LZ  используются
в дисковых утилитах сжатия типа DoubleSpace и Stacker, графических  форматах
типа PNG, а также в универсальных утилитах архивирования и  сжатия,  включая
ZIP, GZIP и LHA.

Помимо пользующихся большим вниманием алгоритмов, базирующихся  на  словаре,
существуют и другие подходы. Алгоритм сжатия Хаффмана (Huffman),  основанный
на статистических колебаниях распределения некоторых значений байтов, лег  в
основу  нескольких  очень  эффективных  методов   сжатия,   известных,   как
арифметическое кодирование (arithmetic  encoding),  энтропийное  кодирование
(entropy coding) или Q-кодирование  (Q-coding).  Арифметическое  кодирование
улучшает   сжатие   Хаффмана   двумя   путями.   Первое   усовершенствование
заключается в том, что оно не  требует,  чтобы  выбранные  коды  были  целым
числом  бит.  В  то  время  как  сжатие  Хаффмана  могло  выбирать  двух-  и
четырехбитовые   коды,   программа   арифметического    кодирования    может
использовать код длиной 6,23 бит. (Что такое 0,23 бит  -  чисто  философский
вопрос, если Вас это заинтересовало,  то  в  отдельном  разделе  Вы  найдете
другое объяснение арифметического  кодирования.)  Второе  усовершенствование
(которое может также использоваться в сжатии Хаффмана)  заключается  в  том,
что арифметическое кодирование использует более сложную статистику.  Она  не
просто следит за частотой появления байта в файле, а оценивает  частоту  его
появления в определенном контексте. Например,  при  использовании  исходного
алгоритма сжатия Хаффмана символ "u", встречающийся не  слишком  часто,  мог
бы получать довольно длинный код. Но  в  сложной  программе  арифметического
кодирования  символ  "u",  следующий  за  "q",   будет   закодирован   очень
компактно, так как высока вероятность того, что "u" следует  сразу  за  "q".
Комбинация  этих  двух  усовершенствований  приводит  очень  к  эффективному
сжатию.
       Другие методы сжатия предназначены для данных определенного  типа,  а
потому они плохо  подходят  для  архивирования.  Многие  усовершенствованные
методы, появлявшиеся в последнее время, основывались на  синтезе  этих  трех
методов (например, использование кодов Хаффмана  для  записей  словаря)  или
выполнения   сложной   предварительной   обработки   данных,   увеличивающей
эффективность сжатия одним из этих методов.

Возможно, одним из наиболее  существенных  событий  за  последние  несколько
десятилетий  в  области  алгоритмов  сжатия  стало  появление  патентов   на
программное обеспечение. С 1981 United States Patent  and  Trademark  Office
(USPTO) начал  принимать  заявки  на  патентование  алгоритмов  программного
обеспечения. Многие из  представленных  патентов  были  по  методам  сжатия.
Наиболее известные из них - патенты фирмы Unisys на алгоритм  сжатия  LZW  и
патенты фирмы IBM на арифметическое кодирование. К сожалению,  первоначально
работа по обработке заявок в USPTO была  поставлена  неважно.  В  результате
чего разным людям  предоставлялись  различные  патенты  на  один  и  тот  же
алгори
1234
скачать работу


 Другие рефераты
Документы в торговых операциях
Состояние водных ресурсов России и Сибири
Валерий Яковлевич Брюсов
Разбиения выпуклого многоугольника


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ