Как сжать двоичный код

Сжатие двоичного кода

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

• Потеря информации в результате сжатия недопустима;
• Допустима частичная потеря информации в результате сжатия.

Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.

При упаковке данных в файловые архивы производится их сжатие без потери информации .

Сжатие с частичной потерей информации производится при сжатии кода изображения (графики, видео) и звука.

Сжатие без потери информации:

• использование неравномерного кода; выявление повторяющихся фрагментов кода.
• использование неравномерного кода; выявление повторяющихся фрагментов кода.
• использование неравномерного кода;
• выявление повторяющихся фрагментов кода.

Сжатие происходит за счет устранения избыточности кода, например, за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов в виде коэффициента повторения.

Важнейшая характеристика процесса сжатия – коэффициент сжатия.

Коэффициент сжатия – отношение объема исходного сообщения к объему сжатого.

Алгоритмы сжатия, использование неравномерного кода

В основе первого подхода лежит использование неравномерного кода.

В восьмиразрядной таблице символьной кодировки ( ASCII ), каждый символ кодируется восемью битами и, следовательно, занимает в памяти 1 байт. Информационный вес символа тем больше, чем меньше его частота встречаемости. С этим обстоятельством и связана идея сжатия текста в компьютерной памяти: отказаться от одинаковой длины кодов символов.

Сжатие с использованием кодов переменной длины

Одним из простейших, но весьма эффективных способов построения двоичного неравномерного кода, не требующего специального разделителя является алгоритм Д.Хаффмана.

Алгоритм Хаффмана — адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

Был разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

Особенностью данного кода является его префиксная структура . Это значит, что код любого символа не совпадает с началом кода всех остальных символов.

Чтобы понять, как строятся префиксные коды, рассмотрим, как построить ориентированный граф, определяющий этот код.

Например, кодовые слова 00, 01, 10, 011, 100, 101, 1001, 1010, 1111, кодируют соответственно буквы: a , b , c , d , e , f , g , h , i .

Построим граф этого кода.

Из начальной вершины выходят две дуги, помеченные 0 и 1. Затем из конца каждой такой дуги входят новые дуги, помеченные 0 и 1 так, чтобы, идя по этим дугам от корня, читалось начало какого-либо кодового слова.

Если при этом какая-то последовательность оказывается прочитанным полностью, то у конца последней дуги пишется кодируемый символ.

Из получившихся вершин снова проводятся дуги — и так далее, до тех пор, пока не будут исчерпаны все коды.

Коэффициентом сжатия называют отношение длины кода в байтах после сжатия к его длине до сжатия.

Деревом называется графическое представление (граф) структуры связей между элементами некоторой системы.

Двоичным деревом называется дерево, в котором любая вершина, имеет не более двух потомков.

Корнем дерева называется единственная вершина, не имеющая родительской вершины.

Листьями дерева называются вершины, не имеющие потомков.

Пример: Предположим, что необходимо выполнить компрессию текстового документа с фразой “мама_мыла_раму”. Наш исходный текст “весит” 112 бит, так как каждый символ занимает 8 бит в кодовой таблице, а таких символов у нас 14 штук.

1. Составляем таблицу частот, то есть, подсчитываем количество вхождений каждой буквы во фразу, в результате чего получим вес каждой буквы:

Алгоритмы сжатия данных без потерь, часть 2

Это очень простой алгоритм. Он заменяет серии из двух или более одинаковых символов числом, обозначающим длину серии, за которым идёт сам символ. Полезен для сильно избыточных данных, типа картинок с большим количеством одинаковых пикселей, или в комбинации с алгоритмами типа BWT.

На входе: AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

На выходе: 3A2B4C1D6E38A

Преобразование Барроуза-Уилера (BWT)

Алгоритм, придуманный в 1994 году, обратимо трансформирует блок данных так, чтобы максимизировать повторения одинаковых символов. Сам он не сжимает данные, но подготавливает их для более эффективного сжатия через RLE или другой алгоритм сжатия.

— создаём массив строк
— создаём все возможные преобразования входящей строки данных, каждое из которых сохраняем в массиве
— сортируем массив
— возвращаем последний столбец

Алгоритм лучше всего работает с большими данными со множеством повторяющихся символов. Пример работы на подходящем массиве данных (& обозначает конец файла)

Благодаря чередованию одинаковых символов, вывод алгоритма оптимален для сжатия RLE, которое даёт «3H&3A». Но на реальных данных, к сожалению, настолько оптимальных результатов обычно не получается.

Энтропийное кодирование

Энтропия в данном случае означает минимальное количество бит, в среднем необходимое для представления символа. Простой ЭК комбинирует статистическую модель и сам кодировщик. Входной файл парсится для построения стат.модели, состоящей из вероятностей появления определённых символов. Затем кодировщик, используя модель, определяет, какие битовые или байтовые кодировки назначать каждому символу, чтобы самые часто встречающиеся были представлены самыми короткими кодировками, и наоборот.

Алгоритм Шеннона — Фано

Одна из самых ранних техник (1949 год). Создаёт двоичное дерево для представления вероятностей появления каждого из символов. Затем они сортируются так, чтобы самые часто встречающиеся находились наверху дерева, и наоборот.

Код для символа получается поиском по дереву, и добавлением 0 или 1, в зависимости от того, идём мы налево или направо. К примеру, путь к “А” – две ветки налево и одна направо, его код будет «110». Алгоритм не всегда даёт оптимальные коды из-за методики построения дерева снизу вверх. Поэтому сейчас используется алгоритм Хаффмана, подходящий для любых входных данных.

1. парсим ввод, считаем количество вхождений всех символов
2. определяем вероятность появления каждого из них
3. сортируем символы по вероятности появления
4. делим список пополам так, чтобы сумма вероятностей в левой ветке примерно равнялось сумме в правой
5. добавляем 0 или 1 для левых и правых узлов соответственно
6. повторяем шаги 4 и 5 для правых и левых поддеревьев до тех пор, пока каждый узел не будет «листом»

Кодирование Хаффмана

Это вариант энтропийного кодирования, работающий схожим с предыдущим алгоритмом методом, но двоичное дерево строится сверху вниз, для достижения оптимального результата.

1. Парсим ввод, считаем количество повторений символов
2. Определяем вероятность появления каждого символа
3. Сортируем список по вероятностям (самые частые вначале)
4. Создаём листы для каждого символа, и добавляем их в очередь
5. пока очередь состоит более, чем из одного символа:
— берём из очереди два листа с наименьшими вероятностями
— к коду первой прибавляем 0, к коду второй – 1
— создаём узел с вероятностью, равной сумме вероятностей двух нод
— первую ноду вешаем на левую сторону, вторую – на правую
— добавляем полученный узел в очередь
6. Последняя нода в очереди будет корнем двоичного дерева.

Арифметическое кодирование

Был разработан в 1979 году в IBM для использования в их мейнфреймах. Достигает очень хорошей степени сжатия, обычно большей, чем у Хаффмана, однако он сравнительно сложен по сравнению с предыдущими.

Вместо разбиения вероятностей по дереву, алгоритм преобразует входные данные в одно рациональное число от 0 до 1.

В общем алгоритм таков:

1. считаем количество уникальных символов на входе. Это количество будет представлять основание для счисления b (b=2 – двоичное, и т.п.).
2. подсчитываем общую длину входа
3. назначаем «коды» от 0 до b каждому из уникальных символов в порядке их появления
4. заменяем символы кодами, получая число в системе счисления с основанием b
5. преобразуем полученное число в двоичную систему

Пример. На входе строка «ABCDAABD»

1. 4 уникальных символа, основание = 4, длина данных = 8
2. назначаем коды: A=0, B=1, C=2, D=3
3. получаем число “0.01230013”
4. преобразуем «0.01231123» из четверичной в двоичную систему: 0.01101100000111

Если мы положим, что имеем дело с восьмибитными символами, то на входе у нас 8х8=64 бита, а на выходе – 15, то есть степень сжатия 24%.

