Приемы и методы работы со сжатыми данными

Регулярно возникает необходимость сжимать данные перед их размещением в архивах или при передаче по каналам связи. Соответственно, существует и обратная необходимость восстановления данных из предварительно уплотненных архивов.

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

‘‘Приемы и методы работы со сжатыми данными’’

Теоретические основы сжатия данных

Регулярно возникает необходимость сжимать данные перед их размещением в архивах или при передаче по каналам связи. Соответственно, существует и обратная необходимость восстановления данных из предварительно уплотненных архивов.
Характерной особенностью большинства типов данных является определенная избыточность. Например, у видеоданных избыточность больше, чем у графических, а степень избыточности графических данных в несколько раз больше, чем текстовых. Кроме того, степень избыточности данных зависти от принятой системы кодирования. Например, кодирование информации средствами русской азбуки на 20-30% больше, чем кодирование адекватной информации средствами английского языка.
Для человека избыточность информации связана с представлением о ее качестве, т. к. избыточность улучшает восприятие в неблагоприятных условиях (просмотр телепередачи при наличии помех, восстановления поврежденного графического материала, чтение текстов в условиях недостаточной освещенности). При обработке информации избыточность также играет важную роль. Например, при преобразовании данных избыточность используется для повышения ее качества. Однако при хранении готовых документов или их передаче избыточность можно уменьшить, что дает эффект сжатия данных.
Если методы сжатия информации применяются к готовым документам, то термин сжатия данных подменяют термином архивация данных, а программные средства, выполняющие эти операции, называют архиваторами.

Объекты сжатия.
В зависимости от того, в каком объекте размещены данные, подвергаемые сжатию, различают:
• уплотнение (архивацию) файлов;
• уплотнение (архивацию) папок;
• уплотнение дисков.
Уплотнение файлов применяют для уменьшения их размеров при подготовке к передаче по каналам электронных сетей или к транспортировке на внешнем носителе малой емкости.Уплотнение папок используют как средство архивации данных перед длительным хранением, в частности, при резервном копировании. Уплотнение дисков служит целям повышения эффективности использования их рабочего пространства, и применяют к дискам недостаточной емкости.
Обратимость сжатия. Несмотря на изобилие алгоритмов сжатия данных, теоретически есть три способа уменьшения их избыточности:
• изменение содержания данных;
• изменение структура данных;
• изменение содержания и структуры данных.
Если при сжатии данных происходит изменение их содержания, метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Такие методы называют также методами сжатия с регулируемой потерей информации. Они применимы для данных, формальная утрата части содержания которых, не приводит к значительному снижению потребительских свойств. Это относится к мультимедийным данным (видеорядам, музыкальным записям, звукозаписям и рисункам). Данные методы обеспечивают более высокую степень сжатия, чем обычные обратимые методы, но их нельзя применять к текстовым документам, базам данных и программному коду.
Форматы сжатия с потерей информации:
• .JPG для графических данных;
• .MPG для видеоданных;
• .MP3 для звуковых данных.
Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим. Из результирующего кода можно восстановить исходный массив путем применения обратного метода. Обратимые методы применяются для сжатия любых типов данных.
Форматы сжатия без потери информации:
• .GIF, .TIF, .PCX и многие другие для графических данных;
• .AVI для видеоданных;
• .ZIP, .ARJ, .RAR, .LZH, .LH, .CAB и многие другие для любых типов данных.

