Типы распознающих устройств в системах синтаксического распознавания образов

Автоматные языки и конечные автоматы.

Конечный (детерминированный) автомат - пятёрка A =( Σ , Q, δ , q ₀, F ), где Σ - конечное множество входных символов (алфавит), Q - конечное множество состояний, δ - функция, определяющая следующее состояние, т.е. отображение Q × Σ в Q, q ₀ Q - начальное состояние и F Q - множество заключительных состояний. Функция δ ( q, a ) интерпретируется следующим образом: автомат A в состоянии q читает входной символ a, переходит в состояние q ’ и сдвигает устройство считывания на один символ вперёд. Отображение δ можно распространить с одного входного символа на цепочку, если определить

δ (q, λ ) = q, δ (q, xa) = δ ( δ (q, x), a), x Σ ^*, a Σ .                 (2.5)

 

Таким образом, δ ( q, λ ) = q ’ понимается так: находясь в состоянии q, автомат A просматривает цепочку x на входной ленте и переходит в состояние q ’, а считывающее устройство смещается вперёд с той части входного потока, которая содержит x. Говорят, что цепочка, или предложение x, допускается автоматом A, если

δ ( q, λ ) = p для некоторого p F.                           (2.6)

 

Множество цепочек, допускаемых A, определяется как

T ( A ) = { x | δ ( q ₀, x ) F }.                           (2.7)

 

Недетерминированный конечный автомат есть пятёрка A = ( Σ , Q, δ , q ₀, F ), где Σ - конечное множество входных символов (алфавит), Q - конечное множество состояний, δ - отображение Q × Σ во множество подмножеств множества Q, q ₀ - начальное состояние и F - множество заключительных состояний.

Единственная разница между детерминированным и недетерминированным вариантами автомата состоит в том, что δ ( q, a ) обозначает множество состояний (возможно, пустое), а не обязательно единственное состояние. Отображение δ ( q, a ) = ( q ₁, q ₂, …, q_l ) интерпретируется следующим образом: автомат в состоянии q, читая на входе символ a, выбирает в качестве следующего любое из состояний q ₁, q ₂, …, q_l, и сдвигает считывающее устройство на один символ вперёд. Как и в случае детерминированного автомата, отображение δ можно распространить с одного входного символа на цепочку, определив

δ (q, λ ) = q, δ (q, xa) =   δ (q_i, a), x Σ ^*, a Σ .           (2.8)

 

Далее можно определить

δ ( { q ₁, q ₂, …, q_l }, x ) = δ ( q_i, x ).                  (2.9)

Цепочка x допускается недетерминированным автоматом A, если найдётся такое состояние p, что

p δ ( q ₀, x ) и p F.                               (2.10)

 

Множество цепочек, допускаемых автоматом A, определяется как

T (A) = {x| p δ (q₀, x и p F)}.                      (2.11)

 

Доказано, что если имеется недетерминированный конечный автомат A, который допускает множество цепочек L, то существует детерминированный конечный автомат A ’, который допускает L. Поэтому в дальнейшем, если в этом не будет необходимости, и те и другие автоматы будут называться просто конечными автоматами [4].

Бесконтекстные языки и магазинные автоматы.

Магазинный автомат определяется как семёрка M = (Σ, Q, Γ , δ, q ₀, Z ₀, F ), где Σ - конечное множество входных символов, Q - конечное множество состояний, Γ - конечное множество магазинных символов, q ₀ Q - начальное состояние, Z ₀ Γ - начальный символ, первым появляющийся в магазинной памяти, F Q - множество заключительных состояний, δ - отображение Q × (Σ U{ λ })× Γ во множество конечных подмножеств Q × Γ ^*.

Устройство магазинного автомата близко к устройству конечного автомата, но он снабжён дополнительной магазинной памятью. Магазинная память организована по стековому принципу, т.е. символы можно вводить или считывать только на вершину и с вершины магазинной памяти [4].

Отображение

δ ( q, aZ ) = {( q ₁, γ ₁ ), , …, ( q_m, γ _m )}, q ₁, …, q_m Q, a Σ , Z Γ , γ ₁, …, γ _m Γ ^*

интерпретируется следующим образом: магазинный автомат, находясь в состоянии q, считывает входной символ a и верхний символ магазина Z, переходит в состояние q_i, заменяя в магазине памяти символ Z на символ γ _i, 1≤ i ≤ m, и продвигает устройство считывания на один символ. Запись

δ ( q, λ , Z ) = {( q ₁, γ ₁ ), ( q ₂, γ ₂ ), …, ( q_m, γ _m )}                  (2.12)

 

