Автор: Дедков Антон, Лицей Вторая школа Научный руководитель: Дединский Илья Рудольфович, МФТИ

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

Алгоритм Хаффмана 1 этап: построение таблицы частот СимволABCD Частота8421 Дедков Антон, Лицей "Вторая школа" Алгоритм Хаффмана сопоставляет символам коды на основе частоты их встречаемости в файле Входной поток: ABACABADABACABA

2 этап: построение дерева Дедков Антон, Лицей "Вторая школа" Символ Частота (Вес) A8 B4 C2 D C [2] D [1] B [4] A [8] Дерево строится таким образом, что символ с меньшим весом наиболее удален от вершины

3 этап: кодирование Кодирование одного из символов ( С ): Находим узел с символом С Проходим путь от узла до корня, накапливая биты (011) Переворачиваем полученную последовательность Получаем код символа С (110) Дедков Антон, Лицей "Вторая школа" [4+3] 3 [2+1] C [2] D [1] B [4] 15 [8+7] A [8] На основе полученного дерева строим новые коды символов

Результат выполнения алгоритма Дедков Антон, Лицей "Вторая школа" ABACABADABACABA ABACABADABACABA Free Сжатый текст (25 байт) Исходный текст (30 байт) В первом случае все коды одной длины – равномерные Во втором случае длина различна – неравномерные коды

Сжатие Качество и мощность алфавита: Мощность алфавита (кол-во символов) Максимальное сжатие Системная информация 2^8 = 256 (1 byte) 8x1x 2^16 = (2 bytes) 16x2x 2^24 = (3 bytes) 24x3x Скорость: Скорость Процессор КомпрессияДекомпрессия AMD Athlon XP GHz 1.47 Mb/sec4.48 Mb/sec Mobile Intel Pentium IV 1.7GHz 0.77 Mb/sec2.91 Mb/sec Дедков Антон, Лицей "Вторая школа"

Архитектура библиотеки Взаимодействие программы происходит только с ядром Ядро предоставляет инструменты для работы с файловой системой архива Модуль, отвечающий за кодирование, абстрагирован от каких либо внешних факторов, он взаимодействует лишь с пакетами данных (CompressorData), которые формирует для него ядро Application Core FileSystem Compressor CompressorData lib_quffman Дедков Антон, Лицей "Вторая школа"

DataFormat archive.quf Root directory (/) File (/file1) File (/file2) Subdirectory (/subdir1) File (/subdir1/file3) Subdirectory (/subdir1/subdir2) File (/subdir1/subdir2/file4) SystemInfo archive.qufSystemInfo… quf(root(subdir(subdir1,subdir(subdir2, file(file4))… DataBlocks File4 Block 2 File4 Block 1 Архив содержит всю информацию о данных Атрибуты: quf, root, subdir, file, block Дедков Антон, Лицей "Вторая школа"

Проблемы Появление в сжатых файлах системной информации Соотношение скорость/качество сжатия Проблема переполнения Перенос вычислений на многопроцессорные системы Дедков Антон, Лицей "Вторая школа"

Итоги Реализован алгоритм сжатия методом Хаффмана Проанализированы факторы влияющие на скорость и качество сжатия Создан формат для хранения сжатых данных Разработана архитектуры библиотеки сжатия Реализованы CLI и GUI на основе фреймворка Qt Дедков Антон, Лицей "Вторая школа"

Спасибо за внимание! Самая свежая версия всегда ждет вас на quffman.googlecode.com (Subversion репозиторий) quffman.googlecode.com Дедков Антон, Лицей "Вторая школа"