Главная
страница 1
Слайд №5 (Сжатие данных)

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

Слайд №6 (Алгоритм Хаффмана)

Алгоритм Хаффмана строит коды символов по частоте их встречаемости в файле. Делится он на 3 основных этапа.

Первый – построение таблицы частот.

Пусть во входном файле есть текст (ABACABADABACABA).

После посимвольного считывания текста получим частоты вхождения каждого символа в текст.

Слайд №7,8 (Построение дерева)

Из таблицы частот мы знаем частоту вхождения каждого символа в файл. Сначала находим два символа с наименьшими частотами (C ; D) -> создаем узел-родитель, вес которого будет равен сумме частот С и D ( при этом эти символы больше не участвуют в нахождении min ).

Аналогично для остальных символов. В результате будет построено дерево, соответствующее тексту.
9.(Сжатие)
Стоит отметитть, что важным фактором влияющим на качество сжатия является Мощность Алфавита.

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

10.(Архитектура библиотеки)
Архитектура библиотеки построена таким образом, чтобы все части были максимально абстрагированы друг от друга, что позволяет менять методы сжатия на лету.
Большая независимость - большая безопасность и лучшая отладка.
Такая абстрагированность – путь к параллельности вычислений, модуль сжатия оперирует лишь со своими пакетами данных и его не волнует, чем занято ядро, можно ли писать в файл или он заблокирован.

11.(DataFormat)

Для сохранения информации и файлах и дерикториях архива, в него записывается дерево директорий в инфиксном виде
QUF атрибут отвечающий за сигнатуру архив
ROOT указывает на корневую директорию архива.
SUBDIR – атрибут, указывающий на поддиректорию.
FILE информация о файлах содержащихся в архиве
BLOCK – указывает местонахождение сжатых частей файла в архиве

12.(Проблемы)
Если сжимать большое кол-во маленьких файлов, то может проявиться обратный эффект, когда размер архива будет значительно превосходить суммарный объем сжимаемых файлов.
О соотношении скорости/качества сжатия можно говорить очень много, но основной параметр который можно варьировать – мощность алфавита и кол-во блоков на которые разбивается файл. Если использовать Большая мощность – маленькая скорость, много системной информации
Эффект переполнения наступит тогда, когда размер файла превысит 2^64 (long long int) для тех кто в танке это много! Примерно 2^22 терабайт

14.(Дальнейшее развитие)

На самом деле Quffman – часть большой идеи по реализации библиотеки параллельного сжатия на основе OpenCL. Я намеренно не стал упоминать об этом ни в целях, ни в задачах, так как это слишком большая работа, которая много больше текущей, и вероятно не будет сделана. Хотя актуальность работы - в переносе на параллельные системы.


Смотрите также:
Слайд №5 (Сжатие данных) Сжатие
49.93kb.
1 стр.
Практикум n 9 Архивирование и сжатие в оc unix по курсу «Операционные системы»
66.02kb.
1 стр.
Программирование потоком данных Сжатие данных
223.56kb.
1 стр.
Неодномерное сжатие и горение термоядерных мишеней
18.79kb.
1 стр.
Лекция от 3 ноября 1999. Записали Ольга Соловьева
92.77kb.
1 стр.
Об особенностях применения компенсаторов
35.88kb.
1 стр.
Программное обеспечение
122.54kb.
1 стр.
Урок №27. Жизненный путь рядовой звезды. Бесшабашная юность начальная стадия эволюции звезд гравитационное сжатие
117.93kb.
1 стр.
Сжатие телевизионных изображений методом слоев
70.75kb.
1 стр.
Фио студента (русск.)
32.87kb.
1 стр.
1. Введение стр 3 Физико-географическая характеристика региона стр 3 Озеро Байкал стр 5
175.68kb.
1 стр.
Асни методов сжатия полутоновых изображений без потерь
80.48kb.
1 стр.