Кажется, не так много — на лазерном диске поместится больше 650 таких картинок. Ну, а если речь идет о фильме? Стандартная скорость кинопроекции — 24 кадра в секунду. Значит на компакт-диске можно записать фрагмент длительностью 650_24=27 секунд. Куда это годится?! А ведь это далеко не единственный случай, когда информации «слишком много». Таким образом, одна из причин использования сжатия данных — желание поместить больше информации в память того же объема. Есть и вторая причина. Сжатие информации ускоряет ее передачу. Но об этом — в следующей главе.
Существует несколько методов сжатия (компрессии10) данных. Все их можно разделить на две группы — сжатие без потерь и с потерями. В первом случае распакованное сообщение точно повторяет исходное. Естественно, так можно обрабатывать любую информацию. Сжатие же с потерями возможно только в тех случаях, когда допустимы некоторые искажения — какие именно, зависит от конкретного типа данных.
Практически все методы сжатия без потерь основаны на одной из двух довольно простых идей.
Одна из них впервые появилась в методе сжатия текстовой информации, предложенном в 1952 году Хафманом. Вы знаете, что стандартно каждый символ текста кодируется одним байтом. Но дело в том, что одни буквы встречаются чаще, а другие реже. Например, в тексте, написанном на русском языке, в каждой тысяче символов в среднем будет 90 букв «о», 72 — «е» и только 2 — «ф». Больше же всего окажется пробелов: сто семьдесят четыре. Если для наиболее распространенных символов использовать более короткие коды (меньше 8 бит), а для менее распространенных — длинные (больше 8 бит), текст в целом займет меньше памяти, чем при стандартной кодировке.
Несколько методов сжатия основаны на учете повторяющихся байтов или последовательностей байт. Простейший из них — RLE11 — широко используется при сжатии изображений. В файле, сжатом таким методом, записывается, сколько раз повторяются одинаковые байты. Например, вместо «RRRRRGGGBBBBBBRRRBBRRRRRRR» будет храниться «5R3G6B3R2B7R»12. Очевидно, что такой метод лучше всего работает, когда изображение содержит большие участки с однотонной закраской.
Другие методы основаны на том, что если некоторая последовательность байт встречается в файле многократно, ее можно записать один раз в особую таблицу, а потом просто указывать: «взять столько-то байт из такого-то места таблицы»13.
Методы сжатия без потерь уменьшают размер файлов не очень сильно. Обычно коэффициент сжатия не превосходит 1/3—1/4. Гораздо лучших результатов можно добиться, используя сжатие с потерями. В этом случае на основе специальных исследований определяется, какой информацией можно пожертвовать.
Например, установлено, что человеческое зрение очень чувствительно к изменению яркости и гораздо меньше, к цветовому тону. Поэтому при сжатии фотографических изображений (и вообще, изображений, в которых нет резких границ между цветами) можно исключить информацию о цвете части пикселов. При распаковке же определять его по соседним. На практике чаще всего применяется метод, использующий более сложную обработку, — JPEG14. Он позволяет сжимать изображение в десятки раз. С учетом особенностей восприятия человеком информации строятся также методы сжатия с потерями видеоизображения (наиболее распространены сейчас методы MPEG15) и звука.
Естественно, сжатие с потерями может использоваться только программами, предназначеными для обработки конкретных видов данных (например, графическими редакторами). А вот методы сжатия без потерь применяются и для любых произвольных файлов (широко известны программы-компрессоры ARJ, ZIP, RAR, StuffIt и др).
Заметим, что не стоит пытаться сжать файлы, которые уже были сжаты: размер их либо уменьшится совсем незначительно, либо даже увеличится.
Примечания
На самом деле, в телевизионном изображении 625 строк.
Compressus (лат.) — сжимание.
Run-Length Encoding (англ.) — кодирование длины последовательности.
Нужна помощь в написании доклада?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
На самом деле, конечно, используются коды цветов и коды, указывающие либо сколько раз повторяется следующий байт, либо сколько следующих байтов — неповторяющиеся.
На этой идее основан широко использующийся для сжатия различных данных метод LZW, названный так по первым буквам фамилий его разработчиков: Lempel, Ziv и Welch.
Joint Photographic Experts Group (англ.) — Объединенная группа экспертов по фотографии, разработавшая одноименный метод сжатия изображений.
Moving Picture Experts Group (англ.) — Группа экспертов по движущимся изображениям
Список литературы
Для подготовки данной работы были использованы материалы с сайта http://macedu.narod.ru