ПОИСК ПОДСТРОК С ПОМОЩЬЮ КОНЕЧНОГО АВТОМАТА И РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах [1; 2; 3; 4].

С помощью конечных автоматов можно успешно решать обширный класс задач. Это обстоятельство подмечено давно, поэтому в литературе по проектированию программного обеспечения часто приводятся рассуждения на тему применения автоматов. Однако в процессе моделирования автомат рассматривается с более высокого уровня, нежели это делается в момент его реализации с использованием конкретного языка программирования [1; 3].

Рассмотрим, как описать конечный автомат для поиска подстроки в строке, когда они совершенно произвольны. На рисунке 1 представлен граф данного автомата.

Рисунок 1. Граф конечного автомата поиска произвольной подстроки в строке

Здесь a — проверяемая часть строки, b — искомая подстрока,

L=L_a=L_b — длина подстроки;

end говорит о выходе из автомата и перехода в начальное состояние в ожидании следующего элемента для проверки.

Программно на языке высокого уровня C# такой автомат реализуется следующим образом:

for (int b = 0; b < isub; )

switch (q)

{

case 0:

{

if (str0[0] == sub[0])

{

if (b == isub - 1)

{

                     kol++;

                     q = 0;

                     b++;

}

else

{

                    q = 1;

                     b = 1;

}

}

else

{

q = 2;

b++;

if (b == isub) q = 0;

}

} break;

case 1:

{

if (str0[b] == sub[b])

{

q = 1;

b++;

if (b == isub) { kol++; q = 0; }

}

else

{

q = 2;

b++;

if (b == isub + 1) q = 0;

}

} break;

 case 2:

{

 b = isub;

 q = 0;

} break;

}

Такой способ поиска подстроки в строке работает эффективно, но его использование не целесообразно, т. к. для работы с текстом имеется свой собственный язык — регулярные выражения. Их работа тоже строится на конечных автоматах, но «скрытно», т. е. программист не беспокоится о построении автомата вручную, а лишь обращается к регулярным выражениям.

Регулярные выражения можно представить себе как мини-язык программирования, имеющий одно специфическое назначение: находить подстроки в больших строковых выражениях.

Язык регулярных выражений предназначен специально для обработки строк. Он включает два средства: [1; 4].

·     набор управляющих кодов для идентификации специфических типов символов;

·     система для группирования частей подстрок и промежуточных результатов таких действий.

С помощью регулярных выражений можно выполнять достаточно сложные и высокоуровневые действия над строками:

·     идентифицировать (и возможно, помечать к удалению) все повторяющиеся слова в строке;

·     сделать заглавными первые буквы всех слов;

·     преобразовать первые буквы всех слов длиннее трех символов в заглавные;

·     обеспечить правильную капитализацию предложений;

·     выделить различные элементы в URI (например, имея http://www.professorweb.ru, выделить протокол, имя компьютера, имя файла и т. д.).

Вот пример поиска и выделения цветом подстроки в тексте с помощью регулярного выражения:

MatchCollection allIp = Regex.Matches(rtb.Text.ToLower(), Class1.Poisk.ToLower());

foreach (Match ip in allIp)

{

 rtb.SelectionStart = ip.Index;

rtb.SelectionLength = ip.Length;

 rtb.SelectionBackColor = Color.FromArgb(255, 160, 122);

}

Здесь в тексте rtb.Text ведется поиск слова Class1.Poisk. Функция ToLower() организует игнорирование регистра, чего можно добиться и стандартными командами регулярных выражений, как RegexOptions.IgnoreCase [4]. Приведем пример программы, выполнение которой построено на основе регулярных выражений. На рисунке 2 представлено окно данной программы. Ее задачей является поиск заданного слова в списке файлов MS Office Word, выбранных пользователем, подсчет числа совпадений и вывода этого результата на экран в виде таблицы.

Рисунок 2. Начальное окно разработанной программы

Поиск заданной подстроки как раз и реализуется с помощью регулярных выражений. Кроме того, используя их можно не только найти и подсчитать, но и выделить полученные совпадения, за что и отвечает приведенный немного выше программный код. Продемонстрируем описанные действия в программной реализации (рисунки 3, 4):

Рисунок 3. Пример выполнения программы

Рисунок 4. Просмотр документа с выделением найденных совпадений

Здесь была представлена лишь малая часть из возможностей регулярных выражений, но даже так можно утверждать, что при работе с текстом такой вид поиска подстроки заметно короче и явно удобнее, чем использование непосредственно конечных автоматов.

Список литературы:
1.    Брауэр В. Введение в теорию конечных автоматов / пер. с англ.; под ред. Ю.И. Журавлева. — М.: Радио и связь, 1987. — 392 с.
2.    Зуева В.Н. Адаптивный поиск информации в Internet // Современные тенденции технических наук: материалы междунар. заоч. науч. конф. (г. Уфа, май 2013 г.). — Уфа: Лето, 2013. — С. 7—10.
3.    Карпов Ю.Г. Теория автоматов: учебник для вузов. — М.; Питер, 2002. — 207 с.
4.    Фаронов В.В. Программирование на языке С#. — СПб.: Питер. 2007. — 240 с.