ISR-8
December 196U

VII-1
VII.

DICTIONARY CONSTRUCTION aND UPDATING
Claudine Harris

1.

Introduction
The dictionaries necessary for the SMART system were describedin Information Storage and Retrieval9 Report No* ISR-7, Sec. III. They
consist of word stern and suffix lists which provide for each stem a
set of semantic concept numbers and syntactic values, a hierarchicalstructure of concepts, a list of syntactic criterion trees (phrases), alist of significant word pairs (phrase names), and a simulated vacuous
dictionary or null dictionary.

The thesaurus of word stems and concept

numbers is available as an alphabetic list of all word stems withcorresponding concept numbers and syntactic codes, and as a numerical
dictionary of all concept numbers with the word stem to which theycorrespond.
Construction of the various dictionaries was carried out
manually to the point where experimental lookups could be made totest the options of the SMART system. The following parts describe
the procedures used in building the dictionaries and in revising them.
Word stems were classified into broad groups first, and the output of
the first lookup operations was used to refine the classifications.
Constant consultation was maintained with the members of the group,
leading to many valuable revisions.

VII 22.

Formation of the First Dictionaries
The first classifications were made on an entirely intuitive

basis following the outline of concepts given in Information Storageand Retrieval, Report No. ISR-7, Sec. III. Out of the 4.0 5 documents,
a representative group of ^8 was selected and most of their technicalvocabulary, as well as some of the nontechnical words* were assigned
concept numbers and entered into the thesaurus. These selected dments were used in the early phases to test the various SMART routines*'
the automatic lookup yielded a list of "words not found'1 which could
then be considered for addition to the dictionary«
The same procedure was followed for the remainder of thecollection. The first lookup of the whole document collection wasmade after most words had been included in the thesaurus. The words
not yet found in the thesaurus amounted, in general, to not more thana dozen per document* including abbreviations* proper names, ete. As
new words were added to existing concept numbers and new concepts werecreated, a graph of the hierarchy of concepts was maintained up to dateand constantly referred to. Invaluable contributions were made by thevarious members of the group in evaluating the hierarchy and by theindividual word stems associated with each concept number in the
numerical dictionary*
At this stage* there were still, a number of "words not found*11
and reference was made to the alphabetic null dictionary to ascertainthat the "words not found" did not occur with a frequency of fourmore*VII-3The versions of the dictionaries arrived at contained 1,944word stems corresponding to 4-18 concepts; this original version wasused in the first experimental lookups of the SMART system. Various
updating procedures described below led to a second version which wasused in the more extensive later experiments*

3.

The Null Dictionary
The null dictionary is described in Information Storage andRetrieval, Report No* ISR-7, Sees. Ill and XI. All distinct wordstems, after right-to-left suffixing, are assigned unique concept
numbers*

All words, which occur in a common word, list, and all wordstems with a frequency of occurrence of less than four are ignored.
In the 4-05 document abstracts used in these studies, the nullthesaurus generated by the THES program contained 2,864. distinct wordstems after suffixing and elimination of common words* With theaddition of a frequency restriction to four occurrences or more, thedictionary size was brought down to a total of 898 distinct "concepts"(word stems).
The output null thesaurus thus generated was available in two
forms for comparison with the SMART dictionaries:

the 2,864. distinct

noncommon word stems listed by frequency of occurrence, and the alphabetic list of noncommon word stems that appeared more than four times.
These two outputs were used to update the SMART dictionaries. Excerpts
from the null outputs are shown in Figs. 1 and 2.

VII-4.

First Suffix
Detected

Frequency

solv

ing

22

spe

ed

22

success

ive

22

suit

able

22

variable

s

22

ampli

fying

23

arithmeti:

23

communie

at ion23

mechan

ism

23

term

s

23

count

er

21

device

s

24

fast

ea

24

Word Stem

Excerpt from the Null Thesaurus Frequency List
Figure 1

First Suffix
Detected

Word Stem
slow

749

small

750

so-call

ed

751

solut

ion

752

solve

753
ing

solv
sort

754
755

s

sourceL"Concept"
Number

756

space

757

special-purpose758

specific

ations

759

speci

al

760

spectral761

1
Excerpt from the Null Alphabetic List of Word Stems
with Frequency Larger than Four
Figure 2