означает, что магазинный автомат в состоянии q_i при верхнем символе в магазине Z независимо от считываемого входного символа перейдёт в состояние q_i и заменит Z на γ _i, 1 ≤ i ≤ m. В этом случае считывающее устройство не работает. Такая операция используется для изменения содержания магазина и обычно называется λ -движением.

Для описания “ситуации” магазинного автомата используется упорядоченная пара ( q, γ ), q Q ₀ и γ Γ ^*. Если ( q ’, β ) δ ( q, a, Z ), q, q ’ Q, для a ( Σ U { λ }), γ, β Γ и Z Γ , то выражение

a ( q, Zγ ) ( q ’, β γ )                                          (2.13)

 

означает, что по правилам перехода данного автомата M входной символ a может вызвать переход M из ситуации ( q, Zγ ) в ситуацию ( q ’, β γ ). Если для символов a ₁, a ₂, …, a_n, a_i ( Σ U { λ }), 1 ≤ i ≤ n, состояний q ₁, q ₂, …, q_{n +1} и цепочек γ ₁, γ ₂, …, γ _{n +1}, γ _i Γ *, 1 ≤ j ≤ n +1, справедливо, что

a: (q_i, γ _i ) (q_i+1, γ _i+1 ), 1 ≤ i ≤ n,                                (2.14)

 

то пишется

a₁a₂…a_n: (q₁, γ ₁ ))  (q_i+1, γ _i+1 ).                                (2.15)

Допускаемые магазинными автоматами языки определяются двумя способами. Для магазинного автомата M язык T ( M ), допускаемый при помощи заключительного состояния, определяется как

T ( M ) = { x | x: ( q ₀, Z ₀ )  ( q, γ ) для некоторых γ Γ и q F }.     (2.16)

 

С другой стороны, язык N ( M ), допускаемый M при пустом магазине, определяется как

N ( M ) = { x | x: ( q ₀, Z ₀ )  ( q, λ ) для некоторого q Q }.            (2.17)

 

Если язык допускается автоматом при пустом магазине, то множество заключительных состояний автомата M не используется. В этом случае обычно принимается F = Ø .

Языки, допускаемые магазинными автоматами при пустом магазине, являются бесконтекстными [4].

Машины Тьюринга.

Машина Тьюринга - шестёрка T = ( Σ , Q, Γ , δ , q ₀, F ), где Q - конечное множество состояний, Γ - конечное множество символов на входе, один из которых - пустой символ B. В начале работы n крайних левых полей на входе машины содержат символы входной цепочки (n - конечное число). Оставшееся бесконечное число полей заполнено специальным символом B - символом «пустое место», который не является входным.

Подмножество Σ Γ , не содержащее B, составляет множество входных символов, δ - отображение Q × Γ в Q × (Γ -{ B })× { L, R } (оно может быть не определено для некоторых аргументов), q ₀ Q - начальное состояние, F Q - множество заключительных состояний.

Разница между машиной Тьюринга и конечным автоматом состоит в том, что машина Тьюринга может изменять содержимое полей на входе при помощи своей читающей-пишущей головки.

Ситуация машины Тьюринга задаётся тройкой ( q, α , i ), где q Q, α (Γ -{ B })* - непустая часть ленты, i - расстояние читающей-пишущей головки от левого конца α . Пусть ( q, A ₁ A ₂ … A_n, i ), 1 ≤ i ≤ n +1 - ситуация машины Тьюринга. Если δ ( q, Ai ) = ( p, x, R ), 1 ≤ i ≤ n, то движение T, под которым понимается элементарное действие машины, может быть записано как

(q, A₁A₂…A_n, i) (p, A₁A₂...A_i-1XA_i+1…A_n, i+1).             (2.18)

 

Это означает, что машина Тьюринга записывает в i-ю клетку символ X и сдвигает головку на одно поле вправо. Если же δ (q, A_i) = (p, X, L), 2≤ i≤ n, то

(q, A₁A₂…A_n, i)  (p, A₁A₂...A_i-1XA_i+1…A_n, i-1).             (2.19)

 

В этом случае машина Тьюринга записывает символ X в i-ю клетку и сдвигает головку на одно поле влево, но не левее левого конца ленты. Если i = n +1, то машина считывает пустой символ B. Если δ ( q, B ) = ( p, X, R ), то

(q, A₁A₂…A_n, n+1)  (p, A₁A₂, …A_n, X, n+2).       (2.20)

 

Если же, наоборот, δ ( q, B ) = ( p, X, L ), то

(q, A₁A₂…A_n, n+1)  (p, A₁A₂, …A_n, X, n).           (2.21)

 

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

