91580

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

Доклад

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

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

Русский

2015-07-21

36.82 KB

0 чел.

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

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

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

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

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

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

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


 

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

35156. Службы каталогов. Пространство имен X.500 и протокол LDAP 30 KB
  Службы каталогов. Основная цель объединения компов в вычислительную сеть это обеспечение совместного использования ресурсов при администрировании вычислительной сети 1 из основных задач это реализация оптимального метода организации общих ресурсов одним из методов эффективного управления множеством ресурсов и множеством потребителей вычислительной сети является разветвленная служба каталогов Служба каталогов – это сетевая служба позволяющая получать доступ без знания точного местоположения ресурса При использовании службы каталогов вся...
35157. Active Directory. Доменная модель службы каталогов. Контроллеры домена. Возможные типы серверов в домене 33.5 KB
  Возможные типы серверов в домене. D помогает управлять как принтерами так и крупными специализированными серверами работающими одновременно в нескольких сетях С помощью D осуществляют манипулирование многими компонентами службы каталогов. В D каждый сервер содержит не менее 3 КИ: 1 КИ – это логическая структура 2 КИ – конфигурация 3 КИ – 1 или несколько пользовательских контейнеров Это поддеревья объединенные в катало объектов Доменная модель служб каталогов В D 1 из важных вещей домен – это совокупность компонентов характеризующихся...
35158. Active Directory. Схема каталога. Репликация данных. Управление службой Active Directory 34 KB
  Схема каталога. Управление службой ctive Directory Любой объект каталога принадлежит к некоторому классу объектов со своей структурой атрибутов. Определения всех классов объектов и совокупности правил позволяющих управлять структурой каталога хранится в специальной иерархической структуре – схеме каталога. Схема каталога хранится в отдельном разделе и допускает возможность расширения.
35159. Службы имен. DNS, WINS 29.5 KB
  Службы имен. Помимо IPадреса для сетевых подключений и подключений удаленного доступа в сети TCP IP может потребоваться средство сопоставления имен компьютеров с IPадресами. Существует четыре механизма разрешения имен: служба DNS служба WINS широковещательное разрешение имен и использование файлов Hosts и Lmhosts. В небольших сетях где IPадреса не изменяются сетевые подключения и подключения удаленного доступа могут пользоваться для разрешения имен файлами Hosts и Lmhosts.
35160. Службы имен. Администрирование DNS 28 KB
  Администрирование DNS. DNSсервер представляет собой дополнительную компоненту операционной системы Windows Server 2003. Управление серверами DNS выполняется с помощью соответствующей оснастки Microsoft Mngement Console mmc. Выполнив команду меню Действие – Подключение к DNSсерверу необходимо указать имя компьютера где установлена служба DNS.
35161. Политики безопасности в домене Windows. Понятие групповой политики. Использование групповых политик 30 KB
  Политики безопасности в домене Windows. Понятие групповой политики. Групповые политики создаются в домене и реплицируются в рамках домена. Объект групповой политики Group Policy Object GPO – основной элемент групповой политики выступающий в качестве самостоятельных элементов каталога.
35162. Политики безопасности в домене Windows. Основные группы параметров 29.5 KB
  Общие сведения о параметрах безопасности: Подразделения домены и сайты связанны с объектами оснастки ГП. Средство параметры безопасности позволяет изменить конфигурацию безопасности для объекта оснастки ГП который в свою очередь повлияет на несколько компьютеров. Параметры безопасности или политики безопасности – это правила для одного или нескольких компьютеров применяемые в целях защиты ресурсов или сети.
35163. Регистрация событий в Windows. Классификация событий 34.5 KB
  Классификация событий. средства протоколирования событий доступные в Windowsсистемах. Когда система замедляется ведет себя непредсказуемо или демонстрирует другое ошибочное поведение нелишне заглянуть в журналы событий и попытаться определить потенциальный источник проблем.
35164. Реестр Windows. Назначение, способы работы с реестром. Меры предосторожности при работе с реестром 40 KB
  В комплект Windows входит редактор реестра программа regedit. Реестр имеет иерархическую древовидную структуру состоящую из разделов подразделов кустов и записей реестра. Существуют специальные редакторы реестра позволяющие просматривать и модифицировать реестр. Категорически не рекомендуется изменять параметры реестра самостоятельно.