91580

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

Доклад

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

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

Русский

2015-07-21

36.82 KB

0 чел.

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

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

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

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

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

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

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


 

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

13100. Классный час на тему «Что значит быть настоящим другом?» 51.5 KB
  Классный час на тему Что значит быть настоящим другом. 4й класс Цель: помочь детям разобраться в том каким должен быть настоящий друг. Задачи: определить важные для дружбы нравственные качества и содействовать их формированию; провести самооценку учащимися
13101. Сабақтың тақырыбы: БАЛА АБАЙ. 80.5 KB
  7 Ана тілі 2сынып Сабақтың тақырыбы: БАЛА АБАЙ. Сабақтың мақсаты: 1. Оқушыларды қазақтың классик ақыны Абай Құнанбаевтың өмірімен толығырақ таныстыру. 2. Мәтіндегі негізгі идеяны ұғындыру. 3. Әр түрлі ой дамыту стратегиялары арқылы өздік жұмыс і
13102. Сабақтың тақырыбы: ҚАНАҒАТ ҚАРЫН ТОЙҒЫЗАР (ел аузынан) 76.5 KB
  8 Ана тілі 3сынып Сабақтың тақырыбы: қанағат қарын тойғызар ел аузынан. Сабақтың мақсаты: 1. Тақырыптың идеясын ашу қанағатшыл шыдамды болуға үйрету. 2. Өтілген сабақ пен жаңа сабақты байланыстыру арқылы шығармашылық ойлау қабілетін дамыту...
13103. Сабақтың тақырыбы: ЕР ТАРҒЫН 47.5 KB
  4 Ана тілі 4сынып Сабақтың тақырыбы: ЕР ТАРҒЫН Сабақтың мақсаты: Батырлар жыры туралы оқушыларға жанжақты түсінік беру. Елін қорғау Отанын халқын сүю батырлар жырының басты қасиеттері екендігін оқушыларға ұғындыру. Ер Тарғынның ...
13104. Сыныптарға арналған «Соңғы қоңырау» салтанатты жиынының сценарийі 59.5 KB
  11 сыныптарға арналған Соңғы қоңырау салтанатты жиынының сценарийі. 2008 жыл. Фанфары Жүргізушілер шығады: Медетов М.О. және Құдайбергенова Шұғыла. Мият: Армысыздар ұстаздар оқушылар Қош бол алтын ұя мектебім атты салатанатты жиынға жиналған қауым.
13105. 1917-1941 ж.ж.кеңес мектебі мен педагогикасы 83.5 KB
  1917-1941 ж.ж.кеңес мектебі мен педагогикасы. Мектептің революциялық қайта құрылуы және алғашқы қадамдары. Халық ағарту ісінің барлық жүйесін қайта құру революцияның алғашқы күндерінен басталады. 1917 жылы 9 қарашадағы декрет бойынша Ағарту ісінің мемлекеттік комисс...
13106. 1941-1970 жж. кеңес мектебі мен педагогикасы 99.5 KB
  1941-1970 жж. кеңес мектебі мен педагогикасы. Ұлы Отан соғысы жылдарындағы мектеп және педагогика. Кеңес халқының фашистік Германияға қарсы соғысы көптеген материалдық күшті керек етті. Еңбекке жарайтын миллиондаған адамдарды бейбіт еңбектен бөлді. Соғыстың ауыр зар...
13107. 1980-1991 ж.ж. Кеңес мектебі мен педагогикасы 57 KB
  1980-1991 ж.ж. Кеңес мектебі мен педагогикасы. Жалпы білім беретін және кәсіби мектеп реформасының егізгі бағыттары 1984. Білім берудің жаңа сипаты мен түрлері дамуы. Жаңашыл мұғалімдердің ғылымитеориялық және әдістемелік ізденісі. Жалпы білім б...
13108. Коменскийдің Ян Амос педагогикалық қызметі мен теориясы. (1592-1670жж) 102.5 KB
  Ян Амос Коменскийдің педагогикалық қызметі мен теориясы. 1592-1670жж. Я.А.Коменскийдің қысқаша ғұмырнамалық деректері. Я.А.Коменскийдің көзқарасының қалыптастыруы. Табиғатқа сәйкес тәрбиелеу қағидасы туралы. Жас кезеңдері. Мектеп жүйесі және оқытудың маз...