TIME EFFICIENT ALGORITHM FOR THE GENERALIZED0 ENTROPYCALCULATION OF TWO-DIMENSIONS WORDS BY THE METHOD OF A SLIDING WINDOW
Journal Title: Современные информационные технологии и ИТ-образование - Year 2018, Vol 14, Issue 3
Abstract
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.
Authors and Affiliations
Ilya Sedyakin, Michael Uljanov
Keywords
Related Articles
- EP ID EP515228
- DOI 10.25559/SITITO.14.201803.560-566
- Views 111
- Downloads 0
PARALLEL IMPLEMENTATION OF SYMMETRIC HORIZONTAL DISTRIBUTION OF DATA ON THE NETWORK TECHNOLOGIES BASIS
The approach to the construction of software and hardware complexes for implementing a symmetric horizontal distribution of tables in relational databases is considered. To solve this problem, we propose to use standard...
ARCHITECTURE OF THE PARALLEL SOFTWARE FOR THE SIMULATION OF MULTIDIMENSIONAL PROBLEMS
The architecture of the parallel software constructed on the basis of a design pattern «Bridge», and intended for simulation of multidimensional tasks (network dynamics; compression of multidimensional data, pattern reco...
BENCHMARKING BIG SPATIAL DATA PROCESSING FRAMEWORKS
Today, the processing of large amounts of spatial data in distributed systems plays a crucial role in many areas of our life. Large data are often unstructured, and special algorithms are required for its processing. One...
THE HYBRID COMPILER TARGETING JAVASCRIPT LANGUAGE
In this paper, we cover our work dedicated to creating a prototype of novel JavaScript execution engine. The work is inspired by the Tizen platform, which announces HTML5 and JavaScript as the main approach for developin...
COMPARISON OF SOLVING A STIFF EQUATION ON A SPHERE BY THE MULTI-LAYER METHOD AND METHOD OF CONTINUING AT THE BEST PARAMETER
A stiff equation, linked with the solution of singularly perturbed differential equations with the use of standard methods of numeral solutions of simple differential equations often lead to major difficulties. First dif...