Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Методы распознавания образов при идентификации объектов бинарного класса в автоматизированных телекоммуникационных комплексах систем управления
Методы распознавания образов при идентификации объектов бинарного класса в автоматизированных телекоммуникационных комплексах систем управления
Основные цели и задачи построения систем распознавания. Построение математической модели системы распознавания образов на примере алгоритма идентификации объектов военной техники в автоматизированных телекоммуникационных комплексах систем управления.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 30.11.2012 |
| Размер файла | 332,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Единственная разница между детерминированным и недетерминированным вариантами автомата состоит в том, что д(q, a) обозначает множество состояний (возможно, пустое), а не обязательно единственное состояние. Отображение д (q, a) = (q1, q2, …, ql) интерпретируется следующим образом: автомат в состоянии q, читая на входе символ a, выбирает в качестве следующего любое из состояний q1, q2, …, ql, и сдвигает считывающее устройство на один символ вперёд. Как и в случае детерминированного автомата, отображение д можно распространить с одного входного символа на цепочку, определив
д (q, л) = q, д (q, xa) = д(qi, a), xУ*, aУ. (2.8)
Далее можно определить
д ( {q1, q2, …, ql},x) = д(qi, x). (2.9)
Цепочка x допускается недетерминированным автоматом A, если найдётся такое состояние p, что
pд (q0, x) и pF. (2.10)
Множество цепочек, допускаемых автоматом A, определяется как
T (A) = {x| pд (q0, x и pF)}. (2.11)
Доказано, что если имеется недетерминированный конечный автомат A, который допускает множество цепочек L, то существует детерминированный конечный автомат A', который допускает L. Поэтому в дальнейшем, если в этом не будет необходимости, и те и другие автоматы будут называться просто конечными автоматами [4].
Бесконтекстные языки и магазинные автоматы.
Магазинный автомат определяется как семёрка M = (У,Q,Г,д,q0, Z0, F), где У - конечное множество входных символов, Q - конечное множество состояний, Г - конечное множество магазинных символов, q0Q - начальное состояние, Z0Г - начальный символ, первым появляющийся в магазинной памяти, FQ - множество заключительных состояний, д - отображение Q?(УU{л})?Г во множество конечных подмножеств Q?Г*.
Устройство магазинного автомата близко к устройству конечного автомата, но он снабжён дополнительной магазинной памятью. Магазинная память организована по стековому принципу, т.е. символы можно вводить или считывать только на вершину и с вершины магазинной памяти [4].
Отображение
д(q, aZ) = {(q1, г1), ,…, (qm, гm)}, q1, …, qmQ, aУ, ZГ, г1, …, гmГ*
интерпретируется следующим образом: магазинный автомат, находясь в состоянии q, считывает входной символ a и верхний символ магазина Z, переходит в состояние qi, заменяя в магазине памяти символ Z на символ гi, 1?i?m, и продвигает устройство считывания на один символ. Запись
д(q, л, Z) = {(q1, г1), (q2, г2),…, (qm, гm)} (2.12)
означает, что магазинный автомат в состоянии qi при верхнем символе в магазине Z независимо от считываемого входного символа перейдёт в состояние qi и заменит Z на гi, 1 ? i ? m. В этом случае считывающее устройство не работает. Такая операция используется для изменения содержания магазина и обычно называется л-движением.
Для описания “ситуации” магазинного автомата используется упорядоченная пара (q, г), qQ0 и гГ*. Если (q',в)д(q, a, Z), q, q'Q, для a(УU{л}), г, вГ и ZГ, то выражение
a (q, Zг)(q', вг) (2.13)
означает, что по правилам перехода данного автомата M входной символ a может вызвать переход M из ситуации (q, Zг) в ситуацию (q', вг). Если для символов a1, a2, …, an, ai(УU{л}), 1 ? i ? n, состояний q1, q2, …, qn+1 и цепочек г1, г2, …, гn+1, гiГ*, 1 ? j ? n+1, справедливо, что
a :(qi, гi)(qi+1, гi+1), 1 ? i ? n, (2.14)
то пишется
a1a2…an: (q1, г1)) (qi+1, гi+1). (2.15)
Допускаемые магазинными автоматами языки определяются двумя способами. Для магазинного автомата M язык T(M), допускаемый при помощи заключительного состояния, определяется как
T (M) = {x| x: (q0, Z0) (q, г) для некоторых гГ и qF}. (2.16)
С другой стороны, язык N(M), допускаемый M при пустом магазине, определяется как
N (M) = {x| x: (q0, Z0) (q, л) для некоторого qQ}. (2.17)
Если язык допускается автоматом при пустом магазине, то множество заключительных состояний автомата M не используется. В этом случае обычно принимается F = O.
Языки, допускаемые магазинными автоматами при пустом магазине, являются бесконтекстными [4].
Машины Тьюринга.
Машина Тьюринга - шестёрка T = (У, Q, Г, д, q0, F), где Q - конечное множество состояний, Г - конечное множество символов на входе, один из которых - пустой символ B. В начале работы n крайних левых полей на входе машины содержат символы входной цепочки (n - конечное число). Оставшееся бесконечное число полей заполнено специальным символом B - символом «пустое место», который не является входным.
Подмножество УГ, не содержащее B, составляет множество входных символов, д - отображение Q?Г в Q?(Г-{B})?{L,R} (оно может быть не определено для некоторых аргументов), q0Q - начальное состояние, FQ - множество заключительных состояний.
Разница между машиной Тьюринга и конечным автоматом состоит в том, что машина Тьюринга может изменять содержимое полей на входе при помощи своей читающей-пишущей головки.
Ситуация машины Тьюринга задаётся тройкой (q, б, i), где qQ, б(Г-{B})* - непустая часть ленты, i - расстояние читающей-пишущей головки от левого конца б. Пусть (q, A1A2…An, i), 1 ? i ? n+1 - ситуация машины Тьюринга. Если д(q, Ai) = (p, x, R), 1 ? i ? n, то движение T, под которым понимается элементарное действие машины, может быть записано как
(q, A1A2…An, i) (p, A1A2...Ai-1XAi+1…An, i+1). (2.18)
Это означает, что машина Тьюринга записывает в i-ю клетку символ X и сдвигает головку на одно поле вправо. Если же д (q, Ai) = (p, X, L), 2?i?n, то
(q, A1A2…An, i) (p, A1A2...Ai-1XAi+1…An, i-1). (2.19)
В этом случае машина Тьюринга записывает символ X в i-ю клетку и сдвигает головку на одно поле влево, но не левее левого конца ленты. Если i=n+1, то машина считывает пустой символ B. Если д (q, B) = (p, X, R), то
(q, A1A2…An, n+1) (p, A1A2,…An, X, n+2). (2.20)
Если же, наоборот, д (q, B) = (p, X, L), то
(q, A1A2…An, n+1) (p, A1A2, …An, X, n). (2.21)
В случае, когда две ситуации машины Тьюринга связаны между собой некоторым конечным числом элементарных действий, будет использоваться обозначение.
Язык, допускаемый машиной Тьюринга, определяется как множество
{x| xУ* и (q0, x, 1) (q, б, i) для некоторых qF, бУ* и i} (2.22)
Считается, что машина T, допускающая язык L, останавливается на каждом допустимом входе (т.е., допустив цепочку, машина прекращает работу). С другой стороны, возможно, что машина T не остановится, если входная цепочка не принадлежит языку L.
Недетерминированная машина Тьюринга - это такая машина, у которой д - отображение Q?Г во множество подмножеств множества Q?(Г-{B})?{L, R}. Можно показать, что если язык L допускается недетерминированной машиной Тьюринга T1, то L допускается и некоторой недетерминированной машиной Тьюринга T2.
Линейно ограниченный автомат.
Линейно ограниченным автоматом M называется шестёрка M = (У, Q, Г, д, q0, F), где Q - конечное множество состояний, Г - конечное множество входных символов, УГ - множество входных символов, д - отображение Q?Г во множество подмножеств Q?Г?{L, R}, q0Q - начальное состояние, FQ - множество заключительных состояний. Множество У содержит два специальных символа, обозначаемых обычно O и $, которые отмечают соответственно левый и правый концы цепочки. Их функция - не дать считывающему устройству уйти с той части цепочки, на которой задан вход.
Из определения следует, что линейный ограниченный автомат есть, в сущности, недетерминированная машина Тьюринга, которая никогда не сдвигается с той части входной ленты, на которой задан вход [4]. Ситуация линейно ограниченного автомата и связь между двумя ситуациями определяются так же, как и для машины Тьюринга. Язык, допускаемый линейным ограниченным автоматом, есть множество
{x|x(У-{O, $})* и (q0Ox$, 1)(q, б, i)
для некоторых qF, бГ* и i}. (2.23)
Если для любого qQ и AГ отображение д(q, A) содержит не более одного элемента, то линейно ограниченный автомат называют детерминированным.
Линейно ограниченные автоматы допускают языки непосредственно составляющих, и только их.
1.5.4 Модификации грамматик
Известно, что бесконтекстные грамматики не являются достаточно мощным средством для описания естественных языков или языков программирования. С другой стороны, языки непосредственно составляющих (но не бесконтекстные) требуют весьма сложного синтаксического анализа. Компромисс достигается путём введения различных обобщений бесконтекстных грамматик. Такими обобщениями являются программные и индексные грамматики [4].
Программные грамматики.
Программные грамматики отличаются тем, что после применения правила подстановки к некоторой промежуточной цепочке выбор следующего правила подстановки ограничен. Каждое правило подстановки состоит из метки, ядра и двух связанных с ядром списков перехода. Если правило можно применить к цепочке, полученной в процессе вывода, то следующее правило выбирается из первого списка (списка переходов при успехе). В противном случае следующее правило выбирается из второго списка (списка переходов при неудаче).
Программной грамматикой Gp называется пятёрка (VN, VT, J, P, S), где VN, VT и P - конечные множества вспомогательных символов, основных символов и правил вывода соответственно, S - начальный символ, SVN, J - множество меток правил подстановки.
Правило вывода из P имеет вид
(r) б>в S(U) F(W). (2.24)
Правило подстановки б>в называется ядром. Здесь бV*VNV и вV*; r - метка (обычно номер правила); U - список переходов при успехе, W - список переходов при неудаче, U, WJ.
Программная грамматика действует следующим образом. Сначала применяется правило с меткой (1). Если делается попытка применить правило (r), чтобы заменить подцепочку б, и выведенная перед этим цепочка содержит б, то применяется правило (r) б>в, и следующее правило выбирается из правил, метки которых содержатся в списке переходов при успехе U. Если выведенная цепочка не содержит б, то правило (r) не используется, а следующее правило выбирается из тех, метки которых содержатся в списке переходов при неудаче W. В случае, когда ядра всех выводов имеют бесконтекстную форму (т.е. A>в), грамматика называется бесконтекстной программной. Аналогично, когда ядра правил имеют регулярный вид или вид правил непосредственно составляющих, грамматика называется регулярной программной или программной грамматикой непосредственно составляющих. Показано, что язык, порождённый бесконтекстной программной грамматикой, может быть языком непосредственно составляющих. Более того, показано, что класс языков, порождённых бесконтекстными программными грамматиками, включает все бесконтекстные языки.
Индексные грамматики.
Это обобщение получается при введении в грамматику нового конечного множества - множества индексов. Грубо говоря, за вспомогательным символом в цепочке могут следовать произвольные списки индексов. Если вспомогательный символ со следующими за ним индексами заменяется одним или несколькими вспомогательными символами, индексы будут следовать за всеми вновь порождёнными вспомогательными символами. Если вспомогательный символ заменяется основным, индексы пропадают.
Индексной грамматикой называется пятёрка Gi = (VN, VT, F, P, S), где VN, VT, F и P - конечные множества вспомогательных символов, основных символов, индексов и правил подстановки соответственно, SVN - начальный символ. Каждый символ из F - это конечное множество специальных (индексных) правил подстановки вида A>б, где A VN и бV*. Правила подстановки из P имеют вид A>X1ш1X2ш2… Xmшm, где X1, X2, …, XmVNUVT, а ш1, ш2, …, шm лежат в F*. Если XiVT, то шi = л.
Определим отношение на цепочках множества (VNF*UVT)* следующим образом:
1. Если бAив - цепочка, в которой б и в(VNF*UVT)*, AVN, иF*, а A>X1ш1X2ш2… Xmшm - правило подстановки из P, в котором XiV, а шiF*, для всех i, то считаем, что
бAивбX1ц1X2ц2…Xmцmв. (2.25)
Здесь цi = л, если XiVT, и цi = шiи, если XiVN .
2. Если бAfив - цепочка, в которой б и в(VNF*UVT)*, AVN, fF и иF*, а A>X1ш1X2ш2… Xmшm - индексное правило из f, то
бAfивбX1ц1X2ц2…Xmцmв, (2.26)
где цi = л, если XiVT, и цi = и, если XiVN.
Показано, что класс индексных языков содержит все бесконтекстные языки как подкласс и является подклассом класса языков непосредственно составляющих. Более того, индексные грамматики достаточно мощны, чтобы обеспечить целый ряд не бесконтекстных свойств в алгоритмических языках.
1.5.5 Языки описания образов
Выбор непроизводных элементов.
Выше было сказано, что первый этап построения синтаксической модели образов состоит в определении множества непроизводных элементов, при помощи которых можно описать эти образы. Выбор непроизводных элементов существенно зависит от природы образов, специфики области применения и от характера доступных технологических средств. Обычно при этом выборе стараются выполнить следующие требования [4]:
1. Непроизводные элементы должны служить основными элементами образов и обеспечивать адекватное и сжатое описание исходных данных в терминах заданных структурных отношений.
2. Поскольку структурная информация в непроизводных элементах не важна, и они считаются простыми и компактными образами, их выделение и распознавание должны легко осуществляться существующими несинтаксическими методами.
Второе требование часто вступает в противоречие с первым, поскольку выбранные непроизводные элементы не всегда легко распознать при помощи несинтаксических методов. С другой стороны, в соответствии с этим требованием можно выбирать довольно сложные непроизводные элементы, лишь бы они были доступны распознаванию. Чем сложнее непроизводные элементы, тем проще могут быть структурные описания, т.е. они могут укладываться в рамки простых грамматик. При реализации распознающей системы достижение компромисса между указанными требованиями может стать весьма важной задачей.
Методы выделения непроизводных элементов можно разделить на две группы. В одной из них упор делается на границы, а во второй - на области изображения.
Выделение непроизводных элементов на границах и остовах.
Множество непроизводных элементов, которые обычно используют для описания границ и остовов, получают по схеме цепного кодирования. На двумерное изображение накладывают прямоугольную сетку, и узлы сетки, которые наиболее близки к точкам изображения, соединяют отрезками прямых. Каждому такому отрезку в соответствии с его наклоном присваивают восьмеричное число. Таким образом, изображение представляется цепью (последовательностью) или цепями восьмеричных чисел. Эта дескриптивная схема обладает рядом полезных свойств. Например, поворот изображения на угол, кратный 45?, сводится к прибавлению восьмеричного числа (сложение по модулю 8) к каждому числу цепочки. Конечно, при этом изображение может исказиться. Только поворот на угол, кратный 90?, никогда не приводит к искажению изображения. Легко выполняются и некоторые другие простые манипуляции с изображением, такие, как растяжение, изменение длины кривой, определение самопересечений. Изменяя шаг сетки, накладываемой на изображение, можно получить любое желаемое разрешение [4]. Этот метод не ограничен изображениями с односвязными замкнутыми изображениями. Его можно применять для описания произвольных двумерных фигур, составленных из прямых и кривых линий и отрезков. На рис.10 показано множество непроизводных элементов и кодовая цепочка 66767011221222, которая описывает кривую.
- 4 -
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Непроизводные элементы из областей.
Второй способ выделения непроизводных элементов - кодирование геометрических образов, которые строятся из областей. Основными непроизводными элементами служат полупространства образов (поля наблюдения). Можно показать, что любая фигура аппроксимируется произвольным многоугольником, который, в свою очередь, можно представить как объединение конечного числа выпуклых многоугольников. Каждый выпуклый многоугольник можно представить в виде пересечения конечного числа полуплоскостей. Если подходящим образом задать последовательность выпуклых многоугольников, составляющих произвольный многоугольник, то можно однозначно определить минимальное множество в некотором смысле множеств, объединение которых даст исходную фигуру. По аналогии с лингвистикой фигура - это «предложение», составляющие её выпуклые многоугольники - «слова», а полуплоскости - «буквы» [4].
Следующий после выделения непроизводных элементов этап состоит в построении грамматики (грамматик), порождающей язык (языки) для описания исследуемых образов. В лучшем случае было бы хорошо иметь систему восстановления грамматики, которая способна строить грамматику по множеству цепочек, описывающих эти образы. К сожалению, такую систему можно построить для некоторых весьма специальных случаев. В большинстве случаев проектировщик при построении грамматики основывается на доступных априорных знаниях и своём опыте.
Использование семантической информации.
Для выделения непроизводного элемента требуется некоторое множество признаков. Непроизводные элементы с разными величинами могут быть описаны величинами признаков. Это множество признаков можно рассматривать как семантическую информацию о непроизводных элементах. Каждый признак можно выразить набором чисел или логических предикатов.
Начальное описание T(x) образа x можно определить выражением
T(x) = (Ts(x), Tv(x)), (2.27)
где Ts(x) - задание непроизводных элементов образа x и их взаимных отношений, а Tv(x) - значение признаков для каждого элемента. Структурная информация об образе x задаётся синтаксическим или иерархическим описанием
H(x) = (Hs(x), Hv(x)), (2.28)
где Hs(x) - синтаксическая компонента, состоящая из множества необходимых для порождения Ts(x) правил подстановки, а Hv(x) - выполнимость интерпретационного правила, соответствующего каждому правилу подстановки грамматики G, которое используется при грамматическом разборе выражения Ts(б). Таким образом, полное описание образа x определено выражением
(T(x), H(x)) = ((Ts(x), Tv(x)), (Hs(x), Hv(x))). (2.29)
Класс образов может быть описан ассоциативной семантической информацией и грамматикой G, такой, что для любого образа x из этого класса Ts (x)L (G). «Смысл» образа выражен как начальным, так и синтаксическим описанием.
Все признаки разделяются на две группы: унаследованные и синтезированные [4]. Унаследованные признаки касаются тех аспектов смысла, которые определяются контекстом фразы, а синтезированные связаны с самой фразой.
Принципиально для определения смысла цепочки в бесконтекстном языке достаточно одних синтезированных признаков. Однако включение унаследованных признаков часто приводит к существенным упрощениям в оценке признаков.
Семантические правила добавляются к бесконтекстной грамматике следующим образом. Каждому символу X(VN U VT) приписано конечное множество A (X) признаков. Оно разделено на два непересекающихся множества синтезированных A0(X) и унаследованных A1(X) признаков. Требуется, чтобы A1(S)=O и A0(X) = O при XVT. Каждый признак бA(X) имеет множество возможных значений Dб, из которого при появлении символа X в дереве синтаксического анализа может быть выбрано одно значение. Пусть множество P состоит из m правил подстановки, и пусть k-е правило имеет вид
Xk0 > Xk1, Xk2, …, Xknk, (2.30)
где Xk0VN, n ? 0, и Xkj(VN U VT), 1 ? j ? nk. Семантическими правилами называются функции fkjб, определённые для всех 1 ? k ? m, 0 ? j ?nk, причём бA0 (Xkj) при j = 0 и бA1 (Xkj) при j > 0. Каждая такая функция - это отображение прямого произведения Dб1?Dб2?…?Dбt во множество Dб для некоторого t = t (k, j, б) ? 0, где каждое бi = бi (k, j, б), 1 ? i ? t, - это признак некоторого символа Xkli для 0 ? li ? nk. Иными словами, каждое семантическое правило переводит определённые признаки символов Xk0, …, Xknk в величину некоторого признака Xkj.
Приписывание семантики цепочкам бесконтекстного языка при помощи семантических правил осуществляется следующим образом. Для любой основной цепочки x нужно обычным образом построить дерево её вывода из начального символа S. Корнем этого дерева является символ S, а вершина, соответствующая применению k-го правила подстановки, является либо основным, либо вспомогательным символом xk0. Пусть X - символ какой-либо вершины этого дерева, а бA (X) - признак этого символа. Если бA0 (X), то X = Xk0 для некоторого k, а если бA1 (X), то X = Xkj для некоторых j и k, 1?j?nk. По определению, признак б имеет величину v для данной вершины, если в соответствующем семантическом правиле
fkjб: Dб1?Dб2?…?Dбt > Dб (2.31)
все признаки имеют величины v1, …, vt для соответствующих вершин, помеченных символами Xkl1, …,Xklt, и v = fkjб (v1, …, vt). Этот процесс оценки признаков нужно проводить по всему дереву до тех пор, пока он не закончится естественным образом [4]. Полученные на этой стадии оценки признаков и являются «смыслом», соответствующим данному выводу.
1.6.6 Синтаксический анализ как распознающая процедура
После того, как построена грамматика, порождающая язык для описания рассматриваемого образа, необходимо построить устройство, распознающее объекты представленные цепочками, порождёнными этой грамматикой. Прямой подход к решению этой задачи состоит в создании отдельной грамматики для каждого класса объектов. Распознающее устройство для данной грамматики будет выделять только те объекты, которые принадлежат соответствующему этой грамматике классу. Например, для m классов объектов C1, C2, …, Cm можно построить m соответствующих грамматик G1, G2, …, Gm, таких, что цепочки, порождённые грамматикой Gi, будут представлять объекты из класса Ci. [4] Тогда для произвольного объекта, описываемого цепочкой x, проблема распознавания сводится к вопросу: верно ли, что
xL (Gi) для i = 1, …, m? (2.32)
Процесс, приводящий к ответу на этот вопрос для одной заданной грамматики, обычно называют «синтаксическим анализом» или «грамматическим разбором». Этот процесс, кроме ответа на вопрос - «да» или «нет», может также давать дерево вывода, т.е. информацию о структуре соответствующего объекта. Блок-схема распознающего алгоритма приведена на рисунке 9.
- 4 -
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Будем считать, что если объекты представляются единственным образом, то среди ответов на вопросы «верно ли, что xL (Gi) для i = 1, …, m?» может быть один только один положительный ответ, а все остальные - отрицательными. При ответе «xL (Gj)» считается, что x принадлежит классу Cj. Если же все ответы отрицательны, то считается, что x не принадлежит ни одному из классов.
Простой способ распознавания состоит в сопоставлении входной цепочки с прототипом или эталоном каждого класса. Эталонная цепочка задаётся в терминах непроизводных элементов. Сопоставление непроизводных элементов может осуществляться параллельно или последовательно. Цепочка x относится к тому классу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с x. В этом случае требуется либо точное совпадение x с эталоном, либо выполнение подходящего критерия согласования. Конечно, не менее важен и выбор эталонных цепочек [4]. Этот подход, хотя и выглядит менее гибким, может быть реализован быстродействующей программой. Однако в действительности иерархическая структурная информация используется недостаточно, и этот подход полезен только тогда, можно определить соответствующие эталонные цепочки и имеющий смысл критерий согласования.
Если грамматика Gi регулярна, то можно построить детерминированный конечный автомат для распознавания цепочек, порождённых Gi. Если Gi - бесконтекстная или программная грамматика, то обычно требуется недетерминированный автомат. В процессе распознавания используется, вообще говоря, некоторая недетерминированная процедура. Задача синтаксического анализа может быть поставлена следующим образом: для заданного предложения x и грамматики G построить треугольник
S
x
и попытаться заполнить его внутреннюю часть деревом вывода x, правильным для грамматики G [4]. Если попытка успешна, то xL (G), в противном случае xL (G). В принципе не важно, как мы пытаемся заполнить треугольник. Это можно делать, начиная с корня дерева (грамматический разбор сверху вниз) или снизу к вершине (разбор снизу вверх). Оба способа называются разборами слева направо, так как там, где это возможно, символы в предложении обрабатываются слева направо. Какой бы способ не использовался, отдельные шаги состоят из попыток найти правило подстановки, подходящее для рассматриваемого участка предложения. Тот факт, что приходится делать пробные попытки, которые впоследствии оказываются ошибочными, делает синтаксический анализ, вообще говоря, неэффективной процедурой. Правило подстановки выбирается только в том случае, если оно удовлетворяет некоторым априорным тестам. Например, выбираются только такие правила подстановки, которые подходят только для данного участка цепочки. Априорные тесты могут быть и более сложными. Правило подстановки может отбрасываться из-за того, что его применение приводит к большему количеству основных символов, чем содержится в исходной цепочке, либо к появлению основного символа, которого в цепочке нет. Быстрота синтаксического анализа зависит от того, насколько удаётся избежать ошибочных проб, которые и приводят к лишним затратам времени. Если порядок выбора шагов и априорные тесты таковы, что на каждом шаге применимо только одно правило подстановки, метод синтаксического анализа не может быть существенно улучшен (при условии, что проверка априорных тестов не слишком длинна). Однако если на каждом шаге есть несколько возможностей, то общее число возможных грамматических разборов растёт экспоненциально. Поэтому выбор априорных тестов и порядок действий становятся чрезвычайно важными [4].
Грамматический разбор сверху вниз.
Синтаксический анализ сверху вниз начинается с символа S, обозначающего всё предложение, и состоит из последовательных пробных подстановок правил, которые порождают подходящие для этого предложения вспомогательные символы. Чистый синтаксический анализ сверху вниз - полностью целенаправленный процесс. Главной целью является вывод из S данного предложения x. Делается предположение, что анализируемая цепочка действительно есть предложение в языке данной грамматики G. Поэтому первый шаг - выяснить, можно ли свести цепочку к правой части некоторого правила подстановки
S>X1X2…XN. (2.33)
Это выясняется следующим образом. Применение данного правила подстановки в случае, когда X1 - основной символ, возможно, если цепочка начинается с этого символа. Если же X1 - вспомогательный символ, ставится подзадача: определить, можно ли какое-либо начало цепочки свести к X1. Если это оказывается возможным, таким же образом проверяется X2, затем X3 и т.д. Если для некоторого Xi не удаётся найти подходящего места в выводе цепочки, то надо попробовать применить другое правило подстановки.
Точно также решаются подзадачи для всех AVN, проверяется применимость правила подстановки A>X1X2…Xl и ставится и решается новая подзадача. Если подзадачу решить не удаётся, то на предыдущем уровне надо попытаться применить другое правило.
При анализе слева направо и сверху вниз иногда вызывает затруднение повторение слева вспомогательного символа: правила подстановки вида A1>A1б могут приводить к бесконечным петлям при анализе. Это происходит, когда сведение части цепочки к символу A1 ставится как подзадача, и первым шагом в её решении оказывается решение той же задачи, т.е. сведение части цепочки к A1. Проблема повторения слева иногда решается путём какого-либо преобразования грамматики или изменения порядка разбора. Большую роль здесь также может сыграть порядок, в котором проверяются различные правые части правил подстановки при одной и той же левой части. Если только одна правая часть содержит повторение слева, то она должна проверяться в последнюю очередь. Однако такая последовательность действий может вступать в противоречие с другими условиями на порядок проверки, например, с требованием, что кратчайшая правая часть проверяется последней.
Грамматический разбор снизу вверх.
В отличие от метода разбора сверху вниз, где символ предложения S развёртывается в заданное предложение при помощи последовательных правил подстановки, при разборе снизу вверх применяют инверсии правил подстановки с тем, чтобы свернуть предложение до начального символа грамматики. Другими словами, в цепочке отыскиваются подцепочки, совпадающие с правыми частями правил подстановки, затем они заменяются на соответствующие левые части.
Легко видеть, что при грамматическом разборе снизу вверх не существует проблемы повторений слева. В общем случае используются два различных метода для обхода тупиков, возникающих при грамматическом разборе. Первый метод - возвращение к тому моменту, с которого можно начать другой вариант синтаксического анализа. Этот метод требует восстановления цепочки в прежней форме или уничтожения некоторых связей, появившихся в дереве вывода. Второй метод заключается в параллельном выполнении всех возможных грамматических разборов предложения. Некоторые из этих вариантов разбора отбрасываются, поскольку их не удаётся закончить. На практике, однако, многие алгоритмы анализа можно усовершенствовать настолько, что при определённых ограничениях на вид грамматики ни возвращения, ни параллельное выполнение разборов не нужны.
Сравнение различных методов синтаксического анализа трудно по следующим причинам. Во-первых, эффективность разбора зависит от вида грамматики: для одних грамматик предложения быстрее разбираются методом снизу вверх, а для других - методом сверху вниз. Во-вторых, если оказалось, что какой-либо метод синтаксического анализа не эффективен для некоторой грамматики, то можно построить её изменённый вариант, для которого этот метод эффективен. Большинство алгоритмов, дающих все грамматические разборы, основано на методе разбора сверху вниз. Однако алгоритмы узкого назначения для грамматик специального вида основано на методе снизу вверх. Алгоритмы синтаксического анализа, работающие по методу сверху вниз, применимы к более широкому классу грамматик, но менее эффективны. Показано, что для любой грамматики существует эквивалентная ей грамматика, такая, что для неё разбор предложения методом сверху вниз проводится ненамного медленнее, чем разбор снизу вверх для исходной грамматики.
LR (k)-грамматики.
При грамматическом разборе слева направо и снизу вверх обычно на каждом шаге есть несколько подцепочек, которые можно заменить вспомогательными символами. Поэтому часто приходится перебирать большое количество вариантов. Для некоторых классов грамматик процесс перебора осуществим при помощи простой и детерминированной процедуры [4].
Один из таких классов называется классом LR (k)-грамматик. Запись LR(k) означает, что при грамматическом разборе слева направо и снизу вверх достаточен просмотр цепочки вперёд на k символов. Неформально будем относить бесконтекстную грамматику G = (VN, VT, P, S) к LR (k)-грамматикам, если для любой выводимой цепочки s верно следующее: s единственным способом записывается в виде вгд, так что существует единственный правый вывод S*вAдвгд, причём A заменено на г на последнем шаге вывода, и если, кроме того, A и г определяются однозначно при просмотре цепочки s слева направо не более, чем на k символов после г. Если часть этих k символов расположена правее конца цепочки, то будем считать, что цепочка s выводима из S$k, где $VN.
Подобные документы
Основные понятия теории распознавания образов и ее значение. Сущность математической теории распознавания образов. Основные задачи, возникающие при разработке систем распознавания образов. Классификация систем распознавания образов реального времени.
курсовая работа [462,2 K], добавлен 15.01.2014Оптико-электронная система идентификации объектов подвижного состава железнодорожного транспорта. Автоматический комплекс распознавания автомобильных номеров. Принципы и этапы работы систем оптического распознавания. Особенности реализации алгоритмов.
дипломная работа [887,3 K], добавлен 26.11.2013Распознавание образов - задача идентификации объекта или определения его свойств по его изображению или аудиозаписи. История теоретических и технических изменений в данной области. Методы и принципы, применяемые в вычислительной технике для распознавания.
реферат [413,6 K], добавлен 10.04.2010Появление технических систем автоматического распознавания. Человек как элемент или звено сложных автоматических систем. Возможности автоматических распознающих устройств. Этапы создания системы распознавания образов. Процессы измерения и кодирования.
презентация [523,7 K], добавлен 14.08.2013Понятие системы распознавания образов. Классификация систем распознавания. Разработка системы распознавания формы микрообъектов. Алгоритм для создания системы распознавания микрообъектов на кристаллограмме, особенности его реализации в программной среде.
курсовая работа [16,2 M], добавлен 21.06.2014Теоретические основы распознавания образов. Функциональная схема системы распознавания. Применение байесовских методов при решении задачи распознавания образов. Байесовская сегментация изображений. Модель TAN при решении задачи классификации образов.
дипломная работа [1019,9 K], добавлен 13.10.2017Обзор задач, возникающих при разработке систем распознавания образов. Обучаемые классификаторы образов. Алгоритм персептрона и его модификации. Создание программы, предназначенной для классификации образов методом наименьшей среднеквадратической ошибки.
курсовая работа [645,2 K], добавлен 05.04.2015Методы распознавания образов (классификаторы): байесовский, линейный, метод потенциальных функций. Разработка программы распознавания человека по его фотографиям. Примеры работы классификаторов, экспериментальные результаты о точности работы методов.
курсовая работа [2,7 M], добавлен 15.08.2011Выбор типа и структуры нейронной сети. Подбор метода распознавания, структурная схема сети Хопфилда. Обучение системы распознавания образов. Особенности работы с программой, ее достоинства и недостатки. Описание интерфейса пользователя и экранных форм.
курсовая работа [3,0 M], добавлен 14.11.2013Описание структурной схемы искусственного нейрона. Характеристика искусственной нейронной сети как математической модели и устройств параллельных вычислений на основе микропроцессоров. Применение нейронной сети для распознавания образов и сжатия данных.
презентация [387,5 K], добавлен 11.12.2015
