244
правки
Изменения
Нет описания правки
# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
# Обобщите алгоритм Хаффмана для ""сжатых"" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.
# Верно ли, что если длины кодовых слов некоторого кода удовлетворяют неравенству Крафта-МакМиллана, то это код является однозначно декодируемым?
# Приведите пример префиксного кода с длинами кодовых слов $1, 2, 3, \ldots, n-1, n-1$.
# Приведите пример префиксного кода с длинами кодовых слов $1, 3, 3, 5, 5, 5, 5, \ldots$ (слов длины $2i+1$ будет $2^i$ для $i$ от 1 до $k$).
# Петя утверждает, что он разработал однозначно декодируемый код $c$, в котором для каждой строки $x$ длина её кода $c(x)$ не больше длины $x$, а хотя бы для одной длина кода строго меньше. Прокомментируйте результат Пети.
# Вася утверждает, что он разработал однозначно декодируемый код $c$, в котором для некоторого $n$ хотя бы для половины строк $x$ длины не больше $n$ длина кода $c(x)$ строго меньше длины $x$. Прокомментируйте результат Васи.
# Пусть вероятности символов упорядочены по убыванию ($p_1 \ge p_2 \ge \ldots \ge p_n$) и являются дробями, у которых числитель 1, а знаменатель - степень двойки. Что можно сказать про арифметическое кодирование в этом случае?
# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в среднем тратит в $c$ раз меньше бит на символ строки, чем код Хаффмана.
# При арифметическом кодировании может повезти и у достаточно длинной строки код получится коротким, хотя длина строки большая, и оценка на длину кода тоже большая. Приведите пример такой строки.
# Для предыдущего задания приведите пример бесконечной последовательности строк возрастающей длины, для которых проявляется описанный эффект.
# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
# Проанализируйте время работы алгоритма арифметического кодирования (с учетом длинной арифметики).
# Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как троичное число, дополненное ведущими нулями до длины $q$. Затем запишем числитель в двоичной записи, а ведущие нули заменим на нули в двоичной записи. Приведите пример строки, когда описанный метод через степени тройки будет лучше классического арифметического кодирования.
# Приведите пример строки, когда метод из предыдущего задания будет хуже классического арифметического кодирования. # Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
# Предложите алгоритм декодирования кода Барроуза-Уиллера.
# Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
# Предложите реализацию преобразования Move to Front за $O(n \log n)$.
# Предложите реализацию преобразования Move to Front за $O(n)$.
