VI~2(1) Identification;(a)a unique serial number;(b)a "subject heading"(six alphabetic characters)

to indicate the subject which the tree embodies;(c)optionally, from one to three "output concept
numbers" to provide for nesting of phrases(as described below)-(2) Structural information consisting of two logical(binary) incidence matrices to indicate which syntactic
elements depend on which others* One of these matrices
indicates the direct connections between elements(hereafter called "nodes"), the other shows indirect(removed) connections•(3) Syntactic information;the syntactic function of each of

the nodes (elements) of a phrase*(U)

Semantic information:

the semantic values of the variousnodes.
(5)Internal control information, e»g., a count of the numberof nodes in the phrase*

The serial number serves only as an identifier whereby the editing
routine can determine which trees must be deleted*

The "output concept

number" does not appear in the output of the criterion routine* Rather, it
is used internally by the routine to indicate when one tree appears in asentence as a part of another (as for example, "information retrieval" isa part of "automatic information retrieval").

VI -3

Each phrase is considered to have one or more "key" nodes in which
the "meaning" of the phrase is concentrated*

This key node is usually thetop

e of the phrase:

the noun in a noun phrase, the verb in a clause,etc-

When a tree is found to match a given part of a sentence, the output

concept numbers for that tree are recorded as semantic values pertaining to
the sentence nodes which mate to individual tree nodes.

Thus, if the sentence

were "Automatic information retrieval is useful.", and 301 were an output
concept number attached to a tree in which the term "information" modifies
the term "retrieval," then the semantic value (concept number) 301 would
be attached to the term "retrieval*"
Because of the relative complexity of this specification, and because
the criterion trees are stored as binary records on magnetic tape (seeFig. 3 ) , an updating routine is required to create and maintain thecriterion tree dictionary*

Two routines, discussed in Sec. VIII ofInformation Storage and Retrieval, Report No. ISR-7, have been programmedto perform this task.

One, called UPCRIT, edits an existing file of trees:

the other, called MAKTRE, creates new tree records from alphabetic input*
Unfortunately, the original MAKTRE routine proved to be inadequate.
In the first place, the routine requires a rather involved procedure fordescribing the structure of trees, even though In fact only about
different types of trees have actually occurred in practice.

'U+

Secondly,, allsemantic information must be repeated anew for each tree, whereas practicalexperience reveals that the tree dictionary consists largely of groups of

VI-6generator which is equal to zero; this is illegal, as is a generator (orconcept number) greater than 3072.

A left parenthesis immediately fo»ome adby a right parenthesis is a valid format; but it defines a relation consisting of a single generator of value zero,, and is therefore illegal asmentioned above. This error is defined as type V and gives rise to adiagnostic on tape A3*D.

Specifications Field
This field extends from the column following the dollar sign up to(but not including) the first space (blank).

It may not be empty; this isillegal (error type S) . It consists of a series of subfields, called tree
specifications, separated by commas, ftach tree specification causes exactly
one tree to be written*
Each tree specification contains a tree type number. This is an
unsigned decimal integer, greater than zero but not greater than the numberof tree types available (this number is currently 13)•

A tree type numberthat falls outside these limits constitutes a "specification1' (S-type)error. Appendix 1 gives the tree types currently available..
Following the tree type number may appear a specification for theserial (identification) number for the tree. If it is absent, the tree will
be written with a serial number of zero.
may take one of three forms:

If present, the serial number part

VI-7
(1)

a slash, followed by an unsigned decimal integer;(2)

the single character "plus"; or(3) the single character "asterisk*11
These identification number specifications control a counter called "S"(for "Serial number")*

The first type causes the counter S to be reset

