Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Девять алгоритмов, которые изменили мир. Остроумные идеи, лежащие в основе современных компьютеров

Сжатие без потери информации: бесплатный сыр бывает не только в мышеловке

Важно понимать, что есть два очень разных вида сжатия: без потери и с потерей информации. Сжатие без потери информации - это самый что ни на есть бесплатный сыр, когда вы действительно получаете кое-что задаром. Алгоритм сжатия без потери информации получает на входе файл, сжимает его в несколько раз, а затем распаковывает, получая в точности исходный файл. Напротив, в случае сжатия с потерей информации файл, получающийся после распаковки, немного отличается от исходного. Сжатие с потерей информации мы обсудим позже, а пока займемся сжатием без потерь. В качестве примера рассмотрим исходный файл, содержащий текст этой книги. После его сжатия и последующей распаковки получается тот же самый текст - не изменилось ни одно слово, ни один пробел, ни одна запятая. Но хочется предостеречь вас от чрезмерных восторгов при виде бесплатного сыра: алгоритмы сжатия без потери информации дают впечатляющее уменьшение размера отнюдь не для всех файлов. Однако хороший алгоритм сжатия может существенно уменьшить размеры файлов большинства часто встречающихся типов.

Но откуда берется этот бесплатный сыр? Как это возможно - взять кусок данных (информации) и уменьшить их «истинный» размер, ничего не испортив, так что впоследствии все можно в точности восстановить? Вообще-то, люди так поступают постоянно, даже не задумываясь. Возьмем, к примеру, ваш ежедневник. Для простоты предположим, что вы работаете пять дней в неделю по восемь часов в день и что ежедневник разбит на интервалы по одному часу. Таким образом, в каждом из пяти дней восемь интервалов, а в неделе их всего 40. Чтобы сообщить кому- то о содержании своего расписания на неделю, вы должны передать 40 единиц информации. Но если кто-то хочет по телефону условиться о встрече на будущей неделе, будете вы рассказывать ему, когда у вас есть время, перечисляя все 40 единиц информации? Конечно, нет! Скорее всего, вы скажете что-то типа: «Понедельник и вторник полностью забиты, в четверг и пятницу я занят с часу до трех, а в остальное время свободен». Это и есть пример сжатия данных без потери информации! Ваш собеседник может точно реконструировать сведения о вашей занятости во всех 40 интервалах, хотя вы явно об этом не говорили.

Быть может, вам подумалось, что такой вид «сжатия» - жульничество, потому что опирается н тот факт, что многие фрагменты расписания одинаковы. Точнее, все интервалы в понедельник и вторник заняты, так что их можно описать очень быстро, а вся остальная неделя свободна за исключением двух интервалов, которые тоже легко описать. Да, действительно, это очень простой пример. И тем не менее, сжатие данных в компьютере устроено потому же принципу: основная идея заключается в том, чтобы найти одинаковые фрагменты данных и с помощью того или иного трюка описать их более эффективно.

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

AAAAAAAAAAAAAAAAAAAAABCBCBCBCBCBCBCBCBCBCAAAAAADEFDEFDEF

Если это сразу не очевидно, подумайте, как бы стали диктовать эти данные по телефону. Уверен, что вместо «Л, Л, А, Л, ..., О, Е, F» вы сказали бы что-то вроде «21 раз Л, потом 10 раз ВС, потом еще 6 раз Л, потом 3 раза DEF». А если бы нужно было сокращенно записать эта данные на бумажке, вы, наверное, написали бы что типа «21A,10BC,6A,3DEF». В данном случае вы сжали исходные данные - 56 знаков - в цепочку, содержащую всего 16 знаков. Это меньше трети исходного размера - совсем неплохо! В информатике этот конкретный трюк называется кодированием длин серий, потому что мы кодируем «серию» повторяющихся знаков с помощью ее «длины».

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

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

Поэтому ученые изобрели целый ряд более сложных трюков, основанных на той же идее (найти повторения и эффективно их описать), но работающих и тогда, когда данные не являются соседними. Мы рассмотрим два таких трюка: «то же, что и раньше» и «более короткий символ». Чтобы создать ZIP-файл, ничего, кроме этих двух трюков, не нужно, а формат ZIP чаще всего применяется для сжатия файлов на персональных компьютерах. Поэтому, поняв стоящие за этими трюками идеи, вы будете понимать, как ваш компьютер использует сжатие, - в большинстве случаев.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы