Автор: Дедков Антон 11 А Научный руководитель: Дединский Илья Рудольфович.

Презентация:



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

Авторы: Дедков Антон 11 А, Шевелев Александр 11 А Научный руководитель: Дединский Илья Рудольфович.
Авторы: Дедков Антон 11 А, Шевелев Александр 11 А Научный руководитель: Дединский Илья Рудольфович.
Архивация данных: основные алгоритмы архивации данных.
Сжатие двоичного кода. Для того чтобы сэкономить место на внешних носителях (винчестерах, флэш дисках) и ускорить передачу информации по компьютерным.
Чижова Надежда 445 Научный руководитель: Юрий Литвинов.
Обобщение метода кодирования Хаффмана с использованием систем счисления Ковалёв Д.С. Новосибирский Государственный Университет Факультет Информационных.
Model/View-архитектура CASE-пакета REAL-MV Тимофей Брыксин, гр. 545 Научный руководитель: А.Н.Терехов Рецензент: Д.В.Кознов.
Сжатие информации Алгоритм Хаффмана. Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.
Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская.
Архиватор программа, осуществляющая объединение нескольких файлов в один архив или серию архивов, для удобства переноса или хранения. Диск с архиватором.
Курсовая работа по дисциплине «Информатика» на тему: «Алгоритм Хаффмана» Автор: Пятко Наталья.
Исполнитель: Утяшева И.А. Научный руководитель: к.ф.-м.н. Винокур В.В.
1 «Разработка методического и технологического обеспечения размещения и сбора сведений об образовательных организациях, используемых в процедурах государственной.
1 Диаграммы реализации (implementation diagrams).
Помехоустойчивое кодирование. Код Рида-Соломона. Передача информации.
Выполнила: Медведева Анастасия, Ученица 11А класса, МОУ СОШ 3. Руководитель: Глазунова Ольга Петровна, учитель информатики. «Сжатие данных. Алгоритм Хаффмана»
Многометодные процедуры оптимального управления Архитектура и реализация программного комплекса Исследовательский Центр процессов управления Работа выполнена.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики и информатики Кафедра информатики.
Транксрипт:

Автор: Дедков Антон 11 А Научный руководитель: Дединский Илья Рудольфович

Цель работы Создание кроссплатформенной библиотеки для сжатия данных методом Хаффмана, а также CLI и GUI фронтендов для взаимодействия конечного пользователя с ней. Дедков Антон 11 "А"

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

Сжатие данных Типы сжатия: Сжатие с потерями Сжатие без потерь Виды кодов: Равномерные Неравномерные Архив С искажениями Без искажений ABAC ABCA Выигрыш Дедков Антон 11 "А"

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

2 этап: построение дерева C2D1 B A C2D1B4A8A8 min C2D1 01 A8A8B4 min min C2D1 B A8A8 min Дедков Антон 11 "А"

3 этап: кодирование (A) ( B )(A) ( C ) (A)( B )(A) ( D ) (A)( B )(A) ( C ) (A)( B )(A) В результате: Кодирование одного из символов ( С ): Находим лист с символом С Проходим путь от листа до корня, накапливая биты (011) Переворачиваем полученную последовательность Получаем код символа С (110) C2D1 B A Исходный текст: ABACABADABACABA 0 Дедков Антон 11 "А"

Сжатие Качество и мощность алфавита: Мощность алфавита (кол-во символов) Максимальное сжатие Системная информация 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 Дедков Антон 11 "А"

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

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 Дедков Антон 11 "А"

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

Итоги Реализован алгоритм сжатия методом Хаффмана Создан формат для хранения сжатых данных Разработана архитектуры библиотеки сжатия Реализован CLI Реализован прототип GUI на основе фреймворка Qt Дедков Антон 11 "А"

Дальнейшее развитие Перенос вычислений на многопроцессорные системы с использованием OpenCL Реализация клиент-серверной архитектуры Доработка GUI Дедков Антон 11 "А"

Спасибо за внимание! Самая свежая версия всегда ждет вас на quffman.googlecode.comquffman.googlecode.com Дедков Антон 11 "А"