91580

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

Доклад

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

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

Русский

2015-07-21

36.82 KB

0 чел.

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

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

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

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

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

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

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


 

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

42172. ИССЛЕДОВВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПОСЛЕДОВАТЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО И ИНДУКТИВНОГО СОПРОТИВЛЕНИЙ 299.5 KB
  Экспериментальное исследование характера изменения тока мощности и падений напряжений на участках последовательной цепи состоящей из активного и индуктивного сопротивлений а также построение круговой диаграммы. При прохождении синусоидального тока по цепи изображенной на рис.1б ток в любом сечении цепи один и тот же а общее напряжение согласно второму закону Кирхгофа равно геометрической сумме падений напряжений на...
42173. ИССЛЕДОВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПОСЛЕДОВАТЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО, ИНДУКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ. РЕЗОНАНС НАПРЯЖЕНИЙ 271.5 KB
  РЕЗОНАНС НАПРЯЖЕНИЙ Цель работы: Исследование явления резонанса напряжений построение резонансных кривых и векторных диаграмм.1 следует иметь в виду что ток в любом элементе схемы один и тот же а питающее напряжение согласно второму закону Кирхгофа равно алгебраической сумме мгновенных значений напряжений на отдельных элементах схемы: 4.2 приведены векторные диаграммы напряжений и токов схемы рис. Ток совпадает по фазе с напряжением угол  = 0 cos = 1 и этот режим называется резонансом напряжений.
42174. ИССЛЕДОВАНИЕ ТЕХНОЛОГИИ ФОРМАТИРОВАНИЯ СЛОЖНЫХ ПО ФОРМАТУ ДОКУМЕНТОВ 654.5 KB
  Рукописные работы дипломные работы курсовые работы рефераты отчёты и пр. Основная часть рукописной работы Раздел 2 следует за титульным листом начинается со страницы № 2 обычно имеет оглавление. Заголовок 1 для глав работы Заголовок 2 для параграфов. Например для форматирования реквизитов Название организации Исполнитель Руководитель работ Название специальности Тема дипломной работы и пр.
42175. ИССЛЕДОВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПАРАЛЛЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ 203 KB
  Общие теоретические сведения В схеме рис.1 Векторная диаграмма этой схемы представлена на рис. Рис. Диаграмма представленная на рис.Ток совпадает по фазе с напряжением . Из точки О1 откладываем отрезок О1К = I2k /mI , по направлению вектора . Отрезок О1К является хордой круговой диаграммы . В масштабе mz откладываем по направлению отрезка О1К отрезок О1А = R2 /mz и из точки А под углом 900 к линии О1К проводим линию изменяющегося параметра AN’. Перпендикуляр, к линии изменяющегося параметра, опущенный из точки О1 совпадает по направлению с хордой.
42176. ИССЛЕДОВАНИЕ ЭЛЕКТРИЧЕСКОЙ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПАРАЛЛЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО, ИНДУКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ. РЕЗОНАНС ТОКОВ 182.5 KB
  Общие теоретические сведения В схеме рис.1 Векторные диаграммы этой схемы при различных значениях емкости С представлена на рис.9 Рис. Если емкость C конденсатора подобрать так чтобы ток полностью компенсировал реактивную составляющую то общий ток будет совпадать по направлению с напряжением рис.
42177. Прилади і методи контролю метеорологічних умов на робочих місцях 99 KB
  Теоретичний вступ До показників які характеризують метеорологічні умови мікроклімат належать: температура відносна вологість швидкість руху повітря теплове випромінювання. Дійсну температуру повітря в робочій зоні визначають за формулою 1: де tч і t0 показники чорного та посрібленого термометрів 0С. Вимірювання температури повітря в приміщенні можна також проводити з допомогою сухого термометра аспіраційного психометра Ассмана. Вимірювання вологості повітря.
42178. Амбулаторно-поликлиническая помощь сельскому населению. Обзор. Состояние, проблемы и перспективы развития в Республике Беларусь 258 KB
  При этом в настоящее время существуют различны, иногда противоположные, мнения относительно действующей организационной модели сельского здравоохранения. Рядом автором она признается несовершеннолетней: недостаточная мощность организаций здравоохранения села рассматривается
42180. ИСПОЛЬЗОВАНИЕ ТЕХНОЛОГИИ «ПРИНЯТИЕ РЕШЕНИЙ» ПРИ РЕШЕНИИ ЗАДАЧ СРЕДСТВАМИ ТАБЛИЧНОГО ПРОЦЕССОРА 293 KB
  Найдите решения уравнения fx=0 с точность до 001 на отрезке [;b] используя опцию Подбор параметра. № варианта Функция fx Отрезок [;b] Шаг h fx = 3x52x4x36x2x4 [2;5] 05 fx = 3x5x36x2x4 [2;5] 05 fx = 2x56x4x3x2x4 [2;5] 05 fx = x39x224x15 [10;10] 05 fx = x23 x 2 [5;5] 05 fx = x36x29x6 [2;5] 05 fx = x36x29x2 [2;5] 05 fx = x39x224x2 [2;5] 05 fx = x33x26 [10;10] 05 fx = x312x245x51 [2;5] 05 fx= x26x8 [2;8] 05 fx =...