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

Необходимость сжатия данных

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

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

Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Это есть форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию — он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифрованию, что затрудняет поиск шифра доступным для взломщика статистическим методом.

Цель работы: изучить необходимость в сжатии данных, способы и программы архивации, классификация архивных файлов.

Необходимость сжатия данных

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

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

Статьи к прочтению:

• Неопасные компьютерные вирусы могут привести
• Непрямое освещение в природе

XnView – бесплатная программа для сжатия изображений без потери качества

Похожие статьи:

• Теоретические основы сжатия данных Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная избыточность. Степень…
• Классические алгоритмы сжатия данных. диспетчеры архивов. их функции. Классические алгоритмы сжатия данных. Диспетчеры архивов. Их функции. Существует достаточно много алгоритмов сжатия данных, однако все они теоретически…

Основные свойства сжатых и зашифрованных данных Текст научной статьи по специальности «Компьютерные и информационные науки»

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Кожевникова Ирина Сергеевна, Васенёва Валерия Андреевна, Николаенко Виктория Григорьевна

Методология оценки стойкости блочных симметричных шифров

Обзор современных теоретико-информационных подходов к решению основных задач криптографии и стеганографии

Сравнение по эффективности суперблоков некоторых современных шифров
Надежные системы защиты электронных публикаций, базирующиеся на эффективном омофонном кодировании

Улучшение криптостойкости нейросетевого алгоритма симметричного шифрования за счет использования комитетов нейронных сетей

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Основные свойства сжатых и зашифрованных данных»

Роб 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0

-30 -28 -26 -24 -22 -20 -18 -16 -14 -12 -10 Рс/Рп, дБ

Рисунок 3. Зависимости Pоб от отношения сигнал/помеха при F=10’5 СТсигнал ГЛОНАСС для ГШП и СП при оптимальном значении частотной отстройки несущей.

0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0

-34 -32 -30 -28 -26 -24 -22 -20 -18 -16 Рс/Рп, дБ

Рисунок 4. Зависимости Pa6 от отношения сигнал/помеха при F=105 С/А сигнал GPS для ГШП и СП при оптимальном значении частотной отстройки несущей.

ОСНОВНЫЕ СВОЙСТВА СЖАТЫХ И ЗАШИФРОВАННЫХ ДАННЫХ

Кожевникова Ирина Сергеевна

Студент Волгоградского государственного университета, лаборант кафедры информационной безопасности,

г. Волгоград Васенёва Валерия Андреевна Студент Волгоградского государственного университета, г. Волгоград

Николаенко Виктория Григорьевна

Студент Волгоградского государственного университета, г. Волгоград

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

Сжатие данных — процедура перекодирования данных, производимая с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных. Сжатие основано на устранении избыточности информации, содержащейся в исходных данных. Примером избыточности является повторение в тексте фрагментов. Подобная избыточность обычно устраняется заменой повторяющейся последовательности более коротким значением (кодом). Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других, при этом возможно заменять часто встречающиеся данные более короткими кодами, а редкие — более длинными

(вероятностное сжатие). Сжатие данных, не обладающих свойством избыточности, невозможно без потерь.

Потребность в сжатии данных возникает по двум причинам:

1. информация не умещается на диске и её нужно уплотнить;

2. необходимо выполнять резервное копирование всей информации на ПК, и часто эти копии занимают большой объём памяти, что опять ведёт к уплотнению информации.

Для реализации сжатия данных существует два основных класса методов сжатия данных: сжатие с потерей информации и сжатие без потери информации.

Сжатие с потерей информации означает, что после распаковки уплотнённого архива мы получим документ, отличный от первоначального. Чем больше сжатие, тем больше потеря информации.

Сжатие без потери информации основано на устранении избыточности информации, которая присутствует почти всегда. Для избыточности есть несколько оснований:

1. каждый символ русского языка обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов;

2. в международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), хотя часто встречающиеся символы можно кодировать меньшим количеством знаков.

3. Иногда в текстах, но чаще в таблицах и графике повторяются коды. Например, если число 0 повторяется 20 раз, то нет смысла ставить 20 нулевых байтов, вместо них ставят один ноль и коэффициент 20.

Анализ свойств сжатых данных, определяющих качество сжатия

Основы теории информации были заложены Клодом Шенноном в 1948 году. Основной характеристикой сжатых данных является энтропия. Под энтропией символа а, имеют в виду вероятность — Р, появления его в тексте (подразумевается количество информации, содержащейся в а), которая равна —Р1од2Р. Если символы некоторого алфавита с символами от а1 до ап имеют вероятности от до Рп то энтропия всего алфавита равна сумме £n-Pilog2Pi. Если задана строка символов этого алфавита, то для нее энтропия определяется аналогично.

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

Энтропия обладает следующими основными особенностями:

• энтропия определяет информативность источника, она максимальна, если буквы равновероятны и независимы;

• энтропия не изменяется при обратимых преобразованиях сообщений;

