Код Гаффмана: відмінності між версіями

Беручи до уваги сказане вище, алгоритм поновлення дерева Хаффмана повинен бути змінений таким чином: при збільшенні ваги потрібно перевіряти його на досягнення допустимого максимуму. Якщо ми досягли максимуму, то необхідно «масштабувати» вагу, зазвичай розділивши вагу листялистка на ціле число, наприклад, 2, а потім перерахувавши вагавагу всіх інших вузлів.

Правильно організоване дерево Хаффмана після масштабування може мати форму, яка значно відрізняється від вихідної. Це відбувається тому, що масштабування призводить до втрати точності нашої статистики. Але зі збором нової статистики наслідки цих «помилок» практично сходять нанівець. Масштабування ваги - досить дорога операція, оскільки вона призводить до необхідності заново будувати все дерево кодування. Але, так як необхідність в ній виникає відносно рідко, то з цим можна змиритися.

Масштабування ваги вузлів дерева через певні інтервали дає несподіваний результат. Незважаючи на те, що при масштабуванні відбувається втрата точності статистики, тести показують, що воно призводить до кращих показників стиснення, ніж якщо б масштабування відкладалося. Це можна пояснити тим, що поточні символи стисливогостисненого потоку більше «схожі» на своїх близьких попередників, ніж на тих, які зустрічалися набагато раніше. Масштабування призводить до зменшення впливу «давніх» символів на статистику і до збільшення впливу на неї «недавніх» символів. Це дуже складно виміряти кількісно, ​​але, в принципі, масштабування робить позитивний вплив на ступінь стиснення інформації. Експерименти з масштабуванням в різних точках процесу стиснення показують, що ступінь стиснення сильно залежить від моменту масштабування ваги, але не існує правила вибору оптимального моменту масштабування для програми, орієнтованої на стиск будь-яких типів інформації.