Реферат: Алгоритмы сжатия данных

В этой работе описывается способ улучшения сжатия файлов формата DjVu.
Файл формата DjVu хранит в сжатом виде одно или несколько растровых изображений, при этом, чем больше эти изображения похожи на печатный текст, тем лучше сжатие. В отличие от сжатия алгоритмом JPEG, при сжатии в DjVu края букв не размываются.
Этот формат был придуман и развивался в фирме AT&T между 1995 и 1999 годами. В 2000 году все права были проданы фирме LizardTech. В том же году LizardTech опубликовала часть кода под лицензией GPL. На основе этого кода группа разработчиков, работавшая над этим проектом в AT&T, создала свой независимый вариант (тоже под лицензией GPL), который называется DjVuLibre [1]. В бесплатно доступных программах есть возможности разархивирования и просмотра DjVu-файлов, но только демонстрационное сжатие. К сожалению, эти программы не работают под Windows (разве что через cygwin — перенос среды Unix в Windows). Программы с полными возможностями продаются фирмой LizardTech; с ее сайта [4] можно также бесплатно скачать программу для просмотра DjVu под Windows.
В DjVu-файле хранится отдельно фон, передний план и монохромная маска, определяющая, какие пиксели изображения принадлежат фону, а какие — переднему плану. Фон и передний план кодируются алгоритмом IW44, который, как и JPEG, несколько размывает изображение. Авторы утверждают, что IW44 достигает уменьшения размеров файла в два раза по сравнению с JPEG при том же уровне искажений.
Черно-белая маска кодируется алгоритмом JB2. Этот алгоритм достигает сжатия в 4-6 раз лучшего, чем TIFF-G4 (CCITT/MMR Group 4). Как и в случае со многими другими алгоритмами (МРЗ, например), алгоритм декодировщика определен жестко, однако в алгоритме кодировщика возможны изменения, улучшающие сжатие.
Часть DjVu-файла, сжатая по алгоритму JB2, представляет собой заархивированную последовательность команд. Эти команды могут иметь вид "поставить такое-то изображение в такую-то точку", а могут иметь вид "поставить одно из ранее встречавшихся изображений в такую-то точку". Так как в первом случае команда содержит целое изображение, пусть и заархивированное, а во втором случае — всего лишь номер, то ясно, что чем больше элементарных изображений одинаковы, тем лучше будет сжатие.
Изображение, поступающее на вход кодировщика, разделяется на буквы выделением черных компонент связности. Алгоритм рассчитан на то, что элементарными изображениями будут как раз буквы, и действительно, после такого разбиения обычно остаются отдельные буквы, хотя и куски в 2-3 буквы тоже часто встречаются.
В отсканированном документе, скорее всего, не будет ни одной пары одинаковых изображений букв, хотя будет очень много букв, неотличимых для человека. Если научиться разбивать буквы на классы неотличимости, то можно заменить все буквы в классе на одну. Человек не заметит изменений в изображении, а размер файла сильно уменьшится.
При помощи алгоритмов, разработанных автором, размер файла уменьшается на 55 ± 5% (для страниц, содержащих только текст; рисунки и диаграммы уменьшают этот показатель, так как занимают много места и не сжимаются). Единственная некоммерческая программа для ЛВ2-сжатия, cjb2 из DjVuLibre, достигает уменьшения размера только на 30 ± 5%.
Теперь опишем общую схему алгоритма классификации букв. Предположим, что имеется алгоритм для сравнения пары букв (сам алгоритм будет описан дальше). По паре букв он выдает один из трех ответов — «да», «нет» или «может быть». Ответ «да» означает, что буквы, по мнению алгоритма, эквивалентны; ответ «нет» означает, что алгоритм считает буквы разными, ответ «может быть» означает, что алгоритм не уверен, но лучше считать их разными во избежание ошибок.

Бесплатно скачать реферат "Алгоритмы сжатия данных" в полном объеме