VII-6

4.

Updating the Dictionaries
A.

The Null Alphabetic List
The alphabetic list of frequent word stems from the null dic-tionary was used to ascertain that no "important11 words had been omitted
from the dictionaries*

The word stems from the alphabetical list thatwere omitted are., in general, words of nontechnical usage which were
not thought likely to make a significant contribution to retrieval fortechnical subject matter*
Understandably, the choice of nontechnical words to be includedin the dictionaries may be open to criticism, and we are a,ware thatdecisions could have been made at this stage on a less-than-adequate
basis.
B.

The Null Frequency List
A partial list of high-frequency word stems supplied by the nulllookup is given in Table 1.

Each stem to which a concept number isassigned by the null thesaurus is given without the suffixes that may
give rise to it. All stems are listed in order of decreasing frequenciesof occurrence down to 37 occurrences* A few words of lesser frequency
are appended as a matter of interest•
Since the null thesaurus is constructed with right-hand suffix
splitting, separate stems may be created from the variant grammaticalforms of certain words. Typical cases are "process," "require," and"use":

Word

Frequency

comput508

technique^system263

automat83

describ

233
209
186

anal
numb

83
77

magnet77

programm
swit ch73
72

circuit

154
139
130

control

71

program127

develop69

machine124.

applicuse

consider
time

65

funct

123
121
112

69
67

form

65

design106

differ

equ

102

solut

used

simul

log

99
98

perform

64
63
62
60

problem

94

inform

60

mem
dat

94
88

ele

59
58

analog

86

stor

giv

85
56

present

57
56

line

44

character
shown

44
42

obtain42

methoddigit
discuss
oper

gener

point
langu

err
bas

54
52
52

Word

electron

Most Frequent Noncommon Words
TABLE 1Frequency

Frequency

Word

Frequency

ord
bin

41

tran&L

51
50

result50

occur

output50

matrix

41
41
40

set

volt

38

transist

49
48

code

38

stud

48

process

37

input

4,8

require35

calcul

48

proces

state

pulse

mean

47
46

35
34

rel

33

speci

45

complexcore

45

routine

33
32

using

W

random

31

type

44

sign

29

requir44
44transistor

1.6

processe

12

Word
networkprocedTABLE 1 (continued)

|

VII

Stem

Suffixes

Frequency

process

ing, ed, or, etc...

37

process

35

processes12requiring, edkk

requires, ment

35

uses, ful, less

123

used

99

using

UU

It is seen that the separate stems give rise to misleading frequency
counts. For example, the total frequency of the common forms of "use,11
not including "usable," "user," and "usage" with frequencies of 1, 3)
and 3 respectively, comes to 266, thus making it the second most common
word stem in the documents.
C. "Use" and "Discuss"
A word, as common in the English language as "use," can be
expected to appear in the requests submitted to the SMART system, as
indeed it does. In a total of 24- requests prepared by a variety ofpeople, including both requests in the natural language and in outline
form - that is, without complete grammatical sentences, the following
distribution of "use" and "discuss" was found*VII-10

Number ofRequests

Occurrencesof "use"Occurrencesof "Discuss"natural language

14.

8

6

outline form

10

0

0

This is sufficient to suggest that such everyday nontechnicalterms be labeled as "common11 words* With this in mind, the requestand document correlations obtained with the first dictionary lookup
were searched for ambiguities introduced by everyday words* When documents that were not relevant to a request were assigned a spurious highcorrelation, it was found that the largest contribution to the correlation came from everyday noncommon words such as "use," "discuss,""procedure," "method," etc*««
Hence, one of the first modifications undertaken in the construction of the second dictionary was to eliminate all such words byclassifying them as "common*11

In so doing, the concept number for"discuss" which corresponded to Jl ways of saying "this is what we aretalking about" was included in the "common" list. Words from the highfrequency table affected by this change were "discuss, give, develop,
consider, present, study."
The words "method, technique, procedure" were also made"common,11 as were their 16 synonyms*

In this collection, the words"handling" and "processing" are technically significant, as in "dataprocessing," and their stems were retained*VII-115*

Refining the Numerical Dictionary by Concept Concordance
The erroneous correlations introduced by "common" words during

the first lookup gave an indication that similar spurious correlations
could arise from technical terms if the numerical concepts which included them had been defined ambiguously*

For example, the word

"generate11 was originally assigned to the concept called 80MAKE together with 16 other words meaning "construction*"
NUMBS, which reads:

The request RANDCM"How can one generate random numbers efficiently?

Which pseudo-random sequences offer long periods an^ ease of generation?"
obviously does not need to be correlated with the many occurrences of
the words "make" and "made" (total frequency 62)•
The analysis of ambiguous concept numbers was made by studying
a concept-document concordance and referring back to individual, documents to ascertain the specific usage of the concepts in each case.
Results were tabulated and the various words reassigned, if necessary.
New concepts were often created in this process, and the hierarchicalstructure revised•

Typical concept analyses are given below.

A concept number was selected for analysis either because it
was visibly ambiguous (8QMAKE), or because it was very frequent (168HIE),or because it appeared in a request with poor document correlations(101TAG), or for a combination of reasons. The concordance between
occurrences of a concept number and the documents was at firstestablished by visual scanning of the document vector output; aprogram now exists, however, to produce the concept concordance automatically. Future updating of the dictionary toward a third version,

VII-12
as well as the formation of a new thesaurus for a different document
collection, will be much aided by this analysis program.
A. Analysis of 101TAG
The concept 101TAG which contained 13 words meaning "designate,
identify" was chosen for analysis because it occurred in two requests
and seemed ambiguous* The word list attached to this concept included:call, designate, identi, index, indicate, label, mark, name, point,
signal, sign, subscript, tag. The concept occurred, in 94 documents,
with the following distribution of significant terms:
Term

Frequency

Number ofDocuments

index
signal (pulse)
identify

17
20

7
H

6

U

All other terms under this concept occurred a total of 91 times,
accounted for almost exclusively by "pointed out, indicated,called..."As a result, the words "indicate, call, name, designate" weremade into common words; the words "sign, signal, mark, point" were removed from 101TAG but kept in their other respective concepts; "identi"
was moved to the concept number for "recognition." Only "index, label,
subscript, tag" remained under 101TAG.
B. "Point" and "Pointed out"
The previous analysis led to a study of the occurrences of"point. 11

VII-13

Meaning of "Point"

Frequency

mathematical usage
location"pointed out"
purpose

12
2U
15
0

Only the meanings of location and mathematics need be retainedfor "point"; the meaning of "purpose" can be ignored; the words"pointed" and "pointing" can be made common.
C. Analysis of 168HIE
The concept 168HIE was an ambiguously wide concept meaning"ordering, or classification."

It included:

classi, grade, hierarchy,

interval, level, order, sequ, serial, step, succession, successive,
tree* The concept occurred in 97 documents and in two requests withthe following distribution of terms;
Term
order
step, interval, level
sequence
sequential
classify, grade
successive
serialtree

Frequency

U
31
23
15

U

13
7
1

The word "order11 was further studied as to distribution of meanings:
Meaning of "Order"

Frequency

ordering (sequence)
mathematical usage
commandpurchasenin order to"

11
10
6
2
12

VII-14
Because of the frequent significant uses of "order/1 it is notpossible to eliminate this word by making it into a common one. However, we can ignore the meaning of "purchasing" and assign "order" toonly three major concept numbers.
It was thought best to separate "successive" from "serial" toallow for the phrase "successive approximation."

Trie word "tree" wasmoved to an existing concept for words descriptive of graphs.
The final assignment of words from 168HIE is shown in thefollowing excerpt from the concept hierarchy, with the more specificwords placed under the general concept of "classification":classi
grade
interval
level
order
step
strati
502SUC
succession
successive

503SEmsequserial~50^HIE
hierarchy

Other types of ordering, such as "reversal" and the phrase"random number," were also introduced, under 168HIE.
D.

Analysis of 80MAKE
The ambiguous concept 80MAKE contained the words: arrange,build, built, construct, create, establish, fabricate, fashion, form,
generate, install, made, make, produce, product, shape, work. The
concept occurred in two requests and. in 16.5 documents with the following distribution of terms which shows how the words were regrouped.

VII-15
Term

Frequency

create, generate, produce
production
makej madeform (geometry)build, built, construct,fabricatework (task, action)
actuate, establish, installshape (geometry)product (goods, result, math)

