91580

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

Доклад

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

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

Русский

2015-07-21

36.82 KB

0 чел.

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

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

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

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

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

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

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


 

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

32964. Гидравлический расчет сложного трубопровода 195.45 KB
  Трубопроводы нашли широкое распространение во многих областях современной жизни, в том числе и в нефтегазовой отрасли. Поэтому диаметр, длина, шероховатость и другие параметры варьируются в широких пределах. Вследствие этого, существуют различные классификации трубопроводов. Учитывая специфику данной работы, рассмотрим деление на простые и сложные трубопроводы.
32966. INFO ОБЩ-ВО: ИСТОКИ, СУЩНОСТЬ, ПЕРСПЕКТИВЫ ЭВОЛЮЦИИ (М.КАСТЕЛЬС. INFO ЭПОХА: ЭКОНОМИКА, ОБЩ-ВО И КУЛЬТУРА) 17.68 KB
  INFO ОБЩВО: ИСТОКИ СУЩНОСТЬ ПЕРСПЕКТИВЫ ЭВОЛЮЦИИ М. INFO ЭПОХА: ЭКОНОМИКА ОБЩВО И КУЛЬТУРА М.Кастельс: концепция info общва: 1. в постиндустриальный info мир вступили США Япония ведущие европейские страны а также некоторые страны АТР.
32967. ИНДУСТРИАЛЬНОЕ И ПОСТИНДУСТРИАЛЬНОЕ ОБЩ-ВО. СУЩНОСТЬ СОВРЕМЕННОЙ ТЕХНОЛОГИЧЕСКОЙ РЕВОЛЮЦИИ (Д.БЕЛЛ. ГРЯДУЩЕЕ ПОСТИНДУСТРИАЛЬНОЕ ОБЩ-ВО. ОПЫТ СОЦ. ПРОГНОЗИРОВАНИЯ) 17.66 KB
  ИНДУСТРИАЛЬНОЕ И ПОСТИНДУСТРИАЛЬНОЕ ОБЩВО. ГРЯДУЩЕЕ ПОСТИНДУСТРИАЛЬНОЕ ОБЩВО. формируется новое общво: постиндустриальное info посткапиталистическое технотронное технологическое супериндустриальное постмодерное общво знаний и т. Постиндустриальное общво это общво в экономике которого в result НТР и существенного роста доходов населения приоритет перешёл от преимущественного производства товаров к производству услуг.
32968. ИНТЕГРАТИВНЫЙ ХАР-Р СОЦ.-ГУМАНИТАРНОГО ЗНАНИЯ 16.07 KB
  ИНТЕГРАТИВНЫЙ ХАРР СОЦ.ГУМАНИТАРНОГО ЗНАНИЯ В сфере социальногуманитарного знания особое место принадлежит философии. экономисты считают экономическую теорию царицей соц. Философия хозва формирует реальное мысленное пространство которое обеспечивает эффективное научное познание нацеленное на комплексное социоэкономическое объяснение явлений и процессов системный подход учёт конкретной специфики той или иной страны.
32969. ИСТОКИ ПОСТНЕКЛАССИЧЕСКОГО ЭТАПА РАЗВИТИЯ НАУКИ (И.ПРИГОЖИН, И.СТИНГЕРС. ВЫЗОВ НАУКИ) 14.72 KB
  ИСТОКИ ПОСТНЕКЛАССИЧЕСКОГО ЭТАПА РАЗВИТИЯ НАУКИ И. ВЫЗОВ НАУКИ Зап. наука: высшая задача науки – сформулировать общие схемы которые бы совпадали с идеалом рационального. Но это привело не к замедлению прогресса науки а способствовало появлению новых концептуальных структур наука выполняет некую универсальную миссию затрагивающую взаимодействие человека и природы и человека с человеком в наши дни основной акцент научных исследований переместился с субстанции на отношение связь время Больцман: м у вероятностью и необходимостью...
32970. ИСТОРИЯ И ФИЛОСОФИЯ НАУКИ КАК МЕЖДИСЦИПЛИНАРНАЯ ДИСЦИПЛИНА 23.23 KB
  ИСТОРИЯ И ФИЛОСОФИЯ НАУКИ КАК МЕЖДИСЦИПЛИНАРНАЯ ДИСЦИПЛИНА Философия входит в жизнь человека очень рано задолго до того как сложится о ней самое 1st элементарное представление навеянное случайными встречами и знакомствами. Философия науки – раздел философии изучающий понятие границы и методологию науки. Периоды преднауки появление элементов научности: докть обоснование систематизация IVв. Дальше начинается триумфальный процесс развития науки производится большое колво открытий.
32971. МЕТОДОЛОГИЧЕСКОЕ ЗНАНИЕ И ЕГО УРОВНИ 14.53 KB
  Термин методология применяется не только к научнопознавательной деятти но и к любой др. деятти человека. Методология познание способа человеческой деятти научной художественной производственной. сферах деятти и их совершенствование.
32972. МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ. ЭМПИРИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ 22.52 KB
  МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ. ЭМПИРИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ Метод греч. Методы естественных наук подразделяют на: 1. методы изучения неживой природы и методы изучения живой природы.