Язык, допускаемый машиной Тьюринга, определяется как множество

{ x | x Σ ^* и ( q ₀, x, 1)  ( q, α , i ) для некоторых q F, α Σ ^* и i }    (2.22)

 

Считается, что машина T, допускающая язык L, останавливается на каждом допустимом входе (т.е., допустив цепочку, машина прекращает работу). С другой стороны, возможно, что машина T не остановится, если входная цепочка не принадлежит языку L.

Недетерминированная машина Тьюринга - это такая машина, у которой δ - отображение Q × Γ во множество подмножеств множества Q × (Γ -{ B })× { L, R }. Можно показать, что если язык L допускается недетерминированной машиной Тьюринга T ₁, то L допускается и некоторой недетерминированной машиной Тьюринга T ₂.

Линейно ограниченный автомат.

Линейно ограниченным автоматом M называется шестёрка M = ( Σ , Q, Γ , δ , q ₀, F ), где Q - конечное множество состояний, Γ - конечное множество входных символов, Σ Γ - множество входных символов, δ - отображение Q × Γ во множество подмножеств Q × Γ × { L, R }, q ₀ Q - начальное состояние, F Q - множество заключительных состояний. Множество Σ содержит два специальных символа, обозначаемых обычно Ø и $, которые отмечают соответственно левый и правый концы цепочки. Их функция - не дать считывающему устройству уйти с той части цепочки, на которой задан вход.

Из определения следует, что линейный ограниченный автомат есть, в сущности, недетерминированная машина Тьюринга, которая никогда не сдвигается с той части входной ленты, на которой задан вход [4]. Ситуация линейно ограниченного автомата и связь между двумя ситуациями  определяются так же, как и для машины Тьюринга. Язык, допускаемый линейным ограниченным автоматом, есть множество

{ x | x ( Σ -{Ø, $}) ^* и ( q ₀ Ø x $, 1) ( q, α , i )

для некоторых q F, α Γ ^* и i }. (2.23)

 

Если для любого q Q и A Γ отображение δ ( q, A ) содержит не более одного элемента, то линейно ограниченный автомат называют детерминированным.

Линейно ограниченные автоматы допускают языки непосредственно составляющих, и только их.

 

Модификации грамматик

Известно, что бесконтекстные грамматики не являются достаточно мощным средством для описания естественных языков или языков программирования. С другой стороны, языки непосредственно составляющих (но не бесконтекстные) требуют весьма сложного синтаксического анализа. Компромисс достигается путём введения различных обобщений бесконтекстных грамматик. Такими обобщениями являются программные и индексные грамматики [4].

Программные грамматики.

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

Программной грамматикой G_p называется пятёрка ( V_N, V_T, J, P, S ), где V_N, V_T и P - конечные множества вспомогательных символов, основных символов и правил вывода соответственно, S - начальный символ, S V_N, J - множество меток правил подстановки.

Правило вывода из P имеет вид

( r ) α → β       S ( U )      F ( W ).                                  (2.24)

 

Правило подстановки α → β называется ядром. Здесь α V ^* V_NV и β V ^*; r - метка (обычно номер правила); U - список переходов при успехе, W - список переходов при неудаче, U, W J.

Программная грамматика действует следующим образом. Сначала применяется правило с меткой (1). Если делается попытка применить правило ( r ), чтобы заменить подцепочку α , и выведенная перед этим цепочка содержит α, то применяется правило ( r ) α → β , и следующее правило выбирается из правил, метки которых содержатся в списке переходов при успехе U. Если выведенная цепочка не содержит α , то правило ( r ) не используется, а следующее правило выбирается из тех, метки которых содержатся в списке переходов при неудаче W. В случае, когда ядра всех выводов имеют бесконтекстную форму (т.е. A → β ), грамматика называется бесконтекстной программной. Аналогично, когда ядра правил имеют регулярный вид или вид правил непосредственно составляющих, грамматика называется регулярной программной или программной грамматикой непосредственно составляющих. Показано, что язык, порождённый бесконтекстной программной грамматикой, может быть языком непосредственно составляющих. Более того, показано, что класс языков, порождённых бесконтекстными программными грамматиками, включает все бесконтекстные языки.

Индексные грамматики.

Это обобщение получается при введении в грамматику нового конечного множества - множества индексов. Грубо говоря, за вспомогательным символом в цепочке могут следовать произвольные списки индексов. Если вспомогательный символ со следующими за ним индексами заменяется одним или несколькими вспомогательными символами, индексы будут следовать за всеми вновь порождёнными вспомогательными символами. Если вспомогательный символ заменяется основным, индексы пропадают.