Классификация алгоритмов

Алгоритмы, применяющие метод «скользящего окна»

Всё началось с алгоритма LZ77 (1977 год), который представил новую концепцию «скользящего окна», позволившую значительно улучшить сжатие данных. LZ77 использует словарь, содержащий тройки данных – смещение, длина серии и символ расхождения. Смещение – как далеко от начала файла находится фраза. Длина серии – сколько символов, считая от смещения, принадлежат фразе. Символ расхождения показывает, что найдена новая фраза, похожая на ту, что обозначена смещением и длиной, за исключением этого символа. Словарь меняется по мере парсинга файла при помощи скользящего окна. К примеру, размер окна может быть 64Мб, тогда словарь будет содержать данные из последних 64 мегабайт входных данных.

К примеру, для входных данных «abbadabba» результат будет «abb(0,1,’d’)(0,3,’a’)»

В данном случае результат получился длиннее входа, но обычно он конечно получается короче.

Модификация алгоритма LZ77, предложенная Майклом Роуде в 1981 году. В отличие от LZ77 работает за линейное время, однако требует большего объёма памяти. Обычно проигрывает LZ78 в сжатии.

DEFLATE

Придуман Филом Кацем в 1993 году, и используется в большинстве современных архиваторов. Является комбинацией LZ77 или LZSS с кодированием Хаффмана.

DEFLATE64

Патентованная вариация DEFLATE с увеличением словаря до 64 Кб. Сжимает лучше и быстрее, но не используется повсеместно, т.к. не является открытым.

Алгоритм Лемпеля-Зива-Сторера-Цимански был представлен в 1982 году. Улучшенная версия LZ77, которая просчитывает, не увеличит ли размер результата замена исходных данных кодированными.

До сих пор используется в популярных архиваторах, например RAR. Иногда – для сжатия данных при передаче по сети.

Был разработан в 1987 году, расшифровывается как «Лемпель-Зив-Хаффман». Вариация LZSS, использует кодирование Хаффмана для сжатия указателей. Сжимает чуть лучше, но ощутимо медленнее.

Разработан в 1987 году Тимоти Беллом, как вариант LZSS. Как и LZH, LZB уменьшает результирующий размер файлов, эффективно кодируя указатели. Достигается это путём постепенного увеличения размера указателей при увеличении размера скользящего окна. Сжатие получается выше, чем у LZSS и LZH, но скорость значительно меньше.

Расшифровывается как «Лемпель-Зив с уменьшенным смещением», улучшает алгоритм LZ77, уменьшая смещение, чтобы уменьшить количество данных, необходимого для кодирования пары смещение-длина. Впервые был представлен в 1991 году в алгоритме LZRW4 от Росса Вильямса. Другие вариации — BALZ, QUAD, и RZM. Хорошо оптимизированный ROLZ достигает почти таких же степеней сжатия, как и LZMA – но популярности он не снискал.

«Лемпель-Зив с предсказанием». Вариация ROLZ со смещением = 1. Есть несколько вариантов, одни направлены на скорость сжатия, другие – на степень. В алгоритме LZW4 используется арифметическое кодирование для наилучшего сжатия.

LZRW1

Алгоритм от Рона Вильямса 1991 года, где он впервые ввёл концепцию уменьшения смещения. Достигает высоких степеней сжатия при приличной скорости. Потом Вильямс сделал вариации LZRW1-A, 2, 3, 3-A, и 4

Вариант от Джеффа Бонвика (отсюда “JB”) от 1998 года, для использования в файловой системе Solaris Z File System (ZFS). Вариант алгоритма LZRW1, переработанный для высоких скоростей, как этого требует использование в файловой системе и скорость дисковых операций.

Lempel-Ziv-Stac, разработан в Stac Electronics в 1994 для использования в программах сжатия дисков. Модификация LZ77, различающая символы и пары длина-смещение, в дополнение к удалению следующего встреченного символа. Очень похож на LZSS.

