GetInfo.Ru – Компьютерная библиотека
Последние поступления
Как выбрать систему управления базы данных
Базы данных03/09/14
Этапы загрузки UNIX (в схеме)
Unix27/03/12
Gatewall Antispam: тотальный контроль электронной почты
Спам21/04/11
Мастер-класс: создаем Интернет-магазин (Часть 1)
Обзоры ПО20/04/11
CorelDRAW Graphics Suite X5: Что нового?
Обзоры ПО20/07/10
Добавить статью
Самые читаемые материалы
Мягкие вычисления(46070)
Эволюционные вычисления(32233)
Сортировка и поиск: Рецептурный справочник(30988)
Алгоритмы архивации данных(25507)
Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет(19528)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Алгоритмы » Использование конечных автоматов

Использование конечных автоматов


Андрей Калинин
andrey@kalinin.ru
http://www.kalinin.ru

Я не хочу давать формальных определений, цель этой заметки --- показать "на пальцах" использование конечных автоматов (КА) для решения различных задач разбора.

Все дело в том, что программисты очень часто сталкиваются с проблемой разделения строк на некоторые осмысленные части, проверки правильности ввода значений и т.д. В принципе, так как очень часто пользователем является человек, то самым естественным для него путем передачи информации будет человеческая речь. Тем не менее, задача выделения смысла из человеческой речи до сих пор не решена (и, вообще-то, вряд ли будет решена в ближайшем будущем). Поэтому для подобных случаев используется формальные описания некоторых структур --- формальные грамматики. Этот раздел информатики является частью более общего --- формальных методов.

Заданная грамматика позволяет указать, какая строка символов принадлежит некоторому множеству, а какая --- нет. Можно привести пример с множеством корректных URL-адресов: грамматика, заданная соответствующим RFC, указывает на то, какие строки являются правильными URL-адресами, а какие --- нет.

Для некоторых типов грамматик существуют соответствующие им алгоритмы разбора строк символов, именно этим и хорошо применение грамматик. Конечные автоматы применяются для простейших грамматик, но зачастую этого хватает. Обычно КА применятся для того, что называется лексическим анализом, т.е. для разбиения исходной строки на набор некоторых лексических единиц (например, выделение из текста слов и чисел).

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

Простейший детерминированый КА работает следующим образом: в нем находится внутренний регистр для хранения текущего состояния и таблица правил вида "символ-состояние ===> состояние" позволяющая по текущему символу на ленте и текущему состоянию перейти в другое состояние (со сдвигом по ленте). Цепочка символов допустима, если КА завершил свою работу в одном из "разрешенных" состояний и не допустима в обратном случае.

На практике составлять таблицу вручную достаточно сложно (для большого количества правил --- если это требуется, то используются автоматические генераторы кода). Тем не менее, подобные задачи, которые просто решаются именно при помощи КА встречаются сплошь и рядом. Например, упомянутая уже задача разбиения текста на числа и слова. Давайте договоримся, что словом считается алфавитносимвольная последовательность, а числом --- только последовательность цифр с возможным знаком перед ней.

Прототип функции, разбирающей текст:

	void parse(const char* string);

Будем считать, что результат работы будет доступен... только внутри функции ;) это не принципиально; мы просто подсчитаем количество слов и чисел в исходном тексте. Для того, что бы хранить текущее состояние, вводится соответствующая переменная (лучше всего использовать перечислимый тип --- нагляднее).

	enum
	{
	   skip,
	   sign,
	   digit,
	   letter,
	   finish
	} state = skip;

Рассматриваемый тип КА работает без возвратов (на это прошу обратить особое внимание --- для разбора строки потребуется только один проход):

	for(const char* current = string; state != finish; current++)
	{
	  // ...
	}

Вышеприведенный цикл как раз и организует этот проход. Теперь интереснее всего содержимое цикла. Оно состоит из оператора switch:

	switch(state)
	{
	case skip   : // ...
	case sign   : // ...
	case letter : // ...
	case digit  : // ...
	case finish : // ...
	}

Т.е., используется для определения текущего состояния КА и перехода в новое. Последний case введен для общности --- при его отсутствии компилятор gcc с флагом -Wall выдаст предупреждение о том, что не все варианты перечислимой переменной были учтены в операторе выбора.

Состояние skip введено для того, что бы обеспечить пропуск всех сивмолов, не являющемеся буквами или цифрами. Логично, что именно с него начинает свою работу КА.

	case skip :
	  if(isalpha(*current)) { state = letter; break; }
	  if(isdigit(*current)) { state = digit; break; }
	  if(*current == '+' || *current == '-') { state = sign; break; }
	  if(*current == 0) { state = finish; break; }
	  break; 

