Digital Signal Processing Reference
In-Depth Information
Figure 5.8.
a) PathScore calculation: node and edge correspondence within the Path-
Score definition: Darkened nodes and edges corresponds to the two paths that give
the highest matching score. The dotted lines show which two edges were matched
together. b) Computational Dependencies for dynamic programming algorithm for
path comparison of two DAGs: The previous problems are represented by the crosses.
Note that all previous problem triangles are contained within the shaded area.
where
a
m
is the mth edge value in sequence A,
b
n
is the
n
th edge value
in sequence B,
A
m
=(
a
1
,
...
,a
m
) is subsequence of edge values from
the first to the
m
th from sequence A, and
B
n
=
(
b
1
,
...,
b
n
) is the sub-
sequence of edge values from the first to the
n
th from sequence B, λ is a
null edge, and the MatchEdge function relates the previous comparison
score of two subsequences to the next score after integrating the com-
parison of an edge from each sequence (see Figure 5.8). The formulation
of MatchEdge is further restricted to be monotonically decreasing with
respect to the previous score, i.e.,
a, b
:(
x
<
y
) →
MatchEdge
(
a,b,x
)<
MatchEdge
(
a,b,y
).
(5.3)
The selection of MatchEdge is up to designer, but should model the
matching probability and informational loss associated with comparing
the two edge values as the representations of macro-structures. A better
match between edge values can mean less of a decrease in score and a
perfect match can avoid any loss in score.
Search WWH ::
Custom Search