Information Technology Reference
In-Depth Information
More details on canonical forms and the “local” or “simple” rules, which result
from them and restrict the possible extensions of a fragment, can be found in [1].
Of course, there are “local” or “simple” rules not only for breadth-first, but also
for depth-first (spanning tree traversal) code words, which specify a restricted set
of extensions known as
rightmost path extensions
. However, for the discussion
in this paper it su
ces to know that, regardless of the canonical form used,
the “local” or “simple” rules basically state that extensions that generated the
sibling nodes to the left of a search tree branch may not be done in this search
tree branch itself or in branches to the right of it.
11.5
Partial Perfect Extension Pruning
If one wants to combine perfect extension pruning with canonical form pruning
as it was described above, the following problem has to be solved: growing the
maximal common fragment can interfere with canonical form pruning and in
particular with the extension restrictions resulting from it (note that this was
no problem in [4] due to the use of a repository of found fragments to avoid
redundant search). Obviously, perfect extensions should not lead to such a re-
striction, because otherwise search results may be lost. The fact that the code
word of a fragment, as it is built by the search, is not canonical is no longer
sucient to prune it, since preferring perfect extensions may have changed the
order of the extensions by which a fragment is built.
As an example consider again the search tree shown in Figure 11.2. If we
simply confined the search to the sub-tree rooted at the fragment
S-C-N
,we
would lose the fragment
O-S-C-N
in the leftmost branch. The reason is that the
extension of
S-C
to
S-C-N
, due to canonical form restricted extensions, prevents
an extension of the sulfur atom in this sub-tree (as described in the preceding
section), because an atom with a higher number, namely the carbon atom, has
already been extended in the preceding step.
Fortunately, this only affects search tree branches to the left of the perfect ex-
tension branch, since the corresponding extensions are ruled out by the perfect
S
S
F
S
C
S
O
O
S
C
S
C
N
S
C
O
O
S
C
N
O
S
C
O
S
C
N
O
S
C
N
C
O
S
C
N
O
S
C
N
C
O
Fig. 11.6.
Search tree for the three molecules in Figure 11.1 with partial perfect
extension pruning (crossed out branches are pruned)
