ЭФФЕКТИВНЫЙ ПО ВРЕМЕНИ АЛГОРИТМ РАСЧЕТА ОБОБЩЕННОЙ ЭНТРОПИИ ДВУМЕРНЫХ СЛОВ МЕТОДОМ СКОЛЬЗЯЩЕГО ОКНА
Authors: УЛЬЯНОВ  М.В. , СЕДЯКИН  И. 
Published: January 2025

В статье, применительно к задаче самоорганизации стержнеобразных частиц на торе, рассматриваются методы вычисления энтропии двумерных слов конечной длины над конечным алфавитом. Наблюдение за изменением энтропии позволяет лучше понять процессы, происходящие при самоорганизации. Для вычисления энтропии используется метод скользящего окна, который заключается в нахождении уникальных конфигураций окон в матрице и подсчете числа уникальных конфигураций. Затем по полученным значениям счетчиков вычисляется энтропия. Основную временную сложность требуют алгоритмы подсчета количества окон, само значение энтропии по известным счетчикам вычисляется быстро. Потому были предложены варианты асимптотически эффективных по времени алгоритмов подсчета количества одинаковых окон, использующих методы преобразования в индекс, дерево поиска и префиксное дерево. При этом энтропия всегда рассчитывается одинаковым способом. Приводятся результаты экспериментального исследования времени работы программных реализаций этих алгоритмов: минимальное, максимальное и среднее время работы на ряде экспериментов для некоторых размеров окна. Сделан вывод об эффективности тех или иных алгоритмов в зависимости от размеров окна. Обосновывается нерепрезентативность энтропии, вычисленной прямым путем, из-за несоразмерно большого количества возможных существующих уникальных конфигураций, даже при малых размерностях алфавита и окна. Предлагается метод быстрого вычисления обобщенной энтропии двумерных слов вместо прямой энтропии.
In the article we consider methods for calculating the entropy of two-dimensional words of finite length over in finite alphabet, with reference to the problem of self-organization of rod-like particles on a torus. Monitoring the change in entropy allows a better understanding of the processes occurring during self-organization. To calculate the entropy, we use the sliding window method, which consists in finding unique configurations of windows in the matrix and counting the number of these configurations. Then, the entropy is calculated from the obtained counter values. The basic time complexity is required by the algorithms for counting the number of windows. Value of entropy is calculated quickly using known counters. Therefore, we purpose variants of asymptotically time efficient algorithms for counting the number of identical windows using the methods of conversion into an index, a search tree and a prefix tree. In this case, entropy is always calculated in the same way. The results of an experimental study of the software operating time implementations of these algorithms are presented: the minimum, maximum, and average operating time on a number of experiments for certain window sizes. The conclusions about the effectiveness of various algorithms, depending on the size of the window were made. We show the non-representativeness of the entropy calculated by the direct path is due to the disproportionately large number of possible existing unique configurations, even with small dimensions of the alphabet and the window. Finally, we purpose the method of quickly generalized entropy of two-dimensional words calculating instead of direct entropy.