Отправляет email-рассылки с помощью сервиса Sendsay

Программирование на MFC, Win32 API, WTL/ATL в среде MS VC++

Подписаться Бесплатная новостная рассылка Подписчиков 35 RSS
←   Февраль 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.softonic.narod.ru/projects.html
Открыта: 14-09-2003

Автор
AlexO

Статистика

35 подписчиков
0 за неделю
←   Все выпуски   →

Программирование на Win32 API, WTL/ATL в среде MS Visual C++


Информационный Канал Subscribe.Ru

Выпуск 6.

Здравствуйте, уважаемые читатели.

Снова перед вами небольшой выпуск

 

Немного общих слов

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

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

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

 

Я не буду пересказывать здесь все, что уже понаписано про архиваторы, поэтомуљ упомяну лишь основные моменты. Все алгоритмы сжатия делятся на две категории:

1.            Без потерь (rar, arj, zip и т.д.), при упаковке сжимаются все данные, а при распаковке данные восстанавливаются "один-в-один" с исходными данными.

2.            С потерями (форматы jpg, dvd, mp3), при таком сжатии исходные данные обрабатываются таким образом, что при распаковке сжатых данных исходные данные уже не будут в точности соответствовать друг другу. То, на сколько сильно они будут отличаться обычно задается в параметрах алгоритма. Как правило, именно алгоритмы с потерями позволяют резко уменьшить объем данных. Легко убедиться, что даже значительная потеря избыточной информации не так страшна, например, при просмотре DivX-фильма.

 

Среди алгоритмов сжатия есть несколько известных - это Runnig (RLE), Huffman, LZW (и еще некоторые LZ-алгоритмы), Арифметическое кодирование.

љ

Арифметическое кодирование

 

В Сети полно исходников различных архиваторов, которые работают по тому или иному алгоритму. В основном используют LZW или его вариации или используют Huffman'а.

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

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

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

 

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

 

 

На сегодня все.

 

Всего наилучшего, Alexander Oshurkov <softonic@narod.ru>

 

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное