ISR-7
June 196U

II•

II-l

THE SMART SYSTEM- GENERAL PROGRAM DESCRIPTION
Michael Lesk

1 • Introduction
SMART (Salton1s Magical Automatic Retriever of Texts) is a
programming system designed to help evaluate proposed information retrieval systems. It includes many different methods for analyzing acollection of English documents and answering search requests.
Sets of input documents and requests are processed in two steps.
Step one involves the reduction of the document to a form useful formachine analysis, including its representation by a list of "concepts" andassociated "weights". If all knowledge is assumed to be representable asa kind of n-dimensional space, any piece of information in the text may
be found by a displacement within this space in some given direction*, Thedifferent directions are identified by "concept numbers," of which up to
1,000 may be defined; each document is then represented by a vector in thespace of concepts. As a low order approximation, concepts may be equatedwith text words. The programs incorporated into SMART provide, however,many ways of eliminating or mitigating the ambiguities and duplications
inherent in this approximation.

The weights attached to the concepts m^ymerely reflect the frequency of occurrence of the concepts, or can be
adjusted in several ways.
The representation of a document by a concept vector permits step
two of the retrieval system to operate. This step compares vectors representing

II-2
retrieval requests (whose treatment is in general identical with that ofreference documents) with document vectors, and produces lists of "answers,"
Should results prove unsatisfactory, various options permit systematic
alterations of the request to produce different answers.
The value of the system lies in the variety of methods that may
be used at each step* The methods include many of the schemes that haveappeared in the literature and thus make SMART particularly useful forcomparing such proposals.
In step one, the reduction of English text to cancept-veator format,
the programs must first read the text and convert text words to concept
numbers by reference to a dictionary.

If one wishes to treat each distinct

English word as a distinct concept, one supplies the program with a Mnullw
thesaurus assigning to each word a distinct number.
be generated automatically.

Such a thesaurus may

If, on the other hand, one wishes to consider

a priori relations believed to exist between words, one must of course supply
the program with a hand-constructed dictionary*. This dictionary may assign"orthogonalized" concept numbers, or, alternatively include complex interrelationshipso

Each word in the SMART dictionary, or thesaurus, may map

into six different concepts, and each concept can represent any number ofwords•

Phrase searching procedures are used to group any collection of

specified words and syntactic relations into a single concept, and concept
relationships may be stipulated in a hierarchical form. Alternatively,
concept relationships may be obtained from statistical criteria, which makeno assumptions about the a priori meanings of words. In fact, except for
keypunching problems, many of the SMART options could function for foreignII-3
language texts, without requiring the researcher to know anything aboutthat language.
Request answering may also be handled in many ways.

The fundamental

procedure is to compare requests with documents by one of three correlation
methods.

If this proves unsatisfactory, however, concept vectors can bealtered in several ways*

Statistical criteria can be applied to detect

relationships between concepts, or a priori hierarchical relationships may
be given in tree structure form.

Such a tree structure may be used totransform the concept vectors in several ways, all alterations of requests
are followed by a recomputation of the correlations and a new analysis ofrequest answers.
The two-step process can thus be visualized as consisting of intradocument and interdocument operations. When all intradocument processing
is completed, the resulting concept-vector may be punched into binary cards.
These binary cards, called the document "list" of concept occurrences, canbe read into the machine 100 times faster than the unprocessed alphabetic
text, and can then be used for all interdocument operations.
Various types of concept vectors may be produced by the intradocument
processing, depending on the thesaurus and the processing options which arecalled into play.

For example, if "orthogonalized" concepts are used, inwhich each piece of information has unique representation as a concept vector^
correlations may be performed immediately. Alteration of the request vector
would necessarily change the meaning of the request and might then be of little
direct usefulness.

On the other hand, if a null thesaurus is used with nophrase-finding options, each text word will have been replaced by a distinct

II-l;
numeric code. Additional processing of the resulting concept vectors mightin this case be quite profitable.

Processing options are discussed indetail in the other sections of this report.
The programmed version of SMART runs on the IBM 709H under a FORTRAN
II monitor.

Twelve tapes are required if all options are used:Bl-6 (including FMS tapes).

Al-6 and

32K core is essential. The Harvard monitor

system is an almost standard FORTRAN II system tape, but persons desiring
to run elsewhere should read the section on "Operational Details" carefully.
SMART is a chain job, with up to seven processing links, plus two
links for writing a library tape with the necessary dictionaries.

The links

are numbered 11,10,1,2,3,ii,5,6,7. The preprocessor which writes the librarytape, consisting of five files is programmed as links 11 and 10. The firstlink, 11, writes the first file of the library, which includes the thesaurus
and its suffix lists. Link 10 adds four more files, which are (in order),another suffix list, a dictionary of phrases specified by syntactic/
semantic/structural information, a dictionary of phrases specified only bysemantic information, and the tree structure (hierarchy) of concepts. Once
generated, the library tape may be mounted on the proper tape drive and thefirst two program links omitted.
After the library is written, control passes to link 1, the mainlink in SMART. This link contains all request answering programs, theconcept vectors for all documents, all statistical programs, the systemsupervisor, and much else. Logically, all other links are merely long subroutines called by it. Link 2 performs dictionary lookups; during its

n-5
execution, link 1 is saved on a scratch tape. Links 3-7 perform syntactic
analysis of texts and phrase searching, using phrases specified syntactically and semantically.

In this five-link section, links 1+, 5, and 6 containthe Kuno Multiple Path Syntactic Analyzer, described in The Computation Laboratory of Harvard University Reports NSF-8 and 9.
for the analyzer.

Link 3 is a pre-editor

Link 7 compares the syntactically analyzed sentences tothe library of phrases, using the Sussenguth structure-matching programs (seeSec. VIII of this report).

The remainder of link 7 handles format con-versions and bookkeeping.

The main program is again on a scratch tapeduring these operations. The figures show the flow of data from tape tocore in the various links, as well as the compiled tape assignments. On the
Harvard system tape, Al contains the FORTRAN monitor, A2 is the card input
tape, A3 the off-line print and B)4 the off-line punch tape.

