ISR-7
June 196U

III-l

III•

DICTIONARY AND HIERARCHY CONSTRUCTION
Claudine Harris

1.

The Document Collection
The SMART system is designed to test and evaluate various approaches

to document retrieval. The document collection chosen must then possess thefollowing characteristics:(a) the collection should be large enough to give valid
statistical results;(b) the collection should be short enough to be handledwith ease;(c) the language of the documents should be amenable toinclusion in a dictionary of practicable size;(d)the semantic content of the documents should lenditself to classification.

With these factors in mind, the Abstracts of Current Computer Literature published in the IRE Transactions on Electronic Computers may constitute a suitable collection. Accordingly, the abstracts published in March,
June and September 1959 are the subject of the current experiments. They
make up a group of closely allied documents within a restricted field.
The SMART system is capable, at this time, of processing texts up
to 1,000 words in length. The given abstracts fall within this range.

III-22• Nature of the Language Data
Each document consists of a paragraph in the natural language
preceded by a title and citation information. At the present time, thebibliographic citation data are not included in the text analysis. Mathematical expressions and proper names of persons, corporate entities ormachines occur frequently in the abstracts.

3.

The Dictionaries
To allow for flexibility in the retrieval system, dictionaries andtables are provided, each containing linguistic data appropriate to certain
phases of the lookup and analysis. These are stem and suffix lists, with
their associated semantic and syntactic values; a hierarchical structure ofconcepts; a list of syntactic criterion trees (phrases); a list of significant word pairs; a simulated vacuous dictionary.
A.

Stem and Suffix Dictionaries
The size of the alphabetic dictionary is kept small by enteringwords in stem foim whenever possible. Each entry is supplied with a stringof semantic codes which identify the concepts with which it is associated.
A second string of codes gives the homographs of the entry for syntactic
analysis.
A word is looked up in the stem dictionary by a left-to-right,
letter-by-letter comparison.

Any suffix present on a text word is thenadded by scanning the suffix list as many times as is necessary.

Suffixes

III-3carry no semantic information, but their syntactic codes are combined withthe stem syntactic codes. Examples of stem and suffix entries are given
in Tables I and II.

Stems

RECKONRECOGN
RECORD
RECORD-REPRODUCERECOVER
RECTI
REDO
REDUCE
REDUCTREEL
REFER
REFERENCE
REFINE
REFLECT
REGENERATEREGISTER

Syntactic
Codes

Concept
Numbers
0013
0332
OI56OI4OI
OijOl
00630026
0306
0063018)40173
018)40173
0191

0026
011U0063
007300814
0111

OI430I180)430)480700)43070
OU30U20h30k3
0U30ii200007001420)430143
Oi430i420)430)48
OU30U0070
0700U30)40

CorrespondingPartial
Homographs
0T10,0T60
0T10,0T60
N0UO,OT1O
N0UO.
0110,0130
0T10
0T10
CT10,0I30
0000
N0UO
0130,0T10
0T10

0T10,0I30
0T10,0T60
OT1O,OI1O,N0UG
N0UO,OT1O,OI1O

Typical Alphabetic Stem Dictionary Entries
TABLE 1

The complete homograph for syntactic analysis is obtained by thecombination of a stem partial homograph and a suffix partial homograph.
For example, a partial homograph such as 0T10 will combine with a partial
homograph from the suffix list, such as V00S0, to form a complete homograph.

In this case, the complete code is VT1S0, indicating a single

object transitive verb in the third person singular.

Ill-li

Alphabetic
Suffix L i s t
FICATIONFICATIONSFIEDFIER
FIERS
FIES
FOLD
FUL
FULLY
FY
FYING

S y n t a c t i c Suffix Codes
058
059
060
061062
063
06ii
065
066
067
068

058
059
060
061
062
063
06k065066067068

NOUS
N0UP
VOOCO
N0US
N0UP
VOOSO
ADJ
ADJ
AVI
VOOPO
ROO 0

POO 0

ADJ

N0VC
N0VC
100 0
GOOSO

N0VS

ADJ

Typical Suffix Dictionary Entries
TABLE 2

When a text "word consists of a stem only, without the addition ofa suffix, the codes derived from the stem are combined with special codes
assigned to "no suffix."

These special codes are 000S0, VOOPO and 100 0,

which are capable of combining with noun and verb partial homographs. Allother parts of speech carry complete homographs in the stem dictionary, asdo irregular verbs and irregular plural nouns.
The present suffix dictionary contains 19k entries. Noun suffixes
are entered in plural as well as singular foims, and adjectival suffixes in
the adverbial form.

