Методы сжатия данных имеют достаточно длинную историю развития, которая началась задолго до появления первого компьютера. В этой статье будет произведена попытка дать краткий обзор основных теорий, концепций идей и их реализаций, не претендующий, однако, на абсолютную полноту. Более подробные сведения можно найти, например, в Кричевский Р.Е. , Рябко Б.Я. , Witten I.H. , Rissanen J. , Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. и др.
Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации. Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт. Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования. Основными техническими характеристиками процессов сжатия и результатов их работы являются:
Степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;
Скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
Качество сжатия - величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму.
Существует несколько различных подходов к проблеме сжатия информации. Одни имеют весьма сложную теоретическую математическую базу, другие основаны на свойствах информационного потока и алгоритмически достаточно просты. Любой способ подход и алгоритм, реализующий сжатие или компрессию данных, предназначен для снижения объема выходного потока информации в битах при помощи ее обратимого или необратимого преобразования. Поэтому, прежде всего, по критерию, связанному с характером или форматом данных, все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие.
Под необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (т.е. сжатой и несжатой информации, в соответствии с некоторым определенным форматом данных), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия, например, данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.
Обратимое сжатие всегда приводит к снижению объема выходного потока информации без изменения его информативности, т.е. - без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой, и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом.
В обратимых алгоритмах кодирование как процесс можно рассматривать со статистической точки зрения, что еще более полезно, не только для построения алгоритмов сжатия, но и для оценки их эффективности. Для всех обратимых алгоритмов существует понятие стоимости кодирования. Под стоимостью кодирования понимается средняя длина кодового слова в битах. Избыточность кодирования равна разности между стоимостью и энтропией кодирования, а хороший алгоритм сжатия всегда должен минимизировать избыточность (напомним, что под энтропией информации понимают меру ее неупорядоченности.). Фундаментальная теорема Шеннона о кодировании информации говорит о том, что "стоимость кодирования всегда не меньше энтропии источника, хотя может быть сколь угодно близка к ней". Поэтому, для любого алгоритма, всегда имеется некоторый предел степени сжатия, определяемый энтропией входного потока.
Перейдем теперь непосредственно к алгоритмическим особенностям обратимых алгоритмов и рассмотрим важнейшие теоретические подходы к сжатию данных, связанные с реализацией кодирующих систем и способы сжатия информации.
Сжатие способом кодирования серий
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.
Сжатие без применения метода RLE
Процесс сжатия данных без применения метода RLE можно разбить на два этапа: моделирование (modelling) и, собственно, кодирование (encoding). Эти процессы и их реализующие алгоритмы достаточно независимы и разноплановы.
Процесс кодирования и его методы
Под кодированием обычно понимают обработку потока символов (в нашем случае байтов или полубайтов) в некотором алфавите, причем частоты появления символов в потоке различны. Целью кодирования является преобразование этого потока в поток бит минимальной длины, что достигается уменьшением энтропии входного потока путем учета частот символов. Длина кода, представляющего символы из алфавита потока должна быть пропорциональна объему информации входного потока, а длина символов потока в битах может быть не кратна 8 и даже переменной. Если распределение вероятностей частот появления символов из алфавита входного потока известно, то можно построить модель оптимального кодирования. Однако, ввиду существования огромного числа различных форматов файлов задача значительно усложняется т.к. распределение частот символов данных заранее неизвестно. В таком случае, в общем виде, используются два подхода.
Первый заключается в просмотре входного потока и построении кодирования на основании собранной статистики (при этом требуется два прохода по файлу - один для просмотра и сбора статистической информации, второй - для кодирования, что несколько ограничивает сферу применения таких алгоритмов, т.к., таким образом, исключается возможность однопроходного кодирования "на лету", применяемого в телекоммуникационных системах, где и объем данных, подчас, не известен, а их повторная передача или разбор может занять неоправданно много времени). В таком случае, в выходной поток записывается статистическая схема использованного кодирования. Данный метод известен как статическое кодирование Хаффмена .
|
|
Сжатие информации — это процесс преобразования информации, хранящейся в файле, к виду, при котором уменьшается избыточность в ее пред-ставлении и соответственно требуется меньший объем памяти для хранения.
Сжатие информации в файлах производится за счет устранения избыточности различными способами, например за счет упрощения кодов или представления повторяющихся символов, или повторяющейся последовательности символов в виде коэффициента повторения и соответствующих символов. Применяются различные алгоритмы подобного сжатия информации.
Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в так называемый архивный файл или архив.
Архивный файл — это специальным образом организованный файл, содержащий в себе один или несколько файлов в сжатом или несжатом виде и служебную информацию об именах файлов, дате и времени их создания или модификации, размерах и т.п.
Целью упаковки файлов обычно являются обеспечение более компактного размещения информации на диске, сокращение времени и соответственно стоимости передачи информации по каналам связи в компьютерных сетях. Кроме того, упаковка в один архивный файл группы файлов существенно упрощает их перенос с одного компьютера на другой, сокращает время копирования файлов на диски, позволяет защитить информацию от несанкционированного доступа, способствует защите от заражения компьютерными вирусами.
Степень сжатия файлов характеризуется коэффициентом Кс, определяемым как отношение объема сжатого файла Vc к объему исходного файла Vо, выраженное в процентах:
Kc=(Vc/ V0)*100%
Степень сжатия зависит от используемой программы, метода сжатия и типа исходного файла. Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 5 - 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей — 60 - 90%. Почти не сжимаются архивные файлы. Программы для архивации отличаются используемыми методами сжатия, что соответственно влияет на степень сжатия.
Архивация (упаковка) — помещение (загрузка) исходных файлов в архивный файл в сжатом или несжатом виде.
Разархивация (распаковка) — процесс восстановления файлов из архива точно в таком виде, какой они имели до загрузки в архив. При распаковке файлы извлекаются из архива и помешаются на диск или в оперативную память.
Программы, осуществляющие упаковку и распаковку файлов, называются про-граммами-архиваторами.
Большие по объему архивные файлы могут быть размещены на нескольких дисках (томах). Такие архивы называются многотомными. Том — это составная часть многотом-ного архива. Создавая архив из нескольких частей, можно записать его части на несколько частей.
Наиболее популярные форматы архивов
ZIP - еще со времен DOS-a один из самых популярных и распространенных архивных форматов, основанный на алгоритмах сжатия предложенных в 80-х годах прошлого столетия израильскими математиками Лемпелем и Зивом. Он отличается приемлемой степенью сжатия информации и достаточно высоким быстродействием. Сегодня он является стандартом де-факто в интернете, и его в обязательном порядке поддерживают практически все программы-архиваторы.
RAR - разработан российским программистом Евгением Рошалем и позволяет получить размер сжатого файла гораздо меньший, чем ZIP, но ценой этому является более продолжительный процесс обработки архива. В целом формат RAR значительно лучше других оптимизирован для решения сложных задач с использованием большого количества файлов и гигабайтных дисковых пространств.
ARJ - несколько устаревший формат, до сих пор отличающийся, наверное, наиболее широкими возможностями по настройке.
CAB - применяется в продуктах Microsoft как стандартный для упаковки файлов, причем его алгоритм, нигде не опубликованный и хранимый фирмой за семью печатями, представляет собой достаточно совершенный продукт, имеющий высокий коэффициент сжатия.
GZIP, TAR - получили наибольшее распространение в системах на базе Unix и ее самой популярной разновидности Linux.
ACE - достаточно новый формат с высокой степенью сжатия, завоевывающий все большую популярность.
Многие программы, являющиеся достаточно популярными в мире архиваторов базируются на том или ином формате и носят аналогичные названия. Например, для ОС Windows наиболее популярными являются архиваторы WinRAR, WinZIP, WinACE. Кроме этого все они имеют инструменты для работы с другими форматами архивов. Несмотря на это, могут возникнуть проблемы с совместимостью форматов архивов в различных программах. Во многих случаях удачным решением проблемы совместимости архивов различных типов является создание архивов в виде самораспаковывающихся программ (EXE-файлов), в состав которых входят все необходимые механизмы для извлечения информации из архива, таким образом, отпадает необходимость иметь на компьютере соответствующую программу-распаковщик архива.
Gif" width="25" height="25" />.php?viewcat=4">Обсудить на форуме
3. Показатель степени сжатия файлов
Сжатие информации в архивных файлах производится за счет устранения избыточности различными способами, например за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов или повторяющейся последовательности символов в виде коэффициента повторения и соответствующих символов. Алгоритмы подобного сжатия информации реализованы в специальных программах-архиваторах (наиболее известные из которых arj/arjfolder, pkzip/pkunzip/winzip, rar/winrar) применяются определенные Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в так называемый архивный файл или архив.
Целью упаковки файлов обычно являются обеспечение более компактного размещения информации на диске, сокращение времени и соответственно стоимости передачи информации по каналам связи в компьютерных сетях. Поэтому основным показателем эффективности той или иной программы-архиватора является степень сжатия файлов.
Степень сжатия файлов характеризуется коэффициентом Кс, определяемым как отношение объема сжатого файла Vc к объему исходного файла Vо, выраженное в процентах (в некоторых источниках используется обратное соотношение):
Кс=(Vc/Vo)*100%
Степень сжатия зависит от используемой программы, метода сжатия и типа исходного файла.
Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых коэффициент сжатия может достигать 5 - 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей Кс = 60 - 90%. Почти не сжимаются архивные файлы. Это нетрудно объяснить, если знать, что большинство программ-архиваторов используют для сжатия варианты алгоритма LZ77 (Лемпеля-Зива), суть которого заключается в особом кодировании повторяющихся последовательностей байт (читай - символов). Частота встречаемости таких повторов наиболее высока в текстах и точечной графике и практически сведена к нулю в архивах.
Кроме того, программы для архивации все же различаются реализациями алгоритмов сжатия, что соответственно влияет на степень сжатия.
В некоторые программы-архиваторы дополнительно включаются средства, направленные на уменьшение коэффициента сжатия Кс. Так в программе WinRAR реализован механизм непрерывного (solid) архивирования, при использовании которого может быть достигнута на 10 - 50% более высокая степень сжатия, чем дают обычные методы, особенно если упаковывается значительное количество небольших файлов однотипного содержания.
Характеристики архиваторов -- обратно зависимые величины. То есть, чем больше скорость сжатия, тем меньше степень сжатия, и наоборот.
На компьютерном рынке предлагается множество архиваторов -- у каждого свой набор поддерживаемых форматов, свои плюсы и минусы, свой круг почитателей, свято верящих в то, что используемый ими архиватор самый лучший. Не будем никого и ни в чем разубеждать -- просто попытаемся беспристрастно оценить самые популярные архиваторы в плане функциональности и эффективности. К таковым отнесем WinZip, WinRAR, WinAce, 7-Zip -- они лидируют по количеству скачиваний на софтовых серверах. Рассматривать остальные архиваторы вряд ли целесообразно, поскольку процент применяющих их пользователей (судя по числу скачиваний) невелик.
Поскольку в задании каждая пара значений (,) встречается один раз, то корреляционная таблица примет вид единичной матрицы. Значит условные средние совпадают со значениями. Отсюда следует, что корреляционное отношение равно 1 и, следовательно...
Аппроксимация функций методом наименьших квадратов
Далее аппроксимируем функцию квадратичной функцией. Для определения коэффициентов, и воспользуемся системой (3.2.1) Используя итоговые суммы таблицы 3, расположенные в ячейках B29, C29, D29, E29, F29, G29 и H29, запишем систему (2.1.4) в виде (3.2...
Виды архиваторов
Разработано большое количество разнообразных методов, их модификаций и подвидов для сжатия данных. Современные архиваторы, как правило, одновременно используют несколько методов одновременно. Можно выделить некоторые основные...
Как можно классифицировать информационные системы по степени автоматизации?
Классификация информационных технологий
Информационные технологии следует классифицировать прежде всего по области применения и по степени использования в них компьютеров. Различают такие области применения информационных технологий, как наука, образование, культура, экономика...
Как один из необходимых этапов в создании эффективной системы безопасности территории, предприятия, ОИД, выполним анализ уязвимости предприятия «FitMax»...
Математическое обоснование степени уязвимости объекта информационной деятельности на примере предприятия ООО "FitMax"
Для каждого из каналов проводятся расчеты вероятности степени защищенности информации. Акустический канал: Виброакустический канал: Человеческий фактор: Исходя из полученных данных...
Микропроцессор: назначение, состав, основные характеристики
Способов работы с файлами в Windows существует несколько. Первый -- это «дисковые папки» в папке «Мой компьютер». С их помощью можно добраться до любого нужного файла в любой папке и на любом диске. Однако этот способ далеко не идеален...
Поисковая система
1. Ручные информационные системы характеризуются отсутствием современных технических средств переработки информации и выполнением всех операций человеком. Например, о деятельности менеджера в фирме, где отсутствуют компьютеры...
Главным показателем эффективности работы продавца-консультанта дверей является обеспечиваемая им доля результативных посещений в общем объеме относящегося к нему клиентского трафика - показатель результативной посещаемости продавца...
Расчет параметров асинхронного энергосберегающего электродвигателя
Характеристики степеней защиты электрических машин обозначают двумя латинскими буквами IP (International Protection) и двумя цифрами...
Система электронной коммерции и статистики для продажи автомобильных запчастей
Важно анализировать количество не только новых, но и вернувшихся посетителей вашего интернет-магазине. Это позволит оценить насколько ваш сайт интересен для целевой аудитории. Кроме того, возвращать посетителей всегда проще...
Цель архивации - обеспечение более компактного размещения информации на диске, а также сокращение времени и соответственно стоимости передачи информации по каналам связи в компьютерных сетях. Кроме того, архивация существенно упрощает перенос информации с одного компьютера на другой, сокращает время ее копирования на внешние носители, позволяет защитить информацию от несанкционированного доступа, способствует защите от заражения компьютерными вирусами.
Основная особенность архивации - это сжатие информации, т.е. преобразование ее к виду, при котором уменьшается избыточность в ее представлении и соответственно требуется меньший объем памяти для хранения.
Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в один так называемый архивный файл или архив, откуда их можно извлечь в первоначальном виде.
Архивный файл (архив) - это специальным образом организованный файл, содержащий в себе один или несколько файлов в сжатом или несжатом виде и служебную информацию об именах файлов, дате и времени их создания или модификации, размерах и т.п.
Процесс записи файлов в архивный файл называется архивацией (архивированием, упаковкой), а извлечение файлов из архива - разархивацией (разархивированием, распаковкой).
Степень сжатия файла при архивировании зависит от его формата. Некоторые форматы (например, графические) предполагают сжатие, выполняемое программами, создающими файлы данных типов, и поэтому при архивации не уменьшаются в размере. Лучше всего при архивации сжимаются текстовые файлы и файлы баз данных, меньше сжимаются файлы исполняемых программ и загрузочных модулей. На степень сжатия также влияет метод сжатия.
Кроме обычных архивных файлов, можно создавать непрерывные, многотомные и самораспаковывающиеся архивы, а также их комбинации, например: многотомные самораспаковывающиеся, многотомные непрерывные и т.д.
Непрерывный (Solid) архив - это архив, запакованный специальным способом, при котором все сжимаемые файлы рассматриваются как один последовательный поток данных.
Непрерывная архивация значительно увеличивает степень сжатия, особенно при добавлении большого количества маленьких похожих файлов. Однако при этом существуют и недостатки:
§ существующие непрерывные архивы обновляются медленнее, чем обычные;
§ зашифрованные непрерывные архивы невозможно изменять;
§ для извлечения одного файла из непрерывного архива необходимо проанализировать все предыдущие заархивированные файлы, поэтому извлечение отдельных файлов из середины непрерывного архива происходит медленнее, чем извлечение из обычного архива. Однако если из непрерывного архива извлекаются все или несколько первых файлов, то в этом случае скорость распаковки практически такая же, как и с обычными архивами;
§ если в непрерывном архиве какой-либо файл окажется поврежденным, то не удастся также извлечь и все файлы, следующие после него. Поэтому при сохранении непрерывного архива на ненадежном носителе рекомендуется добавлять информацию для восстановления.
Непрерывные архивы лучше использовать в тех случаях, когда:
§ архив редко обновляется;
§ нет необходимости часто извлекать из архива один или несколько файлов;
§ архивируется один большой файл;
§ степень сжатия важнее скорости сжатия.
Файлы в непрерывных архивах обычно отсортированы по расширению, однако порядок сортировки можно изменить.
Многотомные архивы - это архивы, состоящие из нескольких частей (томов). Обычно тома используются для сохранения большого архива на нескольких дискетах или других сменных носителях.
Первый том в последовательности имеет обычное стандартное расширение программы-архиватора, а расширения последующих томов - первую букву расширения архиватора и порядковый номер.
Файлы в существующих томах невозможно добавлять, обновлять или удалять.
Самораспаковывающийся (SFX, от английских слов SelF-eXtracting) архив - это архив, к которому присоединен исполнимый модуль. Этот модуль позволяет извлечь файлы, просто запустив архив как обычную программу. Таким образом, для извлечения содержимого SFX-архива не требуется дополнительных внешних программ. SFX-архивы, как и любые другие исполнимые файлы, обычно имеют расширение.EXE, но с ними можно работать так же, как и с любым другим архивом.
SFX-архивы удобны в тех случаях, когда нужно передать кому-то архив, но вы не уверены, что у адресата есть соответствующий архиватор для извлечения файлов.
Многотомные и самораспаковывающиеся архивы также могут быть непрерывными.
Программы, осуществляющие архивацию/разархивацию файлов, называют программы-архиваторы .
Программы-архиваторы можно сравнивать по следующим основным параметрам: интерфейс, методы сжатия (определяющие степень сжатия файлов), типы создаваемых архивов, скорость работы, поддержка форматов других архиваторов.
При создании архива программа-архиватор автоматически присваивает архивному файлу «свое» расширение, например, zip, rar и др.
Управление программой-архиватором осуществляется одним из следующих способов:
1. с помощью командной строки;
2. с помощью встроенной оболочки и диалоговых панелей, позволяющих вести управление с использованием меню и функциональных клавиш.
3. с помощью комбинаций функциональных клавиш в операционных оболочках, которые, как правило, могут предложить на выбор несколько DOS-программ архивации или собственный архиватор оболочки.
4. с помощью элементов графического интерфейса.
Несмотря на множество программ-архиваторов, современный пользователь, как правило, реально работает с двумя форматами архивов: ZIP и RAR.
Программы-архиваторы предназначены для архивации, (упаковки) файлов путем сжатия хранимой в них информации, в целях экономии места на дисках.
Сжатие информации - это процесс преобразования информации, хранящейся в файле, к виду, при котором уменьшается избыточность в ее представлении и, соответственно, требуется меньший объем памяти для хранения.
Сжатие информации в файлах производится за счет устра нения избыточности различными способами, например, за счет упрощения кодов, исключения из них постоянных битов символов или повторяющейся последовательности символов, введения коэффициента повторения символов и т. п. Применяются различные алгоритмы подобного сжатия информации.
Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в архивный файл или архив.
Архивный файл (архив, или файл-архив) - это специальным образом организованный файл, содержащий в себе один или не сколько файлов в сжатом или несжатом виде и служебную инфор мацию об именах файлов , дате и времени их создания или модифи кации, размерах и т. п.
Целью упаковки файлов обычно являются обеспечение более компактного размещения информации на диске, сокращение времени и, соответственно, стоимости передачи информации по каналам связи в компьютерных сетях. Кроме того, упаковка в один ар хивный файл группы файлов существенно упрощает их перенос с одного компьютера на другой, сокращает время копирования файлов на диски, позволяет защитить информацию от несанкционированного доступа, способствует защите от заражения компьютерными вирусами.
Степень сжатия зависит от используемой программы-архиватора, метода сжатия и типа исходного файла. Наиболее хорошо сжимаются текстовые файлы и файлы данных, для которых степень сжатия может достигать 80-90%, меньше сжимаются файлы исполняемых программ и загрузочных модулей - 5-40%. Почти не сжимаются архивные файлы.
Программы архивации отличаются используемыми методами сжатия, что соответственно влияет на степень сжатия.
Разархивация (распаковка) - процесс восстановления файлов из архива точно в таком виде, какой они имели до загрузки в ар хив. При распаковке файлы извлекаются из архива и помещаются на диск или в оперативную память.
Большие по объему архивные файлы могут быть размещены в нескольких томах. Такие архивы называются многотомными. Том - это составная часть многотомного архива. Создавая архив из нескольких частей, можно записать его части на несколько дискет.
ОСНОВНЫЕ ВИДЫ ПРОГРАММ-АРХИВАТОРОВ.
