Глубина дерева Хаффмана
Я читаю «Алгоритмы» Джеффа Эриксона, и у меня возникли проблемы с решением упражнения по жадным алгоритмам:
(b) Предположим, что общая длина N незакодированного сообщения ограничена полиномом от размера алфавита n. Докажите, что любое дерево Хаффмана для частот f[1...n] имеет глубину O(log n).
Я не знаю, как это доказать, потому что думаю, что глубина может достигать n-1, вот так: f[1...n] = {1, 1, 1, 3, 4, 7, 11, 18, 29, ...} (число Лукаса).
Может быть, это потому, что «N ограничено многочленом алфавита размера n», но что это значит? (например, N = k n, а k — константа?) Если это так, я бы сказал, что это потому, что когда я объединяю две вершины u1, u2 (u1 <= u2) в дереве Хаффмана, новая вершина v = u1 + u2, который хотя бы на один раз больше u1, и я знаю, что корень дерева равен n, поэтому я буду объединять вершины не более чем O(log n) раз, поэтому глубина составляет около O(log n ). Но я не знаю, прав ли я.
Не могли бы вы мне помочь? Спасибо!
Пожалуйста, отредактируйте вопрос, чтобы ограничить его конкретной проблемой и указать достаточно подробностей, чтобы найти адекватный ответ.
Ответы 2
Да, вы правы в том, что без каких-либо ограничений глубина действительно может достигать n-1 в крайне несбалансированном случае, когда у вас фактически есть связанный список.
Однако добавлено ограничение «...общая длина N незакодированного сообщения ограничена полиномом размера алфавита n». подразумевает, что N=O(n^k). Следовательно, средняя частота каждого символа равна N/n=O(n^(k-1)). Это означает, что частота ни одного персонажа не является непропорционально большой или маленькой по сравнению с другими. Частоты распределяются более равномерно, что предотвращает чрезмерный дисбаланс при построении дерева.
Если мы рассмотрим двоичное дерево, высота будет логарифмической по количеству листьев, если дерево сбалансировано. Для идеально сбалансированного дерева высота равна O(log n).
Хотя дерево Хаффмана с этим ограничением не всегда идеально сбалансировано, сбалансированный характер слияний из-за тенденции к равномерному распределению частот гарантирует, что высота будет близка к O (log n).
Ваша последовательность в стиле Лукаса является ответом на часть (а) этого вопроса, что является подсказкой о том, что она может быть полезна при ответе на часть (б).
Общая длина сообщения с частотами Лукаса равна двум числам Люка от последней частоты минус один. Таким образом, чтобы получить дерево Хаффмана глубины d, минимальная длина сообщения равна Ld+1 - 1. (Обратите внимание, что L0=2, которое разбивается на начальные {1,1}. Вот почему я сказал «как у Лукаса» ранее. Тогда L1=1, L2=3.) Для длины сообщения N у нас есть N ≥ Ld+1 - 1, чтобы иметь возможность получить дерево глубины d.
Последовательность Люка (как и последовательность Фибоначчи) растет экспоненциально по закону φn, где φ — золотое сечение. В частности Ln > φn-1.
Чтобы получить глубину d, нужно N > φd. Итак, log(N) > d log(φ). p(n) ≥ N, где p — многочлен, скажем, степени k. Итак, log(p(n)) > d log(φ). Используя высшую степень p для получения порядка, мы имеем d ≤ O(k log(n) / log(φ)) или просто d ≤ O(log(n)), поскольку k и φ — константы, независимые от n. . Мы знаем, что d ≥ ⌈log(n)⌉, поэтому d = O(log(n)).
Спасибо! Теперь я понимаю взаимосвязь между частотами и глубиной Дерева Хаффмана.
Это не платформа для помощи в выполнении заданий. Также покажите свои разные попытки и места, где вы застряли.