and replaced by the integer following the slash. The next type (characternplus"j causes 1 to be added to the contents of S; the character "asterisk"

causes no change in S.

In any of these three cases, the final contents of

S become the identification number of the tree.

3.

Continuation Cards
It may happen that there is not enough space on a card image torecord all the information desired.
extending any card image*

A means is provided for indefinitely

This consists of the use of "continuation cards"

which are treated as extensions of preceding cards. Continuation cards areidentified by five blanks in columns 1-5, and an asterisk in column 6.
Continuation cards may legally follow only certain cards:

thosewith no blanks in columns 7-72 and those in which a minus sign (11 punch)precedes all spaces (in columns 7-72),

The reason for these restrictions

is that a blank is considered to terminate the information on a card,
whereas a minus sign indicates that a continuation is expected.

If acontinuation card appears under other circumstances, the error is type C(for "Continuation"); if one occurs at the start of the data, the error isVI-8
type 3 (for "Beginning").

If a card containing a simus sign is not followed

by a continuation card, the error is type Q (for "seQuence").

4.

Internal Processing
After reading each card image from tape, TBECKD checks columns 1-6

to see whether it is a continuation card. If' it is a continuation card, andthe preceding card either had data to column 72 or contained a minus sign,then the data in columns 7-72 of this card are attached to the data from thepreceding card.

If it is not a continuation card, columns 1-6 are further

checked to ensure that they satisfy the requirements of Part 2*
The card image is now scanned character by character, starting incolumn 7. This is done by means of a routine called GETF0R (for "GETcharacter F$Rwardn), which not only retrieves the character from memory, butalso identifies it by type:

digit, letter, etc. Each special character isa distinct type . This information is provided by setting a specific bit in
the sense-indicator register; one bit position corresponds to each type.
A different program section corresponds to each field and subfieldmentioned in Part 2. Transfers of control occur among these various sections
according to the types of character found by the routine.

If any character

appears where it is not expected, a format (F-type) error occurs. Every timea character is fetched, a check is made to see if it is blank or minus. If
it Is, the next card image is read.

If no continuation is implied, processing

resumes on the old card, using the blank that was fetched (a minus always
implies a continuation).

VI-9The routine maintains a list of the relation generators which aregiven by the input. When the dollar sign is detected, these are sorted
into numerical order by value (concept number)*Then the specifications

field is scanned. For each tree type, a table in memory already contains
the direct and indirect connection matrices, the syntactic relation generators (already sorted), and a vector giving the node(s) to which the output
concept number is to be taken as pertaining.

This information is combinedwith the identification number (if any) from the same specification, andwith the relations and output concept numbers already found. Then thisdata are written on tape. A count of the number of trees is updated, andthe next tree specification is examined. When all the information on acard image (and its continuations, if any) is exhausted, the next card
image is read.

A card with a slash in column 1 terminates the process, andis the normal exit.

5-Error Conditions
A variety of checks is made to ensure that the input data are correct.

Any violation of these checks will cause an output message on A3 (the systemoutput tape).

The remainder of the current card image and all following

continuation cards will be skipped and processing will resume with the firstnoncontinuation card . If twenty errors of any type occur during one callof TRECND, it is assumed that the wrong deck is being processed. The result
is that the input tape (A2) is backspaced one record, sense light 1 isturned 0N, and TRECMD exits immediately.

The same action occurs if an end

VI -10of file is detected in the input, or if a redundancy check persists for ten
tries in either input or output.

(The diagnostic messages themselves are

not redundancy checked.) Just before exiting, whether due to error or fromdetection of a "ST0P" sentinel, TRECND uses (STH) to write a message on A3,
giving the count of trees written and of errors found. This occurs even if
no errors occurred.
The errors detected by TRECND fall into one of several classes.
First there are machine errors and tape malpositionings, which result inimmediate termination (KILLx, ERHJZRl); then card format (ERR0R-F), continuation sequence (-B,-C,-Q), concept number range (V), tree specification (S),and count limit (M) checks. The latter occur whenever there are more than
36 nodes, or 64 relation generators, or three output concept numbers, ormore nodes specified than a tree type contains. Appendix 2 contains a listof these error types and the diagnostic messages which they produce, as wellas the action taken after the diagnostic is written.

6.

Use of a TRECND ProgramThis part will describe the use and purpose of TRECND, together withsome examples. A criterion tree such as is produced by TRECND is a prototype,or model, for a part of a sentence. It serves as a sample of a typical phrase
having a definite meaning:for example, "information retrieval" where"information" modifies "retrieval*" To construct a tree that will be usefulin the SMART system, it is necessary to think of several sentences which use
the phrase, then diagram them in the method used by the multiple-path English

VI-11syntactic analyzer, and finally to abstract the common features of thesesentences (as shown in Fig, 1(a)).
The second step is to compare these abstracted phrases with thelist of standard types given in Appendix 1.

In the example, we see thatthe first phrase is of type 7, the second of type 1, and the third oftype 3.

(Since replacing a direct dependence by an indirect dependence

merely generalizes the tree, we may consider the first sentence as belonging
to type 1 as well as type 7.)

It is seen that in all three cases, concept

numbers 53 and 114 ("information") pertain to node number 2, and concept
numbers 26 and 215 ("retrieval") pertain to node 1.

(The node numberingof the various tree types was selected to promote this kind of favorable
occurrence.)

This is shown schematically in Fig* 1(b).

It is now necessary to assign a BCD subject heading (e.g., "INFRET"),
serial numbers for the two trees (e.g., 6,7), and an output concept number(301).

A card is then constructed as shown in Fig. 2.
Figure 3 shows the trees that result from this card, as they appear

on tape (tape unit B5)•

There is an extra field, called "0" for "Output

concept number," which is not mentioned in previous reports. This newformat is fully compatible with the old binary tape format; the $ field isignored by UPGRIT and by previous versions of the criterion routine CRITER.
This field consists of one binary word, whose first six bits form a vector
identifying the "key" node(s) of the tree. The remaining 30 bits are divided
into three 10-bit subfields, each containing one output concept number.

VI-12^(26,215)

0"(53,1U)
AaInformation(53,1M)

good

retrieval(26,215)O(26,215)

0(53,1H)This

providesretrieval(26,215)

information(53,1H)

O(V) (26,215)'SMART'

retrieves(0) (53,1H)

information(a) Sample sentences referring to "information
retrieval," and abstracted phrases

9l

Tree type 1 =/node 1 = (26,215),+ <Q2
node 2 = (53,1U)

J9(26,215)
1!

6(53,1H)

node 1 = (26,215)
Tree type 3 =1(V)2S)

node 2 = (53 , 1 K ) |(V)(26,215) (0T)(53,1U)(b) Relation of Fig. 1(a) to tree types 1 and 3
Construction of Criterion Trees for "Information Retrieval"
Figure 1

VI-13
Step 1.

The BCD index occupies columns 1-6:
INFflttT. • » . .<.

Step 2. The output concept number follows:
INFRET = 301
7..10
Step 3.

The concent numbers for node 1:
BIFHET =301 (26,21$)
11
IS

Step 4. A slash separates the numbers for node 1 from those for node 2:
DJFRET = 301 (26,215) / ( 5 3 , 1 U )1927
S t e p 5-A d o l l a r s i g n i n t r o d u c e s the s p e c i f i c a t i o n sfield:LMFHKT = 301 (26,215) / ( 5 3 , 1 H ) jf 1 / 628..31(which s p e c i f i e s a t r e e of type 1, s e r i a l number 6)
Step 6 .

A comma s e p a r a t e s the f i r s t s p e c i f i c a t i o n from the next:
INFHET = 301 (26,215) / (53,LM) 4 1 / 6 , 3 +32.34( s p e c i f y i n g a t r e e of type 3 , s e r i a l number 7( = 6 + 1) )Step 7 .

A blank t e r m i n a t e s the c a r d :INFRET = 301 (26,215) /(53,1U) # 1 / 6 , 3+^35Construction of a Card to Make Criterion Trees
Figure 2

VI-K
Column Number 1 . . . 5 . . • . 1 0 . . . . 1 5 . . . . 2 0 . . . . 2 5 . . . . 3 0 . . . . 3 5
INFRET = 301 ( 2 6 , 2 1 5 ) / ( 5 3 , 1 1 4 ) 4 1 / 6 , 3 +(a)Card i n p u t t o TRECND

NI<R

1..
1..

D<

4r

..1nm

Sem <v<Synt(b)Binary trees generated from Fig. 3(a)x • • • p • <• •J_U • •••Jo* •••2072

IUFRET

1 X (26,215)
2 II (53,114)
INFRET

1 3D (26,215)
2 31 (53,114)
3 X(c)Cards required by MAKTRE for same result

Binary Tree Resulting from Card of Fig. 2, and a
Sample of Input Required by MAKTRE
Figure 3

VI-15Figure 3(c) shows the seven cards required by MAKTRE to generate
the same two trees.. The two routines produce equivalent output, except
for the fact that MAKTRE does not produce an 0 field.
therefore, TKECND is more general than MAKTRE.

In this respect,VI-16APPENDIX 1
STANI;AftE TREE TYPES

10iOIVIIII

26

20
VIIIIIIX

III\1 (v)IVy\2M0)01(c)o*2 (0,5)