1U
62
53
Ul
21
8
8
7

The words "make, made11 became common; all others were separated
as indicated above.

6.

The Phrase Dictionaries
Construction of the phrase dictionaries is not yet as complete

as that of the word stem and concept dictionaries. To date, 56 distinct phrase names are recognized. They are assigned variously toexisting concept numbers or to concept numbers of their own and tied
into the numerical concept hierarchy. It is not possible to list theexact number of English phrases which can be recognized, since aphrase name can correspond to many combinations of word stems. For
example, the phrase name LNGTRA, concept number 303 and means "languagetranslation," can be formed by three pairs of concepts:

98TRSL and1Q2LNG, 98TRSL and 35LANG, and 98TRSL and lUTEX. The multiplicity
of possible corresponding phrases in English can be seen from a listof the word stems under these concept numbers:

VII-1698
transcribetranscripttranslateword-for-word

102

35

interlingu
language
lingu

Cyrillic
EnglishFrenchMorse
Roman
Russian

1U
abstract
articlebibliographcatalog
copy
document

literature
page
paper
passagereporttext

The phrase dictionary contains 99 such combinations corresponding
to $6 distinct phrases* Since the phrases are concept pairs, rather thanword pairs, many worthless pairs of words co-occurring within a sentence
will be identified as phrases. For example, the phrase name SUCAPP,
which is intended to mean ,fsuccessive approximations," is made up of cooccurrences of 502SUC (succession, successive) and 106NQU (approximate,estimate, incomplete). While the intended noun phrase is included inthis specification, sentences such as "We estimate that a succession ofexperiments is necessary11 or "Successive attempts to refine the translations still yield an incomplete text" are also included*

In the first

sentence, SUCAPP is obtained by the pair "estimate succession" and in
the second sentence by the pair "successive incomplete."
Such ambiguities are resolved by syntactic analysis as describedin Information Storage and Retrieval, Report No. ISR-7, Sec. VI. Briefly,
the SMART system provides for the syntactic analysis of selected sentencesby means of the Kuno Syntactic Analyzer (Mathematical Linguistics andAutomatic Translation, Reports NSF-8 and NSF-9) and for the matching ofthese sentences with a dictionary of preanalyzed syntactic phrases called"criterion trees."

Criterion trees are syntactic phrases with specified

VII-17concept numbers and syntactic dependency relations between the included
concepts*
Returning to the example above, the dependency relations which
can be assigned, are, in general, noun phrase, subject verb, verb
object, and subject object. In the criterion tree dictionary SUCAPP
has been assigned only a "noun phrase" criterion tree, which will notmatch the verb object structure "We estimate that..." nor the subject
object relationship of "Successive attempts.•.yield an incomplete
text."In this manner, the spurious phrases "estimate succession" and"successive incomplete" will not be rendered as "successive
approximation.rl
The syntactical "criterion tree" dictionary now contains 108
trees corresponding to the 56 phrase names and innumerable English
sentences.

The choice of tree structures for a given phrase name wasmade by considering the words within the concept pairs and the possible
sentences in which they might be used. At this time, there are Indistinct tree types, but most phrases are given only the most common
syntactic subgraphs for adjective noun or verb object structure.
As an example, the following example gives the allowed structures forthe phrases LNGTRA and SUCAPP.

VII-18

Phrase Name

Tree Type Allowed

ExampleLNGTRAadjective noun

language translation

LNGTRA

verb object

we translate thedocuments

LNGTRAnoun complement
clausethe documents are
suitable fortranslation

SUCAPPadjective noun

successive approximation

An additional feature of the criterion trees is that thesyntactic dependencies are directed so that a given structure is
not reversible. The simple adjective noun tree assigned to SUCAPP
consists of two nodes indirectly connected as shown below.

0G\ 502SUC\\

Criterion Tree
SUCAPP^b 106NQU
Node 1 must have the concept number 106NQU, and node 2 must have theconcept number 502SUC. The numbering of the nodes indicates thedependence of node 2 on node lj that is, the adjective relationshipbetween node 2 and node 1 is fixed. This specification accepts"successive approximation," but not "approximate succession"; "wetranslate the documents," but not "we have documented the translation."
Evaluation of the dictionary specifications is continuing in
the light of continuing computer experiments.