ОПТИМІЗАЦІЯ КАНОНІЧНИХ КОДІВ ХАФМАНА

Завадський, І., Ковальчук, М. (2025). Optimization of the canonical Huffman codes for word-based natural language text compression. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, 81(2), 159–165. https://doi.org/10.17721/1812-5409.2025/2.25

Канонічні коди Хафмана - це метод стискального кодування джерела даних, що дає можливість швидкого декодування, не зменшуючи ефективності стиснення порівняно з класичними кодами Хафмана. Якщо алфавіт тексту, що стискається, містить не більше 100-200 символів, будь-який код змінної довжини, зокрема коди Хафмана, можна ефективно декодувати наївним 'табличним' методом. Канонічні коди Хафмана доцільно використовувати насамперед якщо алфавіт є великим, тобто містить тисячі символів. У природномовному тексті, наприклад, елементами такого алфавіту можуть бути слова. Найшвидший на сьогодні алгоритм декодування канонічних кодів запропоновано М. Лідлем та А. Мофатом. Ми пропонуємо кілька оптимізацій цього алгоритму, що, як свідчать проведені нами експерименти, дають змогу прискорити його на 20-30\%, не знижуючи коефіцієнту стиснення. Деякі з цих оптимізацій базуються на низькорівневому розпаралелюванні коду з використанням SIMD-архітектури сучасних процесорів, в інших пропонується поєднувати класичне декодування канонічних кодів із універсальним ‘табличним’ методом. Крім згаданих оптимізацій, у статті детально розглянуто канонічні коди Хафмана, включно з базовим та оптимізованим М. Лідлем та А. Мофатом алгоритмами, а також універсальний 'табличний' метод декодування кодів змінної довжини. Представлено результати експериментального порівняння швидкодії базового та оптимізованих алгоритмів. Результати дослідження можуть бути використані в системах інформаційного пошуку та архівування даних.