ISR-7
June 1964.

IV-1

IV. DICTIONARY LOOKUP AND UPDATING PROCEDURESMark Cane

1.

Introduction
The present report describes the routines used to manipulate thethesaurus (or concept dictionary), including all thesaurus lookup programs,
as well as the programs used to set up and update the hierarchy.

The update

programs are described first, including a specification of the input deck,
as well as a detailed explanation of all setup and updating options. Thisis followed by a discussion of the lookup procedures. Examples are given
and detailed flowcharts are shown to illustrate the programs.
The updating section sets up the thesaurus and suffix trees used by
the thesaurus lookup programs. These programs are stored as the first fileof a library tape. Inputs to these program blocks consist of a control card
specifying what is to be done, followed by additional cards containing thedata for the entries to the thesaurus and the suffix trees. A variety ofoptions is provided. Either tree may be set up in its entirety; anexisting tree may be copied onto a new library tape unaltered, or may be
augmented by new data on cards; furthermore, the semantic and syntactic dataassociated with each entry in the trees may be altered.
The block of updating programs also handles the conversion ofsemantic and syntactic data from a format acceptable to the FORTRAN 1-0
package to the packed format used by later programs.

IV-2
2.

Input Deck, Control Card, and Data Card formats
The input deck consists of a single control card, followed by thecards containing the thesaurus entries (if any), terminated by a card withthe letter ,!ZM in columns 1 through 6; the thesaurus entry cards are in turnfollowed by the cards containing the suffix data (if any), which are again
terminated by a card with six "Z fn s.
The control card is divided into four fields:

columns 1-6, 7-12,

13-18, and cclumn 24.• All fields are left-justified.

Table 1 lists thepossible configurations of these fields and the options they control*
A thesaurus input card contains 15 fields. The first field (cardcolumns 1 to 24) contains the English word to be entered.

It must be left-

justified, i.e., the first column must contain the first letter of theword. The next six fields (columns 25 to 48) store the semantic codes(category numbers) associated with the word. Each code is allotted fourcolumns, so that the codes appear in columns 25-28, 29~32, 33-36, etc. The
codes must be left-justified in the field, and must be stored consecutively.
For example, if there are two codes, say f;05 and 237, they must appear in
the first two fields in columns 25-28 and 29~32, respectively. Furthermore,each code must be right-justified within each field*

Thus, for the above

example, columns 25-32 would appear as follows:

25 26 27 28 29 30 31 32
9

0

5

The category numbers must be less them 2

2

3

7

= 4096 in magnitude*IV-3

pfirst Field Second Field Third Field Fourth Field
Col. 1-6

Col. 7-12

Col. 13-18

1

BOTH

START

START

2

BOTH

START

START

3

BOTH

START

UPDATE4BOTH

UPDATE

START

5

BOTH

UPDATEUPDATE

6

THES

START

7

THES

UPDATE

8

SUFFIXSTART

9SUFFIXUPDATE

Col. 2U

OptionBoth the thesaurus andsuffix trees are set up
in their entirety.
Nothing is done with theold tape (an explicit 0
may appear in column 2U) •1

Same as above except thatthe old tape is spaced
past the file with thelookup data.
The second field controls
the action taken for thethesaurus tree: START
means that it is setup
in its entirety, UPDATE
implies that the entries
on the input cards areadded to the tree on theold library tape. The
third field controls theaction taken for thesuffix tree, with definitions as before.
The action specified by
the second field is takenj
on the tree specified in
the first field. The
tree not referred to in
the first field is copied |unaltered from the oldlibrary tape to the new* |I 10

If the first field isblank the lookup file iscopied from the old tapeto the new; nothing isaltered.
Thesaurus and Suffix Setup and Update Control Card Formats
TABIiS 1

IV-4
The last eight fields (columns 49-72) represent the syntactic codes
associated with the given word. Each code is allotted three columns(i.e., columns 49-51? 52-54* etc*).

These codes must again be left-

justified within the entire syntactic field and must be stored consecutively.
ji^ach code must be right-justified within its field.

The syntactic codes

0:

must be less than 2 = 256. The thesaurus input cards may therefore beread with a format of 4A6, 6l4; 813. There are no restrictions on the orderof the input words.
The suffix input cards contain two fields. The first (columns 1-12)
stores the English suffix; the second (columns 13-15) contains a number
associated with each suffix in a one-one correspondence. This number mustbe right-justified within its field and less than 2° = 256 in magnitude.
The first suffix entered must begin with the letter "e" (see l$0K
description)*

3.

Implementation of oetup and Updating
The thesaurus setup and update block consists of the following

subroutines,

CANE (with entry CANE3), ECRW, CANE1 (with entries CEAD and

CRITE), CANE2, TIPUT, TREET (with entry TRADD), and SUFTR (with entry
SUFAD).

CANE1 copies the file from the old library tape to the new tape.

CEAD reads the file into memory from the old tape, and CRITE writes thetrees in memory onto the new tape. CANE is the only routine called fromthe main program.

