91580

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

Доклад

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

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

Русский

2015-07-21

36.82 KB

0 чел.

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

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

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

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

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

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

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


 

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

18431. Средства измерения и представления информации 31 KB
  Лекция 15. Средства измерения и представления информации. Средства измерения и представления информации. Устройства данной группы предназначенные для визуального представления информации человекуоператору и для выдачи сигналов в группу специальных средств обр
18432. Аналоговые и цифровые вторичные приборы ГСП 67 KB
  Лекция 16. Аналоговые и цифровые вторичные приборы ГСП. Приборы выдачи информации. Различают аналоговые и дискретные методы выдачи измерительной информации. В обоих случаях простейшей формой выдачи является отображение результатов измерения на визуально считыв
18433. Классификация и общая характеристика средств управления 41 KB
  Лекция 17. Классификация и общая характеристика средств управления. Для эффективного использования полученной ИИС информации об объекте управления необходимо ее проанализировать выработать по определенным алгоритмам соответствующие команды и передать их к объек
18434. Законы регулирования, регуляторы, исполнительные механизмы и регулирующие органы 106 KB
  Лекция 18. Законы регулирования регуляторы исполнительные механизмы и регулирующие органы. Промышленные автоматические регуляторы. Одной из основных частей низовой локальной системы автоматического регулирования САР является регулятор. В общем случае регулято
18435. Программно-технические комплексы 76.5 KB
  Лекция 19. Программнотехнические комплексы. В настоящее время автоматизация большинства технологических процессов осуществляется на базе универсальных микропроцессорных контроллерных средств которые в России получили название программнотехнических комплексо
18436. Электрические исполнительные механизмы 46.5 KB
  Лекция 20. Электрические исполнительные механизмы. Назначение. Механизмы исполнительные электрические однооборотные постоянной скорости МЭО и МЭОФ предназначены для перемещения регулирующих органов в системах автоматического регулирования технологическими пр
18437. Регулирующие органы 91 KB
  Лекция 21. Регулирующие органы. Регулирующие органы служат для изменения количества вещества или энергии подводимых к объекту регулирования или отводимых от него по определенной программе или поддержание на определенном уровне. Чаще всего с помощью регулирующих
18438. История языка PHP. Установка ПО для работы с PHP 780 KB
  Серверные технологии разработки webсайтов История языка PHP. Установка ПО для работы с PHP. История PHP Язык PHP был разработан как инструмент для решения чисто практических задач. Его создатель Расмус Лердорф хотел знать сколько человек читают его onlineрезюме и написал ...
18439. Конструкции и типы данных PHP 223.5 KB
  Серверные технологии разработки webсайтов Конструкции и типы данных PHP Основной синтаксис Первое что нужно знать относительно синтаксиса PHP – это то как он встраивается в HTMLкод как интерпретатор узнает что это код на языке PHP. В предыдущей лекции мы уже говорили об