Частоты символов объединяющей цепочки
T
(
R
12
)
нового разбора
вычисляют
:
—
для элементов
,
соответствующих
i
-
му и
j
-
му столбцам разборов
R
1
и
R
2
:
p
=
n
1
p
1
i
+
n
2
p
2
j
n
1
+
n
2
;
—
для
i
-
го столбца разбора
R
1
,
которому не соответствует никакой
столбец разбора
R
2
;
—
для
j
-
го столбца разбора
R
2
,
которому не соответствует никакой
столбец разбора
R
1
:
p
=
n
2
p
2
j
n
1
+
n
2
.
В эталонное описание включаются собственные цепочки
e
Т
.
Процедура синтаксического анализа
.
Процедура синтаксического
анализа заключается в вычислении расстояния между контрольной це
-
почкой символов
Т
∗
и каждой эталонной цепочкой
e
T
i
,
i
= 1
, . . . , m
,
в
классе и нахождении по минимуму расстояния индекса класса
k
.
Для этого строится граф
G
(
e
T
i
, T
∗
)
.
Эталонная цепочка помещает
-
ся по горизонтали
,
а контрольная
—
по вертикали
,
количество узлов
вычисляется по формуле
(3).
Горизонтальным и вертикальным дугам
приписываются единичные веса
,
диагональным
—
нулевые
.
Путь из
истока в конечную вершину находится следующим образом
[12]:
—
граф поворачивается на
45
◦
вправо
(
рис
. 6);
—
узлы графа нумеруются от
0
до
q
−
1
слева направо и сверху вниз
;
—
граф дополняется мнимыми узлами с номером
−
1
и дугами
,
име
-
ющими максимальный вес
,
например
,
равный
99,9;
Рис
. 6.
Граф для цепочек
T
i
=
h
fbt
i
и
T
∗
=
h
ftb
i
—
узлы графа распределя
-
ются по уровням
,
число кото
-
рых определяется как
L
=
l
1
+
+
l
2
+ 1
,
где
l
1
и
l
2
—
коли
-
чество символов цепочек
T
∗
и
e
T
i
;
—
составляется список
предыдущих узлов и весов
предыдущих дуг
;
—
кратчайший путь нахо
-
дится за два прохода
.
В пря
-
мом направлении просматри
-
ваются узлы всех уровней от
0
до
L
−
1
,
и для каждого теку
-
щего узла находится преды
-
108 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
3
