О построении дерева Хаффмана - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему О построении дерева Хаффмана. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

О ПОСТРОЕНИИ ДЕРЕВА ХАФФМАНА Э. Ю. Джибладзе

Слайд 2

Описание слайда:

Цели и задачи Цель работы – изучение возможности параллельной реализация алгоритма Хаффмана, основанной на расширении операций матричной алгебры Задачи – программная реализация оптимального кода Хаффмана; – оценка сложности последовательного алгоритма; – реализация параллельного алгоритма матрично-векторного умножения; – реализация параллельного алгоритма построения дерева Хаффмана; – оценка сложности параллельного алгоритма построения дерева Хаффмана.

Слайд 3

Описание слайда:

Алгоритм построения оптимального кода Хаффмана Символы входного алфавита образуют список из N свободных узлов. Вес узла равен либо вероятности, либо количеству вхождений элемента алфавита в сжимаемое сообщение. Выбираются два свободных узла дерева с наименьшими весами. Создается их родитель с весом, равным их суммарному весу. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка. Одной дуге, выходящей из родителя, ставится в соответствие бит 1 , а другой – бит 0. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Слайд 4

Описание слайда:

Реализация последовательного алгоритма

Слайд 5

Описание слайда:

Оценка сложности последовательного алгоритма Пусть M – число символов в сообщении, кодируемых по Хаффману и принадлежащих исходному алфавиту из N элементов. Временные сложности этапов: 1. определение весов дерева по исходному сообщению T1(1)=O(M) ; 2. выбор двух минимальных весов T2(1)=O((N 3)/2) ; 3. замена исходных символов кодами T3(1)=O(M) или для адаптивных версий алгоритма: T3(1)=0 . Таким образом, общее время построения дерева и собственно кодирования даже для улучшенных адаптивных версий будет не менее T(1)=T1(1)+T2(1)+T3(1) = M+(N 3)/2.

Слайд 6

Описание слайда:

Матрично-векторное умножение Обычное представление:

Слайд 7

Описание слайда:

Результаты работы программы

Слайд 8

Описание слайда:

Использование матричных операций при построении дерева алгоритма Хаффмана Алгоритм: Определить частоты встречаемости символов в сообщении, составляющих его алфавит. N ненулевых элементов алфавита – исходное множество узлов дерева. Пока число новых узлов меньше N-1 Упорядочить узлы. Добавить новый узел, соответствующий двум минимальным. Для всех символов алфавита добавить очередной разряд в код Хаффмана. Конец Пока Заменить символы на их коды.

Слайд 9

Описание слайда:

Использование матричных операций при построении дерева алгоритма Хаффмана Рассмотрим множество, состоящее из элементов 0,1, . Пусть T – множество, которому принадлежат элементы матрицы, и P, P1, P2 – предикаты, определенные на T. Тогда операции умножения и сложения любых определим следующим образом (1) (2) Элементы Cij матрицы будем вычислять по следующим формулам (3) (3’)

Слайд 10

Описание слайда:

Определение частот встречаемости символов в сообщении Представим исходное сообщение, символы которого принадлежат множеству входного алфавита , матрицей размера . Пусть – искомый вектор из N чисел, каждое из которых равно числу вхождений соответствующего элемента алфавита в исходное сообщение. Для нахождения его значений образуем новую матрицу размера , каждая строка которой состоит из элементов алфавита , так что , . Выполним умножение матриц , определив в нем операцию умножения компонент (4) Каждая строка произведения будет соответствовать числу вхождений соответствующего символа алфавита в строку матрицы исходного сообщения . Свертка произведения по столбцам (сверху – вниз) позволит получить искомый вектор . При представлении входной матрицы как вектора размера свертки не потребуется.

Слайд 11

Описание слайда:

Использование матричных операций при построении дерева алгоритма Хаффмана

Слайд 12

Описание слайда:

Упорядочивание узлов дерева Рассмотрим возможность использования введенной операции матричного умножения для упорядочения элементов, составляющих вектор исходных значений длины N. Назовем вектором упорядоченности последовательность индексов, соответствующую расположению элементов в порядке их возрастания. Для нахождения значений этого индексного вектора упорядоченности образуем новую матрицу размера , каждая строка которой состоит из элементов исходного вектора . Выполним умножение матриц , определив в нем только операцию умножения компонент (5) Чтобы получить индексный вектор упорядоченности выполним умножение исходного вектора на матрицу , c учетом (5) и при арифметическом сложении: , где

Слайд 13

Описание слайда:

Добавление нового узла Для выбора двух минимальных узлов и добавления соответствующего им нового узла–родителя преобразуем вектор , добавив в него незначащие разряды для всех пока не созданных вершин. Выполним над две операции. Первая, матричная, заключается в создании для каждого нового узла вектора кода длины , разряды которого соответствуют полному множеству как исходных, так и новых узлов дерева. Вектор содержит коды 1,0 в разрядах двух минимальных вершин и код 1 в разряде новой родительской вершины. Вторая операция состоит в добавлении к вектору разряда для значения веса новой вершины, вычисления этого значения и удаления двух минимальных значений. Для нахождения значений умножим вектор на матрицу , значение которой формируются разверткой . При этом операцию умножения определим как (6) где – номер добавляемой вершины. Операцию сложения определим в виде

Слайд 14

Описание слайда:

Формирование кодовых разрядов При добавлении очередной -ой вершины разобьем сформированный вектор на два: вектор , соответствующий элементам исходного алфавита и вектор , состоящий из элементов родительских разрядов. Пусть – матрица кодов, столбцы которой – это векторы , каждый из которых соответствует добавленной вершине. Размер матрицы кодов равен , где – порядковый номер добавляемого узла-родителя. Тогда -ый вектор-столбец матрицы кодов Хаффмана может быть получен умножением матрицы на вектор . При этом операции умножения и сложения определим следующим образом: (7) (8)

Слайд 15

Описание слайда:

Суммарная оценка эффективности распараллеливания Определение частот встречаемости символов в сообщении (общее число сложений ): Упорядочение узлов дерева: Добавление нового узла: Формирование кодовых разрядов: Замена символов сообщения кодами: Суммарная оценка эффективности распараллеливания: (9)

Слайд 16

Описание слайда:

Суммарная оценка эффективности распараллеливания

Слайд 17

Описание слайда:

Пример Пусть задано следующее множество элементов входного алфавита (N=3) и соответствующие им веса: а–5, б–3, в–7. Упорядочим узлы: где

Слайд 18

Описание слайда:

Пример Формируем кодовые разряды: Получили итоговую матрицу:

Слайд 19

Описание слайда:

Список используемых источников 1 Алексеев Е. Р. Учимся программировать на Microsoft Visual C++ и Turbo C++ Explorer / Е. Р. Алексеев, под ред. О. В. Чесноковой. – М. : НТ Пресс, 2007 –352 c. 2 Антонов А. С. Параллельное программирование с использованием технологии MPI: учебное пособие / А. С. Антонов. – М. : МГУ, 2004. –71 с. 3 Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. – М. : Мир, 1979. – С. 255-283 4 Гергель В. П. Теория и практика параллельных вычислений / В. П. Гергель. – М. : Бином. Лаборатория знаний , 2007. – 424 с. 5 История развития теории сжатия информации [Электронный ресурс]. – Режим доступа: 6 Новиков Ф. А. Дискретная математика для программистов: учебник для вузов. 2-е изд. / Ф. А. Новиков. – СПб. : Питер, 2005. – С. 171-215 7 Самойлов М. Ю. Использование матричных операций при построении дерева Хаффмана / М. Ю.Самойлов, Т. А. Самойлова. – Смоленск: СГМА Математическая морфология. Электронный математический и медико-биологический журнал. Русская версия 2.0. –Том 2. – Вып.2, 1997. – 246 с. 8 Хокни Р. Параллельные ЭВМ / Р. Хокни, К. Джессхоуп. – М. : Радио и связь, 1986. – С. 253-255, 264-269