• энтропия определяет экспоненциальную скорость роста мощности множества типичных последовательностей на выходе источника;

• энтропия на сообщение стационарного источника измеряется величиной:

Таким образом, сжатые данные меняют свои свойства. При этом необходимо определить, как это влияет на их защищенность.

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

Вопрос объединения алгоритмов сжатия и шифрования стоит давно. Для его реализации необходимо опре-

делить различия в основных свойствах сжатых и зашифрованных данных для различных алгоритмов сжатия и шифрования.

Для этого предлагается рассмотреть следующие свойства зашифрованных данных, полученные на основании определений стойкости шифрования.

Пусть — шифр, для которого М = |У| = Тогда — совершенный шифр тогда и только тогда, когда выполняются два условия:

(1) 1К(х,у)1 = 1 для любых х Е X,

(И) Распределение Р(к) — равномерно, то есть р(к) = 1/1К1 для любого ключа к Е К.

Доказательство. Путь шифр £в — совершенный. Тогда

Поэтому из неравенства к1 Ф к2 следует нера-вестно ек1(х) Ф ек2(х) для любого х Е X. Это доказывает необходимость условия (1).

Пусть X = [х1^хп]. Зафикрсируем произвольный элемент у Е У и занумеруем ключи так, чтобы ек.

Так как — совершенный шифр, то Р(х^/у) =

Р(Х]). Отсюда и из (1) полуем равенство р(к^) = р(у) для любого ]’ = 1, N , которое доказывает необходимость условия (и).

Пусть условия (1) и (и) выполнены. Тогда, пользуясь для фиксированного элемента у Е V введенной выше нумерацией ключей, имеем, на основании

Ру(У) = ,к)ЕХхК: е]с(х)=у

Достаточность условий теоремы также доказана.

Выделим формулу (2) для определения свойства зашифрованных данных, определяющего его стойкость.

Метод разностного анализа сочетает в себе обобщение идеи общей линейной структуры с применением вероятностно-статистических методов исследования. Этот метод относится к атакам по выбранному открытому тексту. Попытки применить разностный анализ к известному открытому тексту в большинстве случаев приводили к резкому увеличению требуемого материала. Метод был разработанный в 1990 году израильскими математиками Э. Бихамом и А. Шамиром.

