Рекурсивная сеть переходов с фильтрами - Википедия - Filtered-popping recursive transition network

А рекурсивная сеть переходов с фильтром (FPRTN),^[1] или просто сеть с фильтрами (FPN), это рекурсивная переходная сеть (РТН )^[2] расширен картой состояний ключей, возвращающихся из подпрограмма jump требует, чтобы состояния приемника и возврата были сопоставлены с одним и тем же ключом. RTNs находятся конечные автоматы это можно рассматривать как конечные автоматы продлен с куча возвращаемых состояний; а также потребляющие переходы и ${ displaystyle varepsilon}$-переходы, RTNs может определять переходы вызовов. Эти переходы выполняют подпрограмма jump, помещая целевое состояние перехода в стек и переводя машину в вызываемое состояние. Каждый раз, когда достигается состояние акцептора, возвращается состояние наверху стека, при условии, что стек не пуст, и автомат переводится в это состояние.

В этой статье мы называем сети рекурсивных переходов с фильтром. FPNs, хотя этот акроним неоднозначен (например: нечеткие сети Петри ). Сети с фильтрами и FPRTNs однозначные альтернативы.

Формальное определение

ФПН - это структура ${ displaystyle (Q, K, Sigma, delta, kappa, Q_ {I}, F)}$ куда

• ${ displaystyle Q}$ конечный набор состояний,
• ${ displaystyle K}$ конечный набор ключей,
• ${ displaystyle Sigma}$ конечный входной алфавит,
• ${ displaystyle delta: Q times ( Sigma cup { varepsilon } cup Q) to Q}$ - функция частичного перехода, ${ displaystyle varepsilon}$ будучи пустым символом,
• ${ displaystyle kappa: Q to K}$ это карта состояний ключей,
• ${ displaystyle Q_ {I} substeq Q}$ - множество начальных состояний, а
• ${ Displaystyle F substeq Q}$ - набор состояний приемки.

Переходы

Переходы представляют собой возможность выведения FPN из исходного состояния. ${ displaystyle q_ {s}}$ в целевое состояние ${ displaystyle q_ {t}}$ возможно, выполнив дополнительное действие. В зависимости от этого действия мы выделяем следующие виды явно-определенные переходы:

• ${ displaystyle varepsilon}$-переходы переходы формы ${ displaystyle delta (q_ {s}, varepsilon) to q_ {t}}$ и не выполнять никаких дополнительных действий,
• потребляющие переходы переходы формы ${ displaystyle delta (q_ {s}, sigma) to q_ {t}}$ и использовать входной символ ${ displaystyle sigma}$, и
• переходы вызова переходы формы ${ displaystyle delta (q_ {s}, q_ {c}) to q_ {t}}$ и выполнить подпрограмма перейти в вызываемое состояние ${ displaystyle q_ {c}}$ до достижения ${ displaystyle q_ {t}}$.

Поведение переходов между вызовами регулируется двумя типами неявно-определенные переходы:

• для каждого перехода вызова ${ displaystyle delta (q_ {s}, q_ {c}) to q_ {t}}$ FPN неявно определяет толчок переход что приносит машину из ${ displaystyle q_ {s}}$ к ${ displaystyle q_ {c}}$ толкая ${ displaystyle q_ {t}}$ на куча, и
• для каждой пары состояний ${ displaystyle (q_ {f}, q_ {r}) in F times Q}$ FPN неявно определяет поп-переход что приносит машину из ${ displaystyle q_ {f}}$ к ${ displaystyle q_ {r}}$ выскакивая ${ displaystyle q_ {r}}$ из стопки если только ${ displaystyle q_ {r}}$ это состояние наверху стека и ${ Displaystyle каппа (д_ {е}) = каппа (д_ {г})}$.

Push-переходы инициализируются подпрограмма прыжки и поп-переходы эквивалентны операторы возврата.

Цель

А (естественный язык ) текст может быть дополнен метаинформацией с помощью РТН с выходом; например, RTN вставляет XML теги могут использоваться для преобразования простой текст в структурированный XML-документ. RTN с выходом, представляющим естественный язык грамматика будет разграничивать и добавлять синтаксическую структуру каждого текстового предложения (см. разбор ). Другие RTN с выводом могут просто отмечать текстовые сегменты, содержащие соответствующую информацию (см. извлечение информации ). Применение RTN с выходом, представляющим неоднозначная грамматика приводит к набору возможных переводов или интерпретаций ввода. Вычисление этого набора имеет экспоненциальную стоимость наихудшего случая, даже для Парсер Эрли для РТС с выходом,^[3] из-за случаев, когда количество переводов увеличивается экспоненциально w.r.t. длина ввода; например, количество интерпретаций естественный язык предложение увеличивается экспоненциально по сравнению с количество нерешенных предложная фраза вложения:^[4][5]

• в предложении девушка увидела обезьяну в телескоп, неизвестно, использовала ли девочка телескоп или обезьяна держала его (2¹ интерпретации),
• в предложении девушка увидела обезьяну с телескопом в саду, также неизвестно, была ли обезьяна в саду или действие происходило в саду (2² интерпретации),
• в предложении девушка увидела обезьяну с телескопом в саду под деревом, также неизвестно, была ли обезьяна под деревом или действие происходило под деревом (2³ интерпретации),
• и Т. Д.

FPN служат компактным представлением этого набора трансляций, позволяя вычислить его в кубическом времени с помощью анализатора типа Эрли.^[1] Состояния FPN соответствуют состояниям выполнения (см. шаги инструкции ) Эрли-парсера для RTNs без output, а переходы FPN соответствуют возможным трансляциям входных символов. В ${ displaystyle kappa}$ карта результирующей FPN дает соответствие между представленными выходными сегментами и распознанными входными сегментами: с учетом распознанной входной последовательности ${ Displaystyle sigma _ {1} ldots sigma _ {l}}$ и путь FPN ${ displaystyle p}$ начиная с состояния ${ displaystyle q}$ и заканчивая состоянием ${ Displaystyle д ^ { прайм}}$, ${ displaystyle p}$ представляет собой возможный перевод входного сегмента ${ displaystyle sigma _ { kappa (q) +1} ldots sigma _ { kappa (q ^ { prime})}}$. Функция отфильтрованного всплывающего окна требуется, чтобы избежать путей FPN для представления переводов отключен или же перекрытие входные сегменты: вызов FPN может содержать несколько путей трансляции из вызываемого состояния в принимающее состояние, где входные сегменты, которым они соответствуют, имеют одну и ту же начальную точку, но не обязательно имеют одинаковую длину. Только возвращаемые состояния, соответствующие той же точке ввода, что и состояние акцептора, заканчивающее вызов, являются действительный вернуть состояния.

Рекомендации