Its entry. CANE3 , is an error return - in case of error

during reading (i.e., redundancy, end of file encountered) or during writing

IV-5(i.e., redundancy), CANE1, et al. transfer control to ECRW, which prints
out a message explaining the error and transfers to CANE3• The latter turns
on sense light 1 to let the main program know that an error occurred, andthen returns to the main program.
CANE2 controls the main flow of operations of this block. The
flowchart for this routine (Flowchart 1) is generally self-explanatory;
7°
only a few remarks are needed.
The operations of spacing past thethesaurus file and of reading in the old trees to update them are performedin the same manner:

CEAD is called to read in the whole file. If thethesaurus tree is to be set up solely from input cards, the old tree issimply ignored.
Messages are printed out stating the amount of tree storage
remaining for both the thesaurus and suffix trees. This aids in determining
whether future additions are likely to cause either tree to overflow theirallotted storage.
In the event that either tree should exceed its allotted storage,
a message stating the amount of the excess is printed arid a printout indicates whether the thesaurus or suffix trees were involved; sense light 1
is also turned on. If the overflow occurs in the suffix tree, or if it
occurs in the thesaurus and no suffix cards are present to be read, control
is returned to the main program.

If overflow is detected in the thesaurus,

and suffix cards are to be read, it is desirable to space the input tape

The flowcharts appear in the Appendix to this section.

IV-6
past the suffix cards, so that the next setup or update programs can again
test for possible errors. Further, it is then also useful to process thesuffix cards to determine whether the suffix tree will also overflow. In
this case it is, however, undesirable to waste time writing a worthless
file.

The parameter K3PACE is then used to prevent such a tape from being

written.
The buffer provided for the thesaurus input may not be large enoughto contain all input simultaneously.

TIPUT, which reads in the cards, isused to furnish a parameter IRfJV, which is set to 1 if the reading operation
is interrupted because of a filled buffer and is set to 0 if reading stops
because a word ofMZ,Ms is encountered to indicate the end of the inputs cards.
After returning from TBEET or TRADD (depending on whether the tree is set
up or updated., respectively), this parameter is tested.

If it is 1, TIPUT

is called again, and then TRADD is entered if the tree is being updated,in addition to reading in the thesaurus cards, TIPUT packs the semantic andsyntactic codes into a format acceptable to the other routines in SMART.
Internally, each entry in the thesaurus consists cf four computer
words of associated data as shown in Fig. 1. The semantic codes appear in
the first two words in six 12-bit fields (S, to 3, in the diagram). The
codes are left-justified; that is, if for example a word has four semantic
codes, they are stored in fields S.,, S

S«, and 3, . The syntactic codes

occupy the next two words in eight 8-bit fields (Y. to Y p in the diagram).
Note that the fifth field is split between two adjacent words. The codes

IV-7

1

2U 25

12 13

