91580

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

Доклад

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

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

Русский

2015-07-21

36.82 KB

0 чел.

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

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

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

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

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

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

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


 

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

43816. Разработка рыночной стратегии ООО «Империя» на мебельном рынке г. Барнаула 620.59 KB
  Стратегическое планирование – это система «разумной бюрократии», позволяющая определить и связать воедино ключевые направления деятельности предприятия, разбить их на отдельные задачи, распределить ответственность и контролировать выполнение.
43817. Современные молодежные субкультуры деструктивного характера как объект миссионерско-реабилитационной деятельности Русской Православной Церкви 4.14 MB
  Сравнительные социально-психологические характеристики тоталитарных секты и молодежных деструктивных групп на примере субкультур готики и эмо. Процесс образования малых групп включает в себя психологические механизмы которые делают группу группой а именно групповое давление на индивида используется в сектах групповая сплоченность характерно для готов и эмо и разного толка движений лидерство развито в сектах и готической субкультуре принятие групповых решений присуще эмо субкультуре. Для координации деятельности в группе в...
43818. Создание 3D модели технологической оснастки в программ Solid Works 9.32 MB
  Так же существуют несколько САПР систем, используемых на производстве. Наш выбор пал на Систему автоматизированного проектирования- CATIA, французской фирмы Dassault Systèmes. Данная программа является лидером на рынке в сегменте САПР систем, и используется во многих крупных компаниях, таких как: Boeing, Airbus, BMW, Mercedes, Renault
43820. Физико-химические свойства никелевых покрытий, полученных из электролитов с наноуглеродными добавками 486.37 KB
  В работе было проведено исследование влияния добавок УДАТАН и АСМ на кинетику процесса никелирования на микротвердость и износостойкость покрытия. Анализ полученных результатов показал эффективность применения наноуглеродных добавок для повышения твердости и износостойкости никелевого покрытия.
43821. Проект реконструкции участка по улице Октябрьской Советского района г.Орла 3.78 MB
  Орёл расположен в центральной части Среднерусской возвышенности в пределах степной и лесостепной зон. Климат умеренно - континентальный. Средняя температура января - минус 8 - 10 градусов. Ноябрь, декабрь и январь являются самыми пасмурными месяцами.
43822. Оцінка і узагальнення інформації щодо використання методів прогнозування в процесі прийняття управлінських рішень 774.66 KB
  У давнину люди приймали рішення покладаючись на інтуїтивні почуття прогнози астрологів. Для здійснення функцій регулювання економічними процесами необхідно знати майбутнє багатьох економічних явищ з тим щоб прийняти правильне рішення у теперішньому. У ході оцінки альтернатив і прийнятті рішення менеджер повинен прогнозувати можливі результати в різних обставинах. Менеджерська діяльність базується на підготовці та здійсненні необхідного управлінського рішення на основі його економічного обґрунтування і подальшій послідовній систематизації...
43823. Расчет схемы лазерной охранной системы 135.77 KB
  Но в любом случае охранное устройство на какой бы элементной базе не было построено состоит из двух модулей: приемник и передатчик. Схемное построения этих модулей могут быть различны, я в качестве темы для разработки взял схему охранной сигнализации которая обеспечивает контроль окружающего пространства с помощью лазерного луча.
43824. Разработка автоматизированной системы по работе с клиентами для технического отдела ОАО «ЮТК», г. Ессентуки 832.39 KB
  Услуги связи по передаче данных за исключением услуг связи по передаче данных для целей передачи голосовой информации. Основная ценность и полезность данных документов заключается в том что они регламентируют ключевые работы и процессы. Ессентукский филиал ОАО ЮТК оказывает клиентам следующие виды услуг: услуги местной телефонной связи; дополнительные виды обслуживания ДВО; услуги внутризоновой телефонной связи; услуги телеграфной связи; услуги проводного вещания; услуги передачи данных телематические...