Алгоритм Хаффмана
Материал из Википедии — свободной энциклопедии
Алгоритм Хаффмана (англ. Huffman) — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. Используется в программе bzip2 на последнем этапе сжатия данных.
В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.
Этот метод кодирования состоит из двух основных этапов:
- Построение оптимального кодового дерева.
- Построение отображения код-символ на основе построенного дерева.
[править] Алгоритм
- Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.
- Последние n0 символов объединяют в новый символ, вероятность которого равна сумме этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности). n0 вычисляется из системы:
,
где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно. - Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.
- Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.
Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущего шага и т.д.
Каждые m2 элементов, стоящих на одном уровне, нумеруются от 0 до m2-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.
[править] Пример реализации
Пример реализации алгоритма Хаффмана на языке Java (вместо упорядочивания поддеревьев, каждый раз ищем в массиве дерево с минимальным весом)
// скомпилируйте и введите 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]; // веса символов public String[] code = new String[ALPHABETSIZE]; // коды Хаффмана private int getLowestTree(int used) { // ищем самое "легкое" дерево int min=0; for (int i=1; i<used; i++) if (tree[i].weight < tree[min].weight ) min = i; return min; } public void growTree( int[] data ) { // растим дерево for (int i=0; i<data.length; i++) // считаем веса символов weights[data[i]]++; // заполняем массив из "листовых" деревьев int used = 0; // с использованными символами for (int c=0; c < ALPHABETSIZE; c++) { int w = weights[c]; if (w != 0) tree[used++] = new Tree(c, w, true); } while (used > 1) { // парами сливаем легкие ветки int min = getLowestTree( used ); // ищем 1 ветку int weight0 = tree[min].weight; Tree temp = new Tree(); // создаем новое дерево temp.child0 = tree[min]; // и прививаем 1 ветку tree[min] = tree[--used]; // на место 1 ветки кладем // последнее дерево в списке min = getLowestTree( used ); // ищем 2 ветку и temp.child1 = tree[min]; // прививаем ее к нов.дер. temp.weight = weight0 + tree[min].weight; // считаем вес нов.дер. tree[min] = temp; // нов.дер. кладем на место 2 ветки } // все! осталось 1 дерево Хаффмана } public void makeCode() { // запускаем вычисление кодов Хаффмана tree[0].traverse( "", this); } public String coder( int[] data ) { // кодирует данные строкой из 1 и 0 String str = ""; for (int i=0; i<data.length; i++) str += code[data[i]]; return str; } public String decoder(String data) { String str=""; // проверяем в цикле данные на вхождение int l = 0; // кода, если да, то отбрасываем его ... while(data.length() > 0){ for (int c=0; c < ALPHABETSIZE; c++) { if (weights[c]>0 && data.startsWith(code[c])){ data = data.substring(code[c].length(), data.length()); str += (char)c; } } } return str; } } public class HuffmanTest { // тест и демонстрация public static void main(String[] args) { Huffman h = new Huffman(); String str = "to be or not to be?"; // входные данные int data[] = new int[str.length()]; // преобразуем в массив for (int i=0; i<str.length(); i++) data[i] = str.charAt(i); h.growTree( data ); // растим дерево h.makeCode(); // находим коды str = h.coder(data); System.out.println(str); System.out.println(h.decoder(str)); } }
Результат работы для строки "to be or not to be?". Выводятся: символ, его вес и двоичный код. Далее закодированная строка и результат декодирования.
e 2 000 ? 1 0010 n 1 0011 o 4 01 5 10 t 3 110 r 1 1110 b 2 1111 11001101111000100111101000110111010110011011110000010 to be or not to be?
Соответствующее дерево Хаффмана.
root / \ 0 1 / \ / \ 00 o "_" 11 / \ / \ e 001 t 111 / \ / \ ? n b r