35.Алгоритмы сжатия изображений без потерь.

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

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

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG, используют только сжатие без потерь; тогда как другие (TIFF, MNG) или GIF могут использовать сжатие как с потерями, так и без.

Сжатие способом кодирования серий (RLE)

 Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE).

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

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

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.

Недостатком метода RLE является достаточно низкая степень сжатия.

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch — LZW)

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

Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования.

Алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые гнезда в конец словаря.

Алгоритм сжатия работает примерно так: Начните с нулевой строки. Прочитайте символ, и добавьте его к строке. Если строка уже находится в таблице, продолжайте чтение, пока вы не получите строку, которой нет в таблице. Добавьте эту строку к таблице строк. Пишите код для последней известной строки, которая соответствует выходу. Используйте последний символ в качестве основы для новой строки, и продолжайте чтение, пока вы не исчерпаете весь ввод.

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

Кодирование Хаффмена работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление - алфавит ASCII - использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.

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

С помощью этой информации о вероятностях компрессор и декомпрессор могут сконструировать кодирующее дерево. Кодирующее дерево является двоичным деревом с одним листом для каждого символа. Чтобы построить дерево, компрессор начинает с двух символов наименьшей вероятности. Затем он объединяет их как два листа двумя ветвями в узел; этому узлу, в свою очередь, назначается сумма двух вероятностей. Компрессор затем рассматривает этот узел вместе с оставшимися символами в списке вероятностей, и снова выбирает два наименее вероятных элемента. Он продолжает строить и объединять узлы, пока не построит единое дерево с вероятностью корня, равной 1.

Полученное дерево имеет листья с различным расстоянием от корня. Листья, которые представляют символы с наивысшей вероятностью, самые близкие к корню, тогда как символы с наименьшей вероятностью вынесены подальше.

Для кодировки символа компрессор находит путь от корня дерева к листу символа. Предположим, что компрессор хочет закодировать букву s. Он начинает с листа, соответствующего букве s, и переходит в родительский узел, отмечая при этом, по какой ветви он про шел (по 0 или по 1). Он продолжает идти вверх по дереву, пока не достигнет корня. Список ветвей в обратном порядке описывает путь от корня до s: это и есть код Хаффмена для этого символа.

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