Алгоритмы обратимых методов.
При исследовании методов сжатия следует иметь в виду существование следующих доказанных теорем:
• Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации.
• Для любого алгоритма сжатия можно указать такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие методы.
• Для любого алгоритма сжатия можно указать такую последовательность данных, для которой данный алгоритм вообще не позволит получать сжатия.
Таким образом, наивысшую эффективность методы сжатия демонстрируют для данных разных типов и разных объемов.
Далее рассмотрим теоретические алгоритмы обратимых методов сжатия данных.
Алгоритм RLE. В основу алгоритмов RLE (Run-Length Encoding) положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора.
Например, последовательность 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется выходной вектор данных: 0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов). Здесь коэффициент сжатия 8/10 (80%).
Программные реализации данных алгоритмов отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие. Наилучшими объектами для данного алгоритма являются графические файлы, в которых большие одноцветные участки изображения кодируются длинными последовательностями одинаковых байтов. Этот метод может давать эффект для баз данных, имеющих таблицы с фиксированной длиной полей. Для текстовых данных методы, основанные на данном алгоритме, как правило, мало эффективны.
Заметим, что эффективность алгоритма не зависит от объема данных.
Алгоритм KWE. В основу алгоритмов KWE (Keyword Encoding) положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово. Результат кодирования сводится в таблицу, которая прилагается к результирующему коду и представляет собой словарь. Для англоязычных текстов принято использовать двухбайтовую кодировку слов. Образующиеся при этом пары байтов называют токенами.
Эффективность данного метода существенно зависит от длины документа, т. к. из-за прикладывания к архиву словаря длина кратких документов может возрасти.
Данный алгоритм эффективен для англоязычных текстовых документов и файлов баз данных. Для русскоязычных документов, отличающихся длинными словами с приставками, суффиксами и окончаниями, не всегда удается ограничиться двухбайтовыми токенами, и эффективность метода заметно снижается.
Алгоритм Хафмана. В основе этого алгоритма лежит кодирование не байтами, а битовыми группами.
• Перед началом кодировки производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся слов.
• Чем чаще встречается символ, то тем меньшим количеством битов он кодируется.
• Образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.
Например, кодирование символов русского алфавита может иметь вид: А — 1 (1 бит), О — 01 (2 бита), Е — 0010 (4 бита), Т — 0011, И — 000101, и т. д. Таким образом, используя 16 бит, можно закодировать до 256 различных символов, а, используя 20 бит, можно кодировать не только символы, но и группы слогов и слова.
В связи с приложением к сжатому архиву таблицы соответствия на малых файлах алгоритм малоэффективен. Практика показывает, что его эффективность зависит и от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода 18-20 бит).