Verb suffixes include the common endings "ed," "ing"and "s," as well as true verb suffixes such as "fy" with their inflected forms.
This is done for two reasons:to save having to do a double scan of the suffix

list and to permit use of the same suffixes in constructing a vacuous dictionary
Multiple suffixes, such as "fying" could be found by scanning the list firstfor "fy" then for "ing11? however, the method of construction of the vacuous
dictionary does not provide for double scanning of the suffix list, so thatthe words "identify" and "identifying" would not be recognized as arisingfrom the same stem.

III-5Since the syntactic codes of verb suffixes are partial homographs,
it is necessary to enter the combining part of each code as a suitablehomograph of any stem capable of taking on a verb suffix. An example ofthe combination of partial homographs is given in the note to Table 1.
The stem "recti" is coded as a potential verb because it can foim "rectify"
whereas "reduct" carries no syntactic code at all, since it is not a true
English word as it stands and can only accept the suffixes "ion" and "ible,"which have the complete homographs "N0US" and "ADJ."
However, in a limited number of cases, partial syntactic coding
may introduce an ambiguity:

if the word "capital," for example, is coded

as a potential verb to accept the suffix "ize," the plural noun "capitals"
will receive the extraneous coding of a verb in the third person singular.
This difficulty is prevented by entering the stem "capit" with a partial
verb code.

The suffix "als" properly carries with it only the plural noun

code, and "capitalize" is found by a double scan of the suffix list.
Included in the stem dictionary are the so-called common words ofthe English language which carry no significant semantic values, that is,which do not convey information of value in determining the subject matterof a document.

These words are assigned so-called "common" concept numbers

to be ignored in the semantic analysis, but their syntactic codes areavailable for any desired syntactic analysis.
B.

The Semantic Concept Hierarchy
Each entry in the stem dictionary is assigned one or more concept

numbers. An attempt is made to predict all possible uses of a word andeach distinct meaning is coded.

Any one concept can contain an unlimited

III-6

number of stems which may be any part of speech, partial stems, or themnemonics obtained as output of the phrase-finding routines. Table 3 shows
examples of the variety of terms attached to a given concept number.

Concept
NumberExamples of
Included Terms

Concept
NumberExamples of
Included Terms

0069

error
failfault
mistake0275

balancecompensate

0280

error-correcting
x-CORECT (0069,0275)*C0HECT (0070,0306)
ttCOEECT (0069,0306)

0299-x-ERRFND (0069,0215)

0306

correct
fix
recti
repair0070

0215

deviateinaccur
inexact
loss
detectfindnote-* — mnemonic p h r a s e name with i t s component c o n c e p t s

Semantic Concept Classification
TABLE 3

It was first expected to limit the assignment of significant concept
numbers to those parts of the natural vocabulary which were immediately
apparent as carriers of information. However, a careful reading of thedocument collection has shown that many obviously technical terms occur also
in a general sense, and it becomes necessary therefore to code the significant
technical meaning as well as the more general "common" meanings.

III-7The current solution is to consider the natural language as awhole to make up distinct portions of a hierarchy of concepts. It isthus possible to isolate -well-defined areas of mathematics, computertechnology, or applications. The over-all classification plan is shownin Fig. 1.

The inclusion of general meanings in part of the hierarchy

introduces difficulties in the statistical analysis of texts, and it ispossible that portions of the current dictionary may need to be recodedwith "common11 meanings and retained only for syntactic analysis.
In the absence of statistical evidence, the technical parts ofthe concept hierarchy have been structured on an. intuitive basis. It isintended that parent nodes contain the more general terms, and filial
nodes the more specific terms. The decision to include a term within acertain concept number, or make it a son or a brother is based on therequirement to keep ideas separate. Not enough actual retrieval runs
have been made as yet to evaluate specific hierarchical problems. An
excerpt of the hierarchy is shown in Fig. 2, corresponding to the concept numbers of Table 3.

In order to deep the figure simple, only one

term is shown at each node.
C.

Phrase Dictionaries — Criterion Trees and Word Pairs
Using the syntactic codes obtained in the look-up procedure, it

is possible to perform a syntactic analysis of each sentence and to describe
the sentence in syntactic dependency tree form. Typical tree structures areincluded in a criterion tree dictionary, each node of the tree being assigned
the semantic concept numbers of the corresponding words of acceptable naturalphrases.

Ill-8Equipment and Devices

Control Systems

AssociatedEquipment

Computers

Circuitry\Computer
Subassemblies

Components

Mathematics\GeneralTerminology

NumericalAnalysis

AlgebraStatistics

