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

АРХИВАЦИЯ ДАННЫХ ОБЩИЕ ПОНЯТИЯ Одним из наиболее широко распространенных видов сервисных программ являются программы, предназначенные для архивации, упаковки файлов путем сжатия хранимой в них информации. Сжатие информации — это процесс преобразования информации, хранящейся в файле, к виду, при котором уменьшается избыточность в ее представлении и соответственно требуется меньший объем памяти для хранения. Сжатие информации в файлах производится за счет устранения избыточности различными способами, например, за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов или повторяющейся последовательности символов в виде коэффициента повторения и соответствующих символов. Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования. Основными техническими характеристиками процессов сжатия и результатов их работы являются: * степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков; * скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока; * качество сжатия - величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму. Все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие. Под необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Обратимое сжатие всегда приводит к снижению объема выходного потока информации без изменения его информативности, т.е. - без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом. Применяются различные алгоритмы подобного сжатия информации. Все алгоритмы сжатия данных качественно делятся на: 1) алгоритмы сжатия без потерь, при использовании которых данные на приемной восстанавливаются без малейших изменений, и 2) алгоритмы сжатия с потерями, которые удаляют из потока данных информацию, незначительно влияющую на суть данных, либо вообще невоспринимаемую человеком (такие алгоритмы сейчас разработаны только для аудио- и видео- изображений). Характеристики алгоритмов сжатия и их применимость Коэффициент сжатия — основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых данных, то есть: k  S0 Sс , где k — коэффициент сжатия, So — объём исходных данных, а Sc — объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить: • если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному; • если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу. Ситуация с k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2n, число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство: k  S0 S0  1 Делается это следующим образом: если объём сжатых данных меньше объёма исходных, возвращаем сжатые данные, добавив к ним «1», иначе возвращаем исходные данные, добавив к ним «0»). Коэффициент сжатия может быть, как постоянным (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM, усечённое блочное кодирование), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям: • средний (обычно по некоторому тестовому набору данных); • максимальный (случай наилучшего сжатия); • минимальный (случай наихудшего сжатия); или каким-либо другим. Коэффициент сжатия с потерями при этом сильно зависит от допустимой погрешности сжатия или качества, которое обычно выступает как параметр алгоритма. В общем случае постоянный коэффициент сжатия способны обеспечить только методы сжатия данных с потерями. Допустимость потерь Основным критерием различия между алгоритмами сжатия является описанное выше наличие или отсутствие потерь. В общем случае алгоритмы сжатия без потерь универсальны в том смысле, что их применение безусловно возможно для данных любого типа, в то время как возможность применения сжатия с потерями должна быть обоснована. Для некоторых типов данных искажения не допустимы в принципе. В их числе • символические данные, изменение которых неминуемо приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т. п.; • жизненно важные данные, изменения в которых могут привести к критическим ошибкам: например, получаемые с медицинской измерительной аппаратуры или контрольных приборов летательных, космических аппаратов и т. п.; • многократно подвергаемые сжатию и восстановлению промежуточные данные при многоэтапной обработке графических, звуковых и видеоданных. Системные требования алгоритмов Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы: • оперативной памяти (под промежуточные данные); • постоянной памяти (под код программы и константы); • процессорного времени. В целом, эти требования зависят от сложности и «интеллектуальности» алгоритма. Общая тенденция такова: чем эффективнее и универсальнее алгоритм, тем большие требования к вычислительным ресурсам он предъявляет. Тем не менее, в специфических случаях простые и компактные алгоритмы могут работать не хуже сложных и универсальных. Системные требования определяют их потребительские качества: чем менее требователен алгоритм, тем на более простой, а, следовательно, компактной, надёжной и дешёвой системе он может быть реализован. Так как алгоритмы сжатия и восстановления работают в паре, имеет значение соотношение системных требований к ним. Нередко можно, усложнив один алгоритм, значительно упростить другой. Таким образом, возможны три варианта: Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления. Это наиболее распространённое соотношение, характерное для случаев, когда однократно сжатые данные будут использоваться многократно. В качестве примера можно привести цифровые аудио- и видеопроигрыватели. Алгоритмы сжатия и восстановления требуют приблизительно равных вычислительных ресурсов. Наиболее приемлемый вариант для линий связи, когда сжатие и восстановление происходит однократно на двух её концах (например, в цифровой телефонии). Алгоритм сжатия существенно менее требователен, чем алгоритм восстановления. Такая ситуация характерна для случаев, когда процедура сжатия реализуется простым, часто портативным, устройством, для которого объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков. Это могут быть также данные, распаковка которых требуется в очень малом проценте случаев, например, запись камер видеонаблюдения. Техники сжатия данных 1. Сжатие способом кодирования серий (RLE) Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Например: AAABBCCCCDEEEEEE - исходная последовательность 3A2B4C1D6E - сжатая последовательность Первый байт указывает сколько раз нужно повторить следующий байт. Если первый байт равен 00, то затем идет счетчик, показывающий, сколько за ним следует неповторяющихся данных. Описанный метод является простым и очень эффективным способом сжатия файлов. Однако он не обеспечивает большой экономии объема, если обрабатываемый текст содержит небольшое количество последовательностей повторяющихся символов. Недостатком метода RLE является достаточно низкая степень сжатия. 2. Алгоритм Шеннона-Фано Одна из самых ранних техник (1949 год). Создаёт двоичное дерево для представления вероятностей появления каждого из символов. Затем они сортируются так, чтобы самые часто встречающиеся находились наверху дерева, и наоборот. Теоретический материал и примеры построения кода методом ШеннонаФано смотрите в Учебном пособии Алабина Б.К. Теория информации. 3. Алгоритм Хаффмана Это так называемый оптимальный префиксный код или кодирование символами переменной длины. Код переменной длины позволяет записывать наиболее часто встречающиеся символы и фразы всего лишь несколькими битами, в то время как редкие символы и фразы будут записаны более длинными битовыми строками. Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Код Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого символа. А из этого следует, что код Хаффмана однозначно восстановим получателем, даже если не сообщается длина кода каждого переданного символа. Получателю пересылают только дерево Хаффмана в компактном виде, а затем входная последовательность кодов символов декодируется им самостоятельно без какой-либо дополнительной информации. Теоретический материал и примеры построения кода методом Хаффмена смотрите в Учебном пособии Алабина Б.К. Теория информации. ПРИМЕР (Алгоритм Хаффмена) ГДЕ_ЩИ,_ТАМ_И_НАС_ИЩИ Знаки алфавита сообщения выпишем в таблицу в порядке убывания вероятностей. Буква И Щ А Г Д Число вхождений в текст (в порядке убывания) 5 4 2 2 1 1 Вероятность появления в тексте 0,238 0,1912 0,095 0,095 0,0476 0,0476 Е , Т М Н С 1 1 1 1 1 1 0,0476 0,0476 0,0476 0,0476 0,0476 0,0476 Строим кодовое дерево. 1 1 1 1 1 1 1 1 1 1 1 Для составления кодовой комбинации, соответствующей каждому знаку сообщения, необходимо проследить путь перехода знака от корня дерева до конечной вершины соответствующего знака сообщения: Знак Кодовая комбинация 01 И 11 Щ 0011 А 0010 Г 1011 Д 1010 Е 1001 , 1000 Т 00011 М 00010 Н 00001 С 00000 Закодированное сообщение будет следующим: 101110101001001111100000011001000010110000100100000011001111 4. Арифметическое кодирование Совершенно иное решение предлагает т.н. арифметическое кодирование. Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия. Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке. Пример. Пусть алфавит состоит из двух символов: a и b с вероятностями соответственно 0,75 и 0,25. Рассмотрим наш интервал вероятностей [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0; 0,75) и [0,75;1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из интервала [0, 1) а пустому слову соответствует весь интервал [0, 1). После получения каждого следующего символа интервал уменьшается с выбором той его части, которая соответствует новому символу. Кодом цепочки является интервал, выделенный после обработки всех ее символов, точнее, двоичная запись любой точки из этого интервала, а длина полученного интервала пропорциональна вероятности появления кодируемой цепочки. Применим данный алгоритм для цепочки "aaba": Шаг Цепочка Интервал 0 нет [0;1) 1 a [0;0,75) 2 aa 0.75*0.75=0.5625 [0;0,5625) 3 aab 0.5625*0.25=0,140625-0,5625=-0,421875 [0,421875;0,5625) 4 aaba 0,140625*0.75=0,10546875 Границы интервала вычисляются так берется расстояние внутри интервала (0,5625-0,421875=0,140625), делится на частоты [0; 0,10546875) и [0,10546875; 1) и находятся новые границы [0,421875; 0,52734375) и [0,52734375; 0,5625). В качестве кода можно взять любое число из интервала, полученного на шаге 4, например, 0,43. Алгоритм декодирования работает аналогично кодирующему. На входе 0,43 и идет разбиение интервала. Продолжая этот процесс, мы однозначно декодируем все четыре символа. Для того, чтобы декодирующий алгоритм мог определить конец цепочки, мы можем либо передавать ее длину отдельно, либо добавить к алфавиту дополнительный уникальный символ - "конец цепочки". Основная идея заключается в том, чтобы присваивать коды не отдельным символам, а их последовательностям. Вначале рассмотрим идею, лежащую в основе алгоритма, затем рассмотрим небольшой практический пример. Как и во всех энтропийных алгоритмах мы обладаем информацией о частоте использования каждого символа алфавита. Эта информация является исходной для рассматриваемого метода. Теперь введём понятие рабочего отрезка. Рабочим называется полуинтервал [a;b) с расположенными на нём точками. Причём точки расположены т. о., что длины образованных ими отрезков равны частоте использования символов. При инициализации алгоритма a=0 b=1. Один шаг кодирования заключается в простой операции: берётся кодируемый символ, для него ищется соответствующий участок на рабочем отрезке. Найденный участок становится новым рабочим отрезком (т. е. его тоже необходимо разбить с помощью точек). Эта операция выполняется для некоторого количества символов исходного потока. Результатом кодирования цепочки символов является любое число (а также длина его битовой записи) с итогового рабочего отрезка (чаще всего берётся левая граница отрезка). Звучит это довольно сложно. Давайте попробуем разобраться с помощью небольшого примера. Закодируем сообщение «ЭТОТ_МЕТОД_ЛУЧШЕ_ХАФФМАНА» с помощью описанного метода. Составив таблицу частоты появления символов, мы можем приступать к кодированию. На первом этапе составим рабочий отрезок. Выглядеть он будет так: Берём первый символ из потока, это символ «Э». Соответствующий ему отрезок – отрезок [0,96;1). Если бы мы хотели закодировать один символ, то результатом кодирования было бы любое число из этого отрезка. Но мы не остановимся на одном символе, а добавим ещё один. Символ «Т». Для этого составим новый рабочий отрезок с a=0,96 и b=1. Разбиваем этот отрезок точками точно так же как мы сделали это для исходного отрезка и считываем новый символ «Т». Символу «Т» соответствует диапазон [0,24;0,36), но наш рабочий отрезок уже сократился до отрезка [0,96;1). Т. е. границы нам необходимо пересчитать. Сделать это можно с помощью двух следующих формул: High=Lowold+(Highold-Lowold)*RangeHigh(x), Low=Lowold+(Highold-Lowold)*RangeLow(x), где Lowold – нижняя граница интервала, Highold – верхняя граница интервала RangeHigh и RangeLow – верхняя и нижняя границы кодируемого символа. Пользуясь этими формулами, закодируем первое слово сообщения целиком: Шаг 1 2 3 4 Цепочка Нет э эт это этот Интервал [0;1) [0,96000000;1) [0,96960000;0,97440000) [0,97209600;0,97248000) [0,97218816;0,97223424) Результатом кодирования будет любое число из полуинтервала [0,97218816; 0,97223424). Предположим, что результатом кодирования была выбрана левая граница полуинтервала, т. е. число 0,97218816. Рассмотрим процесс декодирования. Код лежит в полуинтервале [0,96;1). Т. е. первый символ сообщения «Э». Чтобы декодировать второй символ (который кодировался в полуинтервале [0,96;1)) полуинтервал нужно нормализовать, т. е. привести к виду [0;1). Это делается с помощью следующей формулы: code=(code-RangeLow(x))/(RangeHigh(x)-RangeLow(x)), где code – текущее значение кода. Применяя эту формулу, получаем новое значение code=(0,972188160,96)/(1-0,96)= 0,304704. Т. е. второй символ последовательности «Т». Снова применим формулу: code=(0,304704-0,24)/(0,36-0,24)= 0,5392. Третий символ последовательности – «О». Продолжая декодирование, по описанной схеме мы можем полностью восстановить исходный текст. ПРИМЕР (Арифметическое кодирование) ГДЕ_ЩИ,_ТАМ_И_НАС_ИЩИ Составим вероятности. Буква И Щ А таблицу частоты Число вхождений в текст (в порядке убывания) 5 4 2 2 появления символов, Вероятность появления в тексте 0,238 0,1912 0,095 0,095 высчитываем Г Д Е , Т М Н С 1 1 1 1 1 1 1 1 0,0476 0,0476 0,0476 0,0476 0,0476 0,0476 0,0476 0,0476 Можем приступать к кодированию. На первом этапе составим рабочий отрезок. Выглядеть он будет так: 0,238 И 0,4292 Щ 0,5242 А 0,6192 Г 0,6668 Д 0,7144 Е 0,762 , 0,8096 Т 0,8572 М 0,9048 Н 0,9524 С 1 Берём первый символ из потока, это символ «Г». Соответствующий ему отрезок – отрезок [0,6192;0,6668). Если бы мы хотели закодировать один символ, то результатом кодирования было бы любое число из этого отрезка. Но мы не остановимся на одном символе, а добавим ещё один. Символ «Д». Для этого составим новый рабочий отрезок с a=0,6192 и b=0,6668. Разбиваем этот отрезок точками точно так же, как мы сделали это для исходного отрезка и считываем новый символ «Д». Символу «Д» соответствует диапазон [0,6668;0,7144), но наш рабочий отрезок уже сократился до отрезка [0,6192;0,6668). Т. е. границы нам необходимо пересчитать. Сделать это можно с помощью двух следующих формул: High=Lowold+(HigholdLowold)*RangeHigh(x), Low=Lowold+(Highold-Lowold)*RangeLow(x), где Lowold – нижняя граница интервала, Highold – верхняя граница интервала RangeHigh и RangeLow – верхняя и нижняя границы кодируемого символа. Пользуясь этими формулами, закодируем первые девять символов нашего выражения: ГДЕ_ЩИ,_Т Шаг 1 2 3 4 Цепочка Нет Г ГД ГДЕ ГДЕ_ Интервал [0;1) [0,6192;0,6668) [0,6509;0,6532) [0,6525;0,6527) [0,6525;0,6525476) 5 6 ГДЕ_Щ ГДЕ_ЩИ [0,65252043;0,65252495) [0,65252151;0,65252237) 7 ГДЕ_ЩИ, [0,65252217;0,65252221) 8 ГДЕ_ЩИ,_ [00,65252217;0,65252217952) 9 ГДЕ_ЩИ,_Т [0,652521777;0,65252217816) Результатом кодирования будет любое число из полуинтервала [0,652521777;0,65252217816). 5. Преобразование Барроуза-Уилера (BWT) Алгоритм, придуманный в 1994 году, обратимо трансформирует блок данных так, чтобы максимизировать повторения одинаковых символов. Сам он не сжимает данные, но подготавливает их для более эффективного сжатия через RLE или другой алгоритм сжатия. Алгоритм: 1. Создаём массив строк. 2. Создаём все возможные преобразования входящей строки данных, каждое из которых сохраняем в массиве. 3. Сортируем массив. 4. Возвращаем последний столбец. Алгоритм лучше всего работает с большими данными со множеством повторяющихся символов. Пример работы на подходящем массиве данных (& обозначает конец файла). Благодаря чередованию одинаковых символов, вывод алгоритма оптимален для сжатия RLE, которое даёт «3H&3A». Но на реальных данных, к сожалению, настолько оптимальных результатов обычно не получается. 6. Алгоритм Лемпела-Зива-Велча (Lempel-Ziv-Welch - LZW) LZW - История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом (J. Ziv) и А. Лемпелем (A. Lempel) статьи в журнале "Информационные теории" под названием "IEEE Trans". В последствии этот алгоритм был доработан Терри А. Велчем (Terry A. Welch) и в окончательном варианте отражен в статье "IEEE Computer" в июне 1984. В этой статье описывались подробности алгоритма и некоторые общие проблемы, с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch). Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку "Объект TSortedCollection порожден от TCollection.". Анализируя эту строку мы можем видеть, что слово "Collection" повторяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничится длинной кодируемой строки в 256 символов, то учитывая байт "флаг" получим, что строка из 80 бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе сжатия файла. Если существуют повторяющиеся строки в файле, то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана (Huffman ), которому требуется два прохода. Данный алгоритм отличают высокая скорость работы, как при упаковке, так и при распаковке, достаточно скромные требования к памяти и простая аппаратная реализация. Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Пример. Предположим, что у нас имеется словарь, хранящий строки текста и содержащий порядка от 2-х до 8-ми тысяч пронумерованных гнезд. Запишем в первые 256 гнезд строки, состоящие из одного символа, номер которого равен номеру гнезда. Алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые гнезда в конец словаря. Прочитаем несколько символов в строку s и найдем в словаре строку t - самый длинный префикс s. Пусть он найден в гнезде с номером n. Выведем число n в выходной поток, переместим указатель входного потока на length(t) символов вперед и добавим в словарь новое гнездо, содержащее строку t+c, где с - очередной символ на входе (сразу после t). Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. При практической реализации этого алгоритма следует учесть, что любое гнездо словаря, кроме самых первых, содержащих одно-символьные цепочки, хранит копию некоторого другого гнезда, к которой в конец приписан один символ. Вследствие этого можно обойтись простой списочной структурой с одной связью. Пример: ABCABCABCABCABCABC - 1 2 3 4 6 5 7 7 7 1A 2B 3C 4 AB 5 BC 6 CA 7 ABC 8 CAB 9 BCA 7. Алгоритмы, применяющие метод «скользящего окна» Всё началось с алгоритма LZ77 (1977 год), который представил новую концепцию «скользящего окна», позволившую значительно улучшить сжатие данных. LZ77 использует словарь, содержащий тройки данных – смещение, длина серии и символ расхождения. Смещение – как далеко от начала файла находится фраза. Длина серии – сколько символов, считая от смещения, принадлежат фразе. Символ расхождения показывает, что найдена новая фраза, похожая на ту, что обозначена смещением и длиной, за исключением этого символа. Словарь меняется по мере обработки файла при помощи скользящего окна. К примеру, размер окна может быть 64Мб, тогда словарь будет содержать данные из последних 64 мегабайт входных данных. К примеру, для входных данных «abbadabba» результат будет «abb(0,1,'d')(0,3,'a')» В данном случае результат получился длиннее входа, но обычно он конечно получается короче. ПРИМЕР (Арифметическое кодирование) ГДЕ_ЩИ,_ТАМ_И_НАС_ИЩИ Заполним таблицу. Позиция 1 2 Символ Г Д Е Выход Г Д Е 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Щ И , Т А М И Н А С И Щ И Щ И , (3,1,’Т’) А М (3,1,’И’) (3,1,’Н) (9,1,’С’) (11,2,’Щ’) И Закодированное выражение: ГДЕ_ ЩИ,(3,1,’Т’)АМ(3,1,’И’)(3,1,’Н)(9,1,’С’)(11,2,’Щ’)И В данном случае результат получился длиннее входа. LZR Модификация алгоритма LZ77, предложенная Майклом Роуде в 1981 году. В отличие от LZ77 работает за линейное время, однако требует большего объёма памяти. Обычно проигрывает LZ78 в сжатии. DEFLATE Придуман Филом Кацем в 1993 году, и используется в большинстве современных архиваторов. Является комбинацией LZ77 или LZSS с кодированием Хаффмана. DEFLATE64 Патентованная вариация DEFLATE с увеличением словаря до 64 Кб. Сжимает лучше и быстрее, но не используется повсеместно, т.к. не является открытым. LZSS Алгоритм Лемпеля-Зива-Сторера-Цимански был представлен в 1982 году. Улучшенная версия LZ77, которая просчитывает, не увеличит ли размер результата замена исходных данных кодированными. До сих пор используется в популярных архиваторах, например RAR. Иногда – для сжатия данных при передаче по сети. LZH Был разработан в 1987 году, расшифровывается как «Лемпель-ЗивХаффман». Вариация LZSS, использует кодирование Хаффмана для сжатия указателей. Сжимает чуть лучше, но ощутимо медленнее. LZB Разработан в 1987 году Тимоти Беллом, как вариант LZSS. Как и LZH, LZB уменьшает результирующий размер файлов, эффективно кодируя указатели. Достигается это путём постепенного увеличения размера указателей при увеличении размера скользящего окна. Сжатие получается выше, чем у LZSS и LZH, но скорость значительно меньше. ROLZ Расшифровывается как «Лемпель-Зив с уменьшенным смещением», улучшает алгоритм LZ77, уменьшая смещение, чтобы уменьшить количество данных, необходимого для кодирования пары смещение-длина. Впервые был представлен в 1991 году в алгоритме LZRW4 от Росса Вильямса. Другие вариации — BALZ, QUAD, и RZM. Хорошо оптимизированный ROLZ достигает почти таких же степеней сжатия, как и LZMA – но популярности он не снискал. LZP «Лемпель-Зив с предсказанием». Вариация ROLZ со смещением = 1. Есть несколько вариантов, одни направлены на скорость сжатия, другие – на степень. В алгоритме LZW4 используется арифметическое кодирование для наилучшего сжатия. LZRW1 Алгоритм от Рона Вильямса 1991 года, где он впервые ввёл концепцию уменьшения смещения. Достигает высоких степеней сжатия при приличной скорости. Потом Вильямс сделал вариации LZRW1-A, 2, 3, 3-A, и 4 LZJB Вариант от Джеффа Бонвика (отсюда “JB”) от 1998 года, для использования в файловой системе Solaris Z File System (ZFS). Вариант алгоритма LZRW1, переработанный для высоких скоростей, как этого требует использование в файловой системе и скорость дисковых операций. LZS Lempel-Ziv-Stac, разработан в Stac Electronics в 1994 для использования в программах сжатия дисков. Модификация LZ77, различающая символы и пары длина-смещение, в дополнение к удалению следующего встреченного символа. Очень похож на LZSS. LZX Был разработан в 1995 году Дж. Форбсом и Т.Потаненом для Амиги. Форбс продал алгоритм компании Microsoft в 1996, и устроился туда работать над ним, в результате чего улучшенная его версия стала использоваться в файлах CAB, CHM, WIM и Xbox Live Avatars. LZO Разработан в 1996 Маркусом Оберхьюмером с прицелом на скорость сжатия и распаковки. Позволяет настраивать уровни компрессии, потребляет очень мало памяти. Похож на LZSS. LZMA “Lempel-Ziv Markov chain Algorithm”, появился в 1998 году в архиваторе 7-zip, который демонстрировал сжатие лучше практически всех архиваторов. Алгоритм использует цепочку методов сжатия для достижения наилучшего результата. Вначале слегка изменённый LZ77, работающий на уровне битов (в отличие от обычного метода работы с байтами), парсит данные. Его вывод подвергается арифметическому кодированию. Затем могут быть применены другие алгоритмы. В результате получается наилучшая компрессия среди всех архиваторов. LZMA2 Следующая версия LZMA, от 2009 года, использует многопоточность и чуть эффективнее хранит несжимаемые данные. 8. Алгоритмы с использованием словаря LZ78 Алгоритм 1978 года, авторы – Лемпель и Зив. Вместо использования скользящего окна для создания словаря, словарь составляется при анализе и разборе данных из файла. Объём словаря обычно измеряется в нескольких мегабайтах. Отличия в вариантах этого алгоритма строятся на том, что делать, когда словарь заполнен. При анализе и разборе файла алгоритм добавляет каждый новый символ или их сочетание в словарь. Для каждого символа на входе создаётся словарная форма (индекс + неизвестный символ) на выходе. Если первый символ строки уже есть в словаре, ищем в словаре подстроки данной строки, и самая длинная используется для построения индекса. Данные, на которые указывает индекс, добавляются к последнему символу неизвестной подстроки. Если текущий символ не найден, индекс устанавливается в 0, показывая, что это вхождение одиночного символа в словарь. Записи формируют связанный список. Входные данные «abbadabbaabaad» на выходе дадут "(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)" An input such as «abbadabbaabaad» would generate the output "(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)". You can see how this was derived in the following example: LZW Лемпель-Зив-Велч, 1984 год. Самый популярный вариант LZ78, несмотря на запатентованность. Алгоритм избавляется от лишних символов на выходе и данные состоят только из указателей. Также он сохраняет все символы словаря перед сжатием и использует другие трюки, позволяющие улучшать сжатие – к примеру, кодирование последнего символа предыдущей фразы в качестве первого символа следующей. Используется в GIF, ранних версиях ZIP и других специальных приложениях. Очень быстр, но проигрывает в сжатии более новым алгоритмам. LZC Компрессия Лемпеля-Зива. Модификация LZW, использующаяся в утилитах UNIX. Следит за степенью сжатия, и как только она превышает заданный предел – словарь переделывается заново. LZT Лемпель-Зив-Тищер. Когда словарь заполняется, удаляет фразы, использовавшиеся реже всех, и заменяет их новыми. Не получил популярности. LZMW Виктор Миллер и Марк Вегман, 1984 год. Действует, как LZT, но соединяет в словаре не похожие данные, а две последние фразы. В результате словарь растёт быстрее, и приходится чаще избавляться от редко используемых фраз. Также непопулярен. LZAP Джеймс Сторер, 1988 год. Модификация LZMW. “AP” означает «все префиксы» — вместо того, чтобы сохранять при каждой итерации одну фразу, в словаре сохраняется каждое изменение. К примеру, если последняя фраза была “last”, а текущая – «next”, тогда в словаре сохраняются „lastn“, „lastne“, „lastnex“, „lastnext“. LZWL Вариант LZW от 2006 года, работающий с сочетаниями символов, а не с отдельными символами. Успешно работает с наборами данных, в которых есть часто повторяющиеся сочетания символов, например, XML. Обычно используется с препроцессором, разбивающим данные на сочетания. LZJ 1985 год, Матти Якобсон. Один из немногих вариантов LZ78, отличающихся от LZW. Сохраняет каждую уникальную строку в уже обработанных входных данных, и всем им назначает уникальные коды. При заполнении словаря из него удаляются единичные вхождения. 9. Алгоритмы, не использующие словарь PPM Предсказание по частичному совпадению – использует уже обработанные данные, чтобы предсказать, какой символ будет в последовательности следующим, таким образом уменьшая энтропию выходных данных. Обычно комбинируется с арифметическим кодировщиком или адаптивным кодированием Хаффмана. Вариация PPMd используется в RAR и 7-zip bzip2 Реализация BWT с открытым исходным кодом. При простоте реализации достигает хорошего компромисса между скоростью и степенью сжатия, в связи с чем популярен в UNIX. Сначала данные обрабатываются при помощи RLE, затем BWT, потом данные особым образом сортируются, чтобы получить длинные последовательности одинаковых символов, после чего к ним снова применяется RLE. И, наконец, кодировщик Хаффмана завершает процесс. PAQ Мэтт Махоуни, 2002 год. Улучшение PPM(d). Улучшает их при помощи интересной техники под названием „перемешивание контекста“ (context mixing). В этой технике несколько предсказательных алгоритмов комбинируются, чтобы улучшить предсказание следующего символа. Сейчас это один из самых многообещающих алгоритмов. С его первой реализации было создано уже два десятка вариантов, некоторые из которых ставят рекорды сжатия. Минус – маленькая скорость из-за необходимости использования нескольких моделей. Вариант под названием PAQ80 поддерживает 64 бита и показывает серьёзное улучшение в скорости работы (используется, в частности, в программе PeaZip для Windows). 10. Двухступенчатое кодирование. Алгоритм Лемпела-Зива Гораздо большей степени сжатия можно добиться при выделении из входного потока повторяющихся цепочек - блоков, и кодирования ссылок на эти цепочки с построением хеш таблиц от первого до n-го уровня. Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву и обычно называется LZ-compression. Суть его состоит в следующем: упаковщик постоянно хранит некоторое количество последних обработанных символов в буфере. По мере обработки входного потока вновь поступившие символы попадают в конец буфера, сдвигая предшествующие символы и вытесняя самые старые. Размеры этого буфера, называемого также скользящим словарем (sliding dictionary), варьируются в разных реализациях кодирующих систем. Экспериментальным путем установлено, что программа LHarc использует 4-килобайтный буфер, LHA и PKZIP - 8-ми, а ARJ - 16килобайтный. Затем, после построения хеш таблиц алгоритм выделяет (путем поиска в словаре) самую длинную начальную подстроку входного потока, совпадающую с одной из подстрок в словаре, и выдает на выход пару (length, distance), где length - длина найденной в словаре подстроки, а distance расстояние от нее до входной подстроки (то есть фактически индекс подстроки в буфере, вычтенный из его размера). В случае, если такая подстрока не найдена, в выходной поток просто копируется очередной символ входного потока. В первоначальной версии алгоритма предлагалось использовать простейший поиск по всему словарю. Однако, в дальнейшем, было предложено использовать двоичное дерево и хеширование для быстрого поиска в словаре, что позволило на порядок поднять скорость работы алгоритма. Таким образом, алгоритм Лемпела-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таблице (length + distance). Очевидно, что эти потоки являются потоками символов с двумя новыми алфавитами, и к ним можно применить один из упоминавшихся выше методов (RLE, кодирование Хаффмана или арифметическое кодирование). Так мы приходим к схеме двухступенчатого кодирования - наиболее эффективной из практически используемых в настоящее время. При реализации этого метода необходимо добиться согласованного вывода обоих потоков в один файл. Эта проблема обычно решается путем поочередной записи кодов символов из обоих потоков. Пример: Первая ступень abcabcabcabcabc - 1 а 1 b 1 c 3 3 6 3 9 3 12 3 Вторая ступень - исключение большой группы повторяющихся последовательностей 1 а 1 b 1 c 12 3 и сжатие RLE, кодирование Хаффмана, арифметическое кодирование. ОБЩИЕ СВЕДЕНИЯ ОБ АРХИВАЦИИ ФАЙЛОВ Понятие процесса архивации файлов Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в так называемый архивный файл или архив. Архивный файл — это специальным образом организованный файл, содержащий в себе один или несколько файлов в сжатом или несжатом виде и служебную информацию об именах файлов, дате и времени их создания или модификации, размерах и т.п. Целью упаковки файлов обычно являются обеспечение более компактного размещения информации на диске, сокращение времени и соответственно стоимости передачи информации по каналам связи в компьютерных сетях. Кроме того, упаковка в один архивный файл группы файлов существенно упрощает их перенос с одного компьютера на другой, сокращает время копирования файлов на диски, позволяет защитить информацию от несанкционированного доступа, способствует защите от заражения компьютерными вирусами. Степень сжатия зависит от используемой программы, метода сжатия и типа исходного файла. Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 5 - 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей — 60 - 90%. Почти не сжимаются архивные файлы. Программы для архивации отличаются используемыми методами сжатия, что соответственно влияет на степень сжатия. Архивация (упаковка) — помещение (загрузка) исходных файлов в архивный файл в сжатом или несжатом виде. Разархивация (распаковка) — процесс восстановления файлов из архива точно в таком виде, какой они имели до загрузки в архив. При распаковке файлы извлекаются из архива и помещаются на диск или в оперативную память. Программы, осуществляющие упаковку и распаковку файлов, называются программами-архиваторами. Большие по объему архивные файлы могут быть размещены на нескольких дисках (томах). Такие архивы называются многотомными. Том — это составная часть многотомного архива. Создавая архив из нескольких частей, можно записать его части на несколько дискет. Основные виды программ-архиваторов В настоящее время применяется несколько десятков программархиваторов, которые отличаются перечнем функций и параметрами работы, однако лучшие из них имеют примерно одинаковые характеристики. Из числа наиболее популярных программ можно выделить: ARJ, РКРАК, LHA, ICE, HYPER, ZIP, РАК, ZOO, EXPAND, разработанные за рубежом, а также AIN и RAR, разработанные в России. Обычно упаковка и распаковка файлов выполняются одной и той же программой, но в некоторых случаях это осуществляется разными программами, например, программа PKZIP производит упаковку файлов, a PKUNZIP — распаковку файлов. Перечень программ сжатия с кратким указанием алгоритмов их работы. PKZIP 1.10: Метод Shrinked -- модифицированный алгоритм LZW с частичной очисткой словаря и переменной длиной кода. Метод Imploded -- модифицированный алгоритм Лемпела-Зива и статическое кодирование Хаффмана. LHArc: Алгоритм Лемпела-Зива и динамическое кодирование Хаффмана. LHA: Алгоритм Лемпела-Зива и статическое кодирование Хаффмана. ARJ: Алгоритм Лемпела-Зива и оригинальный метод кодирования Программы-архиваторы позволяют создавать и такие архивы, для извлечения из которых содержащихся в них файлов не требуются какие-либо программы, так как сами архивные файлы могут содержать программу распаковки. Такие архивные файлы называются самораспаковывающимися. Самораспаковывающийся архивный файл — это загрузочный, исполняемый модуль, который способен к самостоятельной разархивации находящихся в нем файлов без использования программы-архиватора. Самораспаковывающийся архив получил название SFX-архив (SelFeXtracting). Архивы такого типа в обычно создаются в форме .ЕХЕ-файла. К основным функциям архиваторов относятся: - архивация указанных файлов или всего текущего каталога; - извлечение отдельных или всех файлов из архива в текущий каталог (или в указанный каталог); - просмотр содержимого архивного файла (состав, свойства упакованных файлов, их каталожная структура и т.д.); - проверка целостности архивов; - восстановление поврежденных архивов; - ведение многотомных архивов; - вывод файлов из архива на экран или на печать.