Индексной грамматикой называется пятёрка G_i = ( V_N, V_T, F, P, S ), где V_N, V_T, F и P - конечные множества вспомогательных символов, основных символов, индексов и правил подстановки соответственно, S V_N - начальный символ. Каждый символ из F - это конечное множество специальных (индексных) правил подстановки вида A → α , где A V_N и α V ^*. Правила подстановки из P имеют вид A → X ₁ ψ ₁ X ₂ ψ ₂ … X_m ψ _m, где X ₁, X ₂, …, X_m V_NUV_T, а ψ ₁, ψ ₂, …, ψ _m лежат в F ^*. Если X_i V_T, то ψ _i = λ .

Определим отношение  на цепочках множества ( V_NF ^*UV_T )^* следующим образом:

. Если α A θ β - цепочка, в которой α и β ( V_NF *UV_T )^*, A V_N, θ F ^*, а A → X ₁ ψ ₁ X ₂ ψ ₂ … X_m ψ _m - правило подстановки из P, в котором X_i V, а ψ _i F ^*, для всех i, то считаем, что

 

α A θ β α X ₁ φ ₁ X ₂ φ ₂ … X_m φ _m β.                           (2.25)

 

Здесь φ _i = λ , если X_i V_T, и φ _i = ψ _i θ , если X_i V_N.

. Если α Af θ β - цепочка, в которой α и β ( V_NF *UV_T )^*, A V_N, f F и θ F ^*, а A → X ₁ ψ ₁ X ₂ ψ ₂ … X_m ψ _m - индексное правило из f, то

α Af θ β α X ₁ φ ₁ X ₂ φ ₂ … X_m φ _m β ,                         (2.26)

 

где φ _i = λ , если X_i V_T, и φ _i = θ , если X_i V_N.

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

Языки описания образов

Выбор непроизводных элементов.

Выше было сказано, что первый этап построения синтаксической модели образов состоит в определении множества непроизводных элементов, при помощи которых можно описать эти образы. Выбор непроизводных элементов существенно зависит от природы образов, специфики области применения и от характера доступных технологических средств. Обычно при этом выборе стараются выполнить следующие требования [4]:

1. Непроизводные элементы должны служить основными элементами образов и обеспечивать адекватное и сжатое описание исходных данных в терминах заданных структурных отношений.

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

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

Методы выделения непроизводных элементов можно разделить на две группы. В одной из них упор делается на границы, а во второй - на области изображения.

Выделение непроизводных элементов на границах и остовах.

Множество непроизводных элементов, которые обычно используют для описания границ и остовов, получают по схеме цепного кодирования. На двумерное изображение накладывают прямоугольную сетку, и узлы сетки, которые наиболее близки к точкам изображения, соединяют отрезками прямых. Каждому такому отрезку в соответствии с его наклоном присваивают восьмеричное число. Таким образом, изображение представляется цепью (последовательностью) или цепями восьмеричных чисел. Эта дескриптивная схема обладает рядом полезных свойств. Например, поворот изображения на угол, кратный 45º, сводится к прибавлению восьмеричного числа (сложение по модулю 8) к каждому числу цепочки. Конечно, при этом изображение может исказиться. Только поворот на угол, кратный 90º, никогда не приводит к искажению изображения. Легко выполняются и некоторые другие простые манипуляции с изображением, такие, как растяжение, изменение длины кривой, определение самопересечений. Изменяя шаг сетки, накладываемой на изображение, можно получить любое желаемое разрешение [4]. Этот метод не ограничен изображениями с односвязными замкнутыми изображениями. Его можно применять для описания произвольных двумерных фигур, составленных из прямых и кривых линий и отрезков. На рис.10 показано множество непроизводных элементов и кодовая цепочка 66767011221222, которая описывает кривую.

 

Непроизводные элементы из областей.

Второй способ выделения непроизводных элементов - кодирование геометрических образов, которые строятся из областей. Основными непроизводными элементами служат полупространства образов (поля наблюдения). Можно показать, что любая фигура аппроксимируется произвольным многоугольником, который, в свою очередь, можно представить как объединение конечного числа выпуклых многоугольников. Каждый выпуклый многоугольник можно представить в виде пересечения конечного числа полуплоскостей. Если подходящим образом задать последовательность выпуклых многоугольников, составляющих произвольный многоугольник, то можно однозначно определить минимальное множество в некотором смысле множеств, объединение которых даст исходную фигуру. По аналогии с лингвистикой фигура - это «предложение», составляющие её выпуклые многоугольники - «слова», а полуплоскости - «буквы» [4].

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

Использование семантической информации.

