A METHOD OF SEQUENTIAL SEARCHING OF OCCURANCES IN TEXT WITH THE ACCOUNT OF POSSIBLE COLLISIONS

Abstract

One of the fundamental tasks of modern computer information systems is processing of symbol information, the amount of which prevails in the total amount of information. At present, rules-based approach is effectively applied to the tasks of processing symbol information. The paper deals with the peculiarities of text search applying rules-based approach. The main essence of the approach is to find pattern occurrences in the text and possible implementation of substitution (text modification). Meanwhile, when implementing search for occurrences, various kinds of collisions may arise. They should be taken into account to solve the set tasks correctly. For example, algorythms of sequential word matching can run into collisions which involve the possibility of skipping positions of pattern occurrence in a word with some structural peculiarities. The paper presents a method of searching taking into account possible collisions developed by the authors, as well as algorithmic and automatic models of the method. The developed method involves patterm markup and setting a sequence of its viewing in the form of algorithm diagram. Three algorythms (implementation variants) of the method have been developed. Algorithms differ in the possibility to carry out transition to this oк that position of the pattern and the text depending on the result of matching (equality or inequality of the current symbols of the patten and text). An automation model of the method has been developed. The proposed method of sequential matching with the pattern with collisions elimination increases the effectiveness of the computer system when implementing search procedures and symbol information processing. The method can be used in the systems of symbol information processing.