Пусть некоторый блочный шифратор с длиной блока т задается отображением Р: ¿х (К1 х . К2) ^ У, где F = Ря°Ря-1°. °Р2°Р1. При этом к^ Е К^ получаются по некоторой схеме из общего ключа к или выбирается независимо и равновероятно для каждого цикла. Пространство открытых текстов 2 снабжено групповой операцией ® , и для каждого X Е 2 в 2 существует элемент Х-1 Е 2, обратный к X относительно операции ® . Выходной информационный блок (I — 1) -го цикла является входным блоком -го цикла, т.е.Х(0 = У(1 — 1), для I =

2, Я; открытый текст X = Х(1), зашифрованный текст У = У(И).

Пусть одноцикловое преобразование Р^ — криптографически слабое. Сделанное предположение вполне допустимо. Отметим, что под слабым криптографическим преобразованием Р: ЕхК ^У мы будем понимать такое криптографическое преобразование Р(Х,к) = У, для которого по известным величинам У = Р(Х,к), У* = Р*(Х, к) и АХ = Х®(Х*)-1 можно, не зная X и X*, определить множество К’,

Пусть X и X* — открытые тексты. Два открытых текста определяют последовательность разностей А Х(0),А Х(1). АХ(Д), где А Х(0) =АХ = Х®(Х*)-1; АХ(0 = х(1 + 1)®(Х*(1 + 1))-1, ¿ = 1,Р-1; АХ(р) = У®(У*)-1. Тогда для любого 1 < I < И и любой пары (а, Р), можно определить вероятность Р^р = Русловии, что вход X и все одно-цикловые ключи к^ выбраны случайно, независимо и равновероятно. Пара (а,Р), возможных значений вектора (А Х(0),А Х(1)), называется дифференциалом -го цикла.

Выберем пару (а,Р), для которой величина Р^ф-1 принимает максимальное значение, и пару (Х,Х*), такую, что А X = а. Для одноциклового шифра РК, полагая А Х(И -1)=р и зная истинные значения У = Р(Х, к), У* = Р(Х*, к), определим множество вероятных одноцикловых ключей К’. Если теперь эту процедуру провести для различных пар (Х,Х*), удовлетворяющих условию А X = а, то ключи, наиболее часто встречающиеся в множествах К’, можно считать кандидатами в истинный ключ -го цикла шифрования. Ключ всей системы находим с помощью перебора оставшихся неизвестными разрядов ключа системы или с использованием особенностей процедуры выработки цикловых ключей из ключа всей системы.

Для того чтобы описанная процедура приводила к корректным результатам, необходимо, чтобы для данной системы шифрования выполнялась

Гипотеза о статистической эквивалентности: 3(в-1)

тические операции, при замене 5 -блоков на случайно выбранные и даже при внесении минимальных изменений в один 5 -блок.

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

Дифференциальная вероятность ОР? и линейная вероятность ЬР? соответственно для ключезависимой функции f с -битным входом х и п-битным выходом у(х,уЕ вР(2п)) есть

Где Ах и А у являются входным и выходным различием (разностью), а Гх и Гу — входной и выходной масками; х • Гх обозначает результат побитного произведения х и Гх.

Максимальное значения дифференциальной и линейной вероятности для ключезависимой функции f определяется соответственно как

DPl„r = maxAx^o,AyDPf(A х ^А у),

тахгхХуФо LPf (Гу ^ Гх).

1) = Р\ А X = a,k1 = . kR-1 = шк-1

для почти всех значений частей ключа, используемых в циклах шифрования (ш^ . шк-1), где Рг[в> обозначает вероятность события в.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Эффективность метода разностного анализа существенно зависит от выбора характеристики, с помощью которой он проводится. Свойства подстановки Р на разностный анализ систем типа DES не влияют. В то же время, даже изменение порядковой нумерации S -блоков (без изменения их строения) может сильно ослабить DES. При неудачном подборе этой нумерации DES-16 раскрывается за 246 опробований. Стойкость системы DES к методу разностного анализа может также уменьшаться при замене операции векторного сложения на другие арифме-

Таким образом, показано, что для оценки характеристик как сжатых данных, так и зашифрованных данных необходимо вычисление вероятности появления элементов данных в тексте. Для получения этих характеристик вводится понятие статистическая вероятность.

Вероятность p(mi) определяется как предел относительной частоты появления исхода в процессе неограниченного увеличения числа случайных экспериментов п, то есть

Где шпШ1 — число случайных экспериментов (из общего числа п произведенных случайных экспериментов), в которых зарегистрировано появление элементарного исхода Mi.

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

1. Д. Сэломон. Мир программирования: учеб. пособие. М.: Техносфера, 2004. — 368с.

2. Лисицкая И.В. Методология оценки стойкости блочных симметричных шифров / И. В. Лисицкая // АСУ и приборы автоматики: всеукр. межвед. науч.-техн. сб. — Х.: Изд-во ХНУРЭ, 2011. — 156с.

3. Зубов А.Ю. Совершенные шифры: Вступительное слово чл.-корр.РАН Б. А. Севастьянова. М.: Гелиос АРВ, 2003 — 160 с.

Потребность в сжатии данных и программ

Лет пятнадцать назад гибкий диск емкостью 720 Кбайт казался огромным. На нем вполне размещались тексты двух кандидатских диссертаций или одной докторской, но чаще да диске хранились два-три десятка любимых компьютерных игр.

О том, что сегодня для записи приличной компьютерной игры надо иметь целый ящик гибких дисков, можно и не говорить – все знают, что ныне для этого служат лазерные диски CD-ROM. Зато собственные труды, будь то диссертация или реферат, по-прежнему переносят, перевозят и пересылают на гибких дисках. Однако современные документы, насыщенные фотографиями, таблицами, схемами, диаграммами и форматированным текстом уже давно не укладываются ни на один, ни на два гибких диска. Вывод простой: информацию надо каким-то образом уплотнять, а длинные файлы к тому же надо еще «нарезать» на мелкие куски по размеру носителя

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

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

Воспользуйтесь поиском по сайту:

studopedia.org — Студопедия.Орг — 2014-2023 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с) .

Понятие сжатия данных

Для человека избыточность данных часто связана с качеством информации, поскольку избыточность, как правило, улучшает понятность и восприятие информации. Однако когда речь идет о хранении и передаче информации средствами компьютерной техники, то избыточность играет отрицательную роль, поскольку она приводит к возрастанию стоимости хранения и передачи информации. Особенно актуальной эта проблема стает в случае обработки огромных объемов информации при незначительных объемах носителей данных. В связи с этим, постоянно возникает проблема уменьшения избыточности или сжатия данных. Если методы сжатия данных применяются к готовым файлам, то часто вместо термина «сжатие данных» употребляют термин «архивация данных», сжатый вариант данных называют архивом, а программные средства, которые реализуют методы сжатия, называются архиваторами.

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

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

Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым, то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации.

Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Ватолин Д. С. Алгоритмы сжатия изображений. — М.: Диалог-МГУ, 1999.

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

JPEG — для графических данных.

Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым. В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:

GIF, TIFF — для графических данных.

Также необходимо отметить, что основными техническими характеристиками процессов сжатия и результатов их работы являются:

• — степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;
• — скорость сжатия — время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
• — качество сжатия — величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму. Ватолин Д. С. Тенденции развития алгоритмов архивации графики // Открытые системы. — Зима 1995. — № 4.

Существует много разных практических методов сжатия без потери информации, которые, как правило, имеют разную эффективность для разных типов, данных и разных объемов. Однако в основе этих методов лежат три теоретических алгоритма:

алгоритм RLE (Run Length Encoding);

алгоритмы группы KWE (KeyWord Encoding);

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