[fl

S

S

2

36

1
S

3

2U 25

12 13
S

A

S

5

36

6

SEMANTIC CODKS

1

8 9

k

Y

16 17

2

24 25

*3

U 5 12 13

32 33

Y

Y

6

5

\
L

V

Y

20 21

7

Y

28 29

8

36

*J

>

SYNTACTIC CODESInternal Formats of Semantic and Syntactic Codes
Figure 1

are again left-justified.

The rightmost field of the syntactic words(JL in the diagram) is always set equal to zero,(It Is reserved for a

suffix code - see the description of L^j2K).

4.

The Tree Programs - SUFTR, SUFAD, TREET, and TRADD
Before discussing the routines which set up the trees, it //ill be

helpful to give a brief, nonrigorous explanation of some of the concepts
involved.

The principal concepts are illustrated in Fig. 2*

Roots areFor a fuller, more precise discussion see Iverson, A Programming Language,
Wiley (1962) and E. H. Sussenguth, "The Use of Tree Structures for
Processing Files," CACM (May 1963).

IV-8

A Pictorial Representation of a Tree
Figure 2

nodes with no branches entering them; leaves are nodes with no branchesleaving them. Note that while many branches may leave one node, at mostone branch enters each node. The filial set of a node A is the collectionof nodes S such that there is a branch from A to the elements of S. A
member of the filial set is called a son of A; two members of the same
filial set are said to be "brothers."

Thus, in the tree of Fig. 2, A isthe son of B, and C and D cire brothers.
in the trees to be described, each node consists of one machine
word containing three fields (w. , w , vju) • The first field, w , is called
the key; the second, VjU, points to a brother; the third (w ) to a son. The
key is a BCD representation of an English letter. In the trees used inIV-9connection with the thesaurus, each node points to one son, which in turnpoints to its brother*Thus the tree of Fig. 2 can more accurately be

represented by Fig. 3 (with double lines connecting brothers)An English word is represented as a path from a root to a leaf.
A word is always taken to be terminated by a blank (represented here by"*").

Thus the key (w,) of each leaf is the character "*" (represented in

BCD code by the digits "60").

The w~ field of each leaf points to the dateassociated with the word. For example, the words "ADD11 and "ADDRESS,"

Pictorial Representation of a Tree as Represented
in'Memory by SUFTR and TREET
Figure 3Ao-oS

A Pictorial Representation of "ADD" and "ADDRESS" in Tree Form
Figure U

IV-10in tree form, are represented pictorially as shown in Fig. k*

The tree ofFig. k might be stored in memory as shown in Fig. S>.
Consider now the routines SUFTR and SUFAD (see Flowchart 3).
sets up the complete suffix tree initially.

SUFTR

The routine starts by setting

up the first word, and enters nodes consecutively from the beginning of theblock reserved for the suffix tree.

SUFAD adds suffixes to a tree alreadyset up; it begins by adding from the next free location of the suffix

1

Bits
S, 1-5

Bits
6-20

Bits
21 - 35 |

*1

^2

3

Location

100
101

" 1
101

A
D

105

•

105

D

107

#

115

R

120

120
121

E
S

121
123

123

S

121*

*

12U
XXX

107
115

-A
XXXM

«

A Possible Memory Configuration Corresponding
to the Tree of Fig. k
Figure £The w

f i e l d s marked "XXX" p o i n t t o d a t a .

IV-11
block - as determined by an input parameter. Except for this difference,
the two routines are identical and will henceforth be referred to as SUFTR.
SUFTR begins by entering a new suffix by comparing the first letterof the input word with the key of the first root of the tree. If a match
is found, the next letter of the input is compared with the son of thematching key letter (pointed to by the w~ field).

If the routine fails tofind a match, it proceeds to the first brother (pointed to by w O andcompares the input letter with the new key (see Flowchart 3, especially thebox labeled 3).

The search is continued until a match is no longer possible(when no match is found and the w p field is zero, indicating that there isno brother).
as the w

The address of the next free location, K, is then inserted

field of this letter (box J+ of Flowchart 3) and control is trans-ferred to box 1 of the flowchart where the letter of the input word isdefined as the key (wfield) of the word at K.

The address of the next

free location (K- 1) is then inserted as the w~ field of the word at K.
The next letter (its son) will then be put in this new location. Sons arecontinually inserted in this way until the "letter11 of the input word is ablank ("*-u). At that point the data (suffix code) for this word Is stored
in the next free location.
If a match should be found for the entire suffix, this is taken tomean that an alteration of the data associated with that suffix is desired.
Box 5 of Flowchart 3 handles this (of course, if the same suffix is inserted
a second time by mistake no harm will be done; the suffix code will merely
be stored over itself).

IV-12
The algorithm of TKEET is essentially the same as that of SUFTR(TRADD stands in the same relation to TREET as SUFAD does to SUFTR)•

The

similarity of the algorithms may be seen by comparing the parts of Flowchart
2 above the dotted line with Flowchart 3. This similarity is obscured
somewhat by the special requirements that L00K. places upon the order of
the thesaurus tree (see the description of L0#k).

Specifically, L00K

requires that blanks, final f,eu,s, and final w y ,n s be encountered before
any other members of the same filial set, so that possible stems will berecognized. The TREET routine must therefore verify that a blank occurs
always as the first element of a filial set (the one pointed to by the Wo
field of the parent and not by the ^field of a brother). An "e" isalways inserted as the first element of a filial set, except if a blank isstored ahead of it. A "yu is inserted before everything except a blank oran "e". (Note that it is not strictly necessary, from the point of viewof L00K, to insert all n e IM s and "y,n s ahead of everything else; this is
only necessary if these letters occur as final letters of a word. By doing
it in every case, the setup routine becomes more efficient:no rearrangements

or searches through a whole filial set are required if an r,e" or "yn in the
middle of a word should turn out to be a final ''e" or "y" of another word.)
An initial "eM or u y M

is not inserted ahead of other roots.

This rearrangement is accomplished by the sections of TREET represented by the part of Flowchart 2 below the dotted line. If the next
"letter" of the input word is a blank and there is no blank in the filial
set of the last node for which a match was found, the blank is inserted asIV-13the first son of this ncde and the address of the old first son is inserted
in the w
2*field of the new first son. This is done in box 7 of Flowchart

If a blank is already included in the tree at this point, an alterationof the data of the word is called for; this is handled as in the descriptionof SUFTR. Similarly for an "eM if there is no blank in the tree at thispoint, or a My,! if there is no blank and/or "en in the tree at this point.
If the letter in question is already in the tree, TREET moves on to the next
letter of the input word in the normal manner.
As an example of this process, Fig. 6 shows the tree of Fig. 4- withword "AD" inserted.

Similarly, Fig. 5 is changed to the form shown In

Fig. 7, assuming the next free location at 271.
If the letter of the input word to be searched is an "e" and a blankalready occurs in the filial set, the M e n Is inserted just under it (i.e.,the Wp field of the blank is made to point to the "e"), unless the f,efl isalready present there, in which case TREET moves on to the next letter ofthe input word.
If the w

This insertion is accomplished in box 8 of Flowchart 2.

field of the blank is zero, "e" is made a brother in the samemanner as for any other letter (in box 6 of Flowchart 2).

If My" is the

input and a blank and/or an "e" is already in the tree, the same procedure
is followed.

Figure h With the Word "AD" Added to the Tree
Figure 6

IV-1A

Location
100
101

*1
A

w
-3
101

w
-2

D

271

D

107

•
•
•

105
•
•
•

107

*

115

XXX

•
•

115

R

120

E
S

121

S

124
XXX

•
•
•

120
121

123

•
•
•

123
124

• #

•
•

271

1 105

XXX

Figure 5 With "AD" Added t o the Tree
Figure 7

o
R

o
E

o
S

o
S

o
*

Tree of Fig. 6 With "ADDER" Added
Figure 8«IV-

Location

100
101
•
•
•

105

1 % ^2 1*3
101

A
D

271

D

107

•
•
•

107
•
•
•
115
•
•
•
120

*

311

XXX

R

120

E
S

121
123

S

124

124•
•
271
•
•

*

XXX

*

105

XXX

311
312

E
R

115

312

1 313

*-

121
•
•
•
123

313
XXX

Memory Map of Fig. 7 With "ADDER" Added to the Tree
Figure 9

For example, if the word "ADDER'1 were to be added to the trees
depicted in Figs. 6 and 7, and the next free location were 311, Figs* 8
and 9 would be generated, respectively.

IV-16
5. General Description of Thesaurus Lookup
This block of programs "looks up" an input text in a thesaurus
dictionary and suffix lists which have previously been written on tape intree form (see the description of the setup routines.)
Semantic codes (or a code indicating that the word was net found)are entered in a text output block, together with the sentence and wordiii-sentence numbers which identify that word. If the word is not found,
it is put in a "not found" block as is explained below.

If requested(by leaving sense light 3 on), a block is assembled which can be used as
input for syntactic analysis, iiach item contains the English text wordwith its numbers, the semantic and syntactic codes which are entered in
the thesaurus with the item of that word, and a code for the suffix of theword (if any). If the word is not found, a special code is entered(semantic and syntactic words are zeroed) and a search is made for a
possible suffix to aid in syntactic analysis.
The search for a match with an input word proceeds from left toright one letter at a time. The longest possible match is looked for, but
notice is taken of any possible shorter stems which may be found on the way.
If the match is not complete (i.e., if the whole input word is not matched),a suffix is searched for. If no successful match is found for both stemand suffix, the routine backtracks to possible shorter stems and again
searches for suffixes. Certain spelling rules to be described are built
into the program.

IV-17

The thesaurus and suffix tree formats were described as part of the
setup programs.
(1)

Other format specifications are as follows:

Input Text Words•
words.

Each item consists of five machine

The first stores the sentence number of theword in the decrement field and the word-in-sentence
number in the address field.

The next four words

contain the English word in BCD form.
(2)

Text Output.

Each item consists of three words.

The

first contains the sentence and word numbers as above.'
The next two contain either the semantic codes associated with the word (or with its stem) In the thesaurus,
or a "not found" code (all bits "on").
(3)

Syntactic Output.

Each item consists of nine words.

The first four store the English word; the next thesentence and word numbers; the sixth and seventh
contain the semantic codes; and the eighth and ninth
represent the syntactic codes, with the last eightbits of the ninth word being a suffix code (if a suffix
exists) .

If the word was not found, these last fourwords are set equal to zero.

There may, however,still be a suffix code stored in the last word.

Beforethe block of syntactic items is written onto tape It
must be revised, since all blocks are stored inbackward (FORTRAN II) order.
(4)

Not Found Output.

Each item consists of six words.

The first five are identical with the input items.
The sixth word contains a code in the decrement Indicating whether(a)no stem was found, or(b)

no suffix match could be made after
a possible stem was detected »IV-18The address of the sixth word contains the index of
the first letter in the word for which no match could
be found.

This information is generated relative tothe last pass of the lookup process.

Since eachindividual letter appears as an entry in the thesaurus,
a stem consisting of a single letter is always found:the first letter not found is then determined relative
to this stem,
6.

Implementation of Lookup
Three subroutines comprise this block:

L00K, RSSX, and GCRW. The

sole function of the latter is to print messages in case of error while
reading the input tape, or writing the syntactic output tape. RSSX
(Flowchart 5>) looks for a suffix if no stem is found.

Since this is only

wanted for the syntactic analysis, the routine is called only when syntactic
output is desired.

L00K, the only routine called from the main program,performs all other functions (see Flowchart k) •L00K begins by reading in the thesaurus and suffix trees from tape.
Sense light 3 is then examined and transfers are set throughout the program
either to bypass or perform the operations that produce the syntactic output.
If the sense light is on, syntactic output will be produced.
The data output section of L00K is explicitly described in Flowchartk.

The boxes surrounding box 3 store data when a word is found in thethesaurus.

The series of blocks starting with box h perform the operations

needed when a word is not found.

Since the buffer allotted for syntactic

output is not large enough to hold the entire output for a text longer thanIV-19100 words, this output must be written onto tape in pieces. Before it isput on tape, the block must be reversed so as to appear in forward order.
This operation is handled while the tape is being written so that no
additional time is lost.
The actual search through the thesaurus tree is similar in outline
to that of the search in SDFTR (see description of trees and of the SUFTR
routine in Part U of this section) . However, L00K must also take note ofpossible stems which are not complete matches for the input word (e.g., HAND
is a stem of HANDING but the two words obviously do not match completely).
The following are considered indicative of possible stems:(1)

a blank indicating end of word;(2) a final "e" (an "e" followed by a blank with ablank in its filial set);(3) an "i" occurring as a letter of the input wordwith a final "y" in the tree (the parameter ITEST
of Flowchart U ensures that no "y" will be noted
unless the input letter is an "i").
The first possibility corresponds to a word taking a suffix as an
ending, e.g., HAND + ING is HANDING. The second corresponds to a word
dropping an »e" before taking a suffix, e.g., HOPE less the E + ING is
HOPING. The third corresponds to a "y" changing to an "i" before taking
a suffix, e.g., PRETTIER is PRETTY with the »T« changed to an 1+ the suffixER.

IV-20•oYo*Pictorial Representation of a Part of a Thesaurus Tree
Figure 10

The necessity of becoming aware of these stems accounts for the factthat in TREET (see description of TREET in setup section) blanks, ,!e,ns, andny n, s are inserted ahead of other members of a filial set*This restriction

on the order implies that all possible stems must be recognized before any
match is found.
The following example will serve to render this procedure clearer.
Consider a (partial) thesaurus tree as shown in Fig. 10 and assume that the
input word is CODING. 'L00K moves from left to right along the tree matchingC ; 0, and D.

In trying to match the I, the final E of CODE is first en-

countered and is saved as a possible stem. The routine then moves on tofind a match with the I of CODIFY. Eventually the routine fails to matchthe N of CODING with the F of CODIFY. So, remembering that CODE was a
possible stem, a search is made for a suffix beginning with the I. WhenING is found, CODING is recognized as the stem CODE plus the suffix 1NG.

IV-21

7. Spelling Rules Incorporated into Lookup
In order to be able to recognize, for example, that HOPED is
HOPE+ ED while HOPPED is HOP+ doubled letter+ ED, certain spelling rules
are built into L00K. These are summarized in Fig. 11 ("*" represents blank)

Case Description

LongerEndingShorterEnding(a)

B= C (a doubled letter)

*

*

(b)

B^ C and B is an "e"^*(c)

B^ C and B is not an »e»

*

e

e

Case
Number
*

1

1

2

3
U

M

M

y (means C is an i )1y* and e
*

(a)

B= C

*

(b)

B/1 C and C is a vowele(c)

Bfi G and C is not a vowel** and y*ye and ye

I

56

B refers to the last letter for which a match is found in thethesaurus;
G refers to the first letter for which no match is found in
the thesaurus (the current letter being searched for).
Summary of Spelling Rules Built .Into L00K
Figure 11"e" followed by the longer ending is also treated as a possible ending
and is associated with the ue,! stem.

IV-22The three possible types of stems - those terminated by a blank; thoseterminated by an "e" followed by a blank; and if C is an "i", thoseterminated by a "y" followed by a blank - are referred to in column 2
of Fig. 11 by ,?*% "e", and "y", respectively.
The "longer ending" includes C followed by the rest of the word;
the "shorter ending" refers to the rest of the word not including C; "e"followed by the longer ending denotes the concatenation of the letter "e"with the letters of the longer ending.
For example, the input HANDIER would be decomposed into thepossible stems HAND (denoted by "*") and HANDY (denoted by "y").

In thiscase, the longer ending would be "ier", the shorter "er" . B would be theletter "d", and C the letter "i". HOPED would furnish HOPE as a possible
stem.

B = "e", C = "d"; the longer stem is just "d", and "e" concatenatedwith the longer stem is "ed".
The longer of two endings is always treated first; if no match isfound in the suffix table, the shorter one is tried. Examples of cases ofFig. 11 are shown in the following list (L will be used as an abbreviation
for the longer ending; S for the shorter):(a) If the input word is HOPPED, the stem is HOP indicatedby a terminal n*u (blank).

B = p = C, so case 1(a)applies. First a match in the suffix list is attemptedfor L = "ped". None is found so S = "ed" is tried andmatched.

If, however, FINALLY were the input word andFINAL the stem, a match would be found for the longer
ending, namely "ly".

IV-23(b) If the input word is HOPED, the stem is HOPE (a •'*"stem);

B is an M e % "e" + L = "ed" is searchedfirst and a match is found.

For HOPELESS, "e" + L

would be "eless", and no match would be found; but
the search for a suffix matching L = "less" would
be successful.
(c) If the input word is ENDED, the stem is END.
B is a M d M , so that case l(c) applies.

In all of the above cases the semantic and syntactic data are taken fromthe data in the thesaurus tree pointed to by the H*M of the recognized stem.
This explains the significance of the "*" in the longer and shorter ending
columns of Fig. 11.
Consider now the entries EASE and EASY, both included in thethesaurus, and the input words EASING and EASIERo

In both cases, EASE

(marked by the M e M ) and EASY (marked by the ,fyn) will be found as possible
stems.

For EASING, L = "ing" will be found in the suffix list, so L00K willtake the data from the "e" stem EASE, and the suffix code from ,fingM . For
EASIER, the program will fail to find a match for L » "iern and so will
try to match S = ffern.

Since this is successful, the data are taken fromthe rtyn stem EASY and the suffix code from fler,?.
If the input word were HOPED, and both HOPE and HOP were in thethesaurus, L00K would first attempt the longer match with HOPE - marked bya ll*H since the match would be made through the "e" - and apply rule 1(b).
If (as is not the case) no suffix were found to match, the routine would
then backtrack one level to where it had found the possible stems HOP(marked by a "#•") and HOPE (marked by an ,Ten) and apply rule U(b).

IV-24The suffix search uses the same basic search algorithm.

It iscapable of handling many types of multiple suffixesj e.g., for HOPELESSLY
it will find the suffix i,lessiI.

Since the son of the last f,sM is an "* n ,and that no x%" can be found in the filial set of this "s fl , the routine
will re-enter the suffix tree from the beginning, trying to match thesecond '[£" of HOPELESSLY.

It will proceed to find a match with "lyM .

Only the code for the last suffix found is entered in the data of
the syntactic output.

For this reason it is desirable to enter certain

compound suffixes explicitly in the tree to provide a maximum of syntactic
information (e.g., if KINDNESSES is being looked up, arid llnessn and "es"are in the suffix tree but "riesses" is not, L00K will only pick up thedata of "es"; if "nesses" were in the suffix list, enough information would
be available to recognize a plural noun).
L$0K will not find multiple suffixes if there is an "e" telescoped
between the parts; e.g., "ized" is n ize" + "edn, but the one n e " is "used11
by the two parts.

Such suffixes must also be entered separately (e.g.,,ti:,Jed,, as well as nize(l arid "ed") .

8.

Processing of Words Wot Eound by the Thesaurus Lookup
The general purpose of this program block is to supply information

about the words that are not found by the thesaurus lookup-

This information

is useful for deciding upon later alterations (particularly additions) to
the thesaurus.

IV-25
If all the words are found by I#0K, a message to this effect isprinted out. If not, distinct occurrences of the same English word are
combined into one output item. This item contains:(1) the English word in BCD format;(2)

a code indicating whether 100K failed to find a stemin the thesaurus that matched the input word orwhether, having found a possible stem, it was unable
to find a suffix in the suffix list to match therest of the word (see the description of the lookup
block);(3)

the number in the word of the first letter of the
input word for which no match was found in thethesaurus (see the description of the lookup block);(4)

the number of occurrences of the word in the text
looked up;(5)

the sentence and word-in-sentence numbers of theoccurrences of the word.

All of this information except the fourth item, the number of occurrences,is supplied explicitly by L0tfK.

For example, assume that the word PLANET

is not included in the thesaurus, but that the word PLANE is, and is the
only possible stem identified.

Assume further that in a given text PLANET

occurs as the seventh word of the third sentence, and as the tenth word of
the eleventh sentence. The output for this word would then appear as inFig. 12.

IV-26WORD
PLANETKINLSUFFIX

LOC
6

MM
2

SENTENCE AND WORD NUMBERS
3,7
11,10

Output Format f o r a Word not Found i n the Thesaurus
F i g u r e 12

L00K would find a match up to the n e M of PLANE and thus think it
had found a possible stem. It would then fail to find a suffix to matchthe n t" . Thus, the stem-suffix code (KIND) indicates that a potential
stem was found but no suffix was found.

Since "tu is the sixth letter ofthe word PLANET, the location of the letter in the word (LOC) is 6. The
number of occurrences of the word (NUM) is 2. The sentence and word-insentence numbers are as shown.
Subroutine L00K provides two inputs for this block:an array of

the words not found (for format see the description of the thesaurus lookup
block), and a count of the number of computer words in this array. Currently
space is provided for 250 items, each of which consists of six computer
words.

If more than 250 words are not found, only the first 250 areprocessed •The program is composed of three subroutines:

SNCC, BAG;, and CROC.

Only SNCC is called from the main routine. No arguments are needed, since
the inputs are left in common by L00K. SNCC first checks to see if all thewords were found.

If so, a message to that effect is printed out and returnis made to the main program.

If not, a heading for the output is printed

IV-27and the first word of the output block is set up. CROC is then called.
If only one word is not found, CROC immediately proceeds to process it for
printing.

If more than one word is not found, each additional word in the

input block is compared successively with the words in the output block.
If different from all of them, the five pieces of information mentioned
above are stored as a new item in the output block with the occurrence countset to one. If, however, the input word is identical with one of the words
in the output block, the occurrence count of that output item is increased
by one and the sentence and word-in-sentence numbers of this latest
occurrence are stored in the output block. Space is provided for 26 suchoccurrence numbers for each item.

In the unlikely event that more than 26

occurrences are detected, the occurrence count Is increased, but the numbers
are not stored *After all input words are treated in this manner, the output blockis ready to be printed out. CROC unpacks the sentence and word-in-sentence
numbers of each item (see the writeup of I#0K for formats), and puts themin a form acceptable to the FORTRAN 1-0 routines. Subroutine BAG thenprints out (off-line) the relevant information for each item in the format
of Fig. 12. After all items are printed, control is returned to the main
program.

(Since subroutine CRCG uses multiple tagging, the computer isassumed to be in the multiple tag mode when this routine is called) .

APPENDIXENTER

4KSPACE=0
READ IN THE
CONTROL CARD
COPY FILE ON OLD
TAPE ONTO NEW TAPEIDONE BY CANE I)

RETURNERROR-ILLEGAL|CONTROL CARDSENSE LIGHT 1
ON RETURNCALL TIPUT TO READTHESAURUS INPUT CARDSAND PACK SEMANTIC ANDSYNTACTIC DATASETS IROVM IF
STOPPED READING BECAUSEFILLED BUFFER; IROV = 0
IF ALL INPUT DATA IS
READ IN

IS THE"THESAURUS TO^
BE SET UPFROM/SCRATCH?
^ ^No
CALL CEAD TO READ
IN OLD THESAURUS ANDSUFFIX TREES ANDSPACE PAST END
OF FILECALL CEAD TO READ
IN OLD THESAURUS
AND SUFFIX TREES
THUS SPACING TOEND OF FILE

J2*

XCALL TREETTO SET UP
THESAURUS TREECALL TRADD TO ADD[THESE ENTRIES TO THE
THESAURUS TREECALL TIPUT TO READ
IN AND PACK NEXTTHESAURUS DATA

1

| KSPACE'O

KSPACE=1

PRINTOUT AMOUNTOF FREE STORAGE
REMAINING

PRINT OUT AMOUNTBY WHICH STORAGE
EXCEEDED SENSE
LIGHT I ON

CALL CRITE TO WRITETHESAURUS AND SUFFIX h
TREES ON NEW TAPE

RETURNCALL CEAD TO READ
IN OLD THESAURUS
AND SUFFIX TREES

Main Logic of Thesaurus Setup Block(Subroutine CANE2)
Flowchart 1

H RETURNh©

READ IN
ALL SUFFIX
DATA

(a

IS
"SUFFIX TREE"TO BE(a) SET UP FROMSCRATCHi b ) ADDED TOERROR-RETURNSENSE LIGHT 1 ON

Flowchart 1 (continued)(b)IV-30TRAOO__i
KOD£» 1
K=NEXT FREE
LOCATION (INPUTTO TREET)TREET, TRADD
Flowchart 2

IV-31

SUFAD

SUFTR

_J

k

KODE« 1
K'NEXT FREE
LOCATION (INPUTTO SUFAD)STORE DATA OF
I j AT K, FIRSTSHIFTING IT INTO
POSITION
K=K-ld>
RETURNSTORE DATA OK
Ij AT£ (w^a))SUFTR, SUFAD
Flowchart 3k?)LEGEND FOR FLOWCHARTS 2 AND 3 - SUFTR, SUFAD, TREET, TRADD

I

Input data.

jIndex of I; I. is the jth input item.
Jt

Input word (^2characters, always including the terminating

character blank).
w

Machine word.
w. - is the key.
Wo "" is "the address of next w in the same filial set(the next brother of w ) .
w~ - is the address of first w in the filial set (the firstson of w) if w. • * then w

is the address of the data

for the word.
w(a)Machine word in address a.

iIndexes tj t. is the ith letter of word t.

*

Indicates the character blank.

nNumber of input items.

X

A blank machine word, field or character.

sStarting address of the tree.

K

Indexes free space: K is the address of the next free locationin the block.

K starts at s and is decreased.

V

Temporary storage.

eM

The character "e" (in general "x" means the character x ) .

ENTERft
INITIALIZE
READ IN THES ANDSUFFIX TREESCALL GCRW
TO PRINTERROR MESSAGEEXIT

SET TO
BYPASS SYNTAXWRITE REST OF t
' SYNTAX ON TAPE II REVERSING ORDER 'OF BLOCK^"ERROR - - ^ N o i|^WRlTING?^, >H RETURN }STORE SENTENCE B WORD
NUMBERS IN 0 ,l«1 f\
w/«0

TO WRITE ERROR

EXAMINE Vy «l ol TO DECIDE WHICH SPELLING RULES APPLYSTORE STEM DATA ADDRESStS IN M (IF THERE ARE TWO
STORE
THE ONE THAT GOES WITH THE LONGER STEM
IN M, THE OTHER IN M*) SET MFIN TO I OR 2 ACCORDING
TO THE NUMBfR OF POSSIBLE CASESSET i FOR LONGER ENDING, M FOR SHORTER (IF ANY)SETM'Iv«X
FOR CASE lb o » H j l S f c )OTHERWISE
Q'S8(SEE DISCUSSION OF SPELLING RULES)

L00K
Flowchart 1;-Xs)

IV-3UXCODE=w(w3(a))
a= M mSTORE SEMANTICDATA I N w ( a )ANO £ ( a - 1 H N Oj
a s wgla) i *Go To©
If NOT INTO
THIS BOXa = Ss
v •X

M/i

1

STORE SEMANTICANO SYNTACTIC CODES
IN w(a)TO w(o-3)
AND XCODE IN Yj

SET STEM-SUFFIXCODE TO STEMK

SET STEM-SUFFIXCODE TO SUFFIXSTORE THIS CODE,i, AND ENGLISH
WORD AND NUMBERS
OF I j AS NEXT
"NOT FOUND" ITEM

1

STORE NOT FOUND
CODE IN 0
j STORE As AS DATA ,IN Yj CALL RSSX TO IJLOOK FOR SUFFIXES'.JX?
CALL GCRW«I CALL EXIT }I No*' ERROR -.WRITING V, ' ' IS " v .
Y BUFFER V v ^ - - W T )W^ FILLED^"Yes\ WRITE CONTENTS OF Y I
I BUFFER ONTO TAPE j"j REVERSING BLOCK AT
THE SAME TIME

