ОПТИМІЗАЦІЯ КАНОНІЧНИХ КОДІВ ХАФМАНА
Тип публікації :
Стаття
Дата випуску :
23 грудня 2025 р.
Автор(и) :
Ковальчук, Максим
Мова основного тексту :
Англійська
eKNUTSHIR URL :
Том :
81
Випуск :
2
ISSN :
1812-5409
Початкова сторінка :
159
Кінцева сторінка :
165
Цитування :
[APA 7] Завадський, І., & Ковальчук, М. (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
[ДСТУ] Завадський І., Ковальчук М. Optimization of the canonical Huffman codes for word-based natural language text compression. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics. 2025. Vol. 81, no. 2. P. 159—165. DOI: 10.17721/1812-5409.2025/2.25 (date of access: 25.07.2026).
Канонічні коди Хафмана - це метод стискального кодування джерела даних, що дає можливість швидкого декодування, не зменшуючи ефективності стиснення порівняно з класичними кодами Хафмана. Якщо алфавіт тексту, що стискається, містить не більше 100-200 символів, будь-який код змінної довжини, зокрема коди Хафмана, можна ефективно декодувати наївним 'табличним' методом. Канонічні коди Хафмана доцільно використовувати насамперед якщо алфавіт є великим, тобто містить тисячі символів. У природномовному тексті, наприклад, елементами такого алфавіту можуть бути слова. Найшвидший на сьогодні алгоритм декодування канонічних кодів запропоновано М. Лідлем та А. Мофатом. Ми пропонуємо кілька оптимізацій цього алгоритму, що, як свідчать проведені нами експерименти, дають змогу прискорити його на 20-30\%, не знижуючи коефіцієнту стиснення. Деякі з цих оптимізацій базуються на низькорівневому розпаралелюванні коду з використанням SIMD-архітектури сучасних процесорів, в інших пропонується поєднувати класичне декодування канонічних кодів із універсальним ‘табличним’ методом. Крім згаданих оптимізацій, у статті детально розглянуто канонічні коди Хафмана, включно з базовим та оптимізованим М. Лідлем та А. Мофатом алгоритмами, а також універсальний 'табличний' метод декодування кодів змінної довжини. Представлено результати експериментального порівняння швидкодії базового та оптимізованих алгоритмів. Результати дослідження можуть бути використані в системах інформаційного пошуку та архівування даних.
Ключові слова :
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
245.17 KB
Контрольна сума :
(MD5):a3b058b952df4926cfddb3ac9c267431
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International