A20(S)lO(0)'iO(v)

XIi°(s)^9VIiO

Note:

XII

2O

The asterisk shows "key" nodes, i.e., the nodes to whose correspondents
the output concept number will be attached after a match is found.

VI-17APPENDIX 1 (continued)

XIIIid(j?,s)26(90VI-18
APPENDIX 2ERROR TYPES

Whenever one of the errors in the following list is encountered,
the indicated message is -written on tape A3* This message is preceded by%TRECNI)-w

and followed by a copy of the card image to which themessage applies*

The equals sign immediately precedes the first columnof the card image:Type, Action

1 ERRORBR
R

DATA MAY NOT BEGIN WITH CONTINUATION CARD =Q
RRR

SEQUENCE ERROR.

ERRORXERRORQERRORFERRORM
1 ERRORCERRORI"Message

BCD INDEX IS IN ERROR. =NO CONTINUATION CARD FOLLOWS =FORMAT OF THIS CARD IS IN ERROR. =SOME SIZE OR COUNT LIMIT IS EXCEEDED IN =A CONTINUATION CARD IS NOT REQUIRED HERE =THIS ERROR IS THEORETICALLY IMPOSSIBLE. RUN BAD =ERRORS»ERROR IN SPECIFICATION OF TREE TYPE. CARD =JERRORVBINCORRECT SEMANTIC VALUE (CONCEPT NO) IN =s• KILLWsKILLFssKILLTAPOV 1 s| KILLREXCESSIVE REDUNDANCY ON READIN OF =EXCESSIVE REDUNDANCY ON WRITE =END OF FILE ON INPUT, =IMPOSSIBLE E0F OR REDUN AFTER BACKSPACE =END OF TAPE DETECTED ON LIBRARY TAPE, CARD =1Following each type in the above table is a BCD symbol, either "0,""R," or "S." These indicate the action taken after the diagnostic is printed.
"0" means "process the next card image"; ,!R" means "skip continuation cards,
process next noncontinuation card"; and "S" causes an exit with sense light
1 turned M#N.»