91580

Как сжимают информацию без потерь

Доклад

Информатика, кибернетика и программирование

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

Русский

2015-07-21

36.82 KB

0 чел.

Как сжимают информацию без потерь

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

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

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

Как известно, любая информация в компьютере обрабатывается в виде последовательности чисел. При этом если речь идет о звуковой или графической информации, можно найти определенные закономерности. Так, в звуковом файле встречаются промежутки, соответствующие небольшой громкости, а в графическом - низкой освещенности. Если числа, представляющие звук и изображение, имеют прямую зависимость соответственно от громкости и яркости, то в файле очевидны длинные промежутки, где величины чисел будут небольшими и для их представления потребуется меньше двоичных разрядов. При методе сжатия информации, называемом блочным, такие участки объединяются в блоки, и в начале каждого из них указывается, сколько разрядов отводится на представление каждого числа. Хотя блочный метод прост в реализации, но степень сжатия сильно зависит от вида информации. Примером использования блочного метода является графический формат PCX.

Наиболее эффективным методом сжатия информации без потерь является метод Лемпелла-Зива (ЛЗ), названный так в честь двух израильских математиков, предложивших его в 1977 году. Основан он на том, что в каждом компьютерном файле, как правило, выделяется несколько часто встречающихся двоичных комбинаций. Например, в тексте программы на языке программирования высокого уровня постоянно будут встречаться комбинации символов (а в файле с текстом - комбинации соответствующих байт), относящиеся к операторам, процедурам и функциям языка. Можно выделить такие комбинации, составить их список и соответственно подобрать им какие-то более короткие комбинации. Затем заменить длинные комбинации короткими, а в файл записать таблицу, по которой осуществлялась замена. Распаковка файла сводится к операции замен, обратных производимым при записи.

Метод Лемпелла-Зива имеет аналог в повседневной жизни. Каждый, кому приходилось иметь дело с научно-технической литературой, обращал внимание на аббревиатуры, заменяющие длинные слова. В итоге текст будет более компактным и удобочитаемым, а перечень использованных сокращений обычно выносят в начало или конец книги. Читатель либо сначала запоминает список аббревиатур, либо, увидя аббревиатуру, обращается к ее пояснению. Похожим образом действует компьютер, распаковывая файл, архивированный по методу Лемпелла-Зива. Сложности возникают при сжатии информации. Когда человек распределяет аббревиатуры по тексту, он интуитивно понимает, какие слова можно представить в виде сокращений. Для компьютера, которому не свойственна интуиция, объяснить задачу гораздо труднее. Слишком большое число аббревиатур приводит к тому, что длинный "список сокращений" частично поглощает выигрыш от замены длинных слов на более короткие. Заслуга Лемпелла и Зива состоит в том, что они создали четкий алгоритм, сжимающий информацию таким способом. Метод Лемпелла-Зива оказался на практике высокоэффективным для различных видов информации. Примером использования метода Лемпелла-Зива является графический формат GIF.


 

А также другие работы, которые могут Вас заинтересовать

75766. Основные задачи БЖД 12.77 KB
  Основные задачи БЖД Безопасность жизнедеятельности представляет собой область научных знаний охватывающих теорию и практику защиты человека от опасных и вредных факторов во всех сферах человеческой деятельности сохранение безопасности и здоровья в среде обитания. Эта дисциплина решает следующие основные задачи: идентификация распознавание и количественная оценка негативных воздействий среды обитания; защита от опасностей или предупреждение воздействия тех или иных негативных факторов на человека; ликвидация отрицательных последствий...
75767. Опасность – центральное понятие БЖД 14.38 KB
  Опасность центральное понятие БЖД Опасность центральное понятие в науке БЖД под которым подразумеваются любые явления процессы объекты свойства предметов способные в определенных условиях причинить ущерб здоровью и жизни человека. Опасность хранят все системы имеющие энергию химически или биологически активные компоненты а так же свойства несоответствующие условиям жизнедеятельности человека. Потенциальный означает опасность возможная скрытая отложенная на потом. Признаками определяющими опасность являются: ...
75768. Номенклатура опасностей. Идентификация опасностей 16.99 KB
  Номенклатура опасностей. Идентификация опасностей. В процессе идентификации выявляются номенклатура опасностей. Главное в идентификации заключается в установлении возможных причин проявления опасностей.
75769. ДИАГНОСТИКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ МЛАДШИМИ ШКОЛЬНИКАМИ СОДЕРЖАТЕЛЬНОЙ ЛИНИИ «ЧЕЛОВЕК-ОБЩЕСТВО» 179 KB
  Система диагностики результатов освоения младшими школьниками образовательной области Окружающий мир. Оценивание как основой метод диагностики результатов освоения содержательных линий. Оценивание метапредметных результатов освоения содержательных линий образования.
75770. Методы теории вероятностей в анализе безопасности и надежности летательных аппаратов 1.04 MB
  Теория вероятностей возникла в середине 17 в. То, что случайные явления представляют собой не исключение, а правило в реальном мире, было замечено еще в древности. Об этом словами Лукреция Кара прекрасно говорит Альфред Реньи.
75771. НОРМАТИВНО-ПРАВОВОЕ РЕГУЛИРОВАНИЕ АВТОРСКОГО ПРАВА НА ИНТЕРНЕТ-САЙТ 198 KB
  Цели и задачи работы. Целью данной работы является формирование целостного представления о сети Интернет как о явлении, имеющем правовое значение, выявление основополагающих моментов в регулировании ее деятельности. Достижение этой цели зависит от решения следующих задач...
75774. Синтез алгоритмов системы ручного и автоматического управления транспортного самолёта ИЛ-76 7.84 MB
  Аэродинамические характеристики определяющие устойчивость и управляемость самолёта Ил76 на типовых режимах полёта; Анализ продольных и боковых АДХ для транспортного самолёта Ил76 определение положения аэродинамического фокуса...