Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 20
Текст из файла (страница 20)
Существует множество смежных приложений, в которых применить технику обращенных индексов нельзя, зато можно с успехом использовать методы на основе автоматов. Те приложения, для которых подходит технология поиска на основе автоматов, имеют следующие отличительные особенности. 1.
Содержимое хранилища текста„в котором производится поиск, быстро меняется. Вот два примера: а) каждый день аналитики ищут статьи со свежими новостями по соответствующим темам. К примеру, финансовый аналитик может искать статьи с определенными аббревиатурами ценных бумаг или названиями компаний; б) "робот-закупщик" по требованию клиента отслеживает текущие цены по определенным наименованиям товаров. Он извлекает из сети страницы, содержащие каталоги, а затем просматривает эти страницы в поисках информации о ценах по конкретному наименованию. 2.4. ПРИЛОЖЕНИЕ: ПОИСК В ТЕКСТЕ 2.
Документы, поиск которых осуществляется, не могут быть каталогизированы. Например, очень непросто отыскать в сети все страницы, содержащие информацию обо всех книгах, которые продает компания Ашагоп.сош, поскольку эти страницы генерируются как бы "на ходу" в ответ на запрос. Однако мы можем отправить запрос на книги по определенной теме, скажем, "конечные автоматы", а затем искать в той части текста, которая содержится на появившихся страницах, определенное слово, например слово "прекрасно"'. 2,4,2. Недетерминированные конечные автоматы ддя поиска в тексте Пусть нам дано множество слов, которые мы в дальнейшем будем называть ключевыми словами, и нужно отыскать в тексте места, где встречается любое из этих слов.
В подобных приложениях бывает полезно построить недетерминированный конечный автомат, который, попадая в одно из допускающих состояний, дает знать, что встретил одно из ключевых слов. Текст документа, символ за символом, подается на вход НКА, который затем распознает в нем ключевые слова, Существует простая форма НКА, распо- знающего множество ключевых слов. 1. Есть начальное состояние с переходом в себя по каждому входному символу, например, печатному символу АБС11 при просмотре текста. Начальное состояние можно представлять себе, как "угадывание" того, что ни одно из ключевых слов еше не началось, даже если несколько букв одного из ключевых слов уже прочитано, 2. ДлЯ каждого ключевого слова а~аз...аь имеетсЯ Уе состоЯний, скажем еУо еУь ..., еУь Для входного символа а~ есть переход из начального состояния в дь для входного символа а, — переход из д, в дз и т.д. Состояние уг является допускающим и сигнализирует о том, что ключевое слово а,а,...аь обнаружено.
Пример 2.14. Предположим, что мы хотим построить НКА, распознающий слова ыеЬ и еЬау. Диаграмма переходов данного НКА, изображенная на рис. 2.16, построена с помощью изложенных выше правил. Начальное состояние — это состояние 1, а Е обозначает множество печатаемых символов АБС11.
Состояния 2 — 4 отвечают за распознавание слова ивЬ, а состояния 5 — 8 — за распознавание слова еЬау. П Нач Рис. 2. Уб, НКА, осуществляющий поиск слов и еЬ и оЬау 86 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ Безусловно, НКА — не программа. Для реализации данного НКА у нас есть две основные возможности. 1.
Написать программу, имитирующую работу данного НКА путем вычисления множества состояний, в которых он находится по прочтении каждого из входных символов. Такая реализация была рассмотрена на рис. 2.10. 2. Преобразовать данный НКА в эквивалентный ему ДКА, используя конструкцию подмножеств. Затем непосредственно реализовать ДКА. В некоторых программах, обрабатывающих текст, таких„например, как наиболее продвинутые версии команды дгер (едгер и бдгер) операционной системы БХ1Х, используется комбинация этих двух подходов. Однако в нашем случае более удобно преобразование к ДКА, так как это, во-первых, просто, а во-вторых, гарантирует, что число состояний при этом не возрастет.
2.4.3. ДКА, распознающий множество ключевых слов Конструкция подмножеств применима к любому НКА. Но, применяя ее к НКА, построенному по множеству ключевых слов, как в разделе 2.4.2, мы обнаружим, что число состояний соответствующего ДКА никогда не превосходит числа состояний э~ого НКА. А поскольку нам известно, что при переходе к ДКА в худшем случае может произойти зкспоненциальный рост числа состояний, то последнее замечание ободряет и объясняет, почему для распознавания ключевых слов так часто используется метод построения соответствующего НКА, а по нему — ДКА.
Правила, в соответствии с которыми строятся состояния ДКА, состоят в следующем: а) если д, — начальное состояние НКА, то (ас) — одно из состояний ДКА; б) допустим, р — одно из состояний НКА, и НКА попадает в него из начального состояния по пути, отмеченному символами а,а,,а . Тогда одним из состояний ДКА является множество, состоящее из а„р и всех остальных состояний НКА, в которые можно попасть из д, по пути, отмеченному суффиксом (окончанием) цепочки а,а,...а, т.е. последовательностью символов вида а,а;,о,.а . Отметим, что, вообще, всякому состоянию р НКА соответствует одно состояние ДКА. Но на шаге (б) может получиться так, что два состояния на самом деле дают одно и то же множество состояний НКА и поэтому сливаются в одно состояние ДКА.
Например, если два ключевых слова начинаются с одной и той же буквы, скажем, а, то два состояния НКА, в которые он попадает из а, по дуге с меткой а, дают одно и то же множество состояний НКА и, следовательно, сливаются в одно состояние ДКА. Пример 2.15. На рис. 2.! 7 показано, как по НКА (см.
рис. 2.16) построен ДКА. Каждое из состояний ДКА расположено на том же самом месте, что и состояние р, по которому оно построено, в соответствии с приведенным выше правилом (б). Рассмотрим, на- 2.4. ПРИЛОЖЕНИЕ: ПОИСК В ТЕКСТЕ пример, состояние (1, 3, 51, обозначенное для краткости как 135. Это состояние было построено по состоянию 3. Как и всякое множество состояний нашего ДКА, оно включает состояние 1. Кроме того, оно включает состояние 5, так как в него автомат попадает из 1 по окончанию е цепочки нее, приводящей в состояние 3 на рис. 2.16.
Рис. 2Д 7. /1реобраэовование ОКА„иэобраагенного на рис. 2дб, в ДКА Для каждого из состояний ДКА переходы могут быть найдены с помощью конструкции подмножеств. Но тут можно поступить проще. Для всякого множества состояний, включающего начальное состоЯние !1в и некотоРые дРУгие состоЯниЯ РьР„..., Р„, и дла каждого входного символа х вычислим те состояния НКА, в которые по х переходят рь Тогда данное состояние ДКА, т.е. (де, рь рз, ..., р„(, будет иметь переход по символу х в состояние ДКА, содержащее !1в и все те состояния, в которые переходят рь По всем тем символам х, по которым переходов ни из одного р, нет, данный ДКА будет иметь переход по символу х в состояние, содержащее е!в и все те состояния исходного НКА, котоРые достигаютсЯ пеРеходом из в!в по дУге с меткой х.
Рассмотрим состояние 135 на рис. 2.17. НКА на рис. 2.16 имеет переходы по символу Ь из состояний 3 и 5 в состояния 4 и 6, соответственно. Следовательно, 135 по Ь переходит в 146. По входному символу е переходов из состояний НКА 3 и 5 иет, но есть переход из! в 5. Таким образом, по е ДКА переходит из 135 в 15. Точно так же, по эв 135 переходит в 12. По любому другому символу х переходов из состояний 3 и 5 нет, а состояние 1 имеет переход только в себя. Таким образом, по любому символу из Х, за исключением Ь, е и ГЛАВА 2.
КОНЕЧНЫЕ АВТОМАТЫ 88 н, 135 переходит в 1. Обозначим это множество как Х вЂ” Ь вЂ” е- и, а также используем подобные обозначения лля других множеств, получающихся из Х удалением нескольких символов. С) 2.4.4. Упражнения к разделу 2.4 2.4.1. Постройте НКА, распознающие следующие множества цепочек: а) (я) аЬс, аЬс1 н аасс1. Входным алфавитом считать (а, Ь, с, г1); б) 0101, 101 и 011; в) аЬ, Ьс и са. Входным алфавитом считать (а, Ь, с).
2.4.2. Преобразуйте ваши НКА из упражнения 2.4.1 в ДКА. 2.5. Конечные автоматы с эпсилон-переходами Рассмотрим еще одно обобщение понятия конечного автомата. Приладим автомату новое "свойство" — возможность совершать переходы по е, пустой цепочке, т.е. спонтанно, не получая на вход никакого символа. Эта новая возможность, как и недетерминнзм, ввеленный в разделе 2.3, не расширяет класса языков, допустимых конечными автоматами, но дает некоторое дополнительное 'удобство программирования".
Кроме того, рассмотрев в разделе 3.1 регулярные выражения, мы увидим, что последние тесно связаны с НКА, имеющими в-переходы. Такие автоматы будем называть а-НКА. Они оказываются полезными при доказательстве эквивалентности между классами языков, задаваемых конечными автоматами и регулярными выражениями. 2.5.1. Использование 8-переходов Вначале будем оперировать с е-НКА неформально, используя лиаграммы переходов с в в качестве возможной метки. В следующих примерах автомат можно рассматривать как лопускающий последовательности меток, среди которых могут быть в, вдоль путей нз начального состояния в допускающее. Но при этом каждое в вдоль пути "невидимо", т.е, в последовательность ничего не добавляет.
Пример 2.16. На рнс. 2.18 изображен в-НКА, допускающий десятичные числа, которые состоят из следующих элементов. 1. Необязательный знак в илн —. 2. Цепочка цифр. 3. Разделяющая десятичная точка. 4. Еше одна цепочка цифр. Эта цепочка, как и цепочка (2), может быть пустой, но хотя бы одна из них непуста. 2.б. КОНЕЧНЫЕ АВТОМАТЫ С ЭПСИЛОН-ПЕРЕХОДАМИ 89 Рис. 2И8.
е-оКА, допускающий десятичные числа О Нача 2! 9 Использование с-переходов для распознавания ключевых слов ГЛАВА 2. КОНЕЧНЬП АВТОМАТЫ 90 Особого интереса заслуживает переход из состояния йо в д5 по любому из символов ч.,— или н Состояние дь таким образом, представляет ситуацию, когда прочитан знак числа, если он есть, но не прочитана ни одна из цифр, ни десятичная точка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
