11 разів - 44. Якщо ми додамо після невелика кількість байтів для збереження місця вузла і деяку іншу статистику - наша таблиця буде приблизно 50 байтів довжини. Додавши до 30 байтам стислій інформації, 50 байтів таблиці отримуємо, що загальна довжина архівного файлу виросте до 80 байт. Враховуючи, що первісна довжина файлу в розглянутому прикладі була 100 байт - ми отримали 20% стиснення інформації. Не погано. Те що ми дійсно виконали - трансляція символьного ASCII набору в наш новий набір вимагає меншу кількість знаків в порівнянні з стандартним.
Що ми можемо отримати на цьому шляху?
Розглянемо максимум которй ми можемо отримати для різних розрядних комбінацій у оптимальному дереві, яке є несиметричним.
Ми отримаємо що можна мати тільки:
4 - 2 розрядних коду;
8 - 3 розрядних кодів;
16 - 4 розрядних кодів;
32 - 5 розрядних кодів;
64 - 6 розрядних кодів;
128 - 7 розрядних кодів;
Необхідно ще два 8 розрядних коду.
4 - 2 розрядних коду;
8 - 3 розрядних кодів;
16 - 4 розрядних кодів;
32 - 5 розрядних кодів;
64 - 6 розрядних кодів;
128 - 7 розрядних кодів;
--------
254
Отже ми маємо підсумок з 256 різних комбінацій якими можна кодувати байт. З цих комбінацій лише 2 по довжині дорівнюють 8 бітам. Якщо ми складемо число бітів які це представляє, то в результаті отримаємо 1554 біт або 195 байтів. Так у максимумі, ми стиснули 256 байт до 195 або 33%, таким чином максимально ідеалізований Huffman може досягати стиснення в 33% коли використовується на рівні байта Всі ці підрахунки проводилися для НЕ префіксних кодів Хаффмана тобто кодів, які не можна ідентифікувати однозначно. Наприклад код A - 01011 та код B - 0101. Якщо ми будемо отримувати ці коди побітно, то отримавши біти 0101 ми не зможемо сказати який код ми отримали A або B, так як наступний біт може бути як початком наступного коду, так і продовженням попереднього.
Необхідно додати, що ключем до побудови префіксних кодів служить звичайне бінарне дерево і якщо уважно розглянути попередній приклад з побудовою дерева, можна переконається, що всі одержувані коди там префіксние.
Одне остання примітка - алгоритм Хаффмана вимагає читати вхідний файл двічі, один раз вважаючи частоти входження символів, інший разпроізводя безпосередньо кодування.
P.S. Про "ключику" дає дорогу алгоритмом Running. p> ---- Прочитавши оглядову інформацію про Huffman кодуванні подумайтенад тим, що на нашому бінарному дереві може бути і 257 листочків.
Список літератури
1) Опис архіватора Narc фірми Infinity Design Concepts, Inc.; p> 2) Чарльз Сейтер, 'Стиснення даних', "Світ ПК", N2 1991;
Додаток
{$ A +, B-, D +, E +, F-, G-, I-, L +, N-, O-, R +, S +, V +, X-}
{$ M 16384,0,655360}
{********************************************** ********}
{* Алгорит...