Был разработан в 1995 году Дж. Форбсом и Т.Потаненом для Амиги. Форбс продал алгоритм компании Microsoft в 1996, и устроился туда работать над ним, в результате чего улучшенная его версия стала использоваться в файлах CAB, CHM, WIM и Xbox Live Avatars.

Разработан в 1996 Маркусом Оберхьюмером с прицелом на скорость сжатия и распаковки. Позволяет настраивать уровни компрессии, потребляет очень мало памяти. Похож на LZSS.

“Lempel-Ziv Markov chain Algorithm”, появился в 1998 году в архиваторе 7-zip, который демонстрировал сжатие лучше практически всех архиваторов. Алгоритм использует цепочку методов сжатия для достижения наилучшего результата. Вначале слегка изменённый LZ77, работающий на уровне битов (в отличие от обычного метода работы с байтами), парсит данные. Его вывод подвергается арифметическому кодированию. Затем могут быть применены другие алгоритмы. В результате получается наилучшая компрессия среди всех архиваторов.

LZMA2

Следующая версия LZMA, от 2009 года, использует многопоточность и чуть эффективнее хранит несжимаемые данные.

Статистический алгоритм Лемпеля-Зива

Концепция, созданная в 2001 году, предлагает проводить статистический анализ данных в комбинации с LZ77 для оптимизирования кодов, хранимых в словаре.

Алгоритмы с использованием словаря

Алгоритм 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:

Лемпель-Зив-Велч, 1984 год. Самый популярный вариант LZ78, несмотря на запатентованность. Алгоритм избавляется от лишних символов на выходе и данные состоят только из указателей. Также он сохраняет все символы словаря перед сжатием и использует другие трюки, позволяющие улучшать сжатие – к примеру, кодирование последнего символа предыдущей фразы в качестве первого символа следующей. Используется в GIF, ранних версиях ZIP и других специальных приложениях. Очень быстр, но проигрывает в сжатии более новым алгоритмам.

Компрессия Лемпеля-Зива. Модификация LZW, использующаяся в утилитах UNIX. Следит за степенью сжатия, и как только она превышает заданный предел – словарь переделывается заново.

Лемпель-Зив-Тищер. Когда словарь заполняется, удаляет фразы, использовавшиеся реже всех, и заменяет их новыми. Не получил популярности.

Виктор Миллер и Марк Вегман, 1984 год. Действует, как LZT, но соединяет в словаре не похожие данные, а две последние фразы. В результате словарь растёт быстрее, и приходится чаще избавляться от редко используемых фраз. Также непопулярен.

Джеймс Сторер, 1988 год. Модификация LZMW. “AP” означает «все префиксы» — вместо того, чтобы сохранять при каждой итерации одну фразу, в словаре сохраняется каждое изменение. К примеру, если последняя фраза была “last”, а текущая – «next”, тогда в словаре сохраняются „lastn“, „lastne“, „lastnex“, „lastnext“.

Вариант LZW от 2006 года, работающий с сочетаниями символов, а не с отдельными символами. Успешно работает с наборами данных, в которых есть часто повторяющиеся сочетания символов, например XML. Обычно используется с препроцессором, разбивающим данные на сочетания.

1985 год, Матти Якобсон. Один из немногих вариантов LZ78, отличающихся от LZW. Сохраняет каждую уникальную строку в уже обработанных входных данных, и всем им назначает уникальные коды. При заполнении словаря из него удаляются единичные вхождения.

Алгоритмы, не использующие словарь

Предсказание по частичному совпадению – использует уже обработанные данные, чтобы предсказать, какой символ будет в последовательности следующим, таким образом уменьшая энтропию выходных данных. Обычно комбинируется с арифметическим кодировщиком или адаптивным кодированием Хаффмана. Вариация PPMd используется в RAR и 7-zip

bzip2

Реализация BWT с открытым исходным кодом. При простоте реализации достигает хорошего компромисса между скоростью и степенью сжатия, в связи с чем популярен в UNIX. Сначала данные обрабатываются при помощи RLE, затем BWT, потом данные особым образом сортируются, чтобы получить длинные последовательности одинаковых символов, после чего к ним снова применяется RLE. И, наконец, кодировщик Хаффмана завершает процесс.

