Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Теоретические основы сжатия данныхСодержание книги
Поиск на нашем сайте
Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная избыточность. Степень избыточности зависит от типа данных. Например, у видеоданных степень избыточности обычно в несколько раз больше, чем у графических данных, а степень избыточности графических данных в несколько раз больше, чем у текстовых. Кроме того, степень избыточности данных зависит от принятой системы кодирования. Так кодирование текстовой информации средствами русского языка, дает в среднем избыточность на 20-30 % больше, чем кодирование адекватной информации средствами английского языка. Избыточность, как правило, улучшает восприятие, особенно в неблагоприятных условиях (просмотр телепередач в условиях помех, восстановление поврежденного графического материала, чтение при недостаточной освещенности). Однако, когда речь идет о хранении готовых документов или их передачи, то избыточность можно уменьшить, что дает эффект сжатия данных.
· Объекты сжатия В зависимости от того, в каком объекте размещены данные, подвергаемые сжатию, различают: ü уплотнение (архивацию) файлов – для уменьшения размера файла при передаче по сети или транспортировке, например, на дискете; ü уплотнение (архивацию) папок – при резервном копировании ü уплотнение дисков – для повышения использования дискового пространства.
· Обратимость сжатия Несмотря на изобилие алгоритмов сжатия данных, теоретически есть только три способа уменьшения их избыточности. Это либо изменения содержания данных, либо изменение их структуры, либо и то и другое вместе. Если при сжатии данных происходит изменение их содержания, метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Такие методы применимы только для тех типов данных, для которых формальная утрата части содержания не приводит к значительному снижению потребительских свойств. Это относится к мультимедийным данным: видеоряды, музыкальные записи, звукозаписи, рисунки. Методы сжатия с потерей информации обычно обеспечивают гораздо более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым документам, базам данных и, тем более, к программному коду. Характерными форматами сжатия с потерей информации являются: ü.JPG – для графических данных; ü.MPG – для видеоданных; ü.MP3 – для звуковых данных.
Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим. Обратимые методы применяют для сжатия любых типов данных. Характерными форматами сжатия без потери информации являются: ü.GIF,.TIF,.PCX и многие другие – для графических данных; ü.AVI – для видеоданных; ü.ZIP,.ARJ,.RAR,.LZH,.LH,.CAB и многие другие – для любых типов данных.
· Алгоритмы обратимых методов Обсуждая различные методы сжатия, следует иметь в виду, что наивысшую эффективность они демонстрируют для данных разных типов и разных объемов. Существует достаточно много обратимых методов сжатия, однако в их основе лежит сравнительно небольшое количество теоретических алгоритмов, представленных в таблице 1. Таблица 1. Свойства алгоритмов сжатия
Алгоритм RLE В основу этого алгоритма положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указхывается код данных и коэффициент повтора. Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байт) образуется следующий вектор:
При записи в строку он имеет вид: 0; 3; 127;2; 0; 1; 255;4 (всего 8 байт). В данном примере коэффициент сжатия равен 8/10, т.е. экономия объема составляет 20 %. Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие. Наилучшими объектами для данного алгоритма являются графические файлы, в которых большие одноцветные участки изображения кодируются длинными последовательностями одинаковых байтов. Этот метод также может давать заметный выигрыш на некоторых типах файлов баз данных, имеющих таблицы с фиксированной длиной полей. Для текстовых файлов данных методы RLE, как правило, не эффективны.
Алгоритм KWE В основу алгоритмов кодирования по ключевым словам положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово. Результат кодирования сводится в таблицу, которая прикладывается к результирующему коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать двухбайтовую кодировку слов. Образующиеся при этом пары байтов называют токенами. Эффективность данного метода существенно зависит от длины документа, поскольку из-за необходимости прикладывать к архиву словарь длина кратких документов не только не уменьшается, но даже возрастает. Данный алгоритм наиболее эффективен для англоязычных текстовых документов и файлов баз данных. Для русскоязычных документов, отличающихся увеличенной длиной слов и большим количеством приставок, суффиксов и окончаний, не всегда удается ограничится двухбайтовыми токенами, и эффективность заметно снижается.
Алгоритм Хаффмана В основе этого алгоритма лежит кодирование не байтами, а битовыми группами: ü перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов; ü чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется; ü образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.
Пример кодирования символов русского алфавита представлен на рис.1. 1 бит 2 бит 4 бит 6 бит
…………………………………………………………………………………….
16 бит ………………………. ……………………..
Рис..1. Пример побуквенного кодирования русского алфавита по алгоритму Хаффмана
Как видно из схемы, представленной на рис.1, используя 16 бит, можно закодировать до 256 различных символов. Однако ничто не мешает использовать и последовательности длиной до 20 бит – тогда можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова). В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит).
Синтетические алгоритмы Рассмотренные алгоритмы в «чистом виде» на практике не применяются из-за того, что эффективность каждого из них сильно зависит от начальных условий. В связи с этим современные средства архивации данных используют более сложные алгоритмы, основанные на комбинации нескольких теоретических методов. Все они предварительно просматривают и анализируют исходные данные для индивидуальной настройки алгоритма на особенности обрабатываемого материала.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-12-13; просмотров: 466; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.58.52.94 (0.007 с.) |