priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2024-67-4-352-358pribor-163Research ArticleИНФОРМАТИКА И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫINFORMATICS AND INFORMATION PROCESSESБалансируемая структура данных с приоритетами элементов в задаче моделирования дискретных источников информацииBalanceable Data Structure with Element Priorities in the Problem of Discrete Information Source ModelingАксеновА. В.AksenovА. V.

Алексей Владимирович Аксенов — старший преподаватель, кафедра вычислительных систем и сетей

Санкт-Петербург

Aleksey V. Aksenov — Senior Lecturer, Department of Computing Systems and Networks

St. Petersburg

aksenov@guap.ruСанкт-Петербургский государственный университет аэрокосмического приборостроенияSt. Petersburg State University of Aerospace Instrumentation202427112024674352358Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/163

Рассматриваются особенности разработки балансируемой структуры данных, ориентированной на ускоренный доступ к элементам, имеющим высокий приоритет. Подобные структуры могут использоваться в задачах моделирования дискретных источников информации. Предложено самобалансирующееся двоичное дерево поиска, оптимизированное для эффективного хранения и поиска данных на основе приоритетов, коррелирующих с вероятностью порождения символов. Решение позволяет преодолеть ограничения существующих структур данных с учетом требований к памяти и производительности в контексте специфических задач обработки информации.

The features of developing a balanceable data structure focused on accelerated access to elements with high priority are considered. Similar structures can be used in problems of modeling discrete information sources. A self-balancing binary search tree is proposed, optimized for efficient storage and retrieval of data based on priorities that correlate with the probability of symbol generation. The solution overcomes the limitations of existing data structures, taking into account memory and performance requirements in the context of specific information processing tasks.

структура данныхускоренный доступдвоичное дерево поискасамобалансирующаяся структурахранение данныхэффективный поиск данныхdata structureaccelerated accessbinary search treeself-balancing structureefficient data storageefficient data retrievalReferencesАдельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Докл. АН СССР. 1962. Т. 146, № 2. С. 263—266.Adel'son-Vel'skii G.M., Landis E.M. Doklady Akademii Nauk SSSR, 1962, no. 2(146), pp. 263–266. (in Russ.)Кормен Т. Х., Лейзерсон Ч. Е., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2013. 1328 с.Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms, MIT Press, 2009.Guibas L. J., Sedgewick R. A dichromatic framework for balanced trees // Proc. of the 19th Annual Symp. on Foundations of Computer Science (SFCS 1978). Ann Arbor, MI, USA. 1978. Р. 8—21.Guibas L.J., Sedgewick R. Proceedings of the 19th Annual Symposium on Foundations of Computer Science (SFCS 1978), Ann Arbor, MI, USA, 1978, рр. 8–21.Sleator D., Tarjan R. E. Self-Adjusting Binary Search Trees // J. of the Association for Computing Machinery. 1985. Vol. 32, N 3. Р. 652—686.Sleator D., Tarjan R.E. Journal of the Association for Computing Machinery, 1985, no. 3(32), pp. 652–686.Pfaff B. Performance Analysis of BSTs in System Software // ACM SIGMETRICS Performance Evaluation Review. 2004. Vol. 32, is. 1. Р. 410—411.Pfaff B. ACM SIGMETRICS Performance Evaluation Review, 2004, no. 1(32), pp. 410–411.Galperin I., Rivest R. Scapegoat trees // Proc. of the Fourth Annual ACM-SIAM Symp. on Discrete algorithms (SODA '93). Society for Industrial and Applied Mathematics, USA, 1993. Р. 165—174.Galperin I., Rivest R. Proc. of the Fourth Annual ACM-SIAM Symp. on Discrete algorithms (SODA '93), Society for Industrial and Applied Mathematics, USA, 1993, рр. 165–174.Seidel R., Aragon C. R. Randomized search trees // Algorithmica. 1996. Vol. 16. P. 464—497.Seidel R., Aragon C.R. Algorithmica, 1996, vol. 16, рр. 464–497.Cleary J., Teahan W. Experiments on the zero frequency problem // Proc. of the DCC '95 Data Compression Conf. 1995. Р. 480.Cleary J., Teahan W. Proceedings of the DCC '95 Data Compression Conference, 1995, р. 480.Boehm H., Atkinson R., Plass M. Ropes: an Alternative to Strings // Software—Practice and Experience. 1995. Vol. 25, N 12. Р. 1315—1330.Boehm H., Atkinson R., Plass M. Software—Practice and Experience, 1995, no. 12(25), pp. 1315–1330.Hinze R., Paterson R. Finger Trees: A Simple General-purpose Data Structure // J. of Functional Programming. 2006. Vol. 16, N 2. Р. 197—217.Hinze R., Paterson R. Journal of Functional Programming, 2006, no. 2(16), pp. 197–217.

The authors declare that there are no conflicts of interest present.