В этом состоянии, при получении на вход буквы КА считает, что впереди --- слово, цифры или знака --- возможно число. Выражение типа *current == 0, а не !(*current) как написали бы некоторые умники, используется для повышения общности записи и для более удобного последующего чтения. Т.е., я не против записи if(*current), но отрицание там смотрится очень... незаметно, по-моему. Может быть, конечно же, я не прав --- это замечание касается "стиля", а подобные вопросы традиционно вызывают массовые споры ;)

Если на вход поступил знак, то:

	case sign : 
	  if(isdigit(*current)) { state = digit; break; }
	  if(isalpha(*current)) { state = letter; break; }
	  if(*current == 0) { state = finish; break; }
	  state = skip;
	  break;

После знака '+' или '-' в случае поступления на вход цифры все еще возможно, что обрабатывается число. Если попалась буква, то никакого числа не было, а началось слово. Во всех остальных случаях требуется вернуться к состоянию skip для того, что бы продолжить пропуск символов.

	case digit :
	  if(isdigit(*current)) break;
	  if(isalpha(*current)) { state = letter; break; }
	  count_of_numbers++;
	  state == *current ? skip : finish;
	  break;

Предельно ясно --- в случае, если цифровая последовательность закончилась не буквой, то это было число (увеличиваем счетчик --- единственная полезной работой нашего КА будет подсчет количества чисел и слов). Если же встретилась буква, то (по определению выше) последовательность является словом.

	case letter :
	  if(isalpha(*current)) break;
	  count_of_words++;
	  state = *current ? skip : finish;
	  break;

Собственно говоря, это все --- после выхода из цикла переменные count_of_numbers и count_of_words будут содержать в себе количество чисел и слов соответственно (перед входом в цикл их, конечно же, надо было обнулить).

Кто-то мог заметить, что в состоянии sign в данном случае нет необходимости. Это так, но оно введено для того, что бы было проще адаптировать этот пример не только к подсчету слов и чисел, а еще и к выделению слов и чисел со знаком.

Задача и пример элментарны. Но я не стал бы приводить их здесь, если бы, к моему сожалению, очень часто не видел бы то, как вполне грамотные люди в очередной раз пытаются изобрести велосипед. При этом велосипеды получаются, зачастую, настолько кособокие и неправильные, что смотреть на это становится сложно. Например, часто встречающаяся ошибка заключается в том, что организуются возвраты по строке в обратную сторону. Т.е., например, была попытка применить какое-нибудь правило, она оказалась неудачной, тогда для проверки следующего правила производится откат назад и попытка применить новое и т.д. Зачастую это становится очень медленно, а КА позволяет (если его можно, конечно же, применить) обработать строку в один проход. Нет, сущестуют, конечно же, варианты, когда без этого не обойтись. Но в самых распространенных простейших случаях можно обойтись без возвратов.

Если в примере выше этого еще не видно, то могу привести другие примеры. Кроме таких простейших случаев разбора (числа и слова подчинялись в примере очень простым правилам), существуют несколько более сложные варианты применения КА. Например, поиск по образцу.

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

Я видел очень много решений этой задачи, которые программисты делали "от сохи". Существуют специализированные алгоритмы поиска вхождений подстроки в строку (например, алгоритм Кнута-Мориса-Пратта), но то, что делают чаще всего, несколько сомнительно по своему качеству.

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

Это совершенно неправильно! Все дело в том, что на каждой такой итерации теряется информация о том, что на предыдущем шаге символы строки уже сверялись с шаблоном (пусть, и в другом месте), а это можно было бы использовать. Для этого строится конечный автомат с состояниями, соотвествующими длине совпавшей подстроки и правилами, которые каждой паре "длина-символ" выставляют новую "длину" совпавшей подстроки. Например, для подстроки "ababc" можно говорить, что пары "2,a" и "4.a" соответствуют переходу в состояние 3.

Особенно заметен выигрыш построения таблицы переходов (это достаточно простая задача: по подстроке построить подобную таблицу) тогда, когда надо найти не первое, а последнее вхождение подстроки. Год назад я давал задачку на олимпиаде для первокурсников, в которой требовалось как раз найти в строке длиной до 1МБ последнее вхождение подстроки длиной до 255 символов. При этом был тест, в котором вся исходная строка и строка образец состояли из одних только букв "a". В этом случае, используя возвраты, потребовалось бы сделать 255*1024*1024 сравнения... и это ровно в 255 раз больше одного прохода.

Кстати, алгоритм Кнута-Мориса-Прата, в принципе, как раз и является вариацией на тему построения КА, только в нем указано каким именно образом строится таблица переходов.

Резюме

КА это очень полезный инструмент. Очень простой и надежный, к сожалению, о нем часто забывают...

Оригинал статьи: www.kalinin.ru

 
22.03.2003
Версия для печати Версия для печати Запомнить ссылку Запомнить ссылку
Ваша оценка:  1   2   3   4   5     

 О проектеПерепечаткаАвторамПартнерыО нас пишут
Наверх
©2003—2007. GETINFO.RU. ВСЕ ПРАВА ЗАЩИЩЕНЫ.