2.

The SMART Library Tape
The five files of the SMART library tape, as previously indicated,

are written by the first two chain links of the program.

The first file,which is used for each text or request submitted in English, contains thethesaurus.

This thesaurus is used by chain link 2, the lookup, in trans-

lating English into concept numbers. The first file contains four records:
two label records, the thesaurus, and a suffix tree used to assist the thesaurus.

The only function of chain link 11 is to write the thesaurus file5

the corresponding program deck should be the first binary deck in the job
if a new library is to be written.

It exits to chain link 10, which writes

the remaining four files. The second file contains another suffix list.

II-6
used to obtain syntactic information in link 3» the preprocessor for the syntactic analyzer.

This file is written by subroutine UPSUFF. UPCRIT is thenext subroutine called; this routine writes the dictionary of criterion trees
onto the library as the third file; each tree appears as a separate record.
The criterion trees further described in a later section by Lemmon definea phrase by its syntactic, semantic, and structural content.

Chain link 7

will compare this file with the syntactically analyzed sentences to detectphrases.

Another, less accurate, phrase dictionary is written as filenumber four by subroutine CRITS2, in records of 100 phrases. In thisfile, a phrase is defined only by its constituent semantic concepts, without syntactic or structural information. A quick, rough search can thus
be made by subroutine PHROCC to detect phrases, without calling on thesyntactic analysis programs. The fourth file is also used by the syntactic
routines for additional information about the syntactic phrases which arefound.

Finally, the fifth file, written by subroutine GEORGE, contains

the concept hierarchy. All concept vector expansions through the hierarchy
use this file, which consists of two records (see Sec. V of this report).
In general, each of the update subroutines expects to find an old
library tape on A6, and correction cards on A2 (system input tape), before
writing a new file in B5, and spacing A2 and A6 forward to the next file.
In order to get started, options are provided for writing files entirely
from cards. If a subroutine detects an error in the correction cards, anindication of this is given on the print tape and sense light one is turnedon as a signal to the update main program.

Execution is terminated afterII-7

updating if sense light one is found on. Otherwise, the tapes are rewound
and the run proceeds as if a library tape had been premounted on B3>.
In using a null dictionary, there is no need for syntactic tables
or hierarchies; only the dictionary is of significance»

To avoid the un-necessary writing of all five files, chain link 10 may be omitted from a run
and link 11 may be used alone. In this case (since link 11 will try to calllink 10 at exit), the main link (usually link l) may be renamed link 10.
This requires only the change of the *- CHAIN (l,li) card to * CHAIN(10,U) andwill not disturb any other part of the system. Alternatively, a dummylink 10 might be supplied.
It should be noted that A6 is used both as an intermediate tapeduring syntactic processing, and as the unit for the old library tape in
updating.

Thus, if syntactic processing is done in the same run with up-

dating, the old tape may not be file protected.

Care should be exercisedin using this combination of options.

