Завадський, ІгорІгорЗавадськийКовальчук, МаксимМаксимКовальчук2026-06-302026-06-302025-12-23Завадський, І., Ковальчук, М. (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.2510.17721/1812-5409.2025/2.25https://ir.library.knu.ua/handle/15071834/25746Canonical Huffman codes are widely used in data compression and allow fast decoding without compromising compression efficiency compared to classical Huffman codes. If the maximal length of a codeword does not exceed 11-12 bits or long codewords are very rare, any variable-length code, including Huffman codes, can be effectively decoded using a naive ’table’ method. Canonical Huffman codes should be used primarily if the encoded text consists of a relatively large number of long codewords. For example, this is the case of word-level natural language text compression, where words are the symbols of an alphabet. A. Moffat and A. Turpin proposed the fastest state-of-the-art algorithm for decoding canonical codes. We offer several optimizations of this algorithm, which, according to our experiments, can speed it up by 20-30% without reducing the compression ratio. Some of these optimizations are based on low-level code parallelization using the SIMD architecture of modern processors, while others propose combining classical decoding of canonical codes with a universal ’table’ decoding method. In addition to the above optimizations, the article discusses in detail the canonical Huffman codes, including the basic and optimized algorithms, as well as the universal ’table’ method for decoding arbitrary variable-length codes. The results of an experimental comparison of the performance of the basic and optimized algorithms are presented. The results of the study can be used in information retrieval and data archiving systems. Pages of the article in the issue: 159 - 165 Language of the article: EnglishКанонічні коди Хафмана - це метод стискального кодування джерела даних, що дає можливість швидкого декодування, не зменшуючи ефективності стиснення порівняно з класичними кодами Хафмана. Якщо алфавіт тексту, що стискається, містить не більше 100-200 символів, будь-який код змінної довжини, зокрема коди Хафмана, можна ефективно декодувати наївним 'табличним' методом. Канонічні коди Хафмана доцільно використовувати насамперед якщо алфавіт є великим, тобто містить тисячі символів. У природномовному тексті, наприклад, елементами такого алфавіту можуть бути слова. Найшвидший на сьогодні алгоритм декодування канонічних кодів запропоновано М. Лідлем та А. Мофатом. Ми пропонуємо кілька оптимізацій цього алгоритму, що, як свідчать проведені нами експерименти, дають змогу прискорити його на 20-30\%, не знижуючи коефіцієнту стиснення. Деякі з цих оптимізацій базуються на низькорівневому розпаралелюванні коду з використанням SIMD-архітектури сучасних процесорів, в інших пропонується поєднувати класичне декодування канонічних кодів із універсальним ‘табличним’ методом. Крім згаданих оптимізацій, у статті детально розглянуто канонічні коди Хафмана, включно з базовим та оптимізованим М. Лідлем та А. Мофатом алгоритмами, а також універсальний 'табличний' метод декодування кодів змінної довжини. Представлено результати експериментального порівняння швидкодії базового та оптимізованих алгоритмів. Результати дослідження можуть бути використані в системах інформаційного пошуку та архівування даних.enHuffmanencodingcodescanonicaltext compressionХафманкодуваннякодиканонічністискання текстуСтаття