О построении дерева Хаффмана

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

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

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

Оценка сложности последовательного алгоритма
Пусть 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.

Матрично-векторное умножение
Обычное
представление:
Ленточное разбиение:
Горизонтальное разбиение по строкам:
где - i-я строка матрицы A (предполагается, что количество строк m кратно числу процессоров p, т.е. m = k⋅p)

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

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

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

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

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

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

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

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

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

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

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

Пример
Формируем кодовые разряды:
Получили итоговую матрицу:
M=3, N=37 :