EUVIMEDEUVIMED entdecken
Crossref

Optimization of the canonical Huffman codes for word-based natural language text compression

Igor Zavadskyi, Maksym Kovalchuk

Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics · 2025 · (2) · 159-165

DOI: 10.17721/1812-5409.2025/2.25 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics, 2025. Verfasst von Igor Zavadskyi und 1 weiteren Autor:innen. Die Arbeit nennt 10 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Canonical 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.

Zitieren

APA

Zavadskyi, I., & Kovalchuk, M. (2025). Optimization of the canonical Huffman codes for word-based natural language text compression. Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics, 159-165. https://doi.org/10.17721/1812-5409.2025/2.25

Vancouver

Zavadskyi I, Kovalchuk M. Optimization of the canonical Huffman codes for word-based natural language text compression. Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics. 2025:159-165. doi:10.17721/1812-5409.2025/2.25

BibTeX
@article{Zavadskyi2025,
  author = {Zavadskyi, Igor and Kovalchuk, Maksym},
  title = {Optimization of the canonical Huffman codes for word-based natural language text compression},
  journal = {Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics},
  year = {2025},
  number = {2},
  pages = {159--165},
  doi = {10.17721/1812-5409.2025/2.25}
}
Kostenlos starten →