Алгоритмы kwe

В основу алгоритмов кодирования по ключевым словам (KWE = Keyword Encoding) положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово (последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца). Результат кодирования сводится в таблицу, которая прикладывается к сжатому коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать двухбайтную кодировку слов. Образующиеся при этом пары байтов называют токенами.

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

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

Словарные и словарно-статистические алгоритмы сжатия

В 1977 году израильские ученые А.Лемпел и Я.Зив опубликовали работу [], в которой привели разработанный ими алгоритм сжатия данных, названный позже LZ. На основе этого алгоритма в дальнейшем было разработано множество алгоритмов, учитывающих технические возможности компьютеров. В алгоритмах LZ учитываются корреляционные связи между символами, что позволяет значительно увеличить коэффициент сжатия.

Сущность алгоритма сжатия данных LZ состоит в том, что повторяющиеся последовательности символов заменяются указателями на позиции, где они в тексте уже ранее появлялись. Одной из форм такого указателя может быть пара (n,m), которая ссылается на последовательность символов длиной m символов, начинающуюся с позиции n. В большинстве реализаций алгоритма Лепеля-Зива позиция в паре кодируется как смещение (разность) между позициями кодируемой строки и строки, на которую произведена ссылка.

Из-за ограниченного объема оперативной памяти компьютера обычно используется вариант алгоритма Лемпеля-Зива со скользящим окном, когда максимальное значение смещения ограничено некоторым значением.

Сжатие данных происходит следующим образом. В сжатые данные выдаются либо символы сжимаемых данных, либо ссылки на уже просмотренную часть сообщения. Эти ссылки указывают, что текущие символы некоторым количеством m совпадают с теми, что уже были прочитаны, начиная с позиции n. Распаковка начинается сначала сообщения.

Алгоритмы сжатия с потерями

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

Алгоритмы сжатия растровых статических изображений

Изображение – своеобразный тип данных, характеризуемый тремя особенностями.

1. Изображение обычно требует для хранения гораздо большего объема памяти, чем текст. Так, скромная не очень качественная иллюстрация в книге размером 500х800 точек занимает 1,2 Мбайта – столько же, сколько художественная книга из 400 страниц. Английскую пословицу «одна картина стоит тысячи слов» можно отнести к изображениям с низким разрешением, поскольку при высоком разрешении для хранения изображения требуются миллионы машинных слов.

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

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

Для сжатия изображений можно использовать и алгоритмы сжатия без потерь:

универсальные (RLE, LZW, алгоритм Хаффмена с фиксированной таблицей CCITT Group3);

специально разработанные алгоритмы сжатия изображений без потерь (JBIG – разработан группой экспертов Joint Bi-Level Experts Group специально для сжатия 1-битовых черно-белых изображений, получаемых при сканировании документов, передаче факсов; Lossless JPEG – разработан группой экспертов в области фотографии Joint Photographic Experts Group для сжатия без потерь полноцветных 24-битовых изображений или 8-битовыхизображений в градациях серого).

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

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

В настоящее время известны следующие группы алгоритмов сжатия с потерями статических изображений: алгоритмы, использующие двумерные дискретные ортогональные преобразования с разбиением изображения на отдельные матрицы (например, JPEG), алгоритмы рекурсивного (wavelett) сжатия (например, JPEG2000), алгоритмы фрактального сжатия.