Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 287
Текст из файла (страница 287)
В следующем подразделе показано, как найти выход из этой ситуации. Эффективный синтаксический анализ Рассмотрим два приведенных ниже предложения. наие сье яспдепся 1п яессзсп 2 об ссюрпсет ясзепсе 101 саке сье ехаю. нече сье ятпдепся ьп яессзсп 2 ст союрпсет зсзепсе 101 сакеп сье ехаюз Даже несмотря на то, что первые 10 слов в этих предложениях совпадают, они имеют очень сильно отличающиеся друг от друга деревья синтаксического анализа, поскольку первое из них представляет собой команду, а второе — вопрос. При использовании алгоритма синтаксического анализа, действуюгцего слева направо, пришлось бы принять предположение о том, является ли первое слово частью предложения, представляющего собой команду или вопрос, но нельзя было бы подтвердить правильность этого предположения по меньшей мере до обработки одиннадцатого слова, "где" или "га8еп".
Если предположение, принятое в этом алгоритме, оказывается неправильным, то приходится осуществлять полный возврат вплоть до первого слова. Такого рода возврат является неизбежным, но для повышения эффективности алгоритма синтаксического анализа следует предотвратить повторный анализ словосочетания "гуге зщдеп1з ш зесйоп 2 ор Согпрнгег Вс1епсе 101" как АГР после каждого возврата. В этом разделе будет разработан алгоритм синтаксического анализа, в котором исключен указанный источник неэффективности.
В его основе лежит идея, представляющая собой пример динамического программирования — сгг ловле проведения анализа каждой подстроки сохранять резулынаты, чтобы не нужно было проводить ее 1059 Глава 22. Общение повторный анализ в дальнейшем. Например, обнаружив, что словосочетание "г]ге згцдеп]з гп вес]юп 2 о(СошрцГег бсгепсе 101" относится к типу Ггр, можно зарегистрировать этот результат в структуре данных, известной под названием Ъ. диаграммы. Алгоритмы, поддерживающие эти функции, называются диаграммными синтаксическими анализаторами.
Поскольку в данном случае мы имеем дело с контекстно- свободными грамматиками, то любое словосочетание, обнаруженное в контексте одной ветви пространства поиска, вполне может применяться и в любой другой ветви пространства поиска. Диаграмма для последовательности из и строк включает в себя и+1 Ъ. вершину и целый ряд Ъ. ребер, которые соединяют вершины. На рис. 22.2 показана диаграмма с шестью вершинами (обозначенными кружками) и тремя ребрами (обозначенными линиями).
Например, ребро со следующей меткой: !О, 5, Я -Ч ЬГР РР ° ] означает, что словосочетание д(Р, за которым следует ]гр, объединяются, составляя узел Я, который охватывает строку от вершины О до вершины 5. Символ ° в обозначении ребра' отделяет то, что было найдено до тех пор, от того, что осталось найти.
Ребра с символами ° в конце называются полными ребрами. Например, следующее ребро: 10, 2, Я -ь вгр ° РР] указывает, что словосочетание дгр охватывает строку от вершины 0 до вершины 2 (первые два слова) и что если бы мы смогли найти словосочетание ]гр, чтобы продолжить это ребро, то получили бы словосочетание Б. Ребра, подобные этому, в которых точка не достигла конца, называются неполныыи ребрами, и принято говорить, что для этого ребра требуется найти словосочетание ]гр.
!0,5 л — ь)гР УР ! Рис. 22.2. Часть дииграммы, соответствующей предложению "ТЬе аеепг)ее)з а Ьгееге" (Агент чувствует ветерок). Показаны все шесть вершин, но только три из тек ребер, которые требуются для полного сиягпаксического анализа Алгоритм диаграммного синтаксического анализатора показан в листинге 22.4. Его основная идея такова, что в нем объединяются лучшие свойства нисходящего и восходящего синтаксического анализа. Процедура ргес]зспог выполняет нисходящий анализ; она создает записи в диаграмме, которые указывают, какие символы желательно найти и в каких местах.
Процедура Бсаппет — это процедура восходящего анализа, которая начинает работу со слов, но использует любое слово только для продления существующей записи в диаграмме. По аналогии с ней процедура з Именно в связи с тем, что в обозначении ребер применяется символ °, такие обозначения иногда называют правилами с точкой. 1060 Часть у11. Общение, восприятие и Осуществление действий ехсепает формирует составляющие дерева синтаксического анализа в направле- нии снизу вверх, но только для продления существующей записи в диаграмме. Листинг 22.4. Алгоритм диаграммною синтаксического анализатора, где и — начальный символ, и' — новый нетермннальный символ, а свате [у) — список ребер, которые оканчивается в вершине з. Словосочетания, обозначенные греческими буквами, согласуются с некоторой строкой, имеющей длину от нуля н больше символов Еипсейоп С)зале-ратзе(котс(з, дтаттат) гесигпе диаграмма с)зато слало с- массив[о.двепдеп(котс)з)1 пУстых списков АсЫ-Ес)де([О,О,В' -ч ° В]) Еог Е с в Егот О со ьепдт)с(котс)з) бо Всаппет(Е, котс(з[Е)) гесигп с)зато ргосебиге дбс)-Ебде(ес(де) с'* Добавить ребро к диаграмме и проверить, позволяет ли оно продлить или предсказать другое ребро *с' 1Е ребро ес)де не находится в диаграмме сйатг[Епб(ес)де)] Еиеп добавить ребро ес(де к диаграмме одетт[Вас)(ес)де)1 ЕЕ ребро езде не содержит ничего после точки еьеп ехтепс)ет(ес)де) е1ее ртес)вссот(ес)де) ргосебиге Ясаппет(з', котс)) с'* Для каждого ребра, ожидающего в данный момент появления слова заданной категории, выполнить продление этого ребра *с' еог вась [е, у, л -в а ° В []] зп с)ватс[у1 Йо зЕ слово ьсотс) относится к категории В Спеп ХЙЙ-Ебде([Е,У+1,А -ч а В ° [3]) ргосебиге ртес)йссот([е,у,л -ь а ° В [)]) /* Добавить к диаграмме любые правила для В, которые могут помочь продлить это ребро *У еог еась (В ч у) еп ееитесев-рот(В, дтаттат) сто А<И-Ес)де([)',З,В -ь ° у]) ргосебиге ехтепс)ет([у,)с,в -ч у ° 1) у* Проверить, какие ребра могут быть продлены с помощью этого ребра */ ев с в ребро, которое является входным для этой процедуры еог енса [е,у,л — а а ° В' р] зп свате[у) сто зЕ В = В' Еиеп ЛСЫ-ЕбдЕ([Е,)С,Л -Ф П Ев ° ]3]) Для запуска всего алгоритма воспользуемся таким приемом: добавим к диаграмме ребро [О, О, Я' — ь ° Я], где Я вЂ” начальный символ грамматики, а Я' — новый символ, который был только что предложен.
Вызов процедуры Ас[б-ес)де вынуждает процедуру ртес)1ссот ввести ребра, соответствующие правилам, применение которых может привести к получению В, т.е. [ — ь д)р (гр] . Затем осуществляется !Об! Глава 22. Общение поиск первой составляющей этого правила, дгр, и добавление правил, соответствующих каждому способу получения какого-то подходящего словосочетания тур. В конечном итоге процедура предсказателя РкеЖспог добавляет в режиме нисходящего синтаксического анализа все возможные ребра, которые могут использоваться в процессе создания окончательного словосочетания Я.
После завершения работы прелсказателя применительно к словосочетанию Я' алгоритм входит в цикл, в котором вызывается процедура Ясаппег для каждого слова в предложении. Если слово, находящееся в позиции 3', является членом такой категории в, которая отыскивается для некоторого ребра в позиции т', то данное ребро продлевается, а слово отмечается как экземпляр категории Е. Обратите внимание на то, что каждый вызов процедуры Ясаппек приводит к рекурсивному вызову процедур РкеЖ с ток и ехсепс(ек, в результате чего происходит чередование нисходящей и восходящей обработки.
Другой компонент восходящей обработки4, ПрОцеДУра Ехсепс)ег, принимает на входе некоторое полное ребро с левой частью Я и использует его для продления любого неполного правила в диаграмме, которая оканчивается там, где начинается полное ребро, если для этого неполного правила требуется категория Я. На рис. 22.3 и в табл. 22.3 показаны диаграмма и трассировка процесса синтаксического анализа с помощью этого алгоритма предложения "! (ее! й" (которое является положительным ответом на вопрос "Ро уоц Гее! а Ьгееге?" — "Вы чувствуете ветерок?").
В этой диаграмме зарегистрированы тринадцать ребер (обозначенных метками от а до лг), включая пять полных ребер (показанных над вершинами диаграммы) и восемь неполных ребер (показанных под вершинами). Обратите внимание на то, как действуют в цикле процедуры предсказания РгеЖскок, сканирования Ясаппег и продления Ехтепс!ек. Например, в процедуре предсказания используется тот факт, что для ребра а должен быть выполнен поиск словосочетания Я, чтобы можно было разрешить сделать предсказание о том, что должно появиться словосочетание вгр (ребро Ь), а затем словосочетание Ркопоип (ребро с). После этого процедура сканирования распознает, что в нужном месте находится словосочетание Ркопоцп (ребро г!), а процедура продления объединяет неполное ребро .Ь с полным ребром с!для получения нового ребра, е.
4 По традиции применяемая нами процедура Ехтепг1ег именуется Согпр!егег. Но последнее название может сбить с толку, поскольку эта процедура не пополняет ребра — она принимает на входе полное ребро и продлевает неполные ребра. 1062 ЗитР/Ргааоап ВУР!Уа Ь р УР) УР нр а;ЗГЗ Ь:У(гтр УР с)ГР[ргапоап Рис. 22.3.
Диаграмма синтаксического анализа предложения еа Х Г Киот З ХЕ З . ЗавиСЬ тзя ОЗНаЧаЕт, Чта рЕбра Га иМЕ- ет словосочетание Я в левой части правила, а запись б гззРУЧек)говночист, что ребро б имеет словосочетание тзв в левой части, но для него требуется также выполнить згоиск словосочетания ггехь. В этой диаграмме шиеетсн пять полных ребер, показанных над вершинами, и восемь неполных ребер, показанных под вершинами Таблппа 22.3.
ТРассиРовка пРопесса сщпаксическао анализа пРедложениЯ ", Х, Ееот * де з". Дла каждщо ребра от и до и показано, какая процедура используется двя вывода этого ребра из яру~их ребер, уже имеющихся в дищрамме. Некоторые ребра бьищ искмочены в целях сокращения объема таблицы Ребро процедура Этап вывода !п!г!а1иег Ргеб!сгог(а) Ргед!стог(Ь) Бсаппег(с) Ехгспдег(Ь,Н) Ргегйсгог(е) Ргеабсгог(е) Бсаппег(Г) Ехгепдег(я,й) Ргед(сгог(я) Бсаппег0) Ехгепйег(г,й) Ехгепйег(е 0 Часть Ч1!.
Общение, восприятие и осуществление действий ([0,0, З. )Згр УР)) ([0,0, Р(Р— а ° Рюпоип1 ) ([0,1, РГР -+ Ргопоип е]) ([0,1, 5 — + Р(Р ° УР)) (11,1, УР - ° У. Ьй ([1,1, УР . ° УРМ )) ([1,2, УР е УегЬ ° )) ([1,2, УР— е УР ° МР)) ([2,2, Р4Р— е ° Рюпоип)) ([2,3, МР— е Ргопоип ° )) ([1,3, УР. У'ЛР 1) ([0,3, 5 -+ РГР 1'Р е)) 1063 Глава 22. Об!цение Этот алгоритм диаграммного синтаксического анализатора позволяет предотвратить формирование большого класса ребер, которые пришлось бы исследовать при использовании простой восходящей процедуры.
Рассмотрим предложение: "Т)зе г!де !)!е )югзе даче хчаз хч)!д" (Скачка, на которую пустилась эта лошадь, была дикой). Процедура восходящего синтаксического анализа отметила бы словосочетание "г)де !)!е )!огзе" (скакать на лошади) как )хр, а затем отбросила бы все дерево синтаксического анализа, обнаружив, что такой вариант анализа не складывается в общее сло- ВОСОЧЕтаНИЕ ~. НО В ЯЗЫКЕ Еь НЕ раЗрЕШаЕтСя, ЧтОбЫ СЛОВОСОЧЕтаНИЕ )гр СЛЕдОВаЛО За словом "!)зе", поэтому данный алгоритм диаграммного синтаксического анализатора никогда не предсказал бы наличие в этой точке словосочетания и' и поэтому избежал бы напрасного расходования времени на формирование здесь составляющей )гр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
