27. Кодирование по алгоритму Хаффмана. В чем суть

Кодирование Хаффмана – это алгоритм сжатия данных, который формулирует основную идею сжатия файлов. 

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

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

28. Сжатие с потерями jpeg. Достоинства и недостатки.

Алгоритм сжатия JPEG позволяет регулировать соотношение между степенью сжатия файла и качеством изображения. Применяемые методы сжатия основаны на удалении «избыточной» информации.

Оперирует алгоритм областями 8x8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении.

Достоинства формата JPEG:

1. Главным козырем является его универсальность. Его распознает практически каждое воспроизводящее устройство и поддерживают все популярные операционные системы.

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

3. Фотосъемка в стандарте JPEG позволяет процессору камеры производить обработку и сохранение фотографий гораздо быстрее и с меньшими энергозатратами по сравнению со съемкой в RAW-формате.

4. Наконец, JPEG по-прежнему остается идеальным форматом для передачи графических изображений по сети Интернет. Легкие файлы экономят время и сетевой трафик, затрачиваемые на пересылку и просмотр изображений. Поэтому стандарт активно используется на форумах, в соцсетях и на сайтах.

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

Недостатки формата JPEG

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

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

3. Еще одной проблемой использования JPEG при работе с фотоизображениями является невозможность сохранения слоев и каналов для дальнейшей работы с ними.

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