bsuirДоклады БГУИРDoklady BGUIR1729-76482708-0382БГУИР10.35596/1729-7648-2020-18-6-33-40bsuir-2782Research ArticleЭЛЕКТРОНИКА, РАДИОФИЗИКА, РАДИОТЕХНИКА, ИНФОРМАТИКАELECTRONICS, RADIOPHYSICS, RADIOENGINEERING, INFORMATICSString processing model for knowledge-driven systemsString processing model for knowledge-driven systemsIvashenkoV. P.IvashenkoV. P.

Ivashenko Valerian Petrovich, PhD, Associate Professor of the Intelligent Information Technologies Department

220013, Belarus, Minsk, P. Brovki str., 6

tel. +375-17-293-80-92

Ivashenko Valerian Petrovich, PhD, Associate Professor of the Intelligent Information Technologies Department

220013, Belarus, Minsk, P. Brovki str., 6

tel. +375-17-293-80-92

ivashenko@bsuir.byBelarusian State University of Informatics and RadioelectronicsBelarusian State University of Informatics and Radioelectronics2020300920201863340Copyright © Ivashenko V.P., 20202020Ivashenko V.P.Ivashenko V.P.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.bsuir.by/jour/article/view/2782

The purpose of the work is to confirm experimentally theoretical estimates for time complexity of operations of the string processing model linked with the metric space for solving data processing problems in knowledge-driven systems including the research and comparison of the operation characteristics of these operations with the characteristics of similar operations for the most relevant data structures. Integral and unit testing were used to obtain the results of the performed computational experiments and verify their correctness. The C \ C++ implementation of operations of the string processing model was tested. The paper gives definitions of concepts necessary for the calculation of metric features calculated over strings. As a result of the experiments, theoretical estimates of the computational complexity of the implemented operations and the validity of the choice of parameters of the used data structures were confirmed, which ensures near-optimal throughput and operation time indicators of operations. According to the obtained results, the advantage is the ability to guarantee the time complexity of the string processing operations no higher than O  at all stages of a life cycle of data structures used to represent strings, from their creation to destruction, which allows for high throughput in data processing and responsiveness of systems built on the basis of the implemented operations. In case of solving particular string processing problems and using more suitable for these cases data structures such as vector or map the implemented operations have disadvantages meaning they are inferior in terms of the amount of data processed per time unit. The string processing model is focused on the application in knowledge-driven systems at the data management level.

The purpose of the work is to confirm experimentally theoretical estimates for time complexity of operations of the string processing model linked with the metric space for solving data processing problems in knowledge-driven systems including the research and comparison of the operation characteristics of these operations with the characteristics of similar operations for the most relevant data structures. Integral and unit testing were used to obtain the results of the performed computational experiments and verify their correctness. The C \ C++ implementation of operations of the string processing model was tested. The paper gives definitions of concepts necessary for the calculation of metric features calculated over strings. As a result of the experiments, theoretical estimates of the computational complexity of the implemented operations and the validity of the choice of parameters of the used data structures were confirmed, which ensures near-optimal throughput and operation time indicators of operations. According to the obtained results, the advantage is the ability to guarantee the time complexity of the string processing operations no higher than O  at all stages of a life cycle of data structures used to represent strings, from their creation to destruction, which allows for high throughput in data processing and responsiveness of systems built on the basis of the implemented operations. In case of solving particular string processing problems and using more suitable for these cases data structures such as vector or map the implemented operations have disadvantages meaning they are inferior in terms of the amount of data processed per time unit. The string processing model is focused on the application in knowledge-driven systems at the data management level.

