Rambler's Top100 Service калинин.ru / программирование / алгоритмы /  << 21.08.00 >>

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

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

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

Заданная грамматика позволяет указать, какая строка символов принадлежит некоторому множеству, а какая --- нет. Можно привести пример с множеством корректных 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 раз больше одного прохода.

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

Резюме

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


Версия для печати


  Ссылки по теме:
/comment/books/11_07_00.shtml
   Программирование: теоремы и задачи.
/comment/books/08_09_00.shtml
   Искусство программирования.
  Рядом в разделе:
Рекурсия, часть II (11.09.00)
   Собственно, в своей я рассказал немного не о том, о чем хотел. Поэтому сегодня придется дополнять ;) Кроме того, что рекурсия...   >>>>
Рекурсия (04.09.00)
   Возможно для кого-то это будет удивительным, но наиболее известным алгоритмом является сортировка пузырьком (не то, что бы ее все знали, просто...   >>>>
  Рядом по дате:
Java 2: руководство разработчика (22.08.00)
   Я решил, что мне нужна книга по Java тогда, когда появилось требование что-то написать на этом языке более серьезное, чем рисование...   >>>>
Курск (20.08.00)
   Когда я только раздумывал о том, какие разделы будут на моей страничке, этот я решил не организовывать... ну кому интересно то,...   >>>>
  Содержание:
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
   C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Просто так
Студенческое
Туризм
  Байки
Фотографии
Комментарии
   Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Благодарности
Форум
Хронология
 
  В этом разделе:
Полный перебор (11.11.00)
   Зачастую, когда говорят о качестве решения некоторой задачи, для того что бы определить наихудший вариант, приводят пример "полного перебора". Сколько раз...   >>>>
Рекурсия, часть II (11.09.00)
   Собственно, в своей я рассказал немного не о том, о чем хотел. Поэтому сегодня придется дополнять ;) Кроме того, что рекурсия...   >>>>
Рекурсия (04.09.00)
   Возможно для кого-то это будет удивительным, но наиболее известным алгоритмом является сортировка пузырьком (не то, что бы ее все знали, просто...   >>>>
Использование конечных автоматов (21.08.00)
   Я не хочу давать формальных определений, цель этой заметки --- показать "на пальцах" использование конечных автоматов (КА) для решения различных задач...   >>>>
Содержание раздела полностью...
   Примерно в тоже время
Java 2: руководство разработчика (22.08.00)
   Я решил, что мне нужна книга по Java тогда, когда появилось требование что-то написать на этом языке более серьезное, чем рисование...   >>>>
Курск (20.08.00)
   Когда я только раздумывал о том, какие разделы будут на моей страничке, этот я решил не организовывать... ну кому интересно то,...   >>>>
Хронология полностью...
   Содержание
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
  C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Туризм
  Байки
Фотографии
Комментарии
  Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Студенческое
Просто так
Благодарности
Форум
Хронология
© 2000-2008, Andrey L. Kalinin
mailto:andrey@kalinin.ru
Rambler's Top100