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

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



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

Автор: Дедков Антон 11 А Научный руководитель: Дединский Илья Рудольфович.
Автор: Дедков Антон, Лицей Вторая школа Научный руководитель: Дединский Илья Рудольфович, МФТИ.
Архивация данных: основные алгоритмы архивации данных.
Курсовая работа по дисциплине «Информатика» на тему: «Алгоритм Хаффмана» Автор: Пятко Наталья.
Сжатие двоичного кода. Для того чтобы сэкономить место на внешних носителях (винчестерах, флэш дисках) и ускорить передачу информации по компьютерным.
Архиватор программа, осуществляющая объединение нескольких файлов в один архив или серию архивов, для удобства переноса или хранения. Диск с архиватором.
Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская.
Model/View-архитектура CASE-пакета REAL-MV Тимофей Брыксин, гр. 545 Научный руководитель: А.Н.Терехов Рецензент: Д.В.Кознов.
ИСТОЧНИК ИНФОРМАЦИИ ПРИЁМНИК ИНФОРМАЦИИ Кодирующее устройство Декодирующее устройство КАНАЛ СВЯЗИ ШУМ ЗАЩИТА ОТ ШУМА.
Исполнитель: Утяшева И.А. Научный руководитель: к.ф.-м.н. Винокур В.В.
Помехоустойчивое кодирование. Код Рида-Соломона. Передача информации.
Чижова Надежда 445 Научный руководитель: Юрий Литвинов.
Обобщение метода кодирования Хаффмана с использованием систем счисления Ковалёв Д.С. Новосибирский Государственный Университет Факультет Информационных.
AB C D D1D1 A1A1 B1B1 C1C1 M N P. A B C D N Секущая плоскость проходит через точку N, параллельно плоскости DCB.
Генерация средств импорта данных в рамках проектов ИС, реализованных в технологии REAL-IT Выполнил Комиссаров Антон Научный руководитель: Иванов А.Н. Рецензент:
1 Диаграммы реализации (implementation diagrams).
Файловые менеджеры и архиваторы. файловые менеджеры. - специальные программы для проведения различных операций над файлами и папками (копирование, перемещение,
Технические возможности. Наши цели Максимальная гибкость Максимальная скорость считывания и обработки данных Стабильность работы Максимальная простота.
Транксрипт:

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

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

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

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

Алгоритм Хаффмана Алгоритм Хаффмана - алгоритм построения кодов символов по частоте их встречаемости в файле Этапы: Создание таблицы частот Построение дерева Кодирование Дедков Антон 11 "А". Шевелев Александр 11 "А".

Таблица частот Содержимое входного файла: ABACABADABACABA После посимвольного считывания файла получим результат: СимволABCD Частота8421

Построение дерева C2C2 D1D C2C2 D1D C2C2 D1D1 B4B C2C2 D1D1 B4B A8A C2C2 D1D1 B4B4 A8A8

Кодирование (A) ( B )(A) ( C ) (A)( B )(A) ( D ) (A)( B )(A) ( C ) (A)( B )(A) В результате: Кодирование одного из символов ( С ): Находим лист с символом С Проходим путь от листа до корня, накапливая биты Переворачиваем полученную последовательность Получаем код символа С ( 110 ) C2C2 D1D1 B4B A8A Исходный текст: ABACABADABACABA

Качество сжатия Качество и мощность алфавита: Дедков Антон 11 "А". Шевелев Александр 11 "А". Мощность алфавита (символов) Максимальное сжатие Системная информация 2^8 = 256 (1 byte)8x1x 2^16 = (2 bytes)16x2x 2^24 = (3 bytes)24x3x

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

DataFormat Дедков Антон 11 "А". Шевелев Александр 11 "А". 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 2 Архив содержит всю информацию о данных Атрибуты: quf, root, subdir, file, block

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

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

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

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