abstract: В статье рассматривается метод реализации алгоритма Хаффмана, кодирующего входной битовый поток данныхв двоичном алфавите. Применяемый к битовой последовательности входных данных, разделяемой на разбиения фиксированной длины, он позволяет эффективно сжимать исходные данные. Выбор длины разбиения определяет количество символов во входном алфавите. Mетод широко применяется в сложныха лгоритмахупа ковки/распаковки данныхразличны х вычислительныху стройств. Для оценки времени работы алгоритма рассматривается одноленточная детерминированная машина Тьюринга со входной и выходной лентами. Время ее работы оценивается как число шагов в зависимости от длины входных данных. Доказано, что при выборе длины разбиения (битового представления входного алфавита) m = 71 k log n8+1, где n общая длина входных данных, время работы алгоритма Хаффмана может быть сделано почти линейным, более точно, с верхней оценкой O(n k+1 k ) при любом рациональном k 2, k log n. Рассматривается приложение алгоритма Хаффмана к задаче разбиения множества весов X = {x1,..., xM} на два равныхп о весу подмножества. Доказано, что в случае, когда относительныевеса элементов xi имеют вид wi = 2−mi, где mi целое положительное число, алгоритм Хаффмана дает точное решение задачи о разбиении. Библиогр. 12 назв.
keywords: алгоритм хаффмана, алгоритм шеннона-фано, машина тьюринга, сложность вычислений, задача о разбиении множества