Презентация по информатике на тему "Алгоритм Хаффмана"

Алгоритм Хаффмана Идея, положенная в основу кодировании Хаффмана, основана на  частоте появления символа в последовательности. Символ, который  встречается в последовательности чаще всего, получает новый очень  маленький код, а символ, который встречается реже всего, получает,  наоборот, очень длинный код.  При стандартном кодировании каждый символ кодируется 1 байтом,  т.е. 8 битами. При кодировании алгоритмом Хаффмана для любого текста можно  разработать свой код. Для этого алгоритма вам потребуется минимальное понимание  устройства бинарного дерева и очереди с приоритетами.

Предположим, у нас есть строка «beepboopbeer!», для которой,  в её текущем виде, на каждый знак тратится по одному байту.  Это означает, что вся строка целиком занимает 15*8 = 120 бит  памяти. Посмотрим, какой размер будет иметь эта строка при  использовании алгоритма Хаффмана. Чтобы получить код для каждого символа на основе его  частотности, нам надо построить бинарное дерево, такое, что  каждый лист этого дерева будет содержать символ (печатный  знак из строки).  Дерево будет строиться от листьев к корню, в том смысле, что  символы с меньшей частотой будут дальше от корня, чем  символы с большей. Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами — первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню.

Для начала посчитаем частоты всех символов: Символ 'b' 'e' 'p' ‘ ' 'o' 'r' '!' Частота 3 4 2 2 2 1 1 После вычисления частот мы создадим узлы бинарного дерева  для каждого знака и добавим их в очередь, используя частоту в  качестве приоритета:

Теперь мы достаём два первых элемента из очереди и связываем  их, создавая новый узел дерева, в котором они оба будут  потомками, а приоритет нового узла будет равен сумме их  приоритетов. После этого мы добавим получившийся новый  узел обратно в очередь.

Повторим те же шаги и получим последовательно:

Ну и после того, как мы свяжем два последних элемента,  получится итоговое дерево:

Теперь, чтобы получить код для каждого символа, надо просто  пройтись по дереву, и для каждого перехода добавлять 0, если мы  идём влево, и 1 — если направо: Если мы так сделаем, то получим  следующие коды для символов: Символ 'b' 'e' 'p' ' ' 'o' 'r' '!' Код 00 11 101 011 010 1000 1001

Чтобы расшифровать закодированную строку, нам надо, соответственно,  просто идти по дереву, сворачивая в соответствующую каждому биту  сторону до тех пор, пока мы не достигнем листа. Например, если есть  строка «101 11 101 11» и наше дерево, то мы получим строку  «pepe».  Важно иметь в виду, что каждый код не является префиксом для кода  другого символа. В нашем примере, если 00 — это код для 'b', то 000 не  может оказаться чьим­либо кодом, потому что иначе мы получим  конфликт. Мы никогда не достигли бы этого символа в дереве, так как  останавливались бы ещё на 'b'. На практике, при реализации данного алгоритма сразу после  построения дерева строится таблица Хаффмана. Данная таблица — это  по сути связный список, который содержит каждый сим­вол и его код,  потому что это делает кодирование более эффективным. Как правило,  для кодирования используется таблица Хаффмана, а для  декодирования — дерево Хаффмана.   Закодированная строка: «0011 1110 1011 0001 0010 1010 1100 1111 1000  1001» Как вы можете заметить, между ASCII­версией строки и закодированной  версией существует большая разница.