Одной из фундаментальных задач современных компьютерных информационных систем является обработка символьной информации, объем которой превалирует в общем объеме всей информации. В настоящее время применительно к задачам обработки символьной информации эффективно используется продукционный подход. В работе рассматриваются вопросы специфики текстового поиска с применением продукционного подхода. Основная суть подхода заключается в поиске вхождений образца в текст и возможном осуществлении подстановки (модификации текста). Между тем, при реализации поиска вхождений могут возникать различного рода коллизии, которые необходимо учитывать для корректного решения поставленных задач. Алгоритмы последовательного сопоставления слов могут, например, сталкиваться с коллизиями, которые заключаются в возможности пропуска позиций вхождения образца в слово при некоторых их структурных особенностях. В работе описывается разработанный авторами способ поиска с учетом возможных коллизий, а также алгоритмические и автоматные модели способа. Разработанный способ заключается в разметке образца и задании последовательности его просмотра в виде схемы алгоритма. Разработаны также три алгоритма (варианта реализации) способа. Алгоритмы отличаются тем, к каким позициям образца и текста будет осуществляться переход в зависимости от результата сопоставления (равенство или неравенство текущих символов образца и текста). Разработана автоматная модель способа. Способ последовательного сопоставления с образцом с устранением коллизий повышает эффективность вычислительной системы при реализации поисковых процедур и обработки символьной информации. Предлагаемый способ может быть использован в системах обработки символьной информации.
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.
The authors declare that there are no conflicts of interest present.