Summary of the 3^[ART Library Tape (See Fig. 1)
File 1. Four records:

one-word label, thesaurus (approximately

six machine words per entry), one-word label, suffix list.
File 2.

One record.

Suffix list with syntactic information *Approximately 255 machine words.
File 3o

One record per criterion treeo

Criterion trees withsyntactic/semantic/structural specifications.
For simple trees, about 10-20 machine words per tree.

II-8

New
LibraryOld
Library

Diagnostic
Messages

Programs
Links 11,10,1

Other
Programs

Update Instructions
ADDENDA, Corrections
or Complete Files
Output Library

Link

11

File .1:
Four Records

Thesaurus (English* concept numbers + syntax
codes) Suffix list (suffixes- frsuffix numbers).

File 2:
One Record

Suffix list (suffix numbers

File 3:
One Record/
PhraseCriterion trees for phrases.
Complete semantic/syntactic/structural phrases,

File U:One Record/
100 Phrases

Statistical phrase search data.
semantic specification.

File $\

Hierarchy.
Concept tree structure, with crossreferences,^syntactic codes).

10

One Record

Dictionary Update System
Figure 1

Phrases with onlyII-9File iu

100 phrases per record•

Four words per phrase • The

last record is short• All records have a three word label in front ofthem.

Semantic phrase data.
File 5*

Two records. Five-word label; then hierarchy and cross-references 0

3*

The CHIEF Supervisor
After the optional updating is completed, general control of the

SMART system passes to link 1.

This link contains all data accumulated

for documents in each run, all statistical and hierarchical programs, therequest answering programs., and many general housekeeping routines• Link 1
reads all input cards, writes all of the punch output and most of the print
output•
The most inportant program in this link is the supervisory program
called CHIEFo

Its function is to call the subroutines responsible for thevarious processing options as needed, and to see to it that all necessary
tables, flags, and constants are kept up to date. CHIEF makes its decisions
for processing on the basis of the current input on A2 and the options
chosen at the beginning of the niDo
Three main phases of the program are recognized*, The first is a
short initialization stage*

Its major task is to read the list of options

and parameters for this run from the input tape, and to decode it* Various
tables and constants are also read in and set up internally*. The second
stage is devoted to absorbing the document collection for this run*The

mixture of English texts and preprocessed documents is read in and processed11-10as required by the preset options. When the whole collection is present inconcept-vector form, CHIEF passes to the third stage, that of retrieval
operations.

The programmer may choose any of the various retrieval options

available, or omit this stage entirely.

The three stages are described in

the next several paragraphs.
A.

PHASE I:

Initialization

Before the required options can be read in, some housekeeping must
be done. Numerous flags are set equal to zero, lights turned off, andtapes rewound.

The current time is recovered through CLOCK, the date through

DATEIS, and the first page heading is written (by HEADR).

The most signifi-

cant call is to TAPENO to set up the tape instructions in all subroutines.
When these instructions are set, the program can proceed to read the input
tape.

Subroutine NAMES reads the first batch of data consisting of thelist of identifiers for the concept categories.

This list, stored in array

RONAKE, is used by the program whenever a concept number must be referredto; the six character name, rather than the number itself, is always printed.
CHIEF now calls subroutine SETFLG to perform the major task of thisphrase, the decoding of the control cards specifying all the processing
options.

These control cards follow the list of concept names (or the * DATA

or library cards if the optional names list is omitted).
must precede all documents.

The control cards

11-11Each specification is represented by a string of up to 2k BCD
characters plus blanks as desired by the programmer, and separated by acomma from any other specifications.

There exist four classes of speci-

fications, as follows:(1) Instructions to set a bit in a control word called
FLAG (octal 77i|6l) corresponding to a yes-no processing choice; a flag bit would thus control output
printing of the list of words not found in dictionary,or the mode of concept expansion (addition or replacement of terms).
(2) Instructions to set a program parameter to somenumerical or logical value. A typical numericalparameter would specify the value of a cutoff in somecorrelation procedure; a typical logical parameter
might correspond to the method of hierarchial expansion(sons, parents, brothers, or cross references).
(3) One specification that writes an identifying card on
the punch tape.
(k)

Erroneous specifications, which produce nasty messages
on the print tape.

Type 2 specifications are punched as a string of charactersgiving first the six character parameter name, and then its desired
value.

The whole string may be prefixed with SET PARAMETER if a morereadable output is wanted.

For example, to specify the cosine corre-

lation mode, one punches CORMOD COS or SET PARAMETER CORMOD COS. To
set the maximum concept number to 37U, one writes MAXCON 37U or SET
PARAMETER MAXCON 37U-

At present there exist 35 type 1 specifications,ten of type 2, and one of type 3«

A debugging specification, also of

11-12type 1, raises the total to U7oEach type 1 specification may be written

in two fonns, a long, readable form and a short, easy to keypunch form, adding up to a total of 9U legal specifications. A list of these options isgiven in Table 1; they are also further discussed in the text.

B,

PHASE II: Document Absorption
In this phase CHIEF supervises the read-in and processing of all

documents•

The input tape consists of documents, in binary or BCD fonnat,

separated by instruction cards for CHIEFo

These instruction cards aremarked by an # in column one, and are not to be confused with the specifications to SETFLG discussed in a previous part of this section. €HIEF
reads instruction cards until it finds one that refers to a document; at thatpoint transfer is made to the appropriate subroutines for processing*
Each instruction card is identified by an * in column one, a four
letter code in columns 2-5, and a blank in column 6*

If the instructionrefers to a document, the document is specified by a twelve-character namein columns 7-18.

The remainder of the card is available for comments. The

eight instructions are:(1) *NOTE Comment cardo(2) *TIME

Columns 7-72 printed, card ignored*

The current time is printed.

(3) ---STOP Begin phase III; no more documents on tape*,(ii) *RAND

DOCUMENT NAME

Generate a pseudo document withrandom occurrences of random concepts and use it in
all operations as if it were real.

CHIEF calls aninternal subroutine, NAMEIN, to enter the documentname into the tables, and two external subroutines,

11-13

Short Form Bit
Affected in Flag

Long Form
Across the board

AB

All analyses
Answer requests

AA 28
AR 8

Cluster concepts

KC

Cluster documents

KD 12

Clustering search

CS 22

Concept correlations

cc

3

Concept frequencies

CFhConcept relations

CR

2

Criterion trees
Document relations

CT 27
DC 15
DR 13

Edited Answers

EA 18

English texts

ET 35
ES 19
FC XXXXXX

Document correlations

Execute syntax
Flip card XXXXXX

All debugged bits

1

Hierarchical vectors

HE 10
HV 11

Logical vectors

LV 21

Merged clustering

MK 17
PF 16

Hierarchical expansion

Phrase frequencies
Phrase search
Punch document data
Replace by hierarchy

See note following

PS 26
PU 23
RH 9

Set parameter

RS 2U
RC 111
See note following

Smear concepts

SC

Smear replacingSR

Replace by syntax
Request correlations

7
6

Processing Specifications
TABLE 1

n-iU&

Affected in Flag

Smeared vectors

SV

5

Statistical clusters

SK

30

Statistical trees

ST

25

Syntactic analysis

SA

Term correlations

TC

29
32

Term relations

TR

Texts processed

TP

Word frequencies

WF

31
20

33
NF 3U

Words not foundThe effect of the specifications above is generally given byimagining the long form prefixed by print. The excepti ons are obvious.
The specification flip card does not cause any 1
bits of flag to
be set. Flip card causes the next six nonblank characters to be punchedin a flip card.

If six nonblank characters do not precede the next comma,

blanks are used as fill.

Do not use special characters other than the

8-5 punch, which is blanked.

These flip cards are punched immediately.

Set parameter sets up constant for the program t and sets mode
mode switches for correlating and expanding.

Type "Set parameter PARAMX

value" or just "PARAMX value", where blanks are ignored and value is tobe set as the value of PARAMX possibilities are:Parameter Values
GOTREE

Root, branch, filial, refer

CORMOD

COS, ASYM, OVLAP^^^TABLE 1 ( c o n t i n u e d )

J

n-15
Parameter Values ( c o n t i n u e d )CUT0F3CUT0FF times 10,000 f o r document-document
correlation
CUT0F1Same f o r term-term c o r r e l a t i o n

CUT0F2Same for c o n c e p t - c o n c e p tcorrelation

MAXCON Highest t h e s a u r u s number
At l e a s t one s p e c i f i c a t i o n t h a t produces o u t p u t should be givenof c o u r s e .
TABLE 1 ( c o n t i n u e d )RANDOC ( t o g e n e r a t e the random document), and RELOC( t o e n t e r i t s concept v e c t o r i n t o the documentconcept m a t r i x ) .
(5)---LIKE DOCUMENT NAME The document whose name i sgiven

i s marked a s a r e q u e s t , by i n t e r n a l s u b r o u t i n e NAMEIN.
NAMEIN m a i n t a i n s t a b l e s of document names (NAME1 andNAME2) p l u s a t a b l e of f l a g s for each document (DFLAG).
The name s p e c i f i e d on t h e -x-LIKE c a r d i s looked up i n
t h e t a b l e s , and the c o r r e s p o n d i n g DFLAG e n t r y i s s e t t oindicate a request.
(6)-*LIST DOCUMENT NAME A document i n b i n a r y form follows
on the i n p u t t a p e .

CHIEF c a l l s s u c c e s s i v e l y :LISTINt o r e a d the document, MERLST t o p r e p a r e i t for a d d i t i o n
to the document concept m a t r i x , and RELOC t o performt h e a d d i t i o n of the document to t h e c o l l e c t i o n .

11-16(7) *FIND DOCUMENT NAME

Equivalent to a *TEXT foil w e d

by a ---LIKE, with minor differences.

The most importantdifference is that a document looked up by a ---FIND
rather than a #TEXT will not be punched out in processed
form; for this reason, the use of this instruction
should be avoided.
(8)#TEXT DOCUMENT NAME

Standard method of input for an

English text. Initiates all processing for the additionof a document to the collection.

The decoding of this

instruction in accordance with the specifications from
SETFLG is the major job of phase II and is described below.
Control passes first to subroutine SEGMNT to read in the text. If
the ENGLISH TEXTS(ET) specification is given, sense light one is turned on
to indicate printing of the input text. The text must now be looked up
in the dictionary; this is done by link two, the lookup.

Subroutine

LINKUP, internal to CHIEF, dumps most of core onto kk as one, self-loading
record.

Since this record is over 20,000 words long, tape writing errors

are relatively frequent.

Five consecutive attempts are therefore made tocomplete the read or write operations in case of error. Before calling
link2, sense light four is turned on if the specification WORDS NOT FOUND (NF)
was previously given, causing the printout of the words not found in the
dictionary.

Sense light three can also be turned on, telling the lookup

to write a tape of syntactic information for link 3> the analyzer preprocessor.

This tape writing is normally suppressed by means of the NO

SYNTACTIC PROCESSING option (NS).
On return from the lookup, the program proceeds to the statisticalprocessing of the text.

Subroutine MATRIX tabulates the occurrences ofconcepts within sentences; this list is printed by subroutine WFREQ if

11-17
WORD FREQUENCIES (WF) is specified.

ROWSUM and ROCOR now compute term-

sentence correlations, giving a measure of similarity between any twoconcepts based on their co-occurrences in the same sentence.

The cor-relation may be done in any of three ways, selected by the type two specification C0RMD1. This specification can take the three logical values:
COS, ASYM, OVLAP.

These modes are further described as part of the stati-

stical processing.

Correlations may be printed by subroutines WCORR and

WCORND if TERM CORRELATIONS (TC) is specified. MCORR and FRIEND are subroutines, not directly called by CHIEF, to convert the correlation vector
into a list of concepts related to each concept in the text. This list is
stacked in core (the actual correlations are not preserved), and the TERM
RELATIONS specification causes WGROUP to print it. An attempt is now madeto synthesize clusters of terms and count them as units. The subroutines
involved are: CLUMP, CLSMAP and CDENSE, and the specifications involved
are STATISTICAL CLUSTERS (SK) to print the clusters, and CLUSTERING SEARCH(CS) to initiate the entire operation.

If abstracts or titles are processed 9

rather than complete documents, the statistical clustering procedure isinapplicable and NK is specified every run. A subroutine called NOCLMP handles
housekeeping details normally taken care of by CLUMP.
The statistical clustering procedure is important even if not used,however, because of its effect on the processing mechanism.

From this point

on,the program must permit the handling of term clusters as well as single
concepts;a new numbering scheme is therefore introduced.

The document isrepresented in terms of intermediate "cluster numbers" which may stand for
either a cluster or a single concept. A table called MAPKLS is used to store
the data necessary to convert cluster numbers to concept numbers.

11-18CHIEF now i n i t i a t e s the counting of the occurrences of the "clusters' 1(which may be singLe concepts) by c a l l i n g KCOUNT.
phrase detection systems may be c a l l e d .

At this point one of two

The f i r s t i s the f u l l syntactic

system using the Kuno multiple-path syntactic analyzer and the graph*matchingroutines of Sussenguth.

The syntactic processing i s called i f EXECUTE SYNTAX(ES) i s specified a t option time.

The f i r s t analysis produced by the Kuno

analyzer is p r i n t e d if option SYNTACTIC ANALYSIS (SA) i s exercised;

ALLANALYSES(AA) m i l print a l l syntactic analyses.

CRITERION TREES (CT) p r i n t s the l i s t

of t r e e s found to match any t e x t excerpt.

To enter the syntactic system,

CHIEF dumps i t s e l f on Ait, and c a l l s in link 3 (BTOKUN) from B3-

BTOKUN reads

the syntactic information from tape A6 and prepares an input tape to the
Kuno analyzer (using f i l e 2 of the l i b r a r y on B£) on unit B6.

Control i sthen turned over to link k (SETUP), the f i r s t p a r t of package B of the Kuno
analyzer.

SETUP, using the condensed grammar tape on A£, prepares a binary

sentence tape on Bl.

SYNTAX, l i n k 5, i s now executed; t h i s produces a binary

analysis tape on B2.

Link 6, the f i n a l part of the Kuno analyzer (EDIT),w r i t e s a BCD output analysis tape on A6. Finally, link 7 compares t h i s
analysis tape with the c r i t e r i o n tree dictionary i n f i l e 3 of B5, and leaves
a table of detected t r e e s i n core for CHIEF.

A detailed description of t h i s

process i s given as part of the syntactic section by Lemmon.
A l t e r n a t i v e l y , the cheap phrase finder may be used.

This subroutine,

PHROCC, uses the fourth f i l e of the l i b r a r y tape, in which phrases are defined
merely as a pair or t r i p l e t (up to s e x t e t ) of concepts co-occurring in a single
sentence.

PHRASE SEARCH (PS) specifies t h i s search, and STATISTICAL TREES (ST)

11-19prints the results.

This is described in a later section by Evslin andLesk.
At this point each given document has undergone all the intradocument processing possible. A minimum of ten seconds is required for the
lookup operation, and up to perhaps two minutes for the full syntactic processing.

To save time on a subsequent run, each document can be punched out

onto binary cards by LSTOUT.

This punching is controlled by the PUNCH DOCU-

MENT DATA (PU) option. The deck punched in this operation may be resubmittedwith a ---LIST instruction in future runs. When a binary "list" of concept
co-occurrences is used as input in this manner, LISTIN restores the internal
concept vector as it existed previously at the same point. The SMART system
no longer knows or cares, whether the document was read in using a ---LIST or-*TEXT control card.

The programmer should be careful, however, to avoid

mixing documents looked up in different thesauruses, as the concept numbers
may not represent the same concepts. Each document concept vector is now
added to the complete collection.

Since term clusters may have been generated,

the program first examines all "cluster numbers" to see whether they represent
single concept numbers from the thesaurus, or groups of concepts combined by
the clustering programs.

True clusters (i.e. clusters of more than one

concept) are compared with the clusters previously detected in the collection.
If a cluster previously detected reappears, it is "merged" into the table ofterm clusters by identifying it with its previous version.

Clusters are

considered identical if they are "almost" the same members; "almost" being
defined as
number of common members

r, ^

> uo
/ p r o d u c t of size of each c l u s t e r

11-20A new cluster which does not "match" any older cluster is added tothe end of the combined cluster list*

To avoid confusing such a clusterwith a true thesaurus concept, it is assigned a "fake" concept number, higher than 1,000.

An element of the concept-vector of a new document corre-

sponding to a single thesaurus concept is entered directly into documentconcept vector, as under its proper concept number.

The bookkeeping needed

for the comparison and counting operations is performed by subroutine MERLST.
Finally, RELOC and a subroutine called FILLIN, copy the processed
document vector into the document-concept matrix^ DOCWRDo

Control now returns

to the instruction card interpreter in CHIEF and phase II proceeds with thenext documento

Co

PHASE III: Request Answering
After the appearance of a *ST0P card or an end of file, no further

documents are read in and the processing of requests begins. A list of
documents submitted during the present run can first be printed (using the
TEXTS PROCESSED (TP) option), followed by a table of the merged statisticalclustering, if any (using the MERGED CLUSTERING (MK) specification). The
program then correlates the document concept matrix to get document-document
correlations. These are obtained and printed for all documents if DOCUMENT
CORRELATIONS (DC) is specified; documents whose correlation exceeds thecutoff are printed if DOCUMENT RELATIONS (DR) is given as an option. CLUSTER DOCUMENTS (KD) causes the program to cluster the documents into groups.
Normally, one is interested in the response of the system to retrieval
requests. ANSWER REQUESTS (AH) causes the program to correlate the request

11-21vectors, and print all documents having correlations higher than theparameter CUT0F3*

REQUEST CORRELATIONS (KC) will produce the correlation

vector as output.
Two principal methods can now be used to alter the original searchrequests•

The first of these consists in using concept-concept correlations;the second, hierarchical expansions«

If concept-concept correlations areto be computed, the program first transposes the document-concept matrix bysubroutine TRANS, to obtain a matrix useful for concepts rather than document
processing.

Subroutine CONCOR carries out the concept correlations using

ROCOR and ROWSUM.

The options CONCEPT CORRELATIONS (CC) and CONCEPT RELATI-ONS (CR) are used to print the corresponding data*

The actual request

alteration is performed by subroutine SMEAR, which adds to the original
concepts of a request, new concepts which are related to theme

This expansion

is produced by the SMEAR CONCEPTS option (SC), and its results are printed
by

the SMEARED VECTORS (SV) specification. The requests are recorrelatedusing the altered concept vectors after this procedure, and new answers
are produced•

Programs are being written to provide for contraction as well

as expansion of the search request using concept-concept correlation] options
CONCEPT CLUSTERS (KC) , and REPLACE BY SMEARING (SR) control these alterations.
The correlation mode and cutoff parameter are set by C0RMD2 and CUT0F2
specifications of type 2*

