Information Technology Reference
In-Depth Information
X
Z
(3.5, 3, 2)
Y
1.
K
L
(3, 3, 1)
(4, 3, 3)
E
(2, 2, 1)
F
(5, 2, 3)
v
1
v
10
(1, 1, 1)
(6, 1, 3)
(0, 0, 1)
(7, 0, 3)
X
Z
(3.5, 3, 2)
Y
K
M
N
(3.4, 2, 2)
L
2.
(3, 3, 1)
(4, 3, 3)
E
(2, 2, 1)
(
, , )
3.2 2
F
(5, 2, 3)
v
1
v
10
(1, 1, 1)
(6, 1, 3)
(0, 0, 1)
(7, 0, 3)
Z
(3.5, 3, 3)
Y
3.
K
M
(3.2, 2, 2)
N
(3.4, 2, 3)
L
(4, 3, 4)
E
(2, 2, 1)
F
(5, 2, 4)
v
1
v
10
(1, 1, 1)
(6, 1, 4)
(0, 0, 1)
(7, 0, 4)
Fig. 10.5.
Transcription of a transition to a lower level
Once the segment has only edges connecting it to other segments on a lower
level it is transformed into lower level entities by connecting each entity on the
left side with each entity on the right side with an
existPathTo
type of an edge
going from left to right. This is demonstrated in Figure 10.5 by a step number 2
and 3. The transformed segment and all its connecting edges to lower levels are
removed from the graph.
As for the transcription strategy during the transcription process, each vertex
in the transcription graph is assigned two important numbers which are kept
updated through the whole computation. The first number is the vertex's
order
from left
and the other one is a length of a shortest path between the start
vertex and this particular vertex. The left order number makes possible to have
the vertices sorted by their position in the transcription graph as the algorithm
processes its vertices strictly from left to right. Since the left order number is a
floating point number, every time the process needs to insert a vertex between
other two vertices there is always a gap between their left orders. Therefore,
the transcription graph forms a special type of a directed graph referred to as
anetwork
which is also a DAG. Since, vertices can be ordered by its left order
number and it is true that there is no edge pointing from a vertex with higher
left order to a vertex with a smaller left order.
The length of a shortest path from the start vertex is used to limit the weight
of segment sequences that are retrieved from the index to replace the path edges
in the transcription graph. It considers the length of an already computed piece
of path from the start vertex to the particular vertex. The segment sequences of
a maximal weight of a difference of the already computed piece of the result and
the maximal length of a desired path, our
l
, are retrieved and placed into the