strings processinglists processingstring operationconcatenationstring splittingsearching by keystrings processinglists processingstring operationconcatenationstring splittingsearching by keyReferencesIvashenko V.P., Sintsov S.V. [Operations on management data sets in linear memory]. Doklady BGUIR = Doklady BGUIR. 2016;6(100):86-93. (in Russ.)Ivashenko V.P., Sintsov S.V. [Operations on management data sets in linear memory]. Doklady BGUIR = Doklady BGUIR. 2016;6(100):86-93. (in Russ.)Bates R. Language Definition in the Schütz Semantic Editor. JMLC 2003. 2003;2789:229-240. DOI: 10.1007/978-3-540-45213-3_29.Bates R. Language Definition in the Schütz Semantic Editor. JMLC 2003. 2003;2789:229-240. DOI: 10.1007/978-3-540-45213-3_29.Xie T., Taneja K., Kale Sh., Marinov D. Towards a Framework for Differential Unit Testing of Object- Oriented Programs. Proceedings – International Conference on Software Engineering. 2007;1:5-5. DOI:10.1109/AST.2007.15.Xie T., Taneja K., Kale Sh., Marinov D. Towards a Framework for Differential Unit Testing of Object- Oriented Programs. Proceedings – International Conference on Software Engineering. 2007;1:5-5. DOI:10.1109/AST.2007.15.Cadar C., Koushik S. Symbolic execution for software testing: three decades later. Communications of the ACM. 2013;56(2):82-90.DOI: 10.1145/2408776.2408795.Cadar C., Koushik S. Symbolic execution for software testing: three decades later. Communications of the ACM. 2013;56(2):82-90.DOI: 10.1145/2408776.2408795.Le Traon Y., Jéron T., Jézéquel J.-M., Morel P. Efficient Object-Oriented Integration and Regression Testing. IEEE Transactions on Reliability. 2000;49:12-25. DOI: 10.1109/24.855533.Le Traon Y., Jéron T., Jézéquel J.-M., Morel P. Efficient Object-Oriented Integration and Regression Testing. IEEE Transactions on Reliability. 2000;49:12-25. DOI: 10.1109/24.855533.Hirschberg D.S. A linear space algorithm for computing maximal common subsequences. Communications of the ACM. 1975;18 (6):341-343. DOI: 10.1145/360825.360861.Hirschberg D.S. A linear space algorithm for computing maximal common subsequences. Communications of the ACM. 1975;18 (6):341-343. DOI: 10.1145/360825.360861.Gusfield D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge: Cambridge University Press; 1997. DOI: 10.1086/420407.Gusfield D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge: Cambridge University Press; 1997. DOI: 10.1086/420407.Levenshtein V.I. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady. 1966:10(8):707-710. (in Russ.)Levenshtein V.I. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady. 1966:10(8):707-710. (in Russ.)Damerau F.J. A technique for computer detection and correction of spelling errors. Communications of the ACM. 1964;7(3):171-176. DOI: 10.1145/363958.363994.Damerau F.J. A technique for computer detection and correction of spelling errors. Communications of the ACM. 1964;7(3):171-176. DOI: 10.1145/363958.363994.Navarro G. A guided tour to approximate string matching. ACM Computing Surveys. 2001;33(1):31-88. DOI: 10.1145/375360.375365.Navarro G. A guided tour to approximate string matching. ACM Computing Surveys. 2001;33(1):31-88. DOI: 10.1145/375360.375365.Ehrenfeucht A., Haussler D.A New Distance Metric on Strings Computable in Linear Time. Discrete Applied Mathematics. 1988;20(3):191-203. DOI:10.1016/0166-218X(88)90076-5.Ehrenfeucht A., Haussler D.A New Distance Metric on Strings Computable in Linear Time. Discrete Applied Mathematics. 1988;20(3):191-203. DOI:10.1016/0166-218X(88)90076-5.Ivashenko V.P. [Ontological model of space-time relations for events and phenomena in processing of knowledge] Vestnik BrGTU. 2017; 5(107):13-17. (in Russ.)Ivashenko V.P. [Ontological model of space-time relations for events and phenomena in processing of knowledge] Vestnik BrGTU. 2017; 5(107):13-17. (in Russ.)

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