Подсчитываются вероятности появления символов первичного алфавита в исходном тексте (если они незаданы заранее)Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.Последние n0 символов объединяют в новый символ, вероятность которого равна суммарной вероятностиэтих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующееместо (по вероятности). n0 вычисляется из системы:
,
где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно.Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции,предварительно удалив символы, вошедшие в объединение.Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1,получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущегошага и т. д.Каждые m2 элементов, стоящих на одном уровне, нумеруются от 0 до m2-1. Коды получаются из путей (отпервого потомка корня и до листка). При декодировании можно использовать то же самое дерево,считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ,стоящий в листе и производится возврат в корень.Построение дерева ХаффманаБинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана.Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.Общая схема построения дерева Хаффмана:Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементноебинарное дерево, вес которого равен весу символа).Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа— чем чаще используется, тем больше весит).Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. Приэтом вес сформированного узла положим равным сумме весов дочерних узлов.Добавим сформированный узел к списку.Если в списке больше одного узла, то повторить 2-5.Пример реализацииПример реализации алгоритма Хаффмана на языке// скомпилируйте и введите java HuffmanTest
class Tree {
public Tree child0; // потомки "0" и "1"
public Tree child1;
public boolean leaf; // признак листового дерева
public int character; // входной символ
public int weight; // вес этого символа
public Tree() {}
public Tree(int character, int weight, boolean leaf) {
this.leaf = leaf;
this.character = character;
this.weight = weight;
}
/* Обход дерева с генерацией кодов
1. "Распечатать" листовое дерево и записать код Хаффмана в массив
2. Рекурсивно обойти левое поддерево (с генерированием кода).
3. Рекурсивно обойти правое поддерево.
*/
public void traverse(String code, Huffman h) {
if (leaf) {
System.out.println((char)character +" "+ weight +" "+ code);
h.code[character] = code;
}
if ( child0 != null) child0.traverse(code + "0", h);
if ( child1 != null) child1.traverse(code + "1", h);
}
}
class Huffman {
public static final int ALPHABETSIZE = 256;
Tree[] tree = new Tree[ALPHABETSIZE]; // рабочий массив деревьев
int weights[] = new int[ALPHABETSIZE]; //