О битовой длине разбиений входного потока алгоритма Хаффмана при реализации на машинах Тьюринга с почти линейным временем.

М.А. Герасимов

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборникенаучная

Аннотация

Рассматривается задача оптимизации длины разбиения битового входного потока данных при сжатии с помощью алгоритма Хаффмана. Найденная формула определения длины разбиения позволяет оптимально сжимать входной поток данных алгоритмом Хаффмана с почти линейной оценкой временной сложности на машинах Тьюринга для любого размера входных данных.
Язык оригиналарусский
Название основной публикацииМатериалы XVIII международной школы-семинара "Синтез и сложность управляющих систем" имени академика О.Б.Лупанова
СтраницыС. 24-26
СостояниеОпубликовано - 2009
Опубликовано для внешнего пользованияДа

Ключевые слова

  • Алгоритм Хаффмана
  • Машина Тьюринга
  • битовое разбиение.

Цитировать