Additional processing details are included in

the sectiqn on statistical processing0
Hierarchical expansion is performed through subroutine TREESo

It isinitiated by the option HIERARCHICAL EXPANSION (HE) and its details may be11-22
printed by means of the HIERARCHICAL VECTORS (HV) specification. Eachdocument concept-concept vector is extracted from the document concept
matrix, transmitted to the hierarchy programs (Sec. V) and returned tothe matrix after alteration.

The parameter GOTREE may be set to any of

ROOT, BRANCH, FILIAL, or REFER to specify the direction of hierarchicalexpansion, and REPLACE BY HIERARCHY (EH) causes the program to use the
new concepts instead of (rather than in addition to) the original ones
included in a request.
Phase III currently ends with the hierarchical expansion, andSMART returns control to M S .

One more option, EDITED ANSWERS (EA) follows

at this point, producing a final, well edited output page of answers to
the search requests.

The coding of the option is in process.

A complete chart of the SMART system flowcontrol, including a specification of the various phases and processing sections is shown in Flowchart 1.

k.

Text Read In and Lookup
English text is read into the SMART system by a subroutine named

SEGMNT.

SECMNT processes text punched in columns 1-72 of BCD cards;

columns 73-80 are ignored.

Consecutive blanks are treated as a singLe blank.