Flowchart k (continued)

ENGLISH OF Yj
INTO t.
COUNT = NUMBER
OF LETTERS IN t.
RETURN-WORD
TOO SHORT TO
LOOK FOR SUFFIX

i=4

i=COUNT-9v--\*1 i ' H-

a = SsUNSUCCESSFUL
RETURNH a * w 3 (a)a = w 3 (a)STORE w (a)I N YjI

SUCCESSFUL
RETURNa = «K2(a)RSSX

Flowchart 5>

IV-36LEGEND FOR FLOWCHARTS h AND $ - L00K, RSSXThe definitions, unless otherwise noted, are those given in the
Legend for Flowcharts 3 and h (SUFTR, TREET, SUFAD, TRADD).

I now refers

to input text items. Since in the content of L00K s is ambiguous it will
be subscripted with a t when referring to the start of the thesaurus, andan s when referring to the start of the suffix tree.
y

The block of output used as input to the syntactic programs,
indexed by j (though the buffer for this block is too small
to contain all syntax output).

£

Indexes all of the following information connected withpossible stems.
VI

the value of i (the index of the input word).

V

has three fields V , V e , V y indicating whether
possible stems were distinguished by a blank,a final l f e % or a final ,fyn respectively•

VB,VE,VY

contain the address of the data for the stems
distinguished by blanks, f t e % and nyi? respectively.

