Шифр Хафмана

2 КАТЕГОРИИ · 2 БАЛЛА

17. Адаптивное сжатие

Распределите особенности алгоритмов Хаффмана.

Слова для распределения: Дерево строится один раз для всего файла, Не требует предварительного анализа всего файла, Дерево перестраивается в процессе кодирования, Таблица частот передается вместе с кодом, Эффективен для потоковых данных, Требует два прохода по данным

ВЫБОР ОТВЕТА · 2 БАЛЛА

18. Вариативность дерева

Могут ли для одного и того же набора частот существовать разные деревья Хаффмана?

• Да, если есть узлы с одинаковыми весами
• Нет, алгоритм всегда выдает строго одну структуру
• Да, но только если количество символов нечетное
• Нет, так как это нарушит условие однозначного декодирования

КРАТКИЙ ОТВЕТ · 2 БАЛЛА

19. Максимальная длина

Какова максимально возможная длина кодового слова (в битах) для алфавита из 4 символов при использовании алгоритма Хаффмана?

РАСЧЕТ · 2 БАЛЛА

20. Коэффициент сжатия

Текст состоит из 100 символов алфавита из 4 букв. При равномерном коде размер файла — 200 бит. После сжатия Хаффманом средняя длина кода составила 1.6 бита на символ. Вычислите коэффициент сжатия (отношение старого размера к новому).

2 КАТЕГОРИИ · 3 БАЛЛА

21. Хаффман против Шеннона-Фано

Распределите утверждения между двумя методами префиксного кодирования.

Слова для распределения: Основан на последовательном разбиении вероятностей, Не всегда дает минимальную избыточность, Строится сверху вниз (делением алфавита на группы), Всегда строит оптимальное дерево, Строится снизу вверх (от листьев к корню), Гарантирует минимальную среднюю длину кода

ВЫБОР ОТВЕТА · 3 БАЛЛА

22. Нижний предел сжатия

Какая величина определяет теоретический предел сжатия данных без потерь, к которому стремится алгоритм Хаффмана?

• Информационная энтропия Шеннона
• Мощность алфавита
• Дисперсия частот символов
• Коэффициент избыточности кода

КРАТКИЙ ОТВЕТ · 3 БАЛЛА

23. Невозможный набор

Может ли алгоритм Хаффмана сгенерировать следующий набор кодов для алфавита из 3 символов: {0, 10, 110}? Ответ дайте одним словом (Да/Нет) и обоснуйте.

МЕЖПРЕДМЕТНЫЙ БЛОК · 3 БАЛЛА

24. Сжатие ДНК

Цепочка ДНК состоит из нуклеотидов A, C, G, T. В исследуемом фрагменте из 1000 единиц частоты составили: A=0.45, C=0.25, G=0.20, T=0.10. Сколько бит займет этот фрагмент при сжатии кодом Хаффмана? В ответе укажите только число.

2 КАТЕГОРИИ · 3 БАЛЛА

25. Канонический код

Распределите свойства между стандартным кодом Хаффмана и каноническим кодом Хаффмана.

Слова для распределения: Позволяет значительно сэкономить место на хранении таблицы кодов, Структура дерева может быть произвольной при равных весах, Для декодирования нужно передавать всё дерево, Кодовые слова одной длины идут подряд как двоичные числа, Для декодирования достаточно знать только длины кодов каждого символа

ВЫБОР ОТВЕТА · 3 БАЛЛА

26. Числа Фибоначчи

Как будет выглядеть дерево Хаффмана, если частоты символов представляют собой последовательность Фибоначчи (1, 1, 2, 3, 5, 8...)?

• Максимально несбалансированное дерево (бамбук)
• Идеально сбалансированное дерево
• Дерево, где все листья находятся на одном уровне
• Полный граф

КРАТКИЙ ОТВЕТ · 3 БАЛЛА

27. Избыточность

Чему равна средняя длина кода Хаффмана для 8 равновероятных символов? Ответ дайте числом.

РАСЧЕТ · 3 БАЛЛА

28. Лингвистический расчет

В русском языке частота буквы 'о' $\approx 0.11$, а буквы 'ф' $\approx 0.002$. В некотором тексте из 5000 знаков эти буквы встретились согласно их вероятностям. На сколько больше бит суммарно займут все буквы 'ф', чем 'о', если код буквы 'о' — 3 бита, а код 'ф' — 9 бит?

2 КАТЕГОРИИ · 3 БАЛЛА

29. Виды сжатия

Распределите методы сжатия по их основному принципу.

Слова для распределения: Арифметическое кодирование, Deflate (в части LZSS), Код Хаффмана, LZW (Lempel-Ziv-Welch), LZ77, Код Шеннона-Фано

ВЫБОР ОТВЕТА · 3 БАЛЛА

30. Временная сложность

Какова временная сложность построения дерева Хаффмана для алфавита из $n$ символов при использовании приоритетной очереди (кучи)?

• $O(n\log n)$
• $O(n^2)$
• $O(n)$
• $O(2^n)$