A blank is assumed between column 72 of one card and column one of the next
card.
Punctuation marks should be punched as follows:comma - directly following a given word in a sentence,as is normally done in typing.

PHASE ONE
Start

CLOCK
DATE ISHEADRTAPENO

9—@

Reod Toble Of Concept
Identifiers

NAMES

Add I t s Vector To
Document Concept
Motrix)PHASE TWO

Read Instruction
Card

| No

(

Print
Card
Tronster According
To First 6 Columns
Of Card
NOTE
TIME
RAND
FIND
LIKE
LIST
TEXT
STOP

Add Document NameTo Name Tables*)

Print Card A n d \Messagey

RELOC
FILLINI-®
©—H

Was I t Valid?

RANDOCAdd Its Name To List
Of Document Names

I
Yes/

-©

J

Read Specifications
idV—(g) SETFLG
Set Up Flag Word And
Parameters

©-

\
J

Generate A
Document Using
Random Number
Generotor For
Concepts

I

<Z

Real
ClQCK
Print
Time

Initialize
Time-Of-Day
Oate
Page Heading
Tope Commands

~

J*
V

<Bh

Clear Core Areas
Turn Off Switches
Rewind Topes:

Flag As RequestI-*fo3) ERRORLEGENDOPERATIONS PERFORMED
MAIN PROGRAMIN

CD

OPERATIONS PERFORMEDIN SUBROUTINE NAMED TO THE RIGHTCD

DECISION

System Supervisor
Flowchart 1

/Ry__J[^(/

LOOKUP

\

J

V.

Tftit

J

(

V-

V ThesaurusJ ^Write,X
As Needed,
VSyntax And
I
Words Not
JFound_^/Enter Document
Nome In Tables

Read Binary
Cards ForX
V

Documenty@ LISTIN/ " C o r r e c t Cluster * \(Numbers To Match j\ £ o l l e c t i o n Numbers,/

C

Rgal

Scorch Tables
For Document Nome
And Flog As
RequestAdd Vector To
Document Concept
MatrixRestorec

MERLSTr \ — J
Was Core
V
W\Restored P r o p e r l y ? /

X
)
J

RELOC
FILLIN

Yes

I No

®
Any Term - Sentence
Statistics?
( W F * T XCvr T R
R **SSrr<<v*C9 SS On?)
No
I Yes
[N<

€>-

(

Read I n p u P X
English Texti
Print It I f
J
^
ET On
y

I Was I t R e a d \ No
Y Correctly? j
1 Yes

©
H @

®

SEGMNTSTATISTICS

Kg)

Convert Looked-Up Text To^v
Concept-Occurrence List
J

\Concept Occurrences
LOOK

CD-

UP

Dump Core
On A4/ Was Dump \ No
Vsucessful ? /

( Is

Kx)

JYes

/

T

MATRIX^~s

TCv S K v T R v CS On?

)

No

-H®

1 Coll Link 2
Set Sw itches^
ES For Synta> ( —•- Sense Light 3
BNF For Words Nol Found
Sense Light 4 1

1

)

C

Surr
m Occurrences
Ot Conecepts In Sentences
fl Mode Chosen Bv CORMDI
V
C o r r e l a t e According
To CORMDI

(
/if

TC

A
/

Print Correlations(

1

A n a l y z e Correlations By
C o m p a u n g With C U T O F l .
.Construct Relation List

Flowchart 1 (continued)

ROWSUM)ROCOR

V-HA3)

WCORR
WCORND"\J/FRIEND

/Print Relations \o-

SYNTAX
Kuno Analyzer Port 2
Binary Sentence
Tape To Binory
Analysis Tape"*<A3

Is CS JQa?
Yes

No("call Link

Find Maximal Connected ^N.
Concept Sets. Call Them\
Clusters. Left-over Concepts J
become One-member Clusters^,/

cfV—

""

x

(E

S~
"EDIT
Kuno Analyzer Part 3.
Binary Analysis TapevTo BCD Output Tope^

CLUST

)—@

int Clusters If SK On

WCLUST

0

Coll Link 7 W(M)Count Occurrences Of
Concepts Or Clusters, Maki ng J
edejjype-term Clusters As Needei&-Q

KCOUNTC

Relood Core \ , _From Tope ^/Select a List Of"\
Sentences And Write It j — * - @On Tope For Syntax J
Any SyntaOn?)
lis ES On

lYes

®

[fN

©

SYNTAX®-

Dump Core.
I f Write Foils,
Exit>

CRITER
Match Trees Against
Sentences. Count Tree
Occurrences. Usess^Sussenguth Graph Motcher" ° - { Is ES On?)

-*/
\

J

E

®

WMOOAL®-cWas
SA or AA on?
{Yes

Copy Analysis
To Print Tape
WasCT on?

)

I Yes
f Print TrecsA
V-,Dcte£ted
/

-^3)

CRITS

t.

Call Chain
Link 3Using Suffix File In Library
And Looked Up Text, Write A
BCD Sentence Tape For Input
To The Kuno Syntactic Analyzer

J

GCall Link 4}I

Kuno Analyzer, Package B, Port t
Prepare Binary Sentence Tape
Using Condensed Grammar Tape
Tcall

6) WKUNO
3)

Add Concept Numbers
Of Phrases (Trees)To
Concept-Occurrence
List
^

(

-@

ILink 5 V ~Flowchart 1 (continued)

CRITS

STATISTICAL

PHASE THREEPHRASESIs Statistical Phrose^
Searching Ta-B« Done ,PSv ST On?
/\ Yes/Print List Of \" * \ Texts Read I f ,V
TPIsOn/

®-

I

Q

> ^

Increment Previous
Counts By New
Phrase Occurrences

PHROCC(Any More Output )5 TTNo

®

CRITS

(

T

Has More Than I Document
Been Submitted?
Yes

Print Phrases
if ST

w

•
If RF, Print DocumentConcept Matrix

Any Request To
Punch Document
Dato?
(PU On;[Yes

LSTOUT(o)-Ur)

Merge Text Cluster
Numbers With Entire
Collection Clustering

RELOC
FILLIN/ C o r r e l a t e All Doc umentsN
V
Using CORMD3
D3 J

DCORR
ROWSUM
ROCOR

I

WCORR

( » DC, Print

MERLST

X

Adjust Concept Vectors.
Add Document To
Document-concept
Matrix. LV, All Counts* t

Is DCvDRvKD O n ? )ZZT"Punch Cluster
And Count

Correlationsy-%

If DR, Print Relations
Of Documents, Derived Using
CUTOF3A3WDCRNDFRIENDWGROUP£J_^

Rewind Tapes

I)

Adjust To Phase Three;
Clear And Initialize

I
x

WDOCS

I

Position Library
Search Text For
Phrases. Count Them-*v>3)Is RCvAR

On?)

(Bj)

(

Correla te Requests Only
se CORMD3/print Requ<est Correlations
RC On

\

«

I
Flowchart 1 (continued)

ROWSUM
ROCOR

0

Si!

A3)

WCORR

(§)

~«H(

"No

/g\

Is AR On? ))fc/

Print Concept
Relotions If CR On

JYes^Print Answers To Requests."f Answers Are Documents Whose^Correlation With..The Request
I s Higher Thon C U T O F F

p ^ 4

-H§)

REOUSTt Yes(

I s SC On?

r)

Extract Request
Vectors Fromv Document -Concept
Matrix

CONCEPT-CONCEPTSTATISTICS( Print Vectors If SV )Transpose
Document-Concept
MatrixTRANS

Print Concept Occurrences
I f OF On

(r>

No

IU

J

-*<A^

\

°"?

/

CONCORROWSUM
ROCOR

(

\
^
I Print C o r r e l a t i o n s \Y
IfCCOn
/

-HA3)

+®

Add To Each Vector>
The Concepts Related
vTo The Ones Already There/

WDCVECSMEAR¥

I f SV Print
New Request
Vectors

©-

J Yes
'
Correlate Concepts^
By C0RMD2J

LINEUP

3'

WCONFR- \ CCvCRvSVvSCvKC)

V^§) CLUMPI 7Q*>K C v S C v C C v Yes
CFvCRvSV
On?
I

(&>-

WGROUPIsKCOn"?)Cluster C o n c e p t s ^ \And P r i n t Clusters^/

r (S)

*®

-KA3)

Replace Request
Vectors In
Document-Concept^Matrix And Recorrelate

WCORR/ If AR Print
V New Answers

I
Flowchart 1 (continued)

FILLINDCORRI
I f DCvRC Print New
Correlations/ If CRvSVvSCvKc\( Prepore L i s t Of)
yConcept Relations /WDCVEC\/H§> WCORR-WA3)REQUST11-28HIERARCHICAL
PROCESSING

<B>-

1

^ Is HE On)
Yes

No

s

Position Library

r

^ad

V

Hierarchy

^\—g>
i

TREES
CLIMB
CHILD
FILIALCROSS

WA3) WDCVECFILLIN

Recorrelate Requests)

If AR Print
New Answers

A3
B4

A1

Replace Vectors
In Document-Concept
MatrixI f DCvRC
Print New Correlations

End Print And
Punch Tapes
TREES

Call Hierarchy To Alter
Request Vectors
Parameter GOTREE
Sets Mode Of Alteration
RH Is Expansion/Contraction
Choice

C

B5
B3
A5

F0REST^s'Extract Request
Vectors. Print Ifi
HV OnPrint New
Vectors If
HV On

RewindLibrary And
Intermediate
Tapes

DCORR

-*(A3) WCORR*(A|REQUSTJ
Flowchart 1 ( c o n t i n u e d )ENDEND

11-29period — directly after a letter in an abbreviation*,End-of-sentence periods should be precededby a space.
quotes — slash (/) is used for both open and close
quotes*No spaces before close quotes* orafter open quotes*
semicolon - comma period (,•) right after the wordo
colon - two periods (*.) preceded by a space (endof sentence implied).
capitalization - ignoreo
question mark or
exclamation point — oQUE or .EP preceded by a space,,dash

DASH is used*hyphen*A minus sign is used for a

A minus sign followed by a letteris treated as a hyphen (thus: random-access),while a minus sign followed by a blank means
skip to the next line.
avoid — asterisks in column one (this is the normal
end-of-text sentinel), and consecutive dollar signs (another end-of-text sentinel)*
SEGMNT reads up to 1,000 words of English texto

It stores consecutive

text words as consecutive five-word items in core, at location WDLTST*

The

first (FORTRAN-type) word of each item contains the sentence and word numbers:sentence number in the decrement, word number in the address * Theremaining four words, in FORTRAN order, contain up to 2it characters of the
English word, followed with blank fill*

SEGMNT leaves the total number ofwords in location NUMWRD and the total number of sentences in MAXSEN.

If SEGMNT

is entered with sense light one on, the text is printed as it is read in.

11-30The s u p e r v i s o r now w r i t e s a l l of l i n k one, i n c l u d i n g accumulated
d a t a , onto t a p e Ah.
c h a i n l i n k two.

C o n t r o l i s then passed t o t h e d i c t i o n a r y lookup,

The lookup p r o c e s s i s d e s c r i b e d i n Sec. IV i n d e t a i l .

A schematic of t h e r e a d - i n and lookup procedures i s shown i n Flowchart 2 .

5.

Operational Details
SMART, a s p r e s e n t l y coded, r e q u i r e s an IBM 709l| w i t h 12 t a p e s and

32K of c o r e f o r f u l l u s e .

I f n e i t h e r d i c t i o n a r y lookups nor h i e r a r c h i c a lp r o c e s s i n g a r e to be done, t h e programs w i l l run on an IBM 7090.
s y n t a c t i c o p e r a t i o n s a r e o m i t t e d , seven t a p e s w i l l

Ifsuffice.

Four of the t a p e s used by SMART a r e normal FMS t a p e s .

Al mustc o n t a i n a FORTRAN monitor system, p r e f e r a b l y the Harvard M S system.
This i s an almost completely s t a n d a r d FORTRAN I I , v e r s i o n 2, m o d i f i c a t i o nl e v e l 35 system t a p e .
assumed.

The normal c o n f i g u r a t i o n of t h e monitor f i l e

isThe o n l y s p e c i a l f e a t u r e of t h e Harvard system i s t h a t the job

s i g n - o n time i s l e f t i n 75>o*

The d a t e , as u s u a l , i s expected i n ll|2r>.

During t h e run the program a t t e m p t s t o r e a d the time from the p r i n t e r c l o c k(RPQ78C5h)> e x p e c t i n g a normal SHARE p r i n t e r b o a r d .
IB s t a n d a r d l o a d e r .

SMART assumes theI n the absence of t h e s t a n d a r d l o a d e r , t h e t h r e e

p a t c h e s t o BSS c o n t r o l made by the SMART system i n order t o get i t s e l f
l o a d e d may wreak h a v o c .
The system i n p u t must be on t a p e A2.

I t s contents are describedl a t e r , but i t s format must be normal; i . e . lit or 28 word r e c o r d s , withlook-ahead coding.

SMART r e a d s both b i n a r y and BCD data c a r d s .

OutputCHIEF Recognizes *TEXT Card,
Initiates Text Read-In

I

SEGMNT Reads In Text
To Core Array WDLISTICHIEF Dumps Core On
Scratch Tape

MM]