VL

contains the previous letter (i.e. if VI. = i, VL.
" ti-]L,0

Text output — indexed by j .

XCODE

Suffix code .

M

Holds addresses of stem data .

mIndexes m .

MFIN

Total number of addresses in M uM

Temporary storage .
Note:

The dotted boxes are entered only if syntactic outputs
are desired.

LEGEND

ENTER
c
5

I

CALL HEADR TO HEAD
PAGE. WRITE MESSAGE
THAT ALL WORDS FOUND

SETUP THE
FIRST WORD
OF 0
CALL HEADRI

RETURN |0i1n

The number of words not foundStoroge spoce allotted in I
divided by length per item
Input block from L00K
Output blockIndexes Items in I
Indexes Items in 0
Index of current highest Item
in 0

WRITE J • NO OF WORDS
THAT EXCEEDED STORAGE

LUD-

INCREASE COUNT OFOCCURRENCES OF WORD
0j. STORE THE
SENTENCE AND WORD NO S
FOR THIS OCCURRENCE
IF THERE IS STILL ROOMSETUP OCCURRENCE COUNT,STEM-SUFFIX CODE, F I R S f
LETTER NOT FOUND, SENTENCE
AND WORD NUMBERS OF 0•"Jj
IN OUTPUT BUFFER

G

T:

PRIN
PRINT ENGLISH WORD AND
OUTPl
OUTPUT BUFFER OF ITEM 0 j

NOT FOUND BLOCK

flowchart 6

SET OCCURRENCE
COUNT OF 0 n TO 1
STORE THIS INPUT ITEM
( I ) AS A NEW
OUTPUT WORD (0n)(STORE THE WHOLE
ITEM-ENGLISH WORD,
STEM-SUFFIX COOE,NO OF FIRST LETTERNOT FOUND, SENTENCE
AND WORD NUMBERS)