2. Программные средства сжатия данных.
Классические форматы сжатия данных:
Операционная система Формат сжатия Средство архивации Средство разархивирования
MS-DOS .ZIP PKZIP.EXE PKUNZIP.EXE
.RAR RAR.EXE UNRAR.EXE
.ARJ ARJ.EXE
Windows 9x .ZIP WinZip
.RAR WinRAR
.ARJ WinArj
Современные программные средства архивации данных называют диспетчерами архивов, ввиду своих больших функциональных возможностей, выходящих за рамки простого сжатия данных.
К базовым функциям, которые выполняют большинство современных диспетчеров архивов, относятся: извлечение файлов из архивов; создание новых архивов; добавление файлов в имеющийся архив; создание самораспаковывающихся архивов; создание распределенных архивов на носителях малой емкости; тестирование целостности структуры архивов; полное или частичное восстановление поврежденных архивов; защита архивов от просмотра и несанкционированной модификации.
Самораспаковывающиеся архивы. Такие архивы создают при необходимости передачи документа потребителю, если нет уверенности в наличии у пользователя требуемого программного средства. Самораспаковывающийся архив готовится с помощью обычного архива путем присоединения к нему небольшого программного модуля. Архив получает расширение .EXE, характерное для исполнимых файлов. Распаковка самораспаковывающегося архива происходит автоматически.
Распределенные архивы. При необходимости передачи большого архива на носителях малой емкости (например, на ГМД) возможно распределение одного архива в виде малых фрагментов на нескольких носителях. Диспетчер WinZip выполняет такое разбиение сразу на диски, а WinRAR и WinArj предварительно делает разбиение архива на фрагменты заданного размера на жестком диске, которые затем копируются на внешние носители. При использовании диспетчера WinZip каждый том архива дает файлы с одинаковыми именами, поэтому следует маркировать каждый диск пометками на наклейке, чтобы не перепутать последовательность немаркированных томов. Для того чтобы узнать номер тома по метке на диске используйте пункт Свойства контекстного меню дисковода 3,5 (А:) в окне Мой компьютер. Номер тома можно узнать на вкладке Общие в поле Метка тома. В других архиваторах подобных проблем нет.
Защита архивов выполняется с помощью пароля, который запрашивается при попытке просмотра, распаковки или изменения архива. Для наибольшей защиты архива используйте в пароле не только символы английского алфавита и цифры, но и русский алфавит.
К дополнительным функциям диспетчеров архивов относятся сервисные функции, делающие работу более удобной (порой требуется подключение дополнительных служебных программ): просмотр файлов различных форматов без извлечения их из архива; поиск файлов и данных внутри архива; установка программ из архивов и проверка отсутствия компьютерных вирусов в архиве без предварительной распаковки; криптографическая защита архивной информации; декодирование сообщений электронной почты; создание самораспаковывающихся многотомных архивов; выбор и настройка коэффициента сжатия информации и др.
3. Программные средства уплотнения носителей.
В основе уплотнения носителей (например, дисков) также лежит принцип сжатия данных за счет уменьшения избыточности путем изменения структуры (на основе обратимых методов), при этом наблюдаются некоторые особенности:
процесс уплотнения носителей приводит к сжатию записываемых данных, что вызывает эффект кажущегося увеличения емкости носителя;
процесс сжатия данных происходит с помощью программ, работающих автономно в фоновом режиме; пользователь не ощущает разницы в работе с обычным и уплотненным носителем, однако на диске обнаруживается больший объем данных, чем физическая емкость диска;
степень сжатия данных зависит от типа данных, поэтому приращение емкости носителя не является величиной постоянной и постоянно изменяется в зависимости от типа данных, добавляемых на носитель.
Практическая реализация концепции уплотнения дисков:
• на физическом диске (несущем диске) создается скрытый файл (называемый файлом сжатого тома), предназначенный для записи сжатия данных;
• на уровне операционной системы происходит объявление файла сжатого тома в качестве нового уплотненного диска (данные уплотненного диска заносятся в файл сжатого тома на несущем диске);
• если файл сжатого тома занимает весь несущий диск, то несущий диск делается скрытым и его место в ОС занимает уплотненный диск;
• весь обмен информацией с уплотненным диском происходит под управлением специальной программы – драйвера сжатого тома, которая интегрируется в операционную систему и организует ее взаимодействие с нестандартной файловой системой, созданной внутри файла сжатого тома.
Если в ОС имеется уплотненный диск, то операционная система может рассматривать его структуру двояко: как обычный несущий диск, на котором расположен файл сжатого тома, или через драйвер сжатого тома, когда ОС наблюдает его как дополнительный диск, имеющийся в компьютерной системе. Переход от первого представления ко второму называется присоединением уплотненного диска. Обратная операция называется отсоединением.
Наличие в компьютерной системе уплотненного носителя затрудняет ее обслуживание и снижает надежность в связи с особой сложностью восстановления информации в случае неожиданных повреждений аппаратного или программного обеспечения. Однако использование уплотненных дисков для хранения результатов промежуточных операций рационально и оправдано. При этом общее быстродействие системы на ряде операций повышается, так как в операциях чтения/записи участвуют механические устройства, а операции упаковки/распаковки данных выполняются только электронными устройствами.
Для уплотнения диска используется программа Сжатие данных (DriveSpace 3), входящая в состав ОС Windows 98 (ее запуск через команду Пуск – Программы – Стандартные – Служебные – Сжатие данных). В результате операции на гибком диске А: образуется скрытый несущий диск Н:, а сам диск А: при этом рассматривается как уплотненный.


Скачиваний: 3
Просмотров: 14
Скачать реферат Заказать реферат