ISR-7
June 1964.

VII-1

VII.

THE SENTENCE MATCHING PROGRAM - GRAPH
Edward H. Sussenguth, Jr.

1.

Introduction
A fundamental hypothesis of automatic document classificationis that the words of the document itself can be used to detect thesubject matter; words of particular significance are those which occur
frequently in a given text. Commonly occurring words, such as articles,
conjunctions, and prepositions, are normally Ignored, so that only certain
high frequency words are counted.

In addition, words may be normalized

by removing plural, adjective, and verb suffixes, so that variations ofa basic stem are grouped into the same class. Synonym dictionaries may
also be used to group words with similar meanings. After the normalizing
and counting processes, those word classes having the highest frequency ofoccurrence are considered indicative of the document content.
A refinement of this statistical procedure is to consider thewords taken in pairs or triples, not just individually. By so doing,
compound and refined concepts, which are not adequately described by individual words, can be detected; the procedure may then become sensitive tophrases such as "information retrieval11 and "data processing."

However,

if only adjacent word pairs were to be used as part of the phrase-counting
process, a large amount of relevant information would be lost, as may beseen by considering the following four sentences:

VII-2(1) Light radiation occurs above the critical temperature•(2) Kadiation of light occurs above the critical temperature.
(3) Radiation of light waves occurs above the criticaltemperature.
(U)

Under light radiation occurs above the criticaltemperature•

The first three sentences all express the idea that energy in the form oflight is emitted above a certain temperature. However, only in sentence(l) does the word pair "light radiation" occur explicitly. Moreover,although the pair "light radiation" occurs in sentence (U), that sentence
does not indicate that the radiation is in the form of light. What isimportant, then, is not the occurrence of the word pair "light radiation,11
but the fact that the word "radiation" is modified by the word "light."
To use this type of information, the sentence must be analyzed syntactically.
It has been demonstrated that it is possible to perform such an analysis
automatically, so that the syntactic relations between words can be used in
automatic document classification systems.
A tree is a convenient representation of syntactic relations between the words of a sentence. In the simplest form of the syntactic
dependency tree, the words of the sentence and the nodes of the tree are ina one-to-one correspondence, and if word x is dependent upon word y, there
is a branch (x,y) in the tree. The dependency trees for sentences (l), (2),(3) and (U) are shown in Fig. 1.

Although such dependency trees exhibit

the direct syntactic dependence of one word upon another, they do not showVII-3

Sentence(1)

Light radiation occurs above the critical temperature.

Sentence(2)

Radiation of light occurs above the critical temperature,Sentence(3)

Radiation of light waves occurs above the critical temperature

Sentence

Under light radiation occurs above the critical temperature.
Syntactic Dependency TreesFigure 1VII-4.
indirect relations explicitly. Indirect dependencies may be exhibitedin an "indirect dependency" tree, which is derived from the direct
dependency tree by adding branches (u,v) between each node u and allnodes v reachable from u. An example is shown in Fig. 2. Phrases andother combinations of words and modifiers are reflected in the tree
structures as subgraphs or partial subgraphs, and graph-matching
techniques may be used to detect the occurrence of specified phrases
within a syntactically analyzed sentence*In the previous example, thetree of the phrase "light radiation" (see Fig. 3) is a subgraph of thedirect dependency tree of sentence (l), and is a subgraph of theindirect dependency trees of sentences (2) and (3), but is not a fragmentof either dependency tree of sentence(u)•

As explained in previous sections, the statistical (wordcounting), semantic (synonym dictionary), and syntactic (grammaticaldependence) properties of the words of a text have all been incorporated
in the SMART system.

The theoretical implications of these properties

and the implementation of most of the properties on a digital computer
have been discussed in other sections of this report. The present section
contains a discussion of the implementation of the test to determine
whether or not a particular phrase is contained within a specific sentence.
There are three major parts to this test:(l) the syntactic analysis of

the sentence, (2) the representation of the analyzed sentence in a tree
form, and (3) the matching of a phrase (called a criterion tree) with thesentence tree. In the SMaRT system the syntactic analysis is performedby the program developed by Kuno and Oettinger, the construction of theVII-5DirectSyntacticDependencyTree

Radiation of light waves occurs above the critical temperature,

Indirect
Syntactic
Dependency
Tree

Radiation of light waves occurs above the critical temperature*r o l w o a t c tr
Radiationoflightwaves
occursaoove
thecriticaltemperature

Direct Connection Matrix

11
10

1
11w

10atct

1
1
1
1
1
1
1
1

1
1
1

1
1

Indirect Connection Matrix

Direct and Indirect Syntactic Dependency Trees
Figure 2

VII-6»I
light radiation
Query Phrase
Figure 3tree representation follows the outline given by Lemmon (see ref. 3 andSec. VI of this report) and the matching test is a modification of theL 5
structure-matching algorithm described by Sussenguth.

Some of thedetails of the modified structure-matching program are presented below.

2.

The GRAPH Structure-matching Program
GRAPHis a program for testing if criterion graph G is apartial subgraph of sentence graph S. The program is specificallytailored for testing trees which represent syntactically analyzed
English sentences. Figure U is a flow diagram of GRAPH.
The properties used to generate sets in box I of Fig. U are:node values - synonym class types
node values - grammatical typef-degree- direct connections

Familiarity with either ref. U or 5 is assumed.

VII•aCMonZQUJ

111 cr5 h^e> >_J! MAK
NOT REV<s@l
2<UJ a.

