Применение теории автоматов

Содержание

Ключевае слова:
Автомат
Программирование
Визуализатор
Нейронные сети
Микроконтроллеры
Документооборот

Поиск цепочек в тексте

Согласно данным официальной статистики, около 85 % пользователей Интернет постоянно обращаются к поисковым системам (Google, Yandex, Rambler, Yahoo!, Апорт, Поиск@Mail.ru и др.) с целью найти необходимую им информацию о товарах или услугах.

Положения теории автоматов прекрасно подходят для описания таких реальных задач, возникающих в приложениях, как поиск в сети Internet и извлечение информации из текста. Многие современные поисковые системы Интернета используют специальную программу – поисковый робот, который является автоматом.

В век Internet и электронных библиотек с непрерывным доступом обычной является следующая проблема. Задано некоторое множество слов, и требуется найти все докумен¬ты, в которых содержится одно (или все) из них. Популярным примером такого процесса служит работа поисковой машины, которая использует специальную технологию поиска, называемую обращенными индексами (inverted indexes). Для каждого слова, встречающегося в Internet (а их около 100,000,000), хранится список адресов всех мест, где оно встречается. Машины с очень большим объемом оперативной памяти обеспечивают постоянный доступ к наиболее востребованным из этих списков, позволяя многим людям одновременно осуществлять поиск документов.

В методе обращенных индексов конечные автоматы не используются, но этот метод требует значительных затрат времени для копирования содержимого сети и переписывания индексов. Существует множество смежных приложений, в которых применить технику обращенных индексов нельзя, зато можно с успехом использовать методы на основе автоматов. Те приложения, для которых подходит технология поиска на основе автоматов, имеют следующие отличительные особенности:

  1. Содержимое хранилища текста, в котором производится поиск, быстро меняется.
  2. Вот два примера:

    • каждый день аналитики ищут статьи со свежими новостями по соответствующим темам. К примеру, финансовый аналитик может искать статьи с определенными аббревиатурами ценных бумаг или названиями компаний;
    • "робот-закупщик" по требованию клиента отслеживает текущие цены по определенным наименованиям товаров. Он извлекает из сети страницы, содержащие каталоги, а затем просматривает эти страницы в поисках информации о ценах по конкретному наименованию.

  3. Документы, поиск которых осуществляется, не могут быть каталогизированы.

Например, очень непросто отыскать в сети все страницы, содержащие информацию обо всех книгах, которые продает компания Amazon.com, поскольку эти страницы генерируются как бы "на ходу" в ответ на запрос. Однако мы можем отправить запрос на книги по определенной теме, скажем, "конечные автоматы", а затем искать в той части текста, которая содержится на появившихся страницах, определенное слово, например слово "прекрасно".

При построении поисковых систем могут использоваться как ДКА, так и НДКА (см. пример 4).


См. также
Предыдущий раздел - Построение моделей документооборота на основе конечно-автоматной модели теории автоматов
Следующий раздел - Примеры


X