VI-1

ISR-9August, 1965
VI. THE DICTIONARY SETUP PROCEDURES
M. Cane1.

Introduction
The present section describes the routines used to set up thethesaurus (or concept dictionary).

The specifications for the input deckare explained in detail, including also a discussion of all setup options.
The setup section creates the thesaurus and suffice trees used by thethesaurus lockup programs. These trees are then stored as the first fileof a library tape.

2.

Input Deck, Control Card, and Data Card Formats
Inputs to the setup programs consist of a single control card

specifying what is to be done, followed by additional cards containing
the data for the entries to the suffix tree (if any), and the thesaurustree (if any).
The control card is divided into two fields: columns 1-6 andcolumns 7-12. All fields are left-justified.

Table 1 lists the possible

configurations of these fields and the options they control.

1 First Field
1 col. 1-6
BOTH

Second Fieldcol. 7-12

OPTION
Both the suffix and thesaurus trees
are set up from cards. Nothing isdone with the old tape.

VI-2

First Field

1 col. 1-6

Second Fieldcol. 7-12

BOTHSPACEOPTION
Same as above, except that the fileof the old library tape with thelookup data is spaced over.

COPYAll trees are copied from the oldlibrary tape - no further input
cards are expected.

THES

The suffix tree is copied from theold library; the thesaurus is setup from input cards.

SUFFIX

The suffix tree is set up from input
cards; the thesaurus is copied fromthe old library tape.
Thesaurus and Suffix Setup Control Card Formats
Table 1The suffix data cards (if any) follow the control card. Each card
contains two fields: The first (columns 1-12) contains the English suffix;
the second (columns 13-15) contains a number less than 2 - 256 associatedwith each suffix in a one-one correspondence.

The contents of the first

field must be left-justified (i.e., the first letter of the suffix: mustoccur in column l), and the contents of the second field must be rightjustified (e.g., a number such as 97 consisting of two digits, would appear
as a "9" in column lit, and the "7" in column l£j column 13 would be zeroor blank).
13).