VII-8b-degree - direct connections
f-degree - indirect connections
b-degree - indirect connections.
In box IV the connectivity property is used:
kf -connections - direct connections
b*-connections - direct connections
kf -connections - indirect connectionsb^-connections - indirect connections.
The partitioning procedure (box II), the assignment process(boxes V, VI, X, and XII), and the method of family formation exactly
follow the descriptions given in ref. 4 (specifically, in Sees. 3»3Aand 3»3C, 3»4A, and 3«3E, respectively).

The graph transformations

which delete discarded nodes of S and pairs of corresponding nodes
from G and S from pairs of corresponding sets are included (see Sec. 3 0 Dof ref. 4 ) *The program is designed to accommodate sentence trees of up to144 nodes, and criterion trees of up to 36 nodes. The trees are enteredinto the program in the form of binary connection matrices (both directand indirect), and the values associated with the nodes are specified bya binary node value matrix. When the program terminates in either box IX(isomorphism) or box XI (no isomorphism), the correspondences which havebeen found between nodes are listed in a table called KNOWN. The formof this listing is given in Appendix A.

VII-9

GRAPH has been programmed for and tested on the IBM 7094• The
calling sequence for GRAPH is given in Appendix A of this section, andthe subroutines called by GRAPH are described in Appendix B.
A number of tests have been made with GRAPH. In most cases
the properties used to generate sets in box I were sufficient todelineate a one-to-one correspondence or to indicate that no isomorphism
is possible.

(In other words the most frequent path followed in the flow

diagram is the one from box I to II to either VII or XI.) For someexamples, it was necessary to use the connectivity property (box IV)
once, in order to delineate a one-to-one correspondence.

Only to resolve

multiple isomorphisms, reflecting a parallel construction in the sentence,
was it ever necessary to partition (box II) more than twice. In general
the computing time required by GRAPH is of the order of tens of milliseconds; an upper bound is one second.

VII-10APPENDIX APROGRAMMING DETAILS FOR GRAPH

1. Calling Sequence
GALL GRAPH, S, Cor:TSX

GRAPH, hTSX

STSX

C

TSX

*TSX

*

where:
S is address of data for sentence graph
C is address of data for criterion graph

2•

ReturnAccumulator = 1 if C is a partial subgraph of SAccumulator = 0 if C is not a partial subgraph of S
The correspondences which are determined by the process arelisted at location KNOWN.

VII-11Location

Criterion Node(Decrement)

Sentence Node(Address)

not used

KNOWN
KNOWN + 1a(/(a)

KNOWN + 2b*f(b)Ac)

KNOWN + k
Notes:

k is an integer (in location 77^56^) stating how many correspondences exist.

If an isomorphism is found, k = nj if

there is no isomorphism, 0 <k^n.

The order of the listing is determined by the order in which
the correspondences are found.

Data FormatA

number of nodes (n) in graph (in the decrement)

A+l

not used by GRAPH

A+2

number of rows (r) in value matrix (in the decrement)

A+3

value matrix

A+3+w-rindirect connection matrix

A+3+w*(r+n)

direct connection matrix

whereA is S or G
w is ceiling (n/36)•

VII-12

Miscellaneous
Tape Bl is used as a scratch tape.
10311g words are used for GRAPH and its associated subroutines.
Locations 3 H 0 2 g to 77461g of COMMON are used.
Running time is about one second.

APPENDIX BSUBROUTINES USED BY GRAPH

NameFunctionBKBAR

Performs the set operation A = B n C n D

CANDID

Computes those nodes of S which have not been deleted

CDEG

Computes f-degrees

CEL36

Computes ceiling (n/36)

IECVQI

Partitioning routine (see ref. U> Sees. 3*3A, 3*3C)

|FY J
FORM

Family formation routine (see ref. U> Sec. 3*3E)

FRST

Finds first 1 in a binary vector

GAL/MA

Computes f-connectivity of a set

ISIV

Tests if the ith bit of a binary vector is 0 or 1

LAST

Finds last 1 in a binary vector

ORFAM

Given sets A1,A2,...,A , the sets B-.,B2>
where Br= Ar

and B. = A. U B. ,iil+l

SETIF

Sets ith bit of a binary vector to 0

SETIN

Sets ith bit of a binary vector to 1

SIGVCounts number of l!s in one machine word

SIGVWCounts number of l's in w machine words

TRANS

Transposes a logical matrix,B

are computed

VII-13

REFERENCES

1. Salton, G#, "a Flexible Automatic System for the Organization,
Storage and Retrieval of Language Data (SMART)," Information
Storage and Retrieval, Report ISR-5 to the National Science
Foundation, The Computation Laboratory of Harvard University(January 1964.).
2.

Kuno, S., and Oettinger, A. G., "Multiple-path Syntactic Analyzer,"
Proc- of the IFIP Congress-62, Munich (1962).

3. Lemmon, A., "Automatic Identification of Phrases for Document
Classification," Information Storage and Retrieval, Report ISR-5
to the National Science Foundation, The Computation Laboratory ofHarvard University (January 1964.) .
U*Sussenguth, E. H., Jr., "Structure Matching in Information
Processing," Information Storage and Retrieval, Report ISR-6 tothe National Science Foundation, The Computation Laboratory ofHarvard University (April 1964.) .

5*Sussenguth, E. H., Jr., "Automatic Structure-Matching Procedures,"
Information Storage and Retrieval, Report ISR-5 to the National
Science Foundation, The Computation Laboratory of Harvard
University (January 1964).