Реализация с массивом

Структура данных SW – массив (сортировка: около n log₂ n операций).

Основные затраты связаны с операцией Insert.

Бинарный поиск места вставки на i-м шаге в массиве

из k = n  i  1 элементов требует не более log₂(k + 1) операций.

Как легко показать, суммарно за все n  1 шагов алгоритма это даст около n log₂ n операций.

Вставка элемента в найденное место в массиве из k элементов требует в среднем около k/2 операций.

Суммарно по всем значениям k от 1 до n  1 это даст около n²/4 операций.

Итак, реализация алгоритма с использованием упорядоченного массива имеет сложность порядка n².

Реализация со списками

Сначала создается упорядоченный список весов (на это требуется около n log₂ n операций).

Всего около n log₂ n

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

Имеет сложность порядка n log₂n.

Использует реализацию структуры SW на базе так называемой пирамиды

(бинарного дерева, обладающего свойством пирамидальности и размещенного в массиве – рассмотрим позднее).

В этом случае и операция извлечения минимального элемента, и операция вставки имеют сложность

порядка log₂n.

Суммарно по всем шагам это дает сложность

порядка n log₂n

14. Кодирование информации по Хаффману. Оптимальность метода. (Лек 6)

15. Энтропийная оценка оптимальной длины кода. (Лек 6)

16. Динамическое кодирование по Хаффману. Постановка задачи и идея алгоритма. (Лек 6)

Недостатки статического метода Хаффмана :

• двухпроходность алгоритма (сначала вычисляются веса , затем строится дерево (код));

• необходимость передавать кодовое дерево вместе с последовательностью закодированных сообщений.

Алгоритм перестроения дерева Хаффмана

Пусть дерево Хаффмана (ДХ) строится так, что левый сын имеет вес не больший, чем правый.

При этом ДХ, вообще говоря, не единственно.

Пример: заданы веса W₄ = (5, 4, 3, 2).

Дерево Хаффмана является строго бинарным и содержит ровно 2n  1 узлов, n из которых являются листьями.

Действительно, пусть в строго бинарном дереве содержится n листьев (внешних узлов) и s внутренних узлов.

Тогда число исходящих из внутренних узлов веток есть 2s.

Подсчет этих же веток, как входящих во все узлы дерева, кроме корня, дает n + s  1.

Таким образом, 2s = n + s  1.

Отсюда следует s = n  1

и общее число узлов n + s = 2n  1.

В общем случае неубывающая последовательность весов x₁  x₂  x₃  …  x_2n 1, получаемых в порядке взвешенного сочетания узлов в алгоритме Хаффмана, инвариантна для всех деревьев Хаффмана с заданными весами w₁  w₂  …  w_n  1  w_n.

При этом внутренние узлы имеют веса x₁ + x₂, x₃ + x₄, …, x_2n 3 + x_2n 2 = x_2n 1.

Строго бинарное упорядоченное дерево

А) n внешних узлов (листьев) получили веса (w₁, w₂, …, w_n) в каком-то порядке, и каждый внутренний узел получил вес, равный сумме своих сыновей;

• Б) 2n  1 узлов (внутренних и внешних) можно перечислить в такой последовательности (y₁, y₂, …, y_n  1, y_n), что если x_i  вес узла y_i, то x₁  x₂  …  x_2n 1; узлы y_2j 1 и y_2j  братья (сыновья одного отца).

• упорядоченное дерево  дерево Хаффмана