The suffix data thus corresponds to a FORTRAN format of (2A6,|VI-3
The first suffix enteredmust begin with the letter ne,! (c.f., the description of subroutine LOOK in report ISR-7, IV-18).

The termination of

the suffix data is signaled by a card with the letter ,fZM in columns 1-6.
The thesaurus data (if any) appear last. Each thesaurus input
card is divided into 1$ fields. The first (columns 1-2U) contains theEnglish word to be entered, left-justified within the field.

The next sixfields (columns 25-5U) contain the semantic codes (category numbers)
associated with the word.

Each code is allotted five columns, so that thecodes appear in columns 25-29, 30-3U, 35-39, UO-UU, U5-U9, and 50-5U* Eachcode must be right-justified within its allotted field. Records must also
be entered consecutively, starting with the left-most semantic field. For
example, if there are two codes, say 90S> and 237, associated with the word
"CLEAN," these must appear in the first two fields. The card would thenappear as follows:
2 3 k 5 6 7cLEAN12£ 26 27 28 29 J£L_n J£_ J l 3L ^2
9 0 63 1

The category numbers must be less than 2= 32768 in magnitude.

The last eight fields (columns 5>5>-80) contain the syntactic codes
associated with the given word.

These codes must again be left-justified

within the entire syntactic field and must be entered consecutively. Eachcode must be right-justified within its field. The syntactic codes mustobe l e s s than 2• 25>6 in magnitude.

r e a d w i t h a format of UA6, 6 l £ , 813.

The t h e s a u r u s c a r d s may t h e r e f o r e be
The i n p u t words must be in s t r i c tVI-Ubinary coded decimal (BCD) order. The end of the thesaurus data is signaled
by a card with 0-8-5 punches in column 1, and #ENDfc in columns 2-6.

3. Implementation of Setup
The subsection explains how the setup process is accomplished. A
general discussion is presented first, followed by a description of thecomponent programs.

fFirst the suffix tree is created, either from the input data cards,
or by copying the old library tape; the suffix tree is then written onto thenew tape. The old library tape (if any) should be mounted as tape A6, andthe new tape as B$. The thesaurus tree is then created (or copied) and written onto the new tape.
In order to allow a thesaurus of unlimited length, the thesaurus isdivided into blocks by the setup programs. Each block approximately fills
the space allotted to the thesaurus in the lookup link. All words beginningwith the same letter must fit within one block (see description of TIPUT,below). A block may contain words with different initial letters. Allwords beginning with a given letter are read in as a unit. They are added
to the block now being created if this can be done without exceeding thestorage allotted to this block. Otherwise, the present block is written
onto the tape, and a new block is started.

This process is repeated until

For a general discussion of tree structures and their use in the SMART
lookup schemes see Report No. ISR-7* Section IV.

vi-5
all the input cards are exhausted*

A word is associated with each block

gives the highest (relative to the BCD ordering) initial letter of any \ liich
word in the block (c.f., description of subroutine LOOK below).
The following programs comprise the dictionary setup routine:(1) SWRITE and SREAD respectively write and readthe suffix tree. They have one argument,specifying the top location of the tree*(2) TWRITE and TREAD, respectively, write andread a block of the thesaurus.

They eachhave two arguments: The first specifies
the top location of the thesaurus block;the second is the highest initial letterof the block.
(3) SUFTR sets up the suffix tree. It is describedin detail in report ISR-7, IV-U. SUFTR hasfour arguments: The first two indicate wherethe input starts and how many items are included.
The last two arguments are returned by SUFTR.
The first of these gives the top location of thetree.

The last, if positive, indicates the numberof unused locations allotted to the tree. If thelast argument has a negative sign, it gives thenumber of locations by which the tree exceeded its
allotted storage.
(10TREET and TRADD set up the thesaurus tree. Theformer is an entry for starting a new tree (or anew block), and the latter adds to an existingtree.

They each have three arguments, corresponding

to the last three arguments of SUFTR.

These aredescribed in detail in report ISR-7, IV-I4..

TIPUT and TIRJT1 read in the thesaurus data and convert
the semantic and syntactic codes to the proper internalformat. The semantic codes are packed two to a "word indecrement and address respectively. The syntactic codes
are packed into eight 8-bit fields, with the fifth field
split between two words. The last eight bits of thesecond word are left empty.
TIPUT1 is used as initial entry to TIPUT. Bothprograms have three arguments, all of which are createdby the programs themselves. The first is a flag whichis zero for a normal return, negative if the program
returns because its buffer is filled, and positive if thecard signalling the end of the thesaurus inputs has justbeen read. The second is the counts of words put into
the buffer, and the third indicates the initial letter ofthe words in the buffer. TIPUT reads-in all and only
those words beginning with the same letter before returning
control (except for the case where its buffer is filled
before this is accomplished, corresponding to a negative
first argument).
TIPUT also checks to see if the word just read-in
begins with a letter different from the initial letter ofthe previous word. To do this, a word is set up whose
first 6-bits contain the last initial letter found andwhose remaining bits are all "on." The initial machine
word of the next English word is compared against this word;
if the former is greater, a new initial letter is present;
if not, the present letter is taken to be the same as theprevious letter. This procedure implies that the deck neednot be in strict BCD order; in particular, it will sufficefor the cards to be in order with respect to only column 1.

vi-7

©
10
CALL SREAD
TO READ OLD
TAPE SUFFIXESCALL SWRITETO WRITE NEW
TAPE SUFFIXES
tl2_
CALL TREAD
AND TWRITE
TO COPY A
THESAURUS BLOCKl4)

ERR = 0
READ IN PARI, PAR2
TRANSFER ACCORDING

COPYSUFFIX-*©

TO PARIBOTH » ©
THES—» ©

^©

®

®

_30_
CALL SREAD
TO SPACEOVER1SUFFIXESCALL SREAD
CALL SWRITE

J±0_

READ INSUFFIX LISTf2L
CALL SUFTRTO SETUP
SUFFIX TREE15SL
CALL TIPUT1(IROV.KOUNI.FLET)
yfifi-no.

I0RETURN

ERR = 1WRITE ERROR MESSAGE
SENSE LIGHT 1 ON

WRITE MESSAGE
GIVING STORAGE
REMAINING

Subroutine CANE - Supervisor For The
Dictionary - Thesaurus Setup
Flowchart 1

Vl-864

CALL TREAD TOSPACE OUTOLD TAPEf

RETURN

Flowchart 1 (continued)

VI-9\51
IRW = IROVFLETT = FLETCALL TIFUT(lROV,KOUNT,FLET)|

i60
ENDTT=ENDTFLETT=ENDEND|KPARS=(K0UNT/9)xll^©

_2k
CALL TVJRITEFOR THISTHES BLOCKXyX

6l
CALL TRADD(KOUNT.ENDT.ISION)$ISIGNWRITE MESSAGE
GIVING SPACEREMAINING IN
THIS BLOCK,AND:LAST LETTER IN
62
2LQJ
BLOCK
ENDT=

^M

5k

EiffilTJ

WRITE ERRORMESSAGE-THIS
LETTER WON'T F I T
IN ONE THESAURUSBLOCKSENSE LIGHT 1 ON

2L
CALL TIFUT
TO SPACE OUTINPUT TAPLCALL TREET(KOUNT.ENOT.ISIGN)

4RETURN
yes

Flowchart 1 (continued)

noVI-10

If the dictionary were to become so largethat all words beginning with a given letter could
not fit in one block, it would be necessary tobase a division into blocks on more than just theinitial letter. This can be accomplished bychanging the parameter MASK in subroutine TIPUT toensure that the first two letters, for example, betaken into account. All further tests (i.e., thosein LOOK) work properly, no matter what the blocksubdivision turns out to be.
(6) CANE is the supervisory program for the dictionary
setup.

It is the only program called from the mainprogram. Flowchart 1 describes the details of thisprogram; a few additional remarks may be needed.
The numbers appearing above the upper right-handcorner of some of the boxes key the flowchart tothe statement numbers of the program.

In case oferror, sense-light 1 is turned on to inform themain program.

The test in the box labelled ,fHnseeks to determine whether the words just read-in
can be added to the block without overfilling it.
The test is based on the empirical estimate thatan item takes an average of eleven locations whenconverted to tree form.

If this test indicatesthat these words probably will not fit in theblock, control is transferred to the box labelled
ft

G,M to initiate a sequence which writes out thepresent block and begins a new block with these
new input words.
If the test succeeds, control passes to theblock labelled M 6l, M which adds the new words to thepresent block of the tree* A new test is then performed to make sure that the allotted storage has
not been exceeded.

If it has, the end of the blockis reset to the previous point (box 62), and control
is transferred to the sequence -which writes out theblock.