В каких случаях используется сжатие без потерь?

11 ответов на вопрос “В каких случаях используется сжатие без потерь?”

  1. Ready for Job Ответить

    Доброго времени суток.
    Сегодня я хочу коснуться темы сжатия данных без потерь. Несмотря на то, что на хабре уже были статьи, посвященные некоторым алгоритмам, мне захотелось рассказать об этом чуть более подробно.
    Я постараюсь давать как математическое описание, так и описание в обычном виде, для того, чтобы каждый мог найти для себя что-то интересное.
    В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.

    Сжатие. Нужно ли оно в наше время?

    Разумеется, да. Конечно, все мы понимаем, что сейчас нам доступны и носители информации большого объема, и высокоскоростные каналы передачи данных. Однако, одновременно с этим растут и объемы передаваемой информации. Если несколько лет назад мы смотрели 700-мегабайтные фильмы, умещающиеся на одну болванку, то сегодня фильмы в HD-качестве могут занимать десятки гигабайт.
    Конечно, пользы от сжатия всего и вся не так много. Но все же существуют ситуации, в которых сжатие крайне полезно, если не необходимо.
    Пересылка документов по электронной почте (особенно больших объемов документов с использованием мобильных устройств)
    При публикации документов на сайтах, потребность в экономии трафика
    Экономия дискового пространства в тех случаях, когда замена или добавление средств хранения затруднительно. Например, подобное бывает в тех случаях, когда выбить бюджет под капитальные расходы непросто, а дискового пространства не хватает
    Конечно, можно придумать еще множество различных ситуаций, в которых сжатие окажется полезным, но нам достаточно и этих нескольких примеров.
    Все методы сжатия можно разделить на две большие группы: сжатие с потерями и сжатие без потерь. Сжатие без потерь применяется в тех случаях, когда информацию нужно восстановить с точностью до бита. Такой подход является единственно возможным при сжатии, например, текстовых данных.
    В некоторых случаях, однако, не требуется точного восстановления информации и допускается использовать алгоритмы, реализующие сжатие с потерями, которое, в отличие от сжатия без потерь, обычно проще реализуется и обеспечивает более высокую степень архивации.
    Сжатие с потерями
    Лучшие степени сжатия, при сохранении «достаточно хорошего» качества данных. Применяются в основном для сжатия аналоговых данных — звука, изображений. В таких случаях распакованный файл может очень сильно отличаться от оригинала на уровне сравнения «бит в бит», но практически неотличим для человеческого уха или глаза в большинстве практических применений.
    Сжатие без потерь
    Данные восстанавливаются с точностью до бита, что не приводит к каким-либо потерям информации. Однако, сжатие без потерь показывает обычно худшие степени сжатия.
    Итак, перейдем к рассмотрению алгоритмов сжатия без потерь.

    Универсальные методы сжатия без потерь

    В общем случае можно выделить три базовых варианта, на которых строятся алгоритмы сжатия.
    Первая группа методов – преобразование потока. Это предполагает описание новых поступающих несжатых данных через уже обработанные. При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива). В этом случае, второе и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются ссылками на ее первое вхождение.
    Вторая группа методов – это статистические методы сжатия. В свою очередь, эти методы делятся на адаптивные (или поточные), и блочные.
    В первом (адаптивном) варианте, вычисление вероятностей для новых данных происходит по данным, уже обработанным при кодировании. К этим методам относятся адаптивные варианты алгоритмов Хаффмана и Шеннона-Фано.
    Во втором (блочном) случае, статистика каждого блока данных высчитывается отдельно, и добавляется к самому сжатому блоку. Сюда можно отнести статические варианты методов Хаффмана, Шеннона-Фано, и арифметического кодирования.
    Третья группа методов – это так называемые методы преобразования блока. Входящие данные разбиваются на блоки, которые затем трансформируются целиком. При этом некоторые методы, особенно основанные на перестановке блоков, могут не приводить к существенному (или вообще какому-либо) уменьшению объема данных. Однако после подобной обработки, структура данных значительно улучшается, и последующее сжатие другими алгоритмами проходит более успешно и быстро.
    Общие принципы, на которых основано сжатие данных
    Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
    Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon’s source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.
    Немного математики
    Если вероятность появления элемента si равна p(si), то наиболее выгодно будет представить этот элемент — log2p(si) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log2p(si) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = {p(si)} неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как

    Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
    Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента si распределение вероятностей F примет некоторое значение Fk, то есть для каждого элемента F= Fk и H= Hk.
    Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей pk(si) для всех элементов si.
    Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов как

    Где Pk — вероятность нахождения источника в состоянии k.
    Итак, на данном этапе мы знаем, что сжатие основано на замене часто встречающихся элементов короткими кодами, и наоборот, а так же знаем, как определить среднюю длину кодов. Но что же такое код, кодирование, и как оно происходит?

    Кодирование без памяти

    Коды без памяти являются простейшими кодами, на основе которых может быть осуществлено сжатие данных. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
    На мой взгляд, не самое понятное определение. Рассмотрим эту тему чуть более подробно.
    Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a1, a2,… ,an) словом, а число n — длиной этого слова.
    Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.
    Введем еще два обозначения для множества всех непустых слов в алфавите. Пусть — количество непустых слов в первом алфавите, а — во втором.
    Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием.
    Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
    a1 B1
    a2 B2
    …
    an Bn
    Это соответствие называют схемой, и обозначают ?.
    В этом случае слова B1, B2,…, Bn называют элементарными кодами, а вид кодирования с их помощью — алфавитным кодированием. Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.
    Итак, мы определились с понятиями алфавит, слово, код, и кодирование. Теперь введем понятие префикс.
    Пусть слово B имеет вид B=B’B”. Тогда B’ называют началом, или префиксом слова B, а B” — его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ? («пробел»), и само слово B, могут считаться и началами и концами.
    Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять — это префиксное множество. Схема ? обладает свойством префикса, если для любых 1?i, j?r, i?j, слово Bi не является префиксом слова Bj.
    Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.
    Итак, мы разобрались с основными определениями. Так как же происходит само кодирование без памяти?
    Оно происходит в три этапа.
    Составляется алфавит ? символов исходного сообщения, причем символы алфавита сортируются по убыванию их вероятности появления в сообщении.
    Каждому символу ai из алфавита ? ставится в соответствие некое слово Bi из префиксного множества ?.
    Осуществляется кодирование каждого символа, с последующим объединением кодов в один поток данных, который будет являться результатам сжатия.
    Одним из канонических алгоритмов, которые иллюстрируют данный метод, является алгоритм Хаффмана.

    Алгоритм Хаффмана

    Алгоритм Хаффмана использует частоту появления одинаковых байт во входном блоке данных, и ставит в соответствие часто встречающимся блокам цепочки бит меньшей длины, и наоборот. Этот код является минимально – избыточным кодом. Рассмотрим случай, когда, не зависимо от входного потока, алфавит выходного потока состоит из всего 2 символов – нуля и единицы.
    В первую очередь при кодировании алгоритмом Хаффмана, нам нужно построить схему ?. Делается это следующим образом:
    Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей. Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).
    Два символа aj-1 и aj входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов. Затем мы дописываем 0 в начало слова Bj-1, и 1 в начало слова Bj, которые будут впоследствии являться кодами символов aj-1 и aj соответственно.
    Удаляем эти символы из алфавита исходного сообщения, но добавляем в этот алфавит сформированный псевдосимвол (естественно, он должен быть вставлен в алфавит на нужное место, с учетом его вероятности).
    Шаги 2 и 3 повторяются до тех пор, пока в алфавите не останется только 1 псевдосимвол, содержащий все изначальные символы алфавита. При этом, поскольку на каждом шаге и для каждого символа происходит изменение соответствующего ему слова Bi (путем добавление единицы или нуля), то после завершения этой процедуры каждому изначальному символу алфавита ai будет соответствовать некий код Bi.
    Для лучшей иллюстрации, рассмотрим небольшой пример.
    Пусть у нас есть алфавит, состоящий из всего четырех символов — { a1, a2, a3, a4}. Предположим также, что вероятности появления этих символов равны соответственно p1=0.5; p2=0.24; p3=0.15; p4=0.11 (сумма всех вероятностей, очевидно, равна единице).
    Итак, построим схему для данного алфавита.
    Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p’.
    Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
    Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p”.
    Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
    Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.
    Если сделать иллюстрацию этого процесса, получится примерно следующее:

    Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.
    Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:
    a1 = 0
    a2 = 11
    a3 = 100
    a4 = 101
    Поскольку ни один из данных кодов не является префиксом какого-нибудь другого (то есть, мы получили пресловутое префиксное множество), мы можем однозначно определить каждый код в выходном потоке.
    Итак, мы добились того, что самый частый символ кодируется самым коротким кодом, и наоборот.
    Если предположить, что изначально для хранения каждого символа использовался один байт, то можно посчитать, насколько нам удалось уменьшить данные.
    Пусть на входу у нас была строка из 1000 символов, в которой символ a1 встречался 500 раз, a2 — 240, a3 — 150, и a4 — 110 раз.
    Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ?pili = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.
    Напомню, что согласно Шеннону, средняя длина кодов составляет . Подставив в это уравнение наши значения вероятностей, мы получим среднюю длину кодов равную 1.75496602732291, что весьма и весьма близко к полученному нами результату.
    Тем не менее, следует учитывать, что помимо самих данных нам необходимо хранить таблицу кодировки, что слегка увеличит итоговый размер закодированных данных. Очевидно, что в разных случаях могут с использоваться разные вариации алгоритма – к примеру, иногда эффективнее использовать заранее заданную таблицу вероятностей, а иногда – необходимо составить ее динамически, путем прохода по сжимаемым данным.

    Заключение

    Итак, в этой статье я постарался рассказать об общих принципах, по которым происходит сжатие без потерь, а также рассмотрел один из канонических алгоритмов — кодирование по Хаффману.
    Если статья придется по вкусу хабросообществу, то я с удовольствием напишу продолжение, так как есть еще множество интересных вещей, касающихся сжатия без потерь; это как классические алгоритмы, так и предварительные преобразования данных (например, преобразование Барроуза-Уилира), ну и, конечно, специфические алгоритмы для сжатия звука, видео и изображений (самая, на мой взгляд, интересная тема).

    Литература

    Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео; ISBN 5-86404-170-X; 2003 г.
    Д. Сэломон. Сжатие данных, изображения и звука; ISBN 5-94836-027-Х; 2004г.
    http://www.wikipedia.org

  2. Sasius Ответить

    Часть первая – историческая.

    Введение

    Существующие алгоритмы сжатия данных можно разделить на два больших класса – с потерями, и без. Алгоритмы с потерями обычно применяются для сжатия изображений и аудио. Эти алгоритмы позволяют достичь больших степеней сжатия благодаря избирательной потере качества. Однако, по определению, восстановить первоначальные данные из сжатого результата невозможно.
    Алгоритмы сжатия без потерь применяются для уменьшения размера данных, и работают таким образом, что возможно восстановить данные в точности такими, какие они были до сжатия. Они применяются в коммуникациях, архиваторах и некоторых алгоритмах сжатии аудио и графической информации. Далее мы рассмотрим только алгоритмы сжатия без потерь.
    Основной принцип алгоритмов сжатия базируется на том, что в любом файле, содержащем неслучайные данные, информация частично повторяется. Используя статистические математические модели можно определить вероятность повторения определённой комбинации символов. После этого можно создать коды, обозначающие выбранные фразы, и назначить самым часто повторяющимся фразам самые короткие коды. Для этого используются разные техники, например: энтропийное кодирование, кодирование повторов, и сжатие при помощи словаря. С их помощью 8-битный символ, или целая строка, могут быть заменены всего лишь несколькими битами, устраняя таким образом излишнюю информацию.

    История

    Иерархия алгоритмов:

    Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.
    Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.
    Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.

    Проблемы с правами

    Алгоритмы LZ77 и LZ78 получили большую популярность и вызвали волну улучшателей, из которых до наших дней дожили DEFLATE, LZMA и LZX. Большинство популярных алгоритмов основаны на LZ77, потому что производный от LZ78 алгоритм LZW был запатентован компанией Unisys в 1984 году, после чего они начали троллить всех и каждого, включая даже случаи использования изображений в формате GIF. В это время на UNIX использовали вариацию алгоритма LZW под названием LZC, и из-за проблем с правами их использование пришлось сворачивать. Предпочтение отдали алгоритму DEFLATE (gzip) и преобразованию Барроуза — Уилера, BWT (bzip2). Что было и к лучшему, так как эти алгоритмы почти всегда превосходят по сжатию LZW.
    К 2003 году срок патента истёк, но поезд уже ушёл и алгоритм LZW сохранился, пожалуй, только в файлах GIF. Доминирующими являются алгоритмы на основе LZ77.
    В 1993 году была ещё одна битва патентов – когда компания Stac Electronics обнаружила, что разработанный ею алгоритм LZS используется компанией Microsoft в программе для сжатия дисков, поставлявшейся с MS-DOS 6.0. Stac Electronics подала в суд и им удалось выиграть дело, в результате чего они получили более $100 миллионов.

    Рост популярности Deflate

    Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивавшихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG.
    Том Хендерсон придумал и выпустил первый коммерчески успешный архиватор ARC в 1985 году (компания System Enhancement Associates). ARC была популярной среди пользователей BBS, т.к. она одна из первых могла сжимать несколько файлов в архив, к тому же исходники её были открыты. ARC использовала модифицированный алгоритм LZW.
    Фил Катц, вдохновлённый популярностью ARC, выпустил программу PKARC в формате shareware, в которой улучшил алгоритмы сжатия, переписав их на Ассемблере. Однако, был засужен Хендерсоном и был признан виновным. PKARC настолько открыто копировала ARC, что иногда даже повторялись опечатки в комментариях к исходному коду.
    Но Фил Катц не растерялся, и в 1989 году сильно изменил архиватор и выпустил PKZIP. После того, как его атаковали уже в связи с патентом на алгоритм LZW, он изменил и базовый алгоритм на новый, под названием IMPLODE. Вновь формат был заменён в 1993 году с выходом PKZIP 2.0, и заменой стал DEFLATE. Среди новых возможностей была функция разбиения архива на тома. Эта версия до сих пор повсеместно используется, несмотря на почтенный возраст.
    Формат изображений GIF (Graphics Interchange Format) был создан компанией CompuServe в 1987. Как известно, формат поддерживает сжатие изображения без потерь, и ограничен палитрой в 256 цветов. Несмотря на все потуги Unisys, ей не удалось остановить распространение этого формата. Он до сих пор популярен, особенно в связи с поддержкой анимации.
    Слегка взволнованная патентными проблемами, компания CompuServe в 1994 году выпустила формат Portable Network Graphics (PNG). Как и ZIP, она использовала новый модный алгоритм DEFLATE. Хотя DEFLATE был запатентован Катцем, он не стал предъявлять никаких претензий.
    Сейчас это самый популярный алгоритм сжатия. Кроме PNG и ZIP он используется в gzip, HTTP, SSL и других технологиях передачи данных.
    К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году в возрасте 37 лет. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!

    Современные архиваторы

    ZIP царствовал безраздельно до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас ZIP, пожалуй, самый распространённый из форматов, RAR – до недавнего времени был стандартом для распространения различного малолегального контента через интернет (благодаря увеличению пропускной способности всё чаще файлы распространяются без архивации), а 7zip используется как формат с наилучшим сжатием при приемлемом времени работы. В мире UNIX используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).
    Прим. перев. Лично я, кроме перечисленных, сталкивался ещё с архиватором ARJ (Archived by Robert Jung), который был популярен в 90-х в эру BBS. Он поддерживал многотомные архивы, и так же, как после него RAR, использовался для распространения игр и прочего вареза. Ещё был архиватор HA от Harri Hirvola, который использовал сжатие HSC (не нашёл внятных объяснений — только «модель ограниченного контекста и арифметическое кодирование»), который хорошо справлялся со сжатием длинных текстовых файлов.
    В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.
    В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.

    Будущее алгоритмов сжатия

    Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
    С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
    Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.
    В следующей части мы рассмотрим техническую сторону упомянутых алгоритмов и принципы их работы.

  3. Mariri Ответить

    Методом Хаффмана представляет общую схему сжатия, которая имеет много вариантов. Основная схема – присвоение двоичного кода каждой уникальной величине, причем длина этих кодов различна.
    Для того чтобы сформировать минимальный код для каждого символа сообщения, используется двоичное дерево. В основном алгоритме метода объединяются вместе элементы, повторяющиеся наименее часто, затем пара рассматривается как один элемент и их частоты объединяются. Это повторяется до тех пор, пока все элементы не объединятся в пары.
    Рассмотрим пример. Пусть дано сообщение abbbcccddeeeeeeeeef.
    Частоты символов: а: 1, b: 3, c: 3, d: 2, e: 9, f: 1.
    Наиболее редко используемы в этом примере a и f, так что они становятся первой парой: a – присваивается нулевая ветвь, а f – первая. Это означает, что 0 и 1 будут младшими битами для a и f соответственно. Старшие биты будут получены после построения дерева (рис. 2.4).

    Рис. 2.4
    Частоты первых двух символов (a и f) суммируются, что дает 2. Поскольку теперь самая низкая частота 2, эта пара объединяется с d (тоже имеет частоту – 2). Исходной паре присваивается нулевая ветвь, а d – первая. Теперь код для a заканчивается на 00, f – на 01, d – на 1. Код для d будет короче на 1 бит. Дерево строится подобным образом для всех символов. Получаем следующие коды:
    0000 – a,
    0001 – f,
    001 – d,
    010 – b,
    011 – с,
    1 – e.
    Исходная последовательность будет закодирована следующим образом: 00000100100100110110110010011111111110001.
    Полученная таблица кодов передается приемнику информации и используется при декодировании. По алгоритму Хаффмана наименее распространенные символы кодируются более длинным кодом, наиболее распространенные – коротким.
    В результате может быть получена степень сжатия 8:1, что зависит от исходного формата представления информации (1 байт на 1 символ, например, или 2 байта).
    Схема Хаффмана работает не так хорошо для информации, содержащей длинные последовательности повторяющихся символов, которые могут быть сжаты лучше с использованием групповой или какой-либо другой схемы кодирования.
    Вследствие того, что алгоритм Хаффмана реализуется в два прохода (1 – накопление статистики при построении статистической модели, 2 – кодирование), компрессия и декомпрессия в данном алгоритме – сравнительно медленные процессы.
    Другая проблема заключается в чувствительности к отброшенным или добавленным битам. Поскольку все биты сжимаются без учета границ байта, единственный способ, при помощи которого дешифратор может узнать о завершении кода, – достигнуть конца ветви. Если бит отброшен или добавлен, дешифратор начинает обработку с середины кода, и остальная часть данных становится бессмыслицей.Полученная таблица кодов передается приемнику информации и используется при декодировании. По алгоритму Хаффмана наименее распространенные символы кодируются более длинным кодом, наиболее распространенные – коротким.
    В результате может быть получена степень сжатия 8:1, что зависит от исходного формата представления информации (1 байт на 1 символ, например, или 2 байта).
    Схема Хаффмана работает не так хорошо для информации, содержащей длинные последовательности повторяющихся символов, которые могут быть сжаты лучше с использованием групповой или какой-либо другой схемы кодирования.
    Вследствие того, что алгоритм Хаффмана реализуется в два прохода (1 – накопление статистики при построении статистической модели, 2 – кодирование), компрессия и декомпрессия в данном алгоритме – сравнительно медленные процессы.
    Другая проблема заключается в чувствительности к отброшенным или добавленным битам. Поскольку все биты сжимаются без учета границ байта, единственный способ, при помощи которого дешифратор может узнать о завершении кода, – достигнуть конца ветви. Если бит отброшен или добавлен, дешифратор начинает обработку с середины кода, и остальная часть данных становится бессмыслицей.

  4. $herik Ответить

    Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 11 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, базовый уровень) | Сжатие данных без потерь
    Уроки 4 – 5
    Сжатие данных без потерь
    (§3. Сжатие данных)

    Содержание урока

    Основные понятия
    Алгоритм RLE
    Префиксные коды
    Алгоритм Хаффмана
    Сжатие с потерями
    Выводы
    Вопросы и задания
    Задачи

    Основные понятия

    Для того чтобы сэкономить место на внешних носителях (жёстких дисках, флэш-дисках) и ускорить передачу данных по компьютерным сетям, нужно сжать данные — уменьшить информационный объём, сократить длину двоичного кода. Это можно сделать, устранив избыточность использованного кода.
    Например, пусть текстовый файл объёмом 10 Кбайт содержит всего четырех различных символа: латинские буквы «А», «В», «С» и пробел. Вы знаете, что для кодирования одного из четырёх возможных вариантов достаточно 2 битов, поэтому использовать для его передачи обычное 8-битное кодирование символов невыгодно. Можно присвоить каждому из четырёх символов двухбитные коды, например, так:
    А — 00, В — 01, С — 10, пробел — 11.
    Тогда последовательность «АВА САВАВА», занимающая 10 байтов в однобайтной кодировке, может быть представлена как цепочка из 20 битов:
    00010011100001000100
    Таким образом, нам удалось уменьшить информационный объём текста в 4 раза, и передаваться он будет в 4 раза быстрее. Однако непонятно, как раскодировать это сообщение, ведь получатель не знает, какой код был использован. Выход состоит в том, чтобы включить в сообщение служебную информацию — заголовок, в котором каждому коду будет сопоставлен ASCII-код символа. Условимся, что первый байт заголовка — это количество используемых символов N, а следующие N байтов — это ASCII-коды этих символов. В данном случае заголовок занимает 5 байтов и выглядит так:

    Файл, занимающий 10 Кбайт в 8-битной кодировке, содержит 10 240 символов. В сжатом виде каждый символ кодируется двумя битами, кроме того, есть 5-байтный заголовок. Поэтому сжатый файл будет иметь объём
    5 + 10240 • 2/8 байтов = 2565 байтов.
    Коэффициент сжатия — это отношение размеров исходного и сжатого файлов.
    В данном случае удалось сжать файл почти в 4 раза, коэффициент сжатия равен
    k = 10 240/2565 ? 4.
    Если принимающая сторона «знает» формат файла (заголовок + закодированные данные), она сможет восстановить в точности его исходный вид. Такое сжатие называют сжатием без потерь. Оно используется для упаковки текстов, программ, данных, которые ни в коем случае нельзя искажать.
    Сжатие без потерь — это такое уменьшение объёма закодированных данных, при котором можно восстановить их исходный вид из кода без искажений.
    За счёт чего удалось сжать файл? Только за счёт того, что в файле была некоторая закономерность, избыточность — использовались только 4 символа вместо полного набора.
    Следующая страница Алгоритм RLE
    Cкачать материалы урока

  5. Adrienaya Ответить

    В данном алгоритме сжатие информации осуществляется путем статистического кодирования или на основе словаря, который предварительно был создан. Согласно статистическому алгоритму Хаффмана каждому входному символу присваивается определенный код. При этом наиболее часто используемому символу – наиболее короткий код, а наиболее редко используемому – более длинный. В качестве примера на диаграмме приведено распределение частоты использования отдельных букв английского алфавита (рис.1). Такое распределение может быть построено и для русского языка. Таблицы кодирования создаются заранее и имеют ограниченный размер. Этот алгоритм обеспечивает наибольшее быстродействие и наименьшие задержки. Для получения высоких коэффициентов сжатия статистический метод требует больших объемов памяти.

    Рисунок 1. Распределение английских букв по их частоте использования
    Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский имеет самый высокий уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на $30\%$ больше. Если речь идет о стихотворном тексте, избыточность может быть до $2$ раз выше.

  6. Angel567love8 Ответить

    Сжатие без потерь (англ. Lossless data compression) – метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.
    Сжатие данных без потерь используется во многих приложениях. Например, оно используется в популярном файловом формате ZIP и Unix-утилите Gzip. Оно также используется как компонент в сжатии с потерями.
    Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример – исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или GIF, используют только сжатие без потерь; тогда как другие (TIFF, MNG) могут использовать сжатие как с потерями, так и без.
    Техника сжатия без потерь
    Из комбинаторики следует, что нет алгоритма сжатия без потерь, способного уменьшить хотя бы на байт любой файл. Впрочем, признак качества алгоритма сжатия не в этом – алгоритм должен эффективно работать на тех данных, на которые он рассчитан.
    Многоцелевые алгоритмы сжатия отличаются тем, что способны уменьшать широкий диапазон данных – исполняемые файлы, файлы данных, тексты, графику и т.д., и применяются в архиваторах. Специализированные же алгоритмы рассчитаны на некоторый тип файлов (текст, графику, звук и т.д.), зато сжимают такие файлы намного сильнее. Например: архиваторы сжимают звук примерно на треть (в 1,5 раза), в то время как FLAC – в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: так, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.
    Большинство алгоритмов сжатия без потерь работают в две стадии: на первой генерируется статистическая модель для входящих данных, вторая отображает входящие данные в битовом представлении, используя модель для получения «вероятностных» (то есть часто встречаемых) данных, которые используются чаще, чем «невероятностные».
    Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:
    Преобразование Барроуза – Уилера (блочно-сортирующая предобработка, которая делает сжатие более эффективным)
    LZ77 и LZ78 (используется DEFLATE)
    LZW
    Алгоритмы кодирования через генерирование битовых последовательностей:
    · Алгоритм Хаффмана (также используется DEFLATE)
    · Арифметическое кодирование
    Методы сжатия без потерь
    · Многоцелевые
    · Кодирование длин серий – простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений
    · LZW – используется в gif и во многих других.
    · Deflate – используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.
    · LZMA – используется в 7-zip.
    v Сжатие аудио:
    · Apple Lossless – ALAC (Apple Lossless Audio Codec);
    · Audio Lossless Coding – также известен как MPEG-4 ALS;
    · Direct Stream Transfer – DST;
    · Free Lossless Audio Codec – FLAC;
    v Сжатие графики
    · ABO – Adaptive Binary Optimization;
    · GIF – (без потерь только для изображений содержащих менее 256 цветов);
    · JBIG2 – (с потерями или без Ч/Б изображений);
    · JPEG-LS – (стандарт сжатия без потерь / почти без потерь);
    · JPEG 2000 – (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего);
    · PGF – Progressive Graphics File (сжатие с/без потерь);
    · PNG – Portable Network Graphics;
    · TIFF;
    · WMPhoto – (включая метод сжатия без потерь);
    v Сжатие видео
    · Animation codec;
    · CamStudio Video Codec;
    · CorePNG;
    · FFV1.

  10. VideoAnswer Ответить

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *