ISR-9August 1965
XII.

THE TREE MATCHING PROGRAM - MATCH
M. Razar

1*Introduction
In order to determine precisely what concepts are expressed bya given sentence, one must first know the exact interdependencies ofthe various words making up the sentence. For otherwise, one would beunable to group two or more words to generate a more complex concept thanthat expressed by either word alone. As an example of dependencies withina sentence, consider the following three typical sentences*(a) "Charged particles interact strongly."(b) "When charged, particles interact strongly."(c) "Particles with a charge interact strongly."
Clearly (a) and (c) are completely synonymous. That is, the concepts expressed by the phrases "charged particles" and "particles with a charge"
are identical. Note that the actual positions within the sentence of thewords "charged" and "particles" are irrelevant. What is important is theirsyntactic relation - that of an adjective modifying a noun. Conversely, anadjacent position tells one nothing. For in (b), although the phrase"charged particles" appears, there is no direct connection between the twowords.

The word "charged" is part of the adverbial phrase "when charged"

which modifies the verb "interact."
In order to display the syntactic relations of words in a sentence
conveniently, it is customary to write a sentence in tree form.
Fig. 1.)(SeeXII-2(a)CT

Chargedinteract

particlesstrongly.

(b)

When

chargedparticlesinteractstrongly.

interactstrongly.

(c)Particles

withcharge

Typical Sentence Trees
Figure 1XII-3

Once a sentence is in tree form, the various word-dependencies
become clear. Two nodes, A and B are directly dependent if a corresponding branch AB exists in the tree. They are indirectly dependent
if there is a path in the tree leading from A t o B .

Thus in Fig. 1(a)"charged particles" actually constitute a subtree while in (c) only anindirect dependency exists. In Fig. 1(b), there is no connection,direct or indirect, between the words "charged" and "particles.w

More-over, there may be many irrelevant nodes which are connected like "a"and "with" in Fig. 1(c). The point is that given a phrase like "chargedparticles," it is necessary to determine if it is included (directly orindirectly) in a given sentence. This task is performed by the subroutine MATCH.

2.

General Considerations
It was seen that a sentence can be put into tree form to exhibit

word-dependencies. Similarly, any phrase (for example, "chargedparticles") can be thought of as a tree. To determine whether thephrase is included in the sentence, it is sufficient to determine if thephrase tree is a subtree of the sentence tree. Mathematically, one would
like to set up an isomorphism from the phrase tree into the sentence tree.
The routine MATCH will find any such isomorphism, or determine that noneexists.
MATCH is designed to be primarily value-oriented rather thanstructure oriented. In SMART, one deals mainly with trees of simple

XII-4sentence structure for which only fairly simple dependencies exist.
However, the values attached to each node can be quite varied. Just
the opposite would be the case if one were dealing with the graphs
determined by the structures of organic chemical compounds. Then
extremely complex structures would occur but only a relatively few
values (e.g. carbon, hydrogen, oxygen, nitrogen) would be attached tothe nodes. Therefore, MATCH will first determine possible correspondences without structural isomorphism, and only then see if thestructure is correct.
In general, MATCH will take a tree in a form similar to thatof the tree in Fig. 2, and determine whether any correspondence ispossible with a tree referred to as SENT which is actually, (thoughnot necessarily) the tree generated by some sentence. The multiple2(d,e)

13(a,b,c)j•(f)

6 4(g>h), (i,j,g)

Sample of Labeled Tree
Figure 2

values at each node in Fig* 2 are called relation generators. The
totality* of associated relation generators attached to a given nodeis called a relation• More than one relation may be attached to anode and in order to have this node correspond to a node in SENTwith value x, x must be a relation generator of each relation
attached to the node. Thus the labeled tree in Figo 2 could correspond to any one of six trees. Node 1 must correspond to a nodewith value a or b or c; node 2 to a node with value d or ej node 3
to a node with value f; node 4 to a node with value go
The relation generators of a given relation can be thought ofas essentially synonymous words which are part of a common concept.
For example, one might not wish to distinguish among the phrases,"charged particles," "electrified particles/0 ucharged, bodies,85 and"electrified bodies©*

Therefore, one would construct a tree asfollowsi(particles^, bodies)(chargedielectrified)
In practice, of course, all words are represented by (binary) numbers
and this makes possible quite convenient representation of all therelations in a tree* This representation is performed with the helpof a vector EELN, each word of which contains a relation generator anda node number as followss

XII-6

S

DECREMENTTAG

ADDRESS+VALUE OF RELATION GENERATOR

0NODE NUMBER

The sign bit determines the position of a relation generator
within a relation.

In particular, the generators of a given relation

are stored in adjacent positions (see Fig* 3) within RELN^ a plus sign
being used to indicate that a generator is the last of its relation
and a minus sign to indicate that it is not.

cdefg
hig

T

A

0000000000

1
1
1
22
3
KA0A

A
A

Vector RELN for Tree of Figure 2Figure 3
In the last few paragraphs, the storage format for the values
attached to a node was described. The structure of the tree is evensimpler to determine. A vector TPAR is set up so that TPAR(n) contains
the parent of node n in its decrement. If the sign of TPAR(n) is plus,

XII
the corresponding parent is a direct parent and only correspondenceswith direct dependencies will be considered.
indirect dependencies are also considered*If the sign is minus,

As an example, consider

the tree:1^Particles

2^(JCharged
The decrement of TPAR(2) contains 1, indicating that node 1 is theparent of node 2.

If the sign is plus, only direct dependencies arepossible matches and this form corresponds to a subtree of the treein Fig. 1(a) but to no subtree of the tree in Fig. 1(c). With aminus sign in TPAR(2) however, indirect dependencies would be permitted and a match would also be obtained with the tree in Fig. 1(c).
The node values and tree structure of the phrase tree which
is being matched into a sentence constitutes half the informationneeded by MATCH. The other half obviously pertains to the sentencetree into which the phrase tree is being matched*

The information

about the sentence tree structure is very simply stored in a vector
SPAR. SPAR(n) contains the parent of node n in its decrement andno other information. A somewhat useful fact is that the vector
SPAR is arranged so that SPAR(n) < n for all nodes n.
The values attached to the sentence nodes are determined
quite indirectly from a table to be described below. For eachXII-8
possible value under consideration, four words of core are set aside•
The first, VALU, contains the actual value representing an English
word which may appear in a sentence. The other three, VEC1, VEC2 andVEC3 are considered as a single 108-bit logical word referred to hereafter as VEC* The bits are consecutively numbered from 1 to 108 anda 1-bit in position n indicates that node n in the sentence tree has
the value contained in VALU. A zero in bit position n indicates thatnode n has a value other than that in VALU. Note that this limits thesize of the sentence to 108 words, which in practice is no real
limitation.
The motivation behind this format is that one can determine
all possible correspondents of a given node in the phrase tree asfollows. Form a 108-bit word for each relation attached to the nodeby or-ing together the respective contents of VEC corresponding to eachrelation generator. When this is done for each relation attached to
the node, the results are "and-ed" together to give a 108-bit logicalword PCORR with 1-bits in those and only those positions which correspond to sentence nodes whose values make them possible correspondentsof the phrase node in question. Thus if the value attached to nodes 6
and 10 in a sentence is "charged" while the value "electrified" isattached to node 19> then a node in the phrase tree having the single
relation ("charged," "electrified") attached to it will generate aword PCORR with 1-bits in positions 6, 10 and 19.

XII-9The algorithm used by MATCH is fairly simple and is separated
into two distinct parts. The first part has already been discussed
extensively above• We determine, for each node in the phrase tree,
all possible nodes in the sentence tree to which it could correspond•
If any node in the phrase-tree can correspond to no node in thesentence, then clearly no match is possible and the subroutine MATCH
returns this information. If every node has possible correspondents
in the sentence, the second part of MATCH is activated to consider
structural constraints. We choose the node with the fewest possible
correspondents and tentatively assign to it one of its possible correspondents in the sentence tree. (This assigned node in the sentence isreferred to as its image or correspondent.)

The structural constraints

can then be checked by seeing if the parent of the correspondent is acorrespondent of the parent of the node under consideration.

If it is,and if the parent of the node has not yet been tentatively assigned tosomething else, one of the remaining possible correspondents of theparent is assigned to it. This procedure is repeated until all nodesof the phrase tree are assigned images in such a way that the image ofTPAR(n) is always equal to SPAR(image of n) or until all possibilities
of such an assignment are exhausted. A more detailed description ofthe algorithm is found in the flowcharts which are appended to thisreport•

XII-103*

Calling Sequence for MATCH; Returning from MATCH
The calling sequence to MATCH is quite simple. It reads:
CALL MATCH, SPAR, SENSIZ, TPAR, TRESIZ, RELN, REISIZ

where SPAR, TPAR and RELN are the FORTRAN names of each of thesepreviously described vectors. That is, the vectors SPAR, TPAR
and RELN are stored backwards in core so that SPAR(n) is in location SPAR-n; TPAR(n) is in TPAR-n; RELN(n) is in RELN-n. The
lengths of the vectors SPAR, TPAR and RELN are found in thedecrements of SENSIZ, TRESIZ, RELSIZ respectively as FORTRAN
type integers•
When a match is found, the actual correspondence iscommunicated to the main program in the following way. A vector
CjtfRESP of length TRESIZ is set up (as a Fortran array) in such away that CORESP(n) contains the sentence node corresponding tonode n of the phrase tree. This information is contained as adecrement integer in CORESP(n).

Clearly then, the relation

1 = CORESP(n) 3 SENSIZ = 108 must hold for all nodes n.
Once the array CORESP has been set up, MATCH returns theinformation by calling a subroutine HIT with a single argument,
CORESP (that is, CALL HIT, CORESP). Then MATCH proceeds as if it
had failed to find this last correspondence to find any otherpossible ways of mapping the phrase tree into the sentence tree»
When all possibilities for such full correspondences have been exhausted, irrespective of whether any matches at all have been found,
MATCH simply returns control to the main program.

XII-11APPENDIX A
ALGORITHM FOR DETERMINATION OF VALUE CONSTRAINTSON POSSIBLE MATCHESENTERVTCORRl = 0
TC0RR2 = 0
TCORR3 = 0
V

K = TRESIZ>\/PCORRIOt) = 0111111111111\
PC0RR2(iK) = 0111111111111]
PC0RR3(1i) = 01111111111111
K = K- 1*\DETERMINE THE SENTENCE NODES WHICH CANCORRESPOND TO THE RELATION GENERATOR RELN(L)BY MEANS OF A CALL TO XSERCH WHICH SCANS
THE VALU TABLE"ORM THESE INTO TCORR'lLAST GENERATOR OF ITS!RELATION IF +LN(L) ; ?J>-JL.
RELSI|>XJ = NODE TO WHICHRELN(L) IS ATTACHED.
(FOUND IN ADDRESS OF RELN(L))

JZ->1 L = L + IIv

T = TRESIZ"AND" TCORR INTO PCORR(J)NODE(T) = T
NCORR(T) = # OF 1-BITS
IN PCpRR(T)RETURNNO MATCH-^Flowchart 1T- 1

XII-12APPENDIX B
SORTING )6F N^DES IN ASCENDING $RDER 0PjeSBSIBLE CORRESPONDENTS

NUMBER # F

P = 1JLCHANGE = 01L

Q = TRESIZ
R = TRESIZ-1<^NCliRR(Q) : NCjgRR(R)^Q = Q - 1
R = R - 1

V
INTERCHANGE NC0RR(Q) AND NCj0RR(R).
INTERCHANGE NjdDE(Q) AND NODE(R)SET CHANGE ^ Q_^_CHANGE : 0)

Flowchart 2>\ 1 = 1 + 1

XII-13APPENDIX CALGORITHM FOR DETERMINATION OF STRUCTURAL CONSTRAINTSON POSSIBLE MATCHES

I = TRESIZN = NODE(I)LOOP( ) = i

M = LQQP(l)v
TEMP(M) = POSITION OF
MTH 1-BIT IN PCORR(N)FLAGT(N) = 1
IMAGE(N) = TEMP(M)
FLAGS(IMAGE(N)) = 1|N = TPAR(Nlj±[J = SPAR(IMAGE(N))|&/^UGS(J)>fj:IMAGE(TPAR(N)))/J^k_

IS THERE A 1-BIT IN
POSITION J OF PCORR(TPAR(N))
YES
\k

M_6

IMAGE(TPAR(N)) = J I
FLAGT(TPAR(N)) = 1 ;FLAGS ( J ) = 1[_ild^TPAR(TPARfN));

Q>\l/I ft1|K = TRESIZ^FLAGT(K)

jJL

^=H

RETURNMATCH0)-HK = K -I

XII-14APPENDIX C (continued)

VrTPAR(N) s_T)—-jk|j = SPAR(J)1JL

FLAGT(N) = o
FLAGS(IMAGE(N)) = 0
LQOP(I) = M+ lK( M :NCJ0RR(I)J

JLr+ 1

I =( I : TKESEp

i_Lje^P(l) = L ^ P ( I ) + 1
M = U60?(I)N = NjflDE(l)^_RETURN

Flowchart 3