ЭФФЕКТИВНЫЙ ПО ВРЕМЕНИ АЛГОРИТМ РАСЧЕТА ОБОБЩЕННОЙ ЭНТРОПИИ ДВУМЕРНЫХ СЛОВ МЕТОДОМ СКОЛЬЗЯЩЕГО ОКНА
Аннотация
В статье, применительно к задаче самоорганизации стержнеобразных частиц на торе, рассматриваются методы вычисления энтропии двумерных слов конечной длины над конечным алфавитом. Наблюдение за изменением энтропии позволяет лучше понять процессы, происходящие при самоорганизации. Для вычисления энтропии используется метод скользящего окна, который заключается в нахождении уникальных конфигураций окон в матрице и подсчете числа уникальных конфигураций. Затем по полученным значениям счетчиков вычисляется энтропия. Основную временную сложность требуют алгоритмы подсчета количества окон, само значение энтропии по известным счетчикам вычисляется быстро. Потому были предложены варианты асимптотически эффективных по времени алгоритмов подсчета количества одинаковых окон, использующих методы преобразования в индекс, дерево поиска и префиксное дерево. При этом энтропия всегда рассчитывается одинаковым способом. Приводятся результаты экспериментального исследования времени работы программных реализаций этих алгоритмов: минимальное, максимальное и среднее время работы на ряде экспериментов для некоторых размеров окна. Сделан вывод об эффективности тех или иных алгоритмов в зависимости от размеров окна. Обосновывается нерепрезентативность энтропии, вычисленной прямым путем, из-за несоразмерно большого количества возможных существующих уникальных конфигураций, даже при малых размерностях алфавита и окна. Предлагается метод быстрого вычисления обобщенной энтропии двумерных слов вместо прямой энтропии.
Литература
[2] Mikhailov G.A., Voitishek A.V. 2006. Numerical statistical modeling (Monte Carlo methods) [Chislennoe statisticheskoe modelirovanie. Metody Monte-Karlo]. Academia, Moscow, 2006. 368 p. (In Russian)
[3] Uljanov M., Smetanin Y. Entropy Function of Finite Words. Proceedings of 2017 IEEE International Workshop on Engineering Technologies and Computer Science (EnT). Moscow, 2017. Pp. 8-11. DOI: 10.1109/EnT.2017.7
[4] Smetanin Yu.G., Ulyanov M.V., Pestova A.S. The entropic approach to constructing a measure of the symbolic variety of words and its application to the clustering of plant genomes. Matematicheskaya Biologiya i Bioinformatika = Mathematical Biology and Bioinformatics. 2016; 11(1):114–126. (In Russian) DOI: 10.17537/2016.11.114
[5] Stroustrup B., Sutter H. C++ Core Guidelines. The world's leading software development platform - GitHub. Available at: https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md (accessed 24.05.2018).
[6] Knuth D.E. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. 800 p.
[7] Kernighan B.W., Ritchie D.M. C Programming Language, 2nd Ed., Prentice Hall, 1998. 272 p.
[8] Smetanin Yu.G., Ulyanov M.V. Measure of symbolical diversity: Combinatorics on words as an approach to identify generalized characteristics of time series. Business Informatics. 2014; 3(29):40-48. Available at: https://elibrary.ru/item.asp?id=22913101 (accessed 24.05.2018). (In Russian)
[9] Ulyanov M.V. Cluster space of time series: generalized characteristics and symbolic dynamics. Proceedings of 2014 IEEE International Conference on Computer Technologies in Physical and Engineering Applications (ICCTPEA). St. Petersburg, 2014. Pp. 193-194. DOI: 10.1109/ICCTPEA.2014.6893355
[10] Smetanin Yu.G., Ulyanov M.V. Entropy characteristics of diversity in the symbols presentation of time series. Modern Information Technologies and IT-Education. 2014; 10:426-436. Available at: https://elibrary.ru/item.asp?id=23020662 (accessed 24.05.2018). (In Russian)
[11] Uljanov M., Smetanin Y. On a Characteristic Functional for Words over a Finite Alphabet. Informacionnye tekhnologii = Information technologies. 2017; 23(5):333-341. Available at: https://elibrary.ru/item.asp?id=29213868 (accessed 24.05.2018). (In Russian)
[12] Smetanin Yu.G., Ulyanov M.V. On the Number of Possible Reconstructions of Words Using Subwords with Windows of Different Shift. Informacionnye tekhnologii = Information technologies. 2018; 24(4):233–238. (In Russian) DOI: 10.17587/it.24.233-238
[13] Tarasevich Y.Y., Lebovka N.I., Laptev V.V. Percolation of linear k-mers on a square lattice: From isotropic through partially ordered to completely aligned states. Physical Review E. 2012; 86(6):061116. DOI: 10.1103/PhysRevE.86.061116
[14] Tarasevich Yu.Yu., Laptev V.V., Burmistrov A., Shinyaeva T. Influence of anisotropy on percolation and jamming of linear k-mers on square lattice with defects. Journal of Physics: Conference Series. 2015; 633(1):012064. DOI: 10.1088/1742-6596/633/1/012064
[15] Tarasevich Yu.Yu., Burmistrov A.S., Shinyaeva T.S., Laptev V.V., Vygornitskii N.V., Lebovka N.I. Percolation and jamming of linear k-mers on a square lattice with defects: Effect of anisotropy. Physical Review E. 2015; 92(6):062142. DOI: 10.1103/PhysRevE.92.062142
[16] Tarasevich Yu.Yu., Laptev V.V., Vygornitskii N.V., Lebovka N.I. Impact of defects on percolation in random sequential adsorption of linear k-mers on square lattices. Physical Review E. 2015; 91(1);012109. DOI: 10.1103/PhysRevE.91.012109
[17] Lebovka N.I., Tarasevich Yu.Yu., Dubinin D.O., Laptev V.V., Vygornitskii N.V. Jamming and percolation in generalized models of random sequential adsorption of linear k-mers on a square lattice. Physical Review E. 2015; 92(6):062116. DOI: 10.1103/PhysRevE.92.062116
[18] Tarasevich Yu.Yu., Dubinin D.O., Laptev V.V., Lebovka N.I. Impact of defects on electrical connectivity of monolayer of ideally aligned rods. Journal of Physics: Conference Series. 2016; 681(1):012038. DOI: 10.1088/1742-6596/681/1/012038
[19] Tarasevich Yu.Yu., Goltseva V.A., Laptev V.V., Lebovka N.I. Electrical conductivity of a monolayer produced by random sequential adsorption of linear k-mers onto a square lattice. Physical Review E. 2016; 94(4):042112. DOI: 10.1103/PhysRevE.94.042112
[20] Tarasevich Yu.Yu., Laptev V.V., Goltseva V.A., Lebovka N.I. Influence of defects on the effective electrical conductivity of a monolayer produced by random sequential adsorption of linear k-mers onto a square lattice. Physica A: Statistical Mechanics and its Applications. 2017; 477:195–203. DOI: 10.1016/j.physa.2017.02.084
[21] Budinski-Petković Lj., Lončarević I., Dujak D., Karač A., Šćepanović J. R., Jakšić Z.M., Vrhovac S.B. Particle morphology effects in random sequential adsorption. Physical Review E. 2017; 95(2):022114. DOI: 10.1103/PhysRevE.95.022114
[22] Lebovka N.I., Vygornitskii N.V., Gigiberiya V.A., Tarasevich Yu.Yu. Monte Carlo simulation of evaporation-driven self-assembly in suspensions of colloidal rods. Physical Review E. 2016; 94(6):062803. DOI: 10.1103/PhysRevE.94.062803
[23] Lebovka N.I., Tarasevich Yu.Yu., Gigiberiya V.A., Vygornitskii N.V. Diffusion-driven self-assembly of rodlike particles: Monte Carlo simulation on a square lattice. Physical Review E. 2017; 95(5):052130. DOI: 10.1103/PhysRevE.95.052130
[24] Tarasevich Yu.Yu., Laptev V.V., Burmistrov A.S., Lebovka N.I. Pattern formation in a two-dimensional two-species diffusion model with anisotropic nonlinear diffusivities: a lattice approach. Journal of Statistical Mechanics: Theory and Experiment. 2017; 2017(9):093203. DOI: 10.1088/1742-5468/aa82bf
[25] Evans J.W. Random and cooperative sequential adsorption. Reviews of Modern Physics. 1993; 54(4):1281–1329. DOI: 10.1103/RevModPhys.65.1281
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