Для выделения непроизводного элемента требуется некоторое множество признаков. Непроизводные элементы с разными величинами могут быть описаны величинами признаков. Это множество признаков можно рассматривать как семантическую информацию о непроизводных элементах. Каждый признак можно выразить набором чисел или логических предикатов.

Начальное описание T ( x ) образа x можно определить выражением

T ( x ) = ( T_s ( x ), T_v ( x )),                                       (2.27)

 

где T_s ( x ) - задание непроизводных элементов образа x и их взаимных отношений, а T_v ( x ) - значение признаков для каждого элемента. Структурная информация об образе x задаётся синтаксическим или иерархическим описанием

H ( x ) = ( H_s ( x ), H_v ( x )),                                     (2.28)

 

где H_s ( x ) - синтаксическая компонента, состоящая из множества необходимых для порождения T_s ( x ) правил подстановки, а H_v ( x ) - выполнимость интерпретационного правила, соответствующего каждому правилу подстановки грамматики G, которое используется при грамматическом разборе выражения T_s (α ). Таким образом, полное описание образа x определено выражением

(T(x), H(x)) = ((T_s(x), T_v(x)), (H_s(x), H_v(x))).           (2.29)

 

Класс образов может быть описан ассоциативной семантической информацией и грамматикой G, такой, что для любого образа x из этого класса T_s ( x ) L ( G ). «Смысл» образа выражен как начальным, так и синтаксическим описанием.

Все признаки разделяются на две группы: унаследованные и синтезированные [4]. Унаследованные признаки касаются тех аспектов смысла, которые определяются контекстом фразы, а синтезированные связаны с самой фразой.

Принципиально для определения смысла цепочки в бесконтекстном языке достаточно одних синтезированных признаков. Однако включение унаследованных признаков часто приводит к существенным упрощениям в оценке признаков.

Семантические правила добавляются к бесконтекстной грамматике следующим образом. Каждому символу X ( V_N U V_T ) приписано конечное множество A ( X ) признаков. Оно разделено на два непересекающихся множества синтезированных A ₀ ( X ) и унаследованных A ₁ ( X ) признаков. Требуется, чтобы A ₁ ( S )=Ø и A ₀ ( X ) = Ø при X V_T. Каждый признак α A ( X ) имеет множество возможных значений D _α , из которого при появлении символа X в дереве синтаксического анализа может быть выбрано одно значение. Пусть множество P состоит из m правил подстановки, и пусть k-е правило имеет вид

X_{k 0} → X_{k 1}, X_{k 2}, …, X_knk,                                           (2.30)

 

где X_{k 0} V_N, n ≥ 0, и X_kj ( V_N U V_T ), 1 ≤ j ≤ n_k. Семантическими правилами называются функции f _kjα , определённые для всех 1 ≤ k ≤ m, 0 ≤ j ≤ n_k, причём α A ₀ ( X_kj ) при j = 0 и α A ₁ ( X_kj ) при j > 0. Каждая такая функция - это отображение прямого произведения D _{α 1} × D _{α 2} × …× D _{α t} во множество D _α для некоторого t = t ( k, j, α ) ≥ 0, где каждое α _i = α _i ( k, j, α ), 1 ≤ i ≤ t, - это признак некоторого символа X_kli для 0 ≤ l_i ≤ n_k. Иными словами, каждое семантическое правило переводит определённые признаки символов X_{k 0}, …, X_knk в величину некоторого признака X_kj.

Приписывание семантики цепочкам бесконтекстного языка при помощи семантических правил осуществляется следующим образом. Для любой основной цепочки x нужно обычным образом построить дерево её вывода из начального символа S. Корнем этого дерева является символ S, а вершина, соответствующая применению k-го правила подстановки, является либо основным, либо вспомогательным символом x_{k 0}. Пусть X - символ какой-либо вершины этого дерева, а α A ( X ) - признак этого символа. Если α A ₀ ( X ), то X = X_{k 0} для некоторого k, а если α A ₁ ( X ), то X = X_kj для некоторых j и k, 1≤ j ≤ n_k. По определению, признак α имеет величину v для данной вершины, если в соответствующем семантическом правиле

f _kjα : D _{α 1} × D _{α 2} × …× D _{α t} → D _α                             (2.31)

 

все признаки имеют величины v ₁, …, v_t для соответствующих вершин, помеченных символами X_{kl 1}, …, X_klt, и v = f _kjα ( v ₁, …, v_t ). Этот процесс оценки признаков нужно проводить по всему дереву до тех пор, пока он не закончится естественным образом [4]. Полученные на этой стадии оценки признаков и являются «смыслом», соответствующим данному выводу.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: