Рис
. 4.
Сеть
,
соответствующая паре
цепочек
T
1
=
h
hthh
i
и
T
2
=
h
hhth
i
в сток сети
G
(
T
1
,
Т
2
)
,
порождает
цепочку элементарных трансфор
-
маций
,
переводящую
Т
1
в
T
2
.
При
этом движение по левой вертикаль
-
ной стороне клетки
(
i, j
)
означа
-
ет
,
что между последним символом
уже трансформированной части це
-
почки
Т
1
и первым символом еще
не трансформированной ее части
(
символом
,
стоящим в
Т
1
на
i
-
м ме
-
сте
)
вставляется символ
,
стоящий в
T
2
на
j
-
м месте
.
Движение по верх
-
ней горизонтальной стороне этой
клетки означает
,
что в
Т
1
требует
-
ся удалить символ
,
стоящий на
i
-
м
месте
.
Движение по горизонтали означает
,
что символ
,
стоящий в
T
1
на
i
-
м месте
,
остается в выстраиваемой цепочке без изменения
.
Зададим на множестве дуг сети
G
(
T
1
, T
2
)
систему весов
:
каждой
вертикальной и горизонтальной дуге припишем вес
1,
а каждой диа
-
гональной дуге припишем вес
0.
Длину пути
l
(
S
)
определим как сумму
весов всех дуг
,
лежащих на этом пути
.
В качестве меры сходства цепо
-
чек
Т
1
и
Т
2
примем минимальную из длин всех путей
,
принадлежащих
множеству
W
(
T
1
,
Т
2
)
:
r
(
T
1
, T
2
) = min
l
(
S
)
, S
∈
W
(
T
1
, T
2
)
.
(4)
Для нахождения кратчайшего пути из вершины
х
1
в вершину
x
q
можно использовать любой известный алгоритм
[11].
При составлении словаря исходной информацией является набор
цепочек символов
,
полученных в результате сегментации множества
экспериментальных кривых
.
Для выделения наиболее часто повторя
-
ющихся структурных комплексов необходимо осуществить последова
-
тельные трансформации одной цепочки в другую
.
Для этого строят раз
-
бор
R
,
который представляет собой прямоугольную таблицу из
n
строк
(
цепочек символов
)
и
k
столбцов
.
Каждая клетка столбца либо пуста
,
либо содержит один символ
,
причем символы в клетках одного столбца
—
это повторения одного символа
.
Текущая строка является последней
в разборе
.
Трансформации осуществляют согласно критерию
(4).
При
этом возможны некоторые вариации
.
Например
,
для массива из трех це
-
почек
{h
f bt
i
,
h
f tb
i
,
h
hf tb
i}
могут быть записаны два разбора
(
рис
. 5).
Цепочка
Т
(
R
)
,
образованная символами столбцов
,
называется объ
-
единяющей
.
Оценкой вероятности появления символа в столбце разбо
-
ра является частота
р
i
(
R
)
,
которая вычисляется следующим образом
:
104 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
3
