Data compression is a process of transforming data in order to reduce its volume. Two important parameters of any compression algorithm are the compression ratio and speed. The compression ratio is crucial when it comes to storing or transmitting large amounts of original data, while speed becomes significant when small amounts of data are constantly exchanged (such as in message transmission). The goal of this project is to increase the speed of data compression in order to optimize memory usage in electronic devices. The work includes an analysis of existing archiving methods and the possibilities of using binary trees to ensure that the code meets the Fano condition. A coding method based on reducing the depth of leaves in the codeword tree was developed, as well as another method that optimizes the leaf depth during coding by solving the 0-1 Knapsack Problem. Theoretical complexity estimates were obtained for all algorithms and comparisons were made with the classical Huffman algorithm. Practical implementations were also provided. The tests showed that the developed algorithms are superior in terms of time and allow for effective use on small data volumes, despite the average length of the codeword increasing slightly.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Binary Code Compression Based on Decision Trees

  • A. B. Levina,
  • P. G. Chernenko,
  • S. V. Boyko

摘要

Data compression is a process of transforming data in order to reduce its volume. Two important parameters of any compression algorithm are the compression ratio and speed. The compression ratio is crucial when it comes to storing or transmitting large amounts of original data, while speed becomes significant when small amounts of data are constantly exchanged (such as in message transmission). The goal of this project is to increase the speed of data compression in order to optimize memory usage in electronic devices. The work includes an analysis of existing archiving methods and the possibilities of using binary trees to ensure that the code meets the Fano condition. A coding method based on reducing the depth of leaves in the codeword tree was developed, as well as another method that optimizes the leaf depth during coding by solving the 0-1 Knapsack Problem. Theoretical complexity estimates were obtained for all algorithms and comparisons were made with the classical Huffman algorithm. Practical implementations were also provided. The tests showed that the developed algorithms are superior in terms of time and allow for effective use on small data volumes, despite the average length of the codeword increasing slightly.