Двоичные алгоритмы сжатия на основе деревьев решений

Алла Борисовна Левина,Пётр Георгиевич Черненко,Сергей Викторович Бойко

ПРЕПРИНТ

Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.

Двоичные алгоритмы сжатия на основе деревьев решений

А. Б. Левина,

П. Г. Черненко,

С. В. Бойко

2026-08-15

https://doi.org/10.24108/preprints-3116167

Сжатие данных – процесс преобразования данных с целью уменьшения их объёма. Двумя важными параметрами любого алгоритма сжатия являются степень сжатия и скорость. Степень сжатия имеет решающее значение, когда речь идёт о хранении или передаче больших объёмов исходных данных, в то время как скорость становится существенной при постоянном обмене небольшими объёмами данных (например, при передаче сообщений). Целью данной работы является повышение скорости сжатия данных для оптимизации использования памяти в электронных устройствах. Работа включает в себя анализ существующих методов архивирования и возможностей использования бинарных деревьев для обеспечения соответствия кода условию Фано. Разработан метод кодирования, основанный на уменьшении глубины листьев в дереве кодовых слов, а также метод, оптимизирующий глубину листьев во время кодирования путём решения задачи о рюкзаке 0-1. Для всех алгоритмов были получены теоретические оценки сложности и проведено сравнение с классическим алгоритмом Хаффмана. Также были представлены практические реализации. Тесты показали, что разработанные алгоритмы превосходят по времени и позволяют эффективно использовать их при небольших объёмах данных, несмотря на незначительное увеличение средней длины кодового слова.

Ссылка для цитирования:

Левина А. Б., Черненко П. Г., Бойко С. В. 2026. Двоичные алгоритмы сжатия на основе деревьев решений. PREPRINTS.RU. https://doi.org/10.24108/preprints-3116167

Список литературы

1. Shannon, C. E. (1948). A mathematical theory of communication. The Bell system technical journal, 27(3), 379-423;

2. Bell, T. C., Cleary, J. G., & Witten, I. H. (1990). Text Compression. Prentice-Hall, Englewood Cliffs;

3. Storer, J. A. (1987). Data Compression: methods and theory. Computer Science Press, Rockville;

4. Brandenburg, K. (1997). MP3 and AAC Explained. In: The Digital Signal Processing Handbook. CRC Press, Boca Raton;

5. Le Gall, D. (1991). MPEG: A video compression standard for multimedia applications. Communications of the ACM, 34(4), 46-58;

6. Rao, K. R., Bojkovic, Z. S., & Milovanovic, D. A. (2002). Multimedia communication systems: techniques, standards, and networks. Prentice Hall PTR;

7. Nielsen, M. A., & Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge University Press, Cambridge;

8. Schumacher, B., & Westmoreland, M. D. (2010). Quantum Processes, Systems, and Information. Cambridge University Press, Cambridge;

9. Wilde, M. M. (2017). Quantum Information Theory. 2nd edn. Cambridge University Press, Cambridge;

10. Yaglom, A. M., & Yaglom, I. M. (1983). Probability and Information. Nauka, Moscow;

11. Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on information theory, 23(3), 337-343;

12. Liu, X., Liu, X., Lai, Y., Yang, F., & Zeng, Y. (2019). Random decision DAG: an entropy based compression approach for random forest. In International Conference on Database Systems for Advanced Applications. DASFAA 2019, LNCS 11448, pp. 319–323. DOI: 10.1007/978-3-030-18590-9_37.

ПРЕПРИНТ

ИНФОРМАЦИЯ

Использование куки-файлов