I

Control Passes To
Lookup Link, On Tape B3

I

Library Is Read To Obtain
Dictionary
Text Is Altered From
English Form To Looked Up,
Concept Number Form.
Full Syntactic Data Is Placed
On Scratch Tape If Needed* @Words Not Found Printed*©

CHIEF Restored To Control,
Link 1 Read Back Into CoreLOOKUP Schematic
Flowchart 2

11-32goes to A3 to be printed under program control.

Blocked records, innormal format ( l i n e s separated by / ) are used.

Binary cards are w r i t t e n

unblocked on Bl;, in order to be punched.
SMART also requires a scratch tape on AI4. to be used by the mainlink and also as a chain t a p e .

The main chain tape, however, i s B3.

2 to 7 are stacked on i t ; only l i n k s 1 1 , 10, and 1 go on to AI4..

Links

Normally,when no updating i s done, link 1 i s submitted as a nonchain job and a previously w r i t t e n chain tape is mounted on B3The SMART l i b r a r y tape goes on B£.

If a new l i b r a r y tape i s to be

w r i t t e n i n t h i s run, B5 should be blank and the old l i b r a r y tape must be
mounted on A6.

Otherwise, the l i b r a r y i s mounted d i r e c t l y on B5> and updatingi s omitted.
If syntactic processing i s performed, five more tapes are needed.
The analyzer i t s e l f is on B3 with the other chain l i n k s .

The SMART versionof the syntactic analysis differs from the standard version by(1)

having different tape assignments;(2)

running; as t h r e e chain l i n k s r a t h e r than as three jobs;(3)

printing fewer on-line messages;(k)

producing (optionally) only one analysis of each sentence.

The condensed grammar i s mounted on A5>.

Grammar 6C i s used currently in the

SMART system.

The syntactic system also uses A6, B6, Bl, and B2 as i n t e r -mediate t a p e s .

A f u l l SMART run (with syntax but no update) thus reo x uires

three private tapes (B3, Bf>, A£), four monitor tapes (Al, A2, A3, Bl;) andfive scratch tapes (Bl, B2, Alt, A6, B6).

II-33
Having mounted a l l these tapes, further operator intervention i s
not required.

All further i n s t r u c t i o n s are taken from A2.

The format of the input tape i s as follows:(1) Job card.
(2) *XEQ.
(3) Operation instructions, as needed.
(10 Programs.
' # CHAIN (11,U)
binary deck for chain 11
if updating* CHAIN (10,1;)
binary deck for chain 10
if more than
one chain link

* CHAIN (1,10binary deck for link 1* CHAIN (2,3)

if chain tape
not premounted* CHAIN (7,3)k(5) *DATA

(6)

(7)

Optional updating i n s t r u c t i o n s , used i f andonly i f links 11 and 10 are submitted.
Submit:(a)(b)

lookup f i l e update cards
suffix f i l e update cards

(c)
(d)

c r i t e r i o n t r e e update cardss t a t i s t i c a l phrase update cards(e)hierarchy update cards

Table of names of thesaurus c a t e g o r i e s .

This i s a tableof six-character i d e n t i f i e r s used for p r i n t o u t s .

Therei s one i d e n t i f i e r included for each concept number.

Three foimats are allowed for the names table.
(a) BCD format. One card is given for eachidentifier. These cards have *NAMES
punched in columns 1-6, and the six-character
identifier in columns 7-12. The concept
number may be punched as a decimal integer,
beginning in column 13 and continuing for up
to five columns. Each concept number must be
less than 1,000 in magnitude. If no concept
number is provided (i.e. column 13 is blank),
the concept number used for the preceding
card is incremented by one. When all needed
identifiers have been supplied, a card with****** in columns 1-6 terminates the deck.
(b) Binary formed. When a correct BCD deck is
submitted, a binary deck is punched. This
deck may be used as future input.

The first

card is a BCD card containing an octal integer
in columns 1-3, specifying the number of cards
that follow.

The remainder of the deck isbinaryj it has l*-7-9 punches in column one,and contains 25 identifiers per card.
(c) Omit names table entirely. The program will
supply consecutive integers.
Specifications: At this point the options described in Part
3A, and listed in Table 1, must be supplied. All specifications for CHIEF are punched, in any order, on BCD cards. Any
number of cards and any positions on the cards may be used.
Blanks are ignored and commas used to separate specifications.
Since all printing is under the control of some option, atleast one output-producing option must be specified for eachrun.

Read in of the options stops when the firstcard of type nine is recognized,)

Instructions to CHIEF: From this point on, the input
deck consists of the following kinds of cards:(a) *NOTE(b) #TIME(c) *LIKE(d) -KLIST, followed by a binary deck(e) *TEXT, followed by a BCD text(f) *FIND, followed by a BCD text (do not uke)(g) *ST0P. Last card of deck)

End of file: Superfluous if a *ST0P card is included,
but desirable nonetheless.