Программирование на Prolog – дерево Хаффмана

Главная Форумы Программирование Помощь с решением задач на Prolog Программирование на Prolog – дерево Хаффмана

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 9 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #3360

    При передачи текста, символы кодируются. Выгодно кодировать символы, имеющие высокую частоту вхождения более короткими символами, а символы с низкой частотой – длинными. Способ кодирования, при котором разные символы кодируются последовательностями разной длины называется неравномерным кодированием. Последовательность нулей и единиц должна быть такой, чтобы можно было однозначно установить где кончается предыдущий символ и начинается следующий. Алгоритм Хаффмана является оптимальным способом построения такой кодовой таблицы. Разберем алгоритм и напишем на языке Prolog реализующую его программу.

    Алгоритм построения дерева Хаффмана

    На вход алгоритма подается алфавит с частотами вхождения букв, на выходе формируется двоичное дерево из символов алфавита (дерево Хаффмана). При этом символы в дереве размещены так, что для получения кода достаточно пройти от корня дерева до символа, дописывая к коду ноль при переходе по левой ветви и единицу – по правой.

    Каждый элемент рассматривается как узел дерева, т.е. можно считать, что в начале на вход подается список деревьев.

    1. символы алфавита сортируются по убыванию частоты вхождения;
    2. если в списке Trees остался один элемент – то он является корнем дерева Хаффмана, результат получен;
    3. последние два элемента (с наименьшими частотами) удаляются из списка, из них формируется поддерево (Subtree) так, что первый узел становится левым, а второй – правым. В качестве частоты новому узлу присваивается сумма частот его элементов;
    4. узел вставляется в список так, чтобы сохранить порядок элементов (по убыванию частоты);
    5. переход на п.2.

    Проиллюстрируем алгоритм на примере, для этого возьмем часть символов русского алфавита – их частоты вхождения в текст известны. Отсортируем их по частоте:

    Выбираем два символа с наименьшей частотой и объединяем в поддерево:

    Т.к. построение начинается с самых редко используемых символов, то и закодированы они будут наиболее длинными последовательностями.
    Выбираем следующие два узла и объединяем их:

    Продолжаем процесс до тех пор, пока не останется один узел в списке:

    Построение дерева Хаффмана на Prolog

    Фрагмент, реализующий этот алгоритм на языке Visual Prolog:

           	haffmen_tree([SingleTree], SingleTree):-!.
           	haffmen_tree(Trees, HaffmenTree):-
           		qsort(Trees, [A, B|SortedTail]),
           		haffmen_tree([tree(A, B)|SortedTail], HaffmenTree).
           		
           	print_codes(count(Char, _), Codes):-
           		write(Char), write(" -> "), write(Codes), nl.
           	print_codes(tree(Left, Right), Codes):-
           		frontchar(LeftCodes, '0', Codes),
           		frontchar(RightCodes, '1', Codes),
           		print_codes(Left, LeftCodes),
           		print_codes(Right, RightCodes).

    В данном случае используется быстрая сортировка списка после объединения каждой пары узлов, однако более оптимально использовать вставку (из алгоритма сортировки вставками).

Для ответа в этой теме необходимо авторизоваться.