Other

Programming/\/\\/

Data

Linguistics

Communicationwith Machines

Simplified Outline of the Semantic
Concept Classification
Figure 1

Programming
Procedures

III-9Nontechnical Significant
Vocabulary///I\/,
S t r u c t u r a l andS p a t i a l Concepts"Action"(Implementation)
Vocabulary

Time Concepts///

Efficiency

ResultAccuracy

Applications of Comouter Techniques/' / I \N x//

Traffic(Informationand Cargo)/

Military/" ^ -\\

Aircraft
ControlBusiness
Automation////

Artificial
Intelligence

Industrial
Automation

Other Applications(Astronautics, Medicine,Chemistry, etc....)

Figure 1 (continued)

111-10Cti*H0)•HOm4^ft&,Q)
Oco\ CDCOCD-PoCM•P&(DOW0)

og<DCDUU}

Woo(U0)1oQH

III-ll

Each tree is given a serial number, a mnemonic phrase name (alsocalled a subject heading), and a semantic concept number. As in the stem
dictionary, a single concept number may correspond to several ways of
expressing the same idea. There will then be several criterion trees
associated with a given concept number, and that number is included inthe semantic concept hierarchy.
The list of tree mnemonics is essentially a list of phrase names,
or significant word pairs, and it is used in this way by the PHROCC routine.
The list of phrase names supplies for each one, in addition to its own
concept number, the concept numbers of possible component terms, but carries
no syntactic information.
ways:

Phrase names can therefore be obtained in two

as the output of the syntactic criterion tree matching procedure,

and as co-occurrence of terms within a sentence irrespective of the syntax.
Examples of trees and word pairs are given in Tables h and 5.

PhraseName

Concept
Classification

CODWHD0128,0281,0208

code word

CORECT

0280,0275,0069

e r r o r s are compensated for

CORECT

0280,0070,0306

correcting inaccuracies i s possi.ble

CORECT

0280.0069,0306

e r r o r correction i s used

DAPROC

0200,01^7,0191

tape handling procedures

DAPROC

0200,01^7,0053

data processing

DAPROC

0200,01U7,0077

the processing of f i l e s

Typical Associated Phrases

Phrase Dictionary Excerpt
TABLE h111-12

r'dCD

CDCOI1.

o o otifl

H H HP^SO O O O OU M A l A l A l ^r-\ H r-\ <~\ H•o'•H-P<tiCD - P/y1^/^ /C"°V\\2p^

J>

CDJH

Q O O O OvO vO vO ^O M3
H H H HHi

Q

rr\C\JO CD
52J «y1
1JO^1

H11°^ \^^/ ^\P<\ OsC\J\ 0C\J>"ts,CO098)
119)

A)(960(611119)(S)098)

9Prescrib
Semantiand
Syntacti
Codes

CD Oo oo t^oo o o0Treeructu&XJ M
O H^O11M QH HM^><{ HO HQ MrH^1PCOJH

CD CDT J ,£>O£5£pHC\JiHc\jr^-^rH Cgsi'^

ios

1

1MCHTRAMCHTRA

SubjectHeading
orPhraseName52;

fT\j^-*-"°111-13
In Table 5^ three typical trees are given with a diagram of theirnode structures. In the first example, the nodes are not restricted as tosyntax.

This tree will match such sentences as "Machine translation has

been successful."and "Translation by machine is convenient."

Syntactic Analyses Correspondingto Criterion Tree li|0
Figure 3(See Fig. 3.)

Ill-Hi
In the second example, node 2 is a verb meaning "translation,"node 3 is an object, and node h carries the meaning of "machine." Acorresponding sentence would be "We have translated texts with a newmachine."(See Fig. h*)

Syntactic Analysis Corresponding
to Criterion Tree 15>0
Figure h

The third example specifies that node 2 is either a subject or anobject with the meaning of "machine," node 3 is a complement, and node hcarries the meaning of "translation."

A matching sentence would be "Auto-matic devices are not capable of translating texts." (See Fig. 5.)

Ill-15

Syntactic Analysis Corresponding
to Criterion Tree 160
Figure 5D.

The Vacuous Dictionary
A simulated dictionary can be constructed directly from the input

text during the look-up operation. This dictionary assigns a different
concept number to each new word that occurs in the text, a new word being
defined as any new stem obtained by removing suffixes from a text word witha right-to-left scan. Later analysis of documents is then actually basedon the original text words rather than the combined semantic numbers of theconcept hierarchy.

The suffix list used in constructing the simulated

vacuous dictionary is identical with that used for the real stem dictionary.