1. Общие сведения о задаче сжатия данных

Задачей сжатия данных является минимизация технических затрат на хранение или передачу данных путем оптимального кодирования источников [1, стр. 75]. Согласно классической схеме системы связи [1, 2], сжатие данных, т.е. более компактное их представление производится в кодере источника, а задачей декодера источника является соответственно восстановление сжатых данных.

Используя материалы [1-3], укажем основные понятия, связанные с задачей сжатия данных.

Несущественная информация — это информация, которой можно пренебречь при передаче. Например, телефонная связь использует полосу частот в диапазоне 3,4 кГц. Все остальные спектральные составляющие речи отбрасываются, при этом существенная часть информации теряется. Ясно, что первоначальный сигнал не может быть восстановлен полностью. В этом случае говорят о кодировании с потерями.

Избыточная информация — неоднократное повторение в сообщении необходимой для приемника информации. Избыточность может быть устранена без потери информации. Если алгоритм кодирования отбрасывает только избыточную информацию, то говорят о кодировании без потерь.

Степень сжатия определяется затратами для передачи или хранения информации без сжатия и затратами с использованием некоторого метода сжатия

Степень сжатия зависит от используемого алгоритма и свойств источника.

Средняя длина кода вычисляется как сумма длин двоичных кодов, взвешенных вероятностью этих кодовых символов:

Коэффициент сжатия, определяющий эффективность сжатия, задается, как отношение числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия.

Коды сжатия можно классифицировать как коды фиксированной и переменной длины, префиксные и непрефиксные коды.

Перечислим, согласно [2], желаемые свойства полезных кодов источника.

Свойство единственности декодирования. Единственным образом декодируемые коды позволяют однозначно отображать сжатые данные в исходные.

Свойство мгновенной декодируемости. Мгновенно декодируемый код – это такой код, для которого граница настоящего кодового слова может быть определена концом настоящего кодового слова, а не началом следующего кодового слова.

Свойство отсутствия префикса. Достаточным (но не необходимым) условием того, что код единственным образом декодируемый, является то, что никакое кодовое слово не является префиксом другого кодового слова. Коды, удовлетворяющие этому условию, называются кодами свободными от префикса или префиксными кодами.

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

Код Хаффмана – это свободный от префикса код, который может давать самую короткую среднюю длину кода для данного входного алфавита. Заметим, что самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника. Алгоритм кодирования Хаффмана может применяться для преобразования между двумя любыми алфавитами, чаще всего его используют для преобразования произвольного алфавита в двоичный [2].

Рассмотрим работу алгоритма Хаффмана на примере.

Пример. Построить двоичный код Хаффмана для представленного в таблице алфавита. В таблице использованы следующие обозначения X_i – i-тый символ алфавита, Р(X_i) – вероятность появления символа X_i.

У порядочим символы алфавита по убыванию вероятностей их появления и сопоставим их ветвям двоичного дерева.

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

Б удем продолжать этот процесс до достижения корня дерева.

После формирования всего дерева пометим ветви, выходящие из всех вершин символами “0” и “1”. Помечать ветви дерева можно произвольным образом, для определенности ветвь, идущую вверх будем помечать символом “1”, а ветвь, идущую вниз – символом “0”.

После обозначения вершин пройдем все возможные пути по дереву от вершины (крайнее правое положение) дерева до его каждой выходной ветви (крайнее левой положение), запоминая встретившиеся двоичные символы. Полученные последовательности будут являться кодами символов входного алфавита.

З начения, характеризующие построенный код Хаффмана, сведем в таблицу следующего вида. В первом столбце перечислим все символы алфавита (X_i); во втором столбце расположим соответствующие вероятности появления символов входного алфавита Р(X_i); в третьем столбце запишем кодовые слова, соответствующие символам входного алфавита; в последнем – четвертом столбце поместим значения .

Длина кода, , бит

Среднюю длину кода вычислим по формуле:

Результирующее значение =1,94 бит на знак, что не означает, что для передачи одного символа необходимо передавать нецелое число бит, а означает, что для передачи 100 входных символов из алфавита мощностью 4 потребуется примерно 194 бита.

2. Идеи построения алгоритма сжатия Лемпеля-Зива

Существует большое количество модификаций алгоритма Лемпеля-Зива [1, 3], все модификации этого алгоритма основаны на принципе динамических словарей. Перечислим основные идеи, на которых базируется алгоритм Лемпеля-Зива.

1. Каждая очередная закодированная последовательность символов добавляется к раннее закодированным символам таким образом, что вместе с ними она образует разложение всей принятой и переданной информации на несовпадающие между собой фразы. Такое разложение хранится в памяти и используется в дальнейшем в качестве словаря.

2. Кодирование осуществляется при помощи указателей на фразы из уже сформированного словаря фраз. Кодирование является динамической процедурой, ориентированной на блоки. Сам процесс кодирования может быть дополнен скользящими окнами, содержащими текущий словарь фраз, и Look-ahead буфером.

3.1. Zip–модификация алгоритма Лемпеля-Зива

Согласно [3] процесс кодирования начинается с пустого словаря, так что первые элементы являются позициями, которые не ссылаются на более ранние позиции. В словаре рекуррентно формируется выполняемая последовательность адресов. Каждому адресу соответствует последовательность из элементов алфавита. Закодированные данные хранятся в виде пакетов со следующей структурой:

<ссылка на адрес словаря, следующий знак данных>.

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

Пример. Используя Zip–модификацию алгоритма Лемпеля-Зива, закодировать последовательность

Результат кодирования будем записывать в таблицу, содержащую три строки. В первой строке – адрес пакета данных, во второй – пакет данных в виде <адрес словаря, следующий знак данных>, в третьей – содержимое текущего пакета данных.

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

Сформируем первый пакет данных и добавим его в словарь. Первый символ кодируемой последовательности (*) – «а» запишем по первому адресу. Пакет данных будет иметь вид: <0,a>. При формировании текущего пакета данных не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, значение следующего знака данных равно «а», – символу, который необходимо записать в словарь.

Пакет данных: <0,a>

Второй символ кодируемой последовательности (*) – «в» запишем по второму адресу. Пакет данных будет иметь вид: <0,в>. При формировании этого пакета данных также не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, а значение следующего знака данных равно «в», – символу, который необходимо записать в словарь.

Пакет данных: <0,в>

Просматриваем далее входную последовательность abaababbbbbbbabbbba. Будем отмечать в ней подчеркиванием уже закодированные символы. Следующий из незакодированных символов – «а» уже встречался в словаре, поэтому теперь в один пакет запишем объединение этого символа со следующим

Пакет данных: <1,а>

Запись <1,а> в пакете данных означает, что необходимо взять символ(ы) записанные по адресу 1 и добавить к ним символ «а». Далее будем аналогичным образом продолжать процесс кодирования, каждый раз просматривая динамически формируемый словарь справа налево, т.е. с последней записи к первой. Оформим процесс кодирования в таблицу.

Сжатие двоичного кода. Для того чтобы сэкономить место на внешних носителях (винчестерах, флэш дисках) и ускорить передачу информации по компьютерным. — презентация

Презентация на тему: » Сжатие двоичного кода. Для того чтобы сэкономить место на внешних носителях (винчестерах, флэш дисках) и ускорить передачу информации по компьютерным.» — Транскрипт:

1 Сжатие двоичного кода

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

5 Коэффициентом сжатия называют отношение длины кода в байтах после сжатия к его длине до сжатия. Раскодирование (распаковка) текста производится с помощью двоичного дерева кодирования Хаффмана. Деревом называется графическое представление (граф) структуры связей между элементами некоторой системы. Двоичным деревом называется дерево, в котором любая вершина, имеет не более двух потомков. Корнем дерева называется единственная вершина, не имеющая родительской вершины. Листьями дерева называются вершины, не имеющие потомков.