Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 11 лет назад пользователемНадежда Яськова
1 Автор: Дедков Антон, Лицей Вторая школа Научный руководитель: Дединский Илья Рудольфович, МФТИ
2 Цель работы Создание кроссплатформенной библиотеки для сжатия данных методом Хаффмана, а также фронтендов для взаимодействия с ней. Дедков Антон, Лицей "Вторая школа" Задачи Реализация алгоритма сжатия методом Хаффмана Анализ факторов, влияющих на скорость и качество сжатия Создание формата хранения сжатых данных Разработка архитектуры библиотеки сжатия Реализация фронтендов
3 Алгоритм Хаффмана 1 этап: построение таблицы частот СимволABCD Частота8421 Дедков Антон, Лицей "Вторая школа" Алгоритм Хаффмана сопоставляет символам коды на основе частоты их встречаемости в файле Входной поток: ABACABADABACABA
4 2 этап: построение дерева Дедков Антон, Лицей "Вторая школа" Символ Частота (Вес) A8 B4 C2 D C [2] D [1] B [4] A [8] Дерево строится таким образом, что символ с меньшим весом наиболее удален от вершины
5 3 этап: кодирование Кодирование одного из символов ( С ): Находим узел с символом С Проходим путь от узла до корня, накапливая биты (011) Переворачиваем полученную последовательность Получаем код символа С (110) Дедков Антон, Лицей "Вторая школа" [4+3] 3 [2+1] C [2] D [1] B [4] 15 [8+7] A [8] На основе полученного дерева строим новые коды символов
6 Результат выполнения алгоритма Дедков Антон, Лицей "Вторая школа" ABACABADABACABA ABACABADABACABA Free Сжатый текст (25 байт) Исходный текст (30 байт) В первом случае все коды одной длины – равномерные Во втором случае длина различна – неравномерные коды
7 Сжатие Качество и мощность алфавита: Мощность алфавита (кол-во символов) Максимальное сжатие Системная информация 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 Дедков Антон, Лицей "Вторая школа"
8 Архитектура библиотеки Взаимодействие программы происходит только с ядром Ядро предоставляет инструменты для работы с файловой системой архива Модуль, отвечающий за кодирование, абстрагирован от каких либо внешних факторов, он взаимодействует лишь с пакетами данных (CompressorData), которые формирует для него ядро Application Core FileSystem Compressor CompressorData lib_quffman Дедков Антон, Лицей "Вторая школа"
9 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 Дедков Антон, Лицей "Вторая школа"
10 Проблемы Появление в сжатых файлах системной информации Соотношение скорость/качество сжатия Проблема переполнения Перенос вычислений на многопроцессорные системы Дедков Антон, Лицей "Вторая школа"
11 Итоги Реализован алгоритм сжатия методом Хаффмана Проанализированы факторы влияющие на скорость и качество сжатия Создан формат для хранения сжатых данных Разработана архитектуры библиотеки сжатия Реализованы CLI и GUI на основе фреймворка Qt Дедков Антон, Лицей "Вторая школа"
12 Спасибо за внимание! Самая свежая версия всегда ждет вас на quffman.googlecode.com (Subversion репозиторий) quffman.googlecode.com Дедков Антон, Лицей "Вторая школа"
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.