IV-1

IV

Information Analysis and Dictionary Construction
G. Salt on and M. E. Lesk

1.

Introduction
At the base of any information system must always be a system of

information analysis, used to decide what a given information item, ora given search request is all about.

In a conventional library system,

this analysis may be performed by a human agent who uses establishedclassification schedules to decide what category, or categories> will
most reasonably fit a given item.

In certain other well known indexing

systems, keywords or index terms may be manually assigned to documents
and search requests, to be used for the identification of information
content.
Regardless of what type of analysis is performed, and in particularregardless of whether the analysis is done manually or automatically,
it is necessary to start with a set of carefully prepared instructions
specifying the allowable steps, and setting forth in detail the meanings
and implications of choosing one or another of the permissible alternatives.

These instructions often take the form of dictionaries of various

types, listing the allowable information identifiers, and giving for eacha definition which regularizes and controls its use. As will be seen,such dictionaries may take a variety of forms, including almost always
so-called "see" references which provide links for entries to be
replaced by other preferred terms, and "see also11 references which
designate cross-references applicable to the dictionary items.

NegativeIV-2
dictionaries may also exist, containing terms or categories which should not
be used for purposes of information identification.
In view of the importance of the initial information analysis andclassification —all later search and retrieval operations are of courseof no avail in the absence of a careful and consistent determination of
information content —it is appropriate to examine in detail the problems

connected with the generation and use of dictionaries.

Accordingly, thepresent study specifies the form of a variety of dictionaries which have beenfound useful in information analysis, and examines some of the principles
of dictionary construction.

Emphasis ijs placed on those dictionaries which

cam be used for natural language analysis, since many of the information
items and of the search requests to be stored may be expected to be expressedby words or word strings in the natural language.

Performance characteristics

are given, based on search results obtained with various dictionaries, andseveral methods are suggested for the construction of dictionaries by semiautomatic means.

2.

Language Analysis
Consider the problem of taking a document or search request in thenatural language, and of attempting to use some automatic procedure to
generate content identifications for the input texts. Such a task
immediately raises many difficulties brought about by the complexity of
the language, and by the irregularities which govern the syntactic andsemantic structure.

The following principal problems must be dealt with [l]:1) words which carry out syntactic functions but which do notcontribute directly to the specification of information content

IV-3
must often be eliminated (but some words, such as "can" mayoccur both as significant and non-significant words);
2) many distinct words may be used to supply the same or related
meanings; such synonymous words or expressions must be recognized
if an accurate content analysis of documents and search requests
is to be undertaken;
3) many words can be used in several different senses dependingon the context (for example, a word like "base" may variously
represent military bases, lamp bases, bases in baseball, andso on); it is important to identify such homographs, and if
possible to recognize the proper meaning in a given context;h)many types of syntactic equivalences occur in the language,
where completely different constructions are used to represent
the same general idea; as an extension of the overall synonym
problem, it is important to recognize at least the principal
types of syntactic paraphrasing;5)

the use of indirect references is prevalent in the natural
language, where pronouns, collective names, and other particles, are used to refer to entities presumably known by the context;
the identification of the proper antecedents of such pronouns
is difficult, particularly for cases where many different
words can operate as antecedents;
6)

relations may exist between words which are not explicitly
contained in the text, but which can be deduced from the context,
or from other texts previously analyzed; the identification ofsuch relations requires deductive capabilities of considerable
power;

7)

the meaning of many words may change with time, or contrariwise,
new words may be created to refer to entities previously referred
to in different terms (for example, the unit of time previously
known as "millimicrosecond" is now generally known as "nanosecond").

If the natural language is used as primary input to an information

iv-fcsystem, any content analysis system will have to include methods forconsistent language normalization.

One of the most effective ways forproviding such a normalization is by means of suitably constructed
dictionaries.

The following types of dictionaries appear to be of interestin this connection:1)

a negative dictionary containing terms whose use is proscribedfor content analysis purposes;

2)a thesaurus, or synonym dictionary, which specifies for eachdictionary entry, one or more synonym categories, or concept
classes; ambiguous entries are then replaced by many concepts andipany different words (synonyms) may map into the same concept
category; a thesaurus is then used to perform a many-to-many
mapping from word entries to concept classes;

3)

a phrase dictionary may be used to specify the most frequently
used word or concept combinations (called phrases); such a phrase
dictionary can often increase the effectiveness of acontent analysis

by assigning for content identification a relatively unambiguous
phrase, instead of two or more'ambiguous components (for example,
the terms "program" and "language" are more ambiguous, standing
alone, than the phrase "programming language");h)a hierarchical (tree-like) arrangement of terms or concepts,
similar to a standard library classification schedule, which makes
it possible, given a certain dictionary entry to find more general
concepts by going up in the hierarchy, or more specific ones bygoing down (for example, from a concept such as"syntax", one cam

obtain the more general "language", or the more specific "punctuation").
Dictionaries do not, of course, completely eliminate language ambiguities,
but they can serve to reduce the effects of many irregularities by using
appropriate dictionary mapping algorithms.

For example, a correspondence

between a word and a single concept may receive a higher weight than one between

17-5
a word and a multiplicity of concepts, since the former presumably
implies a unique meaning for that word while the latter implies ambiguity.
Even if almost all terms used in a given context are inherently
ambiguous, the juxtaposition of many multiple mappings can often identify
the appropriate concept classes with reasonable accuracy.

The relevant

categories will normally be reinforced, since they apply to many terms,
while the extraneous categories will be randomly distributed.
Consider, for example, the set of terms: "base", "bat", "glove","hit".

Each term is ambiguous, and a given multiple thesaurus mapping

may specify the correspondences shown in Table I.

In that table, three

categories are shown for the word "base", and two categories for each of
the other terms. Despite the apparent ambiguities, a document identified
by the four original terms can nevertheless be assigned to the "baseball"class with reasonable expectation of success, since the other categories
occur more or less at random for the given terms, whereas the "baseball"class is always present.
The principal advantages of synonym and phrase dictionaries forpurposes of content identification may then be summarized as follows:1)

they permit a consistent assignment of concept classes to items
of information thereby replacing either keywords and index
terms assigned to documents and search requests, or the words
occurring in them;2)

they can often be used to resolve ambiguities by looking at
the pattern of occurrence of the concepts;3) they cam serve for the analysis of many different subject
fields and for different types of usage, since it is possible
to adapt the dictionary to the particular search environment.

IV-6|\ Concept\ Classes
Lamps

Games
Baseball Animals

Military
Clothing
Usage

Original^
1 Terms
\
base

y

y

bat

V

glove

y

hit

y

y
y

Sample Thesaurus Mapping
Table I

y
y

1

IV-7
On the negative side, dictionaries are often difficult to construct,particularly if the environment within which they are expected to operate
is subject to change; furthermore most dictionaries are useless unlesstheir mode of usage is consistent for all operations. Obviously if a
dictionary is used in one way for information classification and inanother for information searching, an effective result cannot be guaranteed.
Various thesaurus types are examined in more detail in the next few
paragraphs.

3.

Dictionary ConstructionA)

The Synonym Dictionary (Thesaurus)

As previously explained, a thesaurus is a grouping of words, or wordstems, into certain subject categories, hereafter called concept classes.
A typical example is shown in Pig. 1, where the concept classes are
represented by three-digit numbers, and the individual entries are shown
under each concept number.

In Pig. 2, a similar thesaurus arrangement isshown in alphabetical order of the words included.

The concept numbers

appear in the middle column of Pig. 2 (concept numbers over 32,000 are
attached to "common" words which are not accepted as information identifiers) 1 the last column consists of one or more three-digit syntax codes
attached to the words to be used for purposes of syntactic analysis.
When constructing a thesaurus to be used for vocabulary normalization,
one immediately faces three types of problems: first what words should
one include in the thesaurus; secondly, what type of synonym categories
should one use (that is, should one aim for broad, inclusive concept
classes, or should the classes be narrow and specific); finally, whereiv-fi

o
Z
mm
X
o

UJ
U J U
U Z
Z
*

u
z
p-

wo

p~

<

p-

•M

<l

U

U

vo a
UJ <
OC O
1 1 UJUJ UJ o
> > z

UJ z

UJ 3

o
•
UJ CL az o i u j u i z* u u z »• • • •» - Z Z <
1 1

UJ
UJ O
u
z
z
^
<

X
m\
UJ
CO

OC
UJ
>

p-

tat

UJ

o
UJ
oc oc
•
OC
1 UJ
UJ
O h U i+z a. at p - r - O
I UJ f mm mm* c
3
z oc vo > - » *2* t- UJ M < vO O
UJ u vo UJ z z UJ>J U O < C >mm O UJ — OC <%t a. oc CO • - JC
*

p-

o o
UJ 3
a Q
x
z
P-* • - *1 1
< i UJ U J 3 3 3 3 < — o M U . UL u.
Q . Q . 0 L Q k h h O U ) < U )-J - J -J< H Z j D D U J O l U
UJ UJ UJ UJo • - — — a . a. J LZ CL OCoc vo vo to
vo

5
+

eo
*

»£3

o
z o z
— Z UJ Z OZ O P- O U
UJ OC UO U 1
O K * * OC OC
U O 00 UJ UJ> > OC m> OL
OC OC UJ 3 3u u a v/> «/>
m
P*J
*

mm
+t

p ^

z
UJ
oc
oc
3
* •
O P- O

UJ
oc
UJ

z

M

Z i u o —t
O Z • - PP- Z >o — P- o^ O P*
U mm mm
1 C ^ - Z
ut-acza.t-»*(/>:s1 1 Z O Z ->J U O
wo z za z « u * —— O f . 1 1 O UJ OC Zo ^ x z u. <x ct P - 3

OC
Gd
UJ
UJ
UL
-J
VO
O X Z
O O ^
u - i o r
1 u- pp- » 1( O h h

-J Z
^ •»
UJ ^

< < <
- J UJ UJ
CD Z Zz oc
Z P^ vo

GD
O
<T

^
O
^

o

oc
oc

g 2

p-

u

2 zS

UJ

1/1

LU O

U J M C L<

> V 0 OM O l O Q
• - OC - * - J~ O t OZ UJ
• • • «/l
Q OC
3 UJ

INI < VOM * —UJ • - ^ CO
> UJ UJ UJ

*

-

Z

J Q C K ^ P - U U I

-J

P-

>

U O I U J O Z U J 0 C W 0
Q C < K H D U i Z < U J
UJ X 3 vo O vo O 3 ac
o u j j y z z o i

mm %A
O Z
Z <
o oc

P*

•-*

BLOCK
BLUEPRINT
BONARCROWNARDROWBERBONO
BOOKKEEPINGBOOLEANBORROW
BOTH
BOUND
BOUNDARY
BRAIN
BRANCH
BRANCHPOINT
BREAK
BREAKDOWN
BREAKPOINT
BRIDGEBRIEF
BRITISHBROAD-BAND
BROKE
BROKENBUFFER
BUG
BUILD
BUILT
BULK
BURNOUT
BUS
BUSINESS
BUT
BY
BYTE
C-1100CALCULATECALCULATORCALCULUSCALL
CAMBRIDGECAN
CANCELCANNEDCANNINGCANNOTCANONICALCANSCAPABILITYCAPABLECAPACITANCECAPACITOR-DIODE
CAPIT
CARD
CARE
CARGO
CARRIERCARRYTHESAURUS

CONCEPT NUMBERSSYNTAX CODES

663
58
324
424 0343
346
105
34
20
28
32178
323 0105524
404 0235
48 0042
23
380
689
23
105 0438 0048
32232
437
312
360
360
24
69
60
80
356
69
61
472
32027
32020
31
135
605
237
306
32263
444
32116
363
162
162
32102
706
162
32269
32269
413
228
340 0211
27
32166
331
316 0061
26

070043040
070043070
043
070
070043070
001
043
008080012
070043134135
070
070
070042070
043040070
070
070
070043001043071
001071001071134104135105070043070
043
134133
070
070
070
070
091012074013070
070
043040070
070
070043045040
070
009
043
134133136137071001
009
001
133
070
001071070
071001043
070
070040070
070
070043040

EXCERPTIN

ALPHABETIC OROER

Fig. 2

IV-10should each word appear in the thesaurus structure (that is, given a word,
what are to he its assigned concept classes).
Consider first the words to he included.

There is usually not muchquestion about the fact that common function words (such as "and11, "or","but") should not appear in the synonym dictionary, since these words outof context provide no indication of subject matter. A significant problem
does, however, arise in connection with very frequent words. These may be
non-technical words in the general vocabulary such as "discuss" and "make";or they may be technical words which, in their particular environment, arein effect reasonably common.

For example, in a collection dealing withcomputer science, such words as "machine", "computer", or "automatic" arein effect common words with reasonably high frequency.

If such frequentwords are included in a synonym dictionary, most documents will exhibit
occurrences of these words, and therefore significant matching coefficients
may be obtained between documents and requests, even though the technicaltexts may be really quite dissimilar (except for the fact that they may deal
with computers); if on the other hand these words are excluded, it thenbecomes possible that one or another document cannot be retrieved when infact it is pertinent.

Obviously some compromise must be made as usual,

between one's interest in retrieving everything even remotely useful (thatis, between the necessity of obtaining higfr "recall"), and the need not to
obtain too much extraneous material (the need for high "precision11).
A similar problem arises in connection with very low frequency words.
If, for example, a term such as "Morse Code" is excluded fromthe dictionary,then the very few documents dealing with this type of code may not be
retrievable. On the other hand, if "Morse Code" appears in a thesaurus
category together with many other types of coding systems, then a request

IV-11for "Morse Code" could also produce many other documents dealing withcoding systems, but not with the specific system wanted.
Once the words to he included in the dictionary are chosen, thesecond main problem which arises is the one dealing with the type ofsynonym categories to be created.

It is clear that if very broad andsomewhat fuzzy categories are wanted, such that a given category includes
both somewhat specific terms and also somewhat broader ones, then the
resulting dictionary will in general interpret a question in a reasonably
broad sense, and as a result the recall, that is the proportion of
relevant documents retrieved, will likely be rather high.

At the sametime the precision may be low, since it must be expected that much irrelevantmaterial will also be produced in the process.

If on the other hand thecategories are very specific, the chance of picking up irrelevancies ismuch smaller and therefore the precision is increased; the recall may
suffer, however, since relevant matter is likely to be missed at the sametime.

In either case, that is whether the categories used are broad or

specific, problems will arise if words with very different frequency
characteristics axe included in the same category.

Obviously theeffectiveness of the specific terms is much smaller, if these terms arein fact considered equivalent to broader terms of higher frequency by theapplicable thesaurus mapping.
This discussion then raises the possibility of providing different
thesauruses for different types of questions.

Specifically, if it isexpected that the user is interested in reasonably complete retrieval,
including most everything that is likely to be useful, then the thesaurus
with broad categories which provides high recall and low precision should

IV-12be used.

On the other hand if only a few items are to be retrieved, but

the user insists that these items must be relevant, then the specificthesaurus categories will prove more useful. This then confirms the wellknown fact that any kind of retrieval tool must be constructed with theretrieval environment in mind in which it is expected to operate.
Concerning now the problem of where a given term is to be put withina given thesaurus organization, this depends largely on the type of userwhich may be expected to avail himself of the retrieval systems. As an
example, dictionaries constructed for a population of students may be
expected to require an organization somewhat different from that which would
be useful to advanced research scientists. The latter might, for example,
be interested in the specific physical characteristics of certain devices,whereas the former are more interested in the uses of the devices. A "transistor" could then appear in a category under "three terminal switching
devices", if the users were to be engineers, but it would appear under"computer components", for a user population consisting of computer programmers.
The following principles of thesaurus construction may then be
enunciated:
1)

no very rare concepts should be included in the thesaurus sincethese could not be expected to produce many matches between
documents and search requests;2) very common high frequency terms should also be excluded from thedictionary, since these produce too many matches for effective
retrieval (it is in fact possible to replace individual highfrequency terms by much more specific compound or hyphenatedterms; for example, terms such as "computer" or "control" mightIV-13well be eliminated in favor of a term such as"computer-control",since the former are clearly ambiguous in many contexts whereas
the latter is much more specific);3) non-significant words should be studied carefully before any
are included in the list of words to be eliminated (for example,
a term such as "hand" should be included in a thesaurus dealing
with biology, but it should not' be included if its high frequency
count is due to expressions such as "on the other hand");k)ambiguous terms should be coded only for those senses which are
likely to be present in the document collections to be treated(for example, at least two category numbers must be shown for
the term "field", corresponding on the one hand to the notionof subject area, and on the other hand to its technical sense
in algebra; however, no category nuniber need be shown to cover
the notion of "a patch of land" if the dictionary deals with themathematical sciences or related technical fields);

5)

each concept class should only include terms of roughly equal
frequency so that the matching characteristics are approximately
the same for each term within a category.

Consider as an example some of the synonym dictionaries constructed
for use with the SMART retrieval system.

In that system it was founduseful to operate with a reasonably large number of concept classes (ofthe order of 700 for a given restricted subject field), and to use alsoa large list of non-significant words to be excluded from the content
indications.

This list includes in particular verbs such as "begin","contain", "indicate", "call", "designate" etc., which could not be
depended upon to provide safe content indication... It was also founduseful to isolate high frequency terms into separate categories sothat these terms would not impair the retrieval effectiveness of othermore specific terms.

IV-lA
Consider as an example of the kind of analysis which is normallynecessary for dictionary construction the concept number 101 representing
the notion of "tag". The word list attached to this concept originally
included terms such as "call", "designate", "identify", "identifier","identification", "index", "indicate", "label", "mark", "name", "point","signal", "sign", "subscript", and "tag". The concept occurred in 9k
documents out of some 500, with the following distribution of significant
terms:
Term

Frequency

Number of Documents

index

1?

7

signal(pulse)20

Ik

identify

6kAll other terms under concept 101 occurred a total of 91 times, accounted
for almost exclusively by the terms "pointed out", "indicated", and "call".
As a result of the analysis, the words "indicate", "call", "name", and"designate" were removed from category 101 and were included in the listof common words; the words "sign" and "signal" were also removed fromcategory 101, since they seemed to occur in the document collection onlyin the sense of "pulse signal" and therefore not in the sense of "tag";words with stem "identi" accounting for "identifier", "identification","identify", etc., were moved to a new concept number representing the ideaof recognition. At the end only the terms "index", "label", "subscript"
and "tag" remained under category 101.
Performance figures which measure the efficacy of various types ofdictionaries are given later in this report. Several methods of semi-IV-15
automatic thesaurus construction using aids in the form of frequency
lists and word concordances are also described*

B)

The Null Thesaurus and Suffix List

One of the earliest ideas in automatic information retrieval was
the suggested use of words contained in documents and search requests forpurposes of content identification.

No elaborate content analysis isthen required, and the similarity between different items can be measured
simply by the amount of overlap between the respective vocabularies. While
one should not expect that word matching techniques alone will normally provide adequate retrieval performance, it is nevertheless useful toconsider a word matching technique as part of a retrieval system, since
this provides a standard against which various types of dictionary procedures
may be measured.

This was one of the reasons for including in the SMART

system the so-called null thesaurus. [2,3J
The null thesaurus consists simply of a list of word stems, constructed by using the words included in a typical document collection,
each distinct word stem being furnished with a different sequence number.
The sequence numbers in the null thesaurus are then equivalent to theconcept numbers included in the regular thesaurus, with the exceptionthat each sequence number, of course, has only a single correspondent(words or word stem) in the null thesaurus, compared to the possible
multiple correspondences in the regular thesaurus. A typical sample
from, a null thesaurus is shown in Fig. 3, where the word stems arelisted in the order of increasing frequency of occurrence within adocument collection, rather than in the usual alphabetic order.

IV-16
Clearly, the operation which consists in using the sequence numbers
obtained from a null thesaurus for purposes of document and request
identification leads effectively to a word matching technique for document
retrieval, since sequence numbers and text words are in effect isomorphic.
The main virtues of the null thesaurus per se result from the fact thatthe dictionary look-up routine programmed for the regular thesaurus willserve also for the null thesaurus (because the structure of the two
thesauruses is the same), and that the null thesaurus permits the.word
matching operation to be confined to only those words actually includedin the thesaurus (since the others will not have an assigned sequence number).
This raises a question about the type of null thesaurus which should
be used as a standard for the word matching operations.

The following

alternatives appear of principal importance in this connection:1)

the null thesaurus can include complete English words, or canalternatively be made up from word stems, obtained from theoriginal words by a suffix cut-off;2)

an entry can be included in the null thesaurus for each text word
included in a certain document collection, or expected to beimportant in a given topic area; or, alternatively, function words
and other words not easily used for content identification may be
excluded, or marked with a special identifying code;3)

all non-common words, or word stems may be used, or only thosewords which have certain predetermined frequency characteristics(for example, words occurring more than 5 times but less than 100
times in a given document collection).

In the SMART system, all dictionaries (including regular and nullthesauruses) are based on word stems rather than original words; furthermore, common words appear on an exclusion list, and are thus notIV-17ui

5 ^9'o«"*<**iA«'i»a*o*4fM<**ift*f*«*o»«0'<**i**f*>e

-

x * x

1/1 , j i/>

^

^

<

*

Ul

Q. ^

-J

-I

v>

xooou>»uix<->.-ja»>-^^»wov>ujx
u«P2vox€r^ujuju»ujp^x^>*«oorkXw^<<ooouiui

X O O l*>O ID UlII*OJOCXflCi

t/)

•

>
«J

Ul

wwacozohh

UJox-

X I/) «/*

IP

2

ui a:
O < enUl (ft .

<r u i M

UJ

ui an

•(0
Q

5 *S* 3

St *

—

5

UJ

— o

M

as

Z a

_«

5 «w
—
u«

O -J

(£ ^ O . I

X

3

C

o

2

S u i x u i
« s
a— v
x »»
> > •>• >Ul
JUJO
O * O
41
<
Uli/)t/>O — — h- X
O O h O J
t- • s o a.
c u i u sx UJ •- KJ — LJ x x x o a
QCQL-^2Z«rfiuil*QX«<lZM^<^IMOlM,AI2^,/IK3>^SSSui^^

8

cur
U. 3
o

NMNNNNNNNNNNNMM

IV-18included in any of the dictionaries.

Experiments were conducted with the

SMART system, using both unrestricted vocabularies (full null thesaurus),
as well as frequency restricted entries (partial null). A sample set of
document abstracts of some 50,000 total running words, would typically
produce a full null thesaurus of about 2,800 distinct word stems, and apartial null dictionary of about 900 stems (assuming a frequency of at least
four occurrences for each entry listed).
If it is desired to list wbrd stems, rather than full words, thesemust of course first be generated by a suffix cut-off system.

To thiseffect, a suffix dictionary is built, a typical example of which is shownin Fig. 4.

The lookup procedure in this suffix dictionary is describedin the next chapter together with the lookup procedures for the otherdictionaries.

The structure of the suffix dictionary may, however, beexamined immediately.

It may be seen from Fig. k that each suffix is listedwith a sequence number and with one or more syntactic codes. The latter may
be used if it later becomes necessary to recombine stems and suffixes into
complete, acceptable words, as may be required, for example, to carry out
a syntactic analysis.
The syntactic codes included in the suffix dictionary represent only
partial homographs which must be combined with complementing codes attachedto the word stems in order to determine which suffixes match which stems.
(The syntactic codes attached to the word stems included in the null thesaurus
are not shown in the output of Fig. 3-)

For example, a partial homographsuch as 0T10 from the null dictionary will combine with a partial homographcode from the suffix list, such as V00S0, to form a complete homograph.

In

this case the complete code is VTISO, indicating a single object transitive
verb in the third person singular.

17-19Alphabetic
Suffix List
1 FICATIONFICATIONS
FIED
PIER
FIERS
FEES
FOLD
FUL
FULLY
FY
PYING

Syntactic Suffix Codes

058
059
060
06l
062
O63
06U
065
066
O67
068

058
059
060
061
062

N0US
N0UP
VOOCO
N0US
N0UP

POO 0

063

vooso

06k
065
066

ADJ
ADJ
AVI

N0VC
N0VC

067
068

VOOPO
ROO 0

100 0
GOOSO

Typical Suffix Dictionary Entries
Pig. h

ADJ

N0VS

ADJ

IV-20A typical suffix dictionary for English suffixes may contain about
200 entries. To simplify the look-up algorithm, noun suffixes may beentered in the plural as well as singular forms, and adjectival suffixes
may also be listed in the adverbial form.

Verb suffixes should include

the common endings "ed", "ing", and "s", as well as true verb suffixes
such as "fy" with their inflected forms.

(Multiple suffixes, such as"fying" could be detected by a dual scanning of the suffix list, looking
first for "ing" and then for "fy"; a dual scan is avoided if such multiple
suffixes are also entered in the suffix dictionary.)
In general, it is possible to encode word stems and suffixes in sucha way that no ambiguity results when the fragments are combined into fullwords.

For example, the stem "recti" is coded as a potential verb because

it can form "rectify"; the stem "reduct", on the other hand, is carried
without syntax codes, since it can be combined only with common suffixes
such as "ion" and "ible" which by themselves are carried as complete homographs, representing respectively "noun singular" and "adjective".
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 may be 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" can then be found by a double scan of thesuffix list.[2]IV-21C)

The Rirase Dictionaries

Both the regular as well as the null thesauruses are based on entries
corresponding either to single words or to single word stems • In attempting
to perform a subject analysis of written text, it is possible however, togo further by trying to locate "phrases" consisting of sets of words which
are judged to be important in a given subject area. For example, in thefield of computer science, the concepts of "program1' and "language" maymean many things to many people*

On the other hand, the phrase concept

which results from a combination of these individual words, that is,"programming language" has a much more specific connotation*

Such phrases

can be used for subject identification by building phrase dictionaries tobe used in locating combinations of concepts, rather than individual concepts
alone*Such phrase dictionaries would then normally include pairs, or triples,or quadruples of words or concepts, corresponding in written texts to themore likely noun and prepositional phrases which may be expected to be
indicative of subject content in a given topic area.
Many different strategies can be used in the construction of phrase
dictionaries. For example, it is possible to base phrase dictionaries on
combinations of high-frequency words or word stems occurring in documents andsearch requests; alternatively, one may want to use a thesaurus before appeal
is made to a phrase dictionary*

Under those circumstances, the phrase

dictionary would then be based on combinations of concept categories includedin the thesaurus, rather than on combinations of words.
Furthermore, given the availability of a phrase dictionary one canrecognize the presence of phrases in a given text under a variety of circumstances: for example, the existence of a phrase may be recognizedwhenever the phrase components are present within a given document, regard-IV-22less of any actual syntactic relation between the components; alternatively,
the presence of a phrase may be inferred whenever the components arelocated within the same sentence of a given document, rather them merely
within the boundaries of the same document; finally, even more stringent
restrictions can be imposed before a phrase is actually accepted, by
checking that a pre-established syntactic relation actually exists between
the phrase components in the document under consideration.
In the SMART system, the phrase dictionaries are based on co-occurrencesof thesaurus concepts, rather than text words, and t*o principal strategies
are used for phrase detection: the so-called "statistical phrase" dictionary
is based on a phrase detection algorithm which takes into account only thestatistical co-occurrence characteristics of the phrase components; specifically a statistical phrase is recognized, if and only if all phrase
components are present within a given document or within a given sentenceof a document, and no attempt is made to detect any particular syntactic
relation between the components; on the other hand, the "syntactic phrase"
dictionary includes not only the specification of the particular phrase
components which are to be detected, but also information about the permissible
syntactic dependency relations which must obtain if the phrase is to berecognized.

Thus, if it were desired to recognize the relationship between

the concept "program" and the concept "language", then any possible combination of these two concepts such as, for example, "programming language","languages and programs", "linguistic programs", would be recognized as
proper phrases in the statistical phrase dictionary; in the syntactic
dictionary, on the other hand, an additional restriction would consist inrequiring that the concept corresponding to"program" be syntacticallydependent on the concept n3.anguage". This eliminates phrases such asIV-23"linguistic programs", and "languages and programs", but would permit thephrases "programming languages", or "programmed languages".
A typical excerpt from a statistical phrase dictionary used inconnection with the SMART system is shown in Fig. 5*

It may be seen thatup to six phrase components are permitted in a given phrase, but that theusual phrase specification consists of two, or at most three, .components.
With each phrase

included in Pig. 5 is listed a phrase concept number

which replaces the individual component concepts in a given document
specification whenever the corresponding phrase is detected by the phrase
processing algorithm in use. For example, the first line of Fig. 5 showsthat a phrase with concept number 5^3 is detected whenever the concepts
5 ^ and 608 are jointly present in the document

under consideration.

Whenever such a phrase concept is attached to a given document specification,
the weight of the phrase concept can be increased over and above the original
weight of the component concepts to give the phrase specification added
importance.
Since the phrase components used in the SMART system represent concept
numbers rather than individual words, a given phrase concept number does
then in fact represent many different types of English word combinations
depending of course on the number of word stems assigned to each component
concept by the original thesaurus mapping.
The

syntactic phrase dictionary has a more complicated structure asshown by the excerpt reproduced as Fig. 6.

Here, each syntactic phrase

also known as a "criterion tree" or "criterion phrase", consists not onlyof a specification of the component concepts, but also of syntactic indicators, as well as of syntactic relations which may obtain between the

IV-*

PHRASE
CONCEPT
S4T
?*7

->*->
7*r>
?«<>
AQ4

*>oi

COMPONENTCONCEPTS_^.^_^_^-

••

544
*>tr
**ft
ftp
A<*

1*00
7ft*

?oi

*>A*

4?-*

64*

64*
?04
* 0 *
^Q*

60*

?M
7*1

64ft
?1«
1.704
7 A A

ft

• 0
-n
-n

-0
-0
-0

-0

-0

- A

-n
-n
-n
• n

-o

-n

-0
-0

- 0

-0

.0

-n
-n

-0
-n

-0

-n

-0
-r>

-0

-0

1AO

4 A
IP*
2or>

-0

-0
-0

?1

?Q*

-0

- A

-0
-0
-n

?1

ft*S
ICft
?4«

- A

-n
-n

-0

-0

- A

-0

-0

- A

- 0

. A

- O

-0
-o

-n

le*

- A

-o
- 0

-n
-0

AO0

ft**
*1
44

70

**?->

*A«

- A

-n

-rt

- 0

41 1
41 1
411
Aftft
Aftft
*Aft
ft ftft
*Aft
AAf,
*ftft
ftft6
Aftft

-j^r»

*->«

-0

-n

-n

n n
*7rt

- A

- 0

- A

-0

-0

4*

^*o
476
6^1

-n
-n

-n

-n

*»v>

t -x

ftOl

-0

-n

V»7

4ft
20*

- 0
-0
-0

-~»

-n
• n

?^4

*47
*47
*«7

4 *
•>4^

4*0

ftOl
?««

***
***

• A

-n

-n
- 0

-n

- 0

- A

- A

-n

-0

-0
-n
-o

- A

-0

. A

- A

^ « i

- A

-0

1 71

U"»

470

- A

- A

44*
AAA

*4*>

- A

-n

4*«

- A

. 0

'•1

* 0 1

40A
40A
1 «A

- A

- 0

?07

A 10

14

?A7
*?«

*o*

-^

61«
61 •
"ft

ft?!
ft?

f on
1 i*>

4A©
^A^

AO*

**?

i « *

. A

-n
-r»

-0
-A
-A
-A

-0
-o

-A

-A

-r>

- A

-0
-n
-n
-n

-0
_A

-0
-n

-0
-n

-A

-0

-n

-A

M Q

-n
-n

-n

-o

-A

?AQ

„o

-n

-A

-A

1™

- 0

-0

-n

-n

-n
-n

-n

-A

_n

-A

-A
-A
-A
-A

f O I

*«7

*OA

-n

AO*

-»•»'>

- A

1^0
610
60*
«^A
?*5
ft40

- A

-0

-0

- 0

- 0

_p

-n

-0

-0
-0

- 0

-0

-0
-0

- A

- 0

47?

- 0

-0

*4l

•»«7
ft«M
*16
51?
l?ft->
l?ft->
17ft->
l?ft">
l?ft7

2*7

-o

- 0

-n
-n
-o
-n
-n

*^ft

* A A

1 ^

-0

- O

™1

?6

* 1

-n

-0

1*4
?6
?1ft
ft?

- A

-0

-n

-0
-n

1 0 9

?16
2*6
A*Q

* H
AAA

47A

VM

->A

^oi

< 0 »

*0]
" 8

00 A
0« A

A10

0 7

644

Q7

*9«

l*n

-n

- A

-0

- 0

*>n
121

-n

-n

-0

-0

*ftn

- A

- 0

-0
-0
-n

- 0
-A
-A
-A
-A

-»
-0

-n

-0

-0

-0
-0
-n

-0
-0
-0

-0
-0

-0
-0

EXCERPT FROMSTATISTICAL PHRASE DICTIONARY

F1-. •-0'

IV-25included concepts. For example, the first phrase shown in Pig. 6 carries
the concept number 1*22, and the mnemonic indicator MAGSWI to indicatethat this phrase deals in one way or another with magnetic switches.
Fig. 6 also shows that the first component of the phrase must consist
either of concepts 185 or 62k,

while the second phrase component must

represent concept 225. The indicators after the dollar sign in the output
of Fig. 6 carry the syntactic information.

In particular, the information •given for the phrase MAGSWI indicates that this particular phrase must beeither of syntactic types 7, or 15, or 16.
More specifically, there exist four mail classes of syntactic specifications, corresponding respectively to noun phrases, subject-verb relations,verb-object relations, and subject-object relations. The four syntactic
classes are in turn subdivided into approximately twenty syntactic types,
each of which specifies a particular syntactic relation between the components.
The particular relations which apply to a sample phrase, labelled SYOTAX,
are shown in Fig. 7.

It may be seen in the figure, that the first componentof the phrase mast correspond either to concepts 11 or 158, whereas thesecond component corresponds to concepts 102, 188, or 170. Also specified
in Fig. 7 are the four allowable format types namely 1, 3, h and 13.
formats are specified in the center of Fig. 7 in the form of syntactic
dependency trees.
Dependency trees are characterized by the fact that vertical displacement along a given path of the tree denotes syntactic dependence,the dependent structures being always listed below the corresponding
governing structures.

This can be illustrated by using the example ofFig. 7, where the format type 1 specifies that the second component,

TheseIV-26

NAME OUTPUT
OF
CONTREE
CEPT

FIRST
SECOND TYPE 7 TYPE 15 TYPE 16
NOOE
NODE
SERIAL SERIAL SERIAL
CONCEPTS
143
398
399

«AC<*WT«4?9(lA496?t|/(2Z9|$7/i4?t]*/*Qft,iA +MANMCH*517(6^0)/H16)$V144tl5/40r»
MANROL = 2 8 6 ( 2 ' 9 0 ) / ( i n ) $ 7 / 1 4 S t 5 4 . # 1 5 / # 0 1 » l 6 ^ t l 9 >MATH0P*594(6]5>/(7*ll6t3 76>S7/l47
MCHRK D«69(689)/(6001% 1/148
M r H r O D « 3 ° 4 M * ? » 2 e n ) / M 4 9 4 i • 6 0 o # 6 n i \* i / i 4 o , n / 4 f > 4
MCHOPF«O^(61^)/{6"»0)S7/1^0
M'H0Rl»41(«!'n/(6*%6'MlS7/1«1 • H / 4 0 *MrHTlM,6qi(^17)/(^?f^o^f^01• ^ • • l ? * ! ) $ 7 / l * ?
MfMTTMx^QI ( * 1 " M / f f % M * ) f l / 1 ' ' *MrHTRAO^M9*1/ni9«6^lSl/l*4f44.f«4.«4^,104fl*/4«Afl6«'tl94»
MCMACC«*P'»(6^2>/(1?1 ) M / ! « o f
HCMC0R»5 5 ^ ( « > 6 9 ) / |is/40*

12M$7/il7f15/39«

MrMcrrs?^4(^4)/f 1'"1$1/1*'S6 + «1*/41''
M r M < p A ««*<>, ? i ? w c 171 ) f 1 / i * ? 9 n * t l « / 4 1 1
MMT00L«4 7 i M * 7 ) / < 6 0 0 l $ 7 / 1 6 « *vtN«TA*?94f24*>/(?*0>S7/l6*tl*/*12
MI$TRA«A68(4f • ' < » ! 1 / ( * 4 6 ) S l / ! * 6 « * * f : * / 4 l *Ml<iTRA»66«( U p /(»<*<•)* ! / ! 6 * » l * / 4 l 4
VT * r * A « 6 M ( 4 0 f ) / ( H i • * * - " ! * " / I A**
Ml?TQA«^6«(f *"M/< *4*)*7/l7->
MLTACC*4fl1 (A-»?W<«^>S 7 /171 f l*/41«»
M T W C j M t 7 ^ ( . 1 t 1 | / f i 1 4 If*/ 1 ^1
N * T L N G » 2 8 * M ! ' * 2 ) / ( * < » ! " ' 9 ) $ " ' / l 74 f l * / 4 1 f f 1 6 *MCTP^c«6*»0(f ! 8 > / ( ^ ? ^ ) S ' r / ! ' , <NLN^v<s7?7f40^,!?** )/r?07l$7/!7AN^r,rMD«Oi f 6 ^ n / C 4 " 4 t f / 1 7 7 t l * / 4 1 *N 0 G 0 ! G « 2 8 8 f 6 ~ 4 ) / c f n $ 1/178 • * • • l * / 4 l P
N0GS!M»67O(**1>/lft04)$7/18*
NCGVPT«2A0(?*4)/f ?88«4**«6*,<*>$?/1«1 • l * / 4 ? *M 0 f M M O ? M 6 r ) / ( ^ ? ) S V ^ ; t ! W 4 ? !
MPTp^t«^^"r(4*f?OAfl47f*6«) /('.?!
l f / ! 8 * » l e / 4 ? ?
MtirD^W«44^ f * 4 Q > / ( 4 4 l>«7/1«4fl<»/4?'>^i|MQAC«l«t£?'M/f*?«1$'T/!*c
MUMCPfjr,»7«(Ai%*10
1 / ( 4 ? * l S ' " l a f « ! e / 4 ' 4N,«M0A0«T?*C*o"r>/(6',Mf/M7
N j M R A T » « ; 0 ( 2 « *I / ( * 0 I M 1 I S 1 / ! 6 S

N'|M<TB-s?4?(4?*)/t6?c)$7/i*Q
M84)/«62*)S7/19r
N , i v T f G i 7 2 '^ p r p c ^ . c o ^ r l * * 5 t * l ^ » / l 6 1 c » S 7 / 1 0 ! t i r . / 4 7^
O A P r M C « ? i | ^ r ? * " M / f 2"M l ^ l / i . 0 " # * » *0 A T G F N « 6 * ' M ^ 4 > / t ^ 4 0 # ^ ? 5 ) $ l / l Q 4 f 3* f l«i/42^tl 74.
PATGfN»£*'M*'"3»/f<»4',W*6'Mf?'!96»**»1*/4?flf174
OMMTCM«M6(*«,*)/f-7t*f4>Sl / 2 ^ l t**»l« /4"**«l**Ot » * T J M * * 9 ' > ( * 1 » ) / ( "»41 ) $ 7 / < * f t * t 1 S / 4 ' * *PLyV49«^0*»C<k7T I / ( ? 4 l » $ - / ? « 4 t l S / 4 ^ 6
P N 7 r o N « 4 * > « ( 4 A « ) / M * ^ » $ V 2"* * « 1 S / 4 1 7p^qrpf «6]9(*n»/(6r2)$7/2A^«l?/4*^^© < ' > * < L V « 2 9 ' < M 2 > / r 6 ' * ? >S V ? * 7 f 1 * / 4 1 Q
p r ^ , « o e s 9 i ( « 0 # k f 6 1 * 1 / ( f * 8 > t * /?'.*
D0LP0L«39»(!^)/(^^^)S7/*>n^
P0WD1S«652( *4$t64«n/t64*>$l/210»'*«'»! */4*0
D^VlO*«65* ('POi /(649 \%\ f?\? %* +p o w « ^ " » 6 K B f*i4tA*61/fA4*)91/M4« , «'P^W^pr,?*-* (*«*,) /(*49)$7/?l*.
Or»wT<«tA«4 (4<^f•*?4>/f44'3 1^"'/21,*

EXCERPT FROMCRITERION TREE DICTIONARY

IV-27
corresponding in this case to either concept numbers 102, 188 or 170,be syntactically dependent on the first component corresponding toconcept 11 or 158; furthermore, the second component is specified as an
adjective, whereas the first component is specified as a. noun.

Examplescorresponding to each of the syntactic format frames listed are shown on
the right-hand side of Fig. 7. For instance, the first tree of format type1 might correspond to English phrases such as"syntactic analysis","syntactic synthesis", "phrase relations", "subject correspondence", andso on*

Because of the multiple assignment of concepts to phrase components,

and the multiplicity of syntactic format types specified for each phrase,a given criterion phrase generally represents many hundreds of English phrases
or sentences.

This feature is used to match the many sentence parts in thelanguage which are semantically similar, but syntactically quite distinct.
Since the syntactic dependency specifications are always directedfrom a dependent component to a governing component, the grammaticalstructure of a syntactic phrase, unlike that of a statistical phrase, iswell determined.

For the first example of Fig. 7 (format type 1) the string"phrase relations" is an acceptable interpretation, but not "relational
phrase"; similarly for format type 13 an acceptable interpretation is "thisanalysis is applicable to Russian grammar", but the transposed "this grammar
is applicable to Russian analysis" would not be accepted.

D)

The Concept Hierarchy

Hierarchical arrangements of subject headings have been used for many
years in library science and related documentation activities.

In general,such arrangements make it possible to classify more specific topics underIV-28PHRASE SPECIFICATION:SYNTAX(11,158)7(102,188,170) $ 1,3,^13
CONCEPTNODE 1NODE 1
11 ANAL

CONCEPTNODE 2

FORMATSNODE 2102

SYNTHESIS

1

SENTENCE
158

<3>

©A
PHRASECLASS

SUBJECT

CORRESPOND i

WORD

SYNTACTIC ANALYSISPHRASE RELATIONLANGUAGE

170

SAMPLE PHRASESINTERLINGUSYNTHESSYNTHETFORMATS

3

ANALYSIS OP SENTENCES
3©v/

WE CAN ANALYZE THE
LANGUAGEx...SYNTHESIZE A SYNTAX

O (D0
h

THE GRAMMAR IS NOWAVAILABLE FOR ANALYSISGROUPINDEPEND
RELATE188

GRAMMAR
13
SYNTAXSYNTACTIC

THIS ANALYSIS IS
APPLICABLE TO

8©0

Criterion Jhrase Specification
Pig- 7

RUSSIAN GRAMMAR

1

IV-29more general ones, and to formulate a search request by starting with ageneral formulation, and progressively narrowing the specification down tothose areas which appear to be of principal interest. Thus, one can startwith a topic area such as "mathematics", and from there proceed to "algebra"
which is a subdivision of mathematics, from where in turn one can go to"graph theory", which then leads to "tree structures", from where finally
one can obtain the syntactic dependency trees previously illustrated inFig.

J.
In a content analysis system, a hierarchical arrangement of words orword stems can be used both for information identification and for retrieval
purposes.

Thus, if a given search request is formulated in terms of"syntactic dependency trees", and it is found that not enough useful materialis actually obtained, it is possible to "expand" this request to include alltree structures or indeed all abstract graphs, by using a hierarchicalsubject classification.
A hierarchy of concept numbers is included in the SMABT system, and
it is assumed'that a thesaurus look-up operation precedes any hierarchicalexpansion operation. A typical example from the SMART concept hierarchy
is shown in Fig. 8.

The broad, more general concepts appear on the left

side of the figure, corresponding to the "roots" of the hierarchical tree;
and the more specific concepts appear further to the right.

For example,

concept 270 is the root of a sub-tree, this concept has four sons on thenext lower level, namely concepts 22k,

^71, ^72, and 488.

Concept 22^

in turn has two sons, labelled 26l and 33I5 similarly, concept U71 has
four sons, including 338, 371, ^58 and hjO.

It may be seen from Fig. 8,that the sons of a concept, representing more specific terms, are shownIV- 30
below their parents and further to the right.
The hierarchy of Pig. 8 also provides for the inclusion of crossreferences from one concept to another, which are connected to the original
concept by broken lines.

Such cross references represent general, unspeci-

fied types of relations between the corresponding concepts, and receive in
general a different interpretation than the generic inclusion relations
normally represented by the hierarchy.
It would be nice if it were possible to give some generally applicablealgorithm for constructing hierarchical subject arrangements.

This is, infact/a topic which has preoccupied many people including mathematicians,
philosophers, and librarians for many years.

In general, one can sa^' thatbroad concepts should be near the top of tree, whereas specific concepts
should be near the bottom; furthermore there appears to be some relationship between the frequency of occurrence of a given concept in a document
collection, and its place in the hierarchy.

More specifically those concepts

which exhibit the highest frequency of occurrence in a given document
collection, and which by this very fact appear to be reasonably common,should be placed on a higher level than other concepts whose frequency ofoccurrence is lower.
Concerning the specific place of a given concept within the hierarchy,
this should be made to depend on the user population and on the type of
expansion which is most often requested.

Thus, a concept corresponding to"syntactic dependency tree" would most reasonably appear under the broader
category of "syntax", which in turn could appear under the general classof "language", assuming that the user population consists of linguists
or grammarians; on the other hand, if the users were to be mathematiciansor algebraists, then the "syntactic dependency trees" should probably appearIV-31
cowccrr
NUMBER

•

***
584

**n

NUMBER
•
1
?

**
*84

62*

-n *
pn 4

1*0

074
114
494

192
2«
^25
7

101
101

10«

12*
1"

246
46»
460
401

^OQ

321
*4l

55?
62«
64?
64*

3**
«37

*4'
4«0

74• 5
114• 6494
7-fl* 819* 9
246 10*74 n
468 1246* i*
491 14-0 15
260 1648* 17-0 18
270 10?>4 ?*
261 ?1
331 2?
471 23338 ?437] 25
4*8 26
470 ?•*
47? 2834 ?9488 TO-0 31'09 32651 ?*
628 34642 oc
44 3
• A

1CC

*?~

1A9

321
340
380
*7*
64ft

A*0

*64
4A»
3*5

***

*30

M2

2*6

320

34l

-n *2

320
346

330
346
335
460
347
3^9

«5l
460
347

**A
37

*?A 3ft*24 ^032* 40'<4 3 41344 u->-0 43'21 44349 45
380 46«7? 4 764ft 4fl-0 49
326 *0323 «il

3?4
3?«
34* .
344

326

SEQUENCE

141
329

341

-REFERENCESHIERARCHY EXCERPT
Fig. 8

53
54
56
*6
87
58

IV- 32
under "abstract trees", which in turn would come under "graph theory", abranch of algebra.

It does not appear reasonable to expect that ahierarchical arrangement of concepts will serve equally well for all uses
under all circumstances.

Rather any hierarchy will serve its function, if

it can be counted upon to suggest ways of broadening or narrowing a given
search request or a given interpretation of the subject matter under mostof the circumstances likely to arise in practice.

k.

Dictionary Performance
In order to obtain an idea of the relative effectiveness of thevariou? dictionaries in a retrieval situation, seme experimental results
may be presented, based in each case on averages obtained with 17 searchrequests used in conjunction with a document collection of some 500 document
abstracts in the computer literature.

The retrieval performance is measured

by two parameters, known respectively as recall and precision.

Recall isdefined as the proportion of relevant material actually retrieved and ahigh recall score therefore implies that much of what is useful in acollection has actually been produced, during the search operation.

Precision,on the other hand, is the proportion of retrieved material which is actually
relevant, and a high precision score implies that very little uselessmaterial had been obtained as a result of a given search.

Clearly both ofthese parameters are important, and a perfect search would therefore
exhibit both a high recall and a high precision.
Recall and precision results can be presented in many different forms.
One of the simplest ways in which to exhibit the performance measures isin the form of recall-precision graphs.

Such graphs are obtained by looking

at many recall points for each search request, and computing in each caseIV-33the corresponding precision. For example, recall may be computed after
retrieving five documents, and again after ten documents, and so on,
in increments of five documents; in each case, the recall presumably
increases, as more relevant documents are retrieved, and the precision
may decrease at the same time if additional irrelevant documents are also
produced.

In any case, these several recall-precision points can beplotted on a curve, and the curves obtained can be averaged for many
search requests. This produces the typical recall-precision graphs usedin the present section.

A)

The Null Thesaurus

As previously explained, the null thesaurus is used as part of aword matching, or word stem matching procedure. This dictionary can,however, be used in various different ways: for example, it is possible
to apply the dictionary look-up procedure to whole documents, that is, toall word stems contained in a given document, or to only certain document
excerpts such as titles or section headings; furthermore, a given sequencenumber from the null thesaurus can be assigned to a document specification
with a uniform weight if, and only if, the corresponding word stem appears
in the given document; alternatively, the sequence numbers can be weighted
in such a way that the weight of a sequence number reflects the frequencyof occurrences in the document of the corresponding word or word stem.
Typical results obtained with the null thesaurus are shown in Pigs.
9 and 10, respectively.

Fig. 9 exhibits the average output obtained byusing the null thesaurus, first only for word stems occurring in the titles ofthe documents, and then for ^ i word stems contained in the complete document

IV-3^
abstracts.

Fig. 10, on the other hand, illustrates the effect of theweighting procedure.

In each case, a perfect result would be indicated by-having both a recall and a precision of 1, whichin the recall-precisiongraph implies a curve concentrated in the upper right-hand corner of thegrid.

The fact that the ciirves actually vary between a precision of 0.8

and 0.9 for a recall of 0.1, and a precision of 0.1 to O.k for a recall of
1 shows that the retrieval results were less than perfect.
Fig. 9 indicates first of all that the null thesaurus procedure, whenapplied to the document titles only, performs much less well than when thethesaurus look-up is extended to complete document abstracts.

Indeed theso-called "null title only" process produces a precision inferior by about
20 to 30 percent for a given recall level, compared to the other "full null"and "null title 2" processes.

It is interesting to note, in this connection,that the "null title only" procedure is effectively equivalent to the useof a so-called KtfIC index (keyword-in-context) which is widely advocatedand used for retrieval purposes.

Permuted document titles are listed ina KWIC index in such a way that a given title appears in the proper alphabetic position corresponding to each of the principal words contained in
the title (for example, a title such as "Information Retrieval" will belisted under I for information and again under R for retrieval).

It may bethat a XWIC index is more useful than no index at all, but it is quite
clear —

as reflected in the results of Fig. 9 — that a process whichtakes into account only the words from document titles is nob nearly aseffective as an equally simple process which matches word stems from falltext.
The other two curves included in Fig. 9 cover the already mentioned

Null Title
Only

IV-35
Pull Bull

Null T i t l e 2

S*h—

0.1
0.2
0-3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

O.83070.68000.57200.53230.48l6
0.4l420.3^890.26870.20160.1463

0.1
0.2
0-3
0.4
0.5
0.6
0.7
0.8
0.9

0.9446
O.8853
O.78810.70490.64370.58120.51480.4262
O.35181.0

0.2761

0.1
0.2
0.3
0.4
0.5
0.6

0.7
0.8
0.9
1.0

.9563
,8648
• 7968
.7381
6371
5589
,4877
4o86
3^26
0.2613PRECISION

.4

.6

.8

Comparison Based on Document Length(averages over 17 search requests)
Fig. 9•9

1.0

RECALLIV-36
Full Null

Null LogVec
O

O

0.1
0.2
0.3

0.84600.68410.5926
0.52160.4399
O.3897
O.32880.27620.22410.1643

0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9

0.95630.8648
C7968
O.7381
O.6371
0.55890.48770.4086
0.34261.0

0-2613

RECALL
Comparison Based on Stem Weights(averages over 17 search requests)
Fig. 10

IV-37cases where all word stems included in the complete document abstract arematched (full null), and where all word stems are used, but stems included
in document titles are weighted twice as heavily as other word stems (nulltitle 2 ) . As can be seen there is not much to choose between these two
methods, although the increased title weights seem to perform slightly
better for high recall points*

It should be noted that both of thecomplete word matching procedures produce very high precision when the recall
is low. This reflects the fact that the documents which exhibit the highest
similarity with the search requests, and which therefore are retrieved early
in a given search operation —assuming that documents are retrieved indecreasing order of similarity with the search requests — may be expected
to be almost all relevant to the given request. Or, differently expressed,a word matching procedure will be useful if the requestor desires to see
only a few documents, and does not insist on obtaining everything that isrelevant within a given collection.

The more sophisticated thesaurus

procedures may then be expected to be useful mainly for the purpose ofraising the precision for high recall values, that is, to retrieve documents
which cannot be immediately obtained by a word matching process.
Pig. 10 shows that the word matching procedure which assigns weights
to the stems in proportion to their frequency within a given document(full null) is much more effective than the equivalent matching process
in which weights are disregarded (null logvec).

The logical vector

process is one where each word stem is assigned the same weight, namely
1, and no distinction is made between more and less important stems.
To summarize then, the word stem matching procedure performs bestwhen all word stems are used from null document abstracts, or full documents,

IV-38and when the steins are weighted in accordance with their frequency within
the document.

Furthermore, this process produces high precision if aless than complete recall performance is desired, because documents
whose word stems match the stems present in the search requests are
generally found to be useful to the requestor.

B)

The Regular Thesaurus

The regular thesaurus provides synonym recognition and may therefore
be expected to be useful in retrieving some documents which cannot beeasily obtained by a word matching procedure alone.

The results obtainedwith two synonym dictionaries constructed for the computer literature areshown in Pig. 11. The first dictionary, called "Harris 2", is a thesaurus
constructed by hand using ad hoc methods to group the terms included in
the thesaurus.

The other dictionary, termed "Harris 3", was built using

the thesaurus construction principles, outlined in the preceding part,which provide for the isolation of high frequency words and for theelimination of many words whose information content is unclear.

Fig. 11shows a comparison between the retrieval effectiveness of the full nullthesaurus and the two regular thesauruses previously referred to..
It may be noticed first of all that the performance of the Harris 3
thesaurus is better throughout than that of the Harris 2 dictionary,
thus indicating the effectiveness of the thesaurus construction procedures
compared to ad hoc methods. Pig. 11 also indicates that the performanceof the null dictionary degrades as the recall values become larger.
Initially, the null thesaurus produces a higher precision than the Harris
2 dictionary, since false retrievals due to questionable synonyms

XV-39Harris Two

P u l l Null
r%

. ...

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

^

^_«„

0.1
0.2
0.3
0.4.
0.5
0.6
0.7
0.8
0.9
1.0

0.95630.86480.7986
O.73810.6371
0.55890.4877
0.4o860.3^26
O.2613-Harris Three
•

**

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.95510.82420.73890.67960.60700.5702
0.52330.48210.44520.3951

0.97350.8973
0.82U50.75510.71460.64990.60120.551^
O.4973O.ltiiSPRECISION

/\K
1.0
0.9
0.8

k L

Pk
p

•

Rs L

0.7

-\

0.6
0.5
>
0.4

RS is
N

0.3

y
1

1

>
0.2
0.1

0 1
.1

.2

.k

.6

•7

Comparison Based on Thesauruses(averages over 17 search requests)
Fig. 11

.8

•9

- »
1.0 RECALLIV-^O
included in the regular thesaurus cannot be generated by the null process.
Eventually, as more documents are retrieved, the performance of the nullthesaurus which offers no synonym detection at all becomes less attractive.
The Karris 3 dictionary is competitive with the null dictionary for
precision, but also maintains the recall advantage by careful isolationof high frequency words, and by the corresponding promotion of important
low frequency words.
As an example of the performance of synonym dictionaries, consider
the search result obtained with a collection on aeronautical engineering
for a request whose text reads "how does scale height vary with altitudein ah atmosphere".
with the search

The ranked output in decreasing correlation orderrequest shown in Table II indicates that more relevant

documents have low ranks (and therefore high correlation with the request)
for the regular thesaurus procedure than for the null thesaurus.

Moreover,the regular thesaurus has succeeded in promoting a number of relevant
documents, such as documents number 617,

621, 15+ and 302. One of thepromoted documents, number 621 is found to contain the sentence "variations
in air density between day and night in the region 190 to 280 km are foundto be small11. This sentence contains no matching words with the request,
and is therefore useless for a word matching procedure.

The regularthesaurus, however, contains both "air" and "atmosphere" in the same concept
class, thus explaining in part why the rank of document 621 improves froml4th for the null thesaurus to tth for the regular synonym dictionary.
The same type of analysis reveals that the relevant document 15+ contains
a sentence reading "density data are given for the altitude range of 370
to JJ-00 km", which is again used by the thesaurus since"height" are grouped in a common class.

"altitude" andIV-41

Noll Thesaurus

Regular Thesaurus

Rank

Document

Relevant

Rank

Document

Relevant

Promoted

1
2

622

yes
yes

1
2

622
616

3
k

617
621
578
619
15+

yes
yes
yes
yes

yes
yes

yes
yes

yes

3
k
5
6

7
• 8

9
10
11
12

616
IOC
578
619
617
613
620
6lh

ktf

15

371

5
6

yes

7
8
9
10
11
12

yes

15+
719
618

13
Ik

yes
yes

13
It

yes

621

15

.

Query Text:

10c'

620

yes

613
6lU
302
618
U36
710

1
"How does scale height vary withaltitude in an atmosphere ?"Example of Thesaurus Perfoimance
Table IIyes

1IV-^2
Fig. 12 does for the "Harris 3" thesaurus what FJ.g. 9 did for thenull dictionary: specifically, it shows the effect of using the thesaurus
for title words only, compared to using it throughout, and of applying
higher weights to the title than to the remainder of the text. The
results are substantia3.1y in agreement with those previously obtained
for the null thesaurus: the "title only" process is again much poorer,indicating that synonym recognition for title words alone, while better
than no synonym recognition at all, is still not nearly so effective asfull synonym detection; also as before, the increased weighting of title
words does not substantially add to the retrieval effectiveness.

C)

The Phrase Dictionary

The performance of the statistical phrase dictionary may be evaluatedby using the output of Figs. 13 and lU. Fig. 13 presents a comparison
between the early "Harris 2" thesaurus, and the same thesaurus supplemented
by statistical phrases of equal weight. The same procedures are comparedin Fig. lb for the more powerful "Harris 3" thesaurus. Fig. lU also includes
performance figures for two combined searches consisting first of the regular *thesaurus look-up followed, by a statistical phrase look-up, in which phrases
are weighted one and a half times as much as individual concepts.
Fig. 13 shows that the statistical phrase process affords a noticeable
improvement in retrieval effectiveness, compared with the "Harris 2"
thesaurus alone; a much smaller improvement is obtained over "Harris 3",
as seen in Fig. 1^. The third dictionary includes fewer ambiguities, thus
explaining why the phrase process is less important in this case.
For both synonym dictionaries it may be noticed that for very highIV-43Harris Three

H3 T i t l e Only

o — o
0.1
0.2
0-3

0.1
0.2
0.3

0.97350.89630.81890.77820.71370.65170.61020.5^920.5002

o.4
0.5
0.6

0.7
0.8
0.9
1.0

H3 T i t l e 2

V

o.k

0.5
0.6
0-7
0.8
0-9
1.0

0.4201

X— — —X

O.&37
0.7436
0.67330.65^70.58280.5328
O.47390.3925
O.287U
0.2320

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.98040.89530.85350.79070.73240.65700.61540.55790.48550.3969PRECISION
iK

1.0

K

I
0.9

1

0.8

\

fe.
r^v
1

0.7

"SSi L

0.6

NX

N

0.5

o.k

N
^

-3 c

0.3
^*^> c

0.2
0.1

0 1

— >

.1

.6

.2

.8

Comparison Based on Dictionary with Title heights(averages over 17 search requests)
Fig. 12.9

1.0

RECALLIV-M*
precision, the dictionary without phrases is preferable.

This result

reflects the feeling, already expressed in connection with the nullthesaurus, that the first few documents are best retrieved by thesimplest possible methods, when the chances of erroneous analysis are
smallest.

The statistical phrase procedure, as well as the regularthesaurus look-up, may always generate an occasional concept which isin error.

Such concepts may affect the retrieval results, thus depressing

precision.

On the other hand, the increasingly more sophisticated text

analysis which becomes possible through the phrase detection procedureis undoubtedly responsible for retrieving at least some documents whichcannot be brought to the surface by other simpler methods. This accounts
for the beneficial effect ofsall well-built dictionaries in improving
the recall performance, usually at a loss in precision.
The observed usefulness of synonym and phrase dictionaries raises
the important question of how such dictionaries are best prepared.

This

question is examined in more detail in the next part.

5-

Automatic Thesaurus Construction
Under normal circumstances, the task of constructing a subject dictio-nary for a given topic area is one which demands many skills, including
also a great deal of persistence and tenacity.

It is not usually enoughto be a subject expert in a given area, but training is also normally
expected in linguistics and philosophy.

Furthermore, since the task isof large proportions, a committee is often appointed which thrashes out
controversial questions and eventually produces a suggested standard
The search results exhibited in this report for documents and dictionaries
in the computer literature have been confirmed for other subject areas,
including aeronautical engineering and documentation, also processedwith the SMART programs.

IV-45Harris Two

H2 Stat. 1

.9551

0.6
0-7
0.8
0-9
1.0

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

.8242
.7398
.6796
.6070
5702
•5233
4821
4452

0.3951

0.9^71
O.83720.77860.72^20.67170.61820.5464
O.50340.46700.3704

.8
.6
,1 .2
.3
-4
-5
Comparison Based on Phrase Dictionary (Harris 2)(averages over 17 search requests)
Fig. 13.9

IV-^6Harris Three

H3 iStat. 1

o———o

X-

X

0.1
0.2
0.3

0.95880.87060.81690.78360.72050.6526
0.61520.55100.5035
0>213

0.1
0.2
0-3

0.97350.8973
82U5
7551
71^6
6U99
6012
551^
U973
0.U118

o.k
0.5

c.6

0.7
0.3
0.9
1.0

o.u

0.5
0.6
0.7
0.8
0-9
1.0

H3 Stat. 1.5
0.1
0.2
0.3
O.k
0.5
0.6
0.7
0.8
0.9

0.9735
O.8963
O.81890.77820-7137c.65170.61020.5^920.5002

1.0

0.U201PRECISION\
1.0••"•"J™

'

0.9
•
0.8

^s!
0.7

\ \
NT)

0.6

>s

s

^^^^ r

0.5

i

o.u

!

0.^1
0.2
0.1

01

1

1

.k

.5

.6

.8

1.0

Comparison Based on Phrase Dictionary (Harris 3)(averages over 17 search requests)

Fig. lk>
RECALLIV-^7
dictionary.

Such a committee produced standard frequently ends bysatisfying no one, despite the enormous effort which goes into its construction.
Clearly, if it were necessary to follow this particular pattern inorder to build a useful dictionary for retrieval purposes, then any saving
which might result from automatic search and retrieval methodology would
promptly be lost through the elaborate preparations required to bui3.d
dictionaries.
This situation has led to many efforts calculated to produce dictionaries
either fully-automatically, or in any case by more systematic procedures
than a committee-controlled process. Any reasonably standardized methodfor dictionary construction not only saves time and decreases costs, butalso permits a great deal more latitude in the type of retrieval procedures
which can be implemented.
1)

The following principal advantages are evident:

the retrieval procedures can be extended to collections in manydifferent areas, since the dictionary problem no longer constitutes an impediment;2)

it becomes possible to investigate differences in vocabulary
between different subject areas, notably the frequently heard
assertion that the vocabulary in some subject areas is "soft"(that is, not well standardized and ambiguous), whereas in otherareas it is "hard";3)

it removes any possible differences in retrieval effectivenessbetween different subject areas due to disturbances introducedby varying methods of thesaurus construction;k)

it becomes possible to investigate the retrieval effectivenessof a variety of thesauruses for a given collection, including
variations in the thesaurus size, in the number of concept
classes, and in the correspondents assigned to each class.

IV-48No matter what particular method of thesaurus construction is adopted,
the main virtue of an automatic process is to eliminate the human element,
either completely if a fully-automatic method can he found, or partially
if the process is semi-automatic.

In the latter case, it is desirable torestrict the human activities to questions which require only local
decisions within the given subject area, rather than global considerations
involving linguistic knowledge, and experience in subject classificationand indexing.
Some systematic procedures for thesaurus construction are describedin the next few paragraphs, and a simplified example is given of one
particular semi-automatic process.

A)

Fully Automatic Methods

Most automatic methods for thesaurus construction are based on the
vocabulary contained in a cample document collection assumed to be typicalfor a given subject area.[b,5,6]

In particular, a frequency count is madeof the words contained in a set of documents, and each document is identified by certain high frequency words included in it.

The choice of thesewords may be based strictly on frequency characteristics, or alternatively
on more complicated properties of the word distribution for the given
collection.

In any case, the sample collection is initially represented

by a term-document matrix, or a term-document graph as shown in Fig. 15*
The matrix element at the intersection of row
matrix represents the weight of termjiand column

in documentjof thei ; this same weightis represented in the graph of Fig. 15 (b) by the labelled branch between
nodes

T.

and

D^.

IV-49terms assigned to documentsTdocument
vectors

l

T

\

3

T

5

\

T

6

T

7

3

0

0

2

0

6

l

0

0

1

3

2

0

2

0

2

3

0

0

0

1

2

1

0

k
3

l

0

(a) Term-Document Matrix Showing Frequencyof Terms Assigned to Documents(b) Term-Document Graph for Matrix offig* 15 (a)Term-Document Graphs and Matrices
Pig. 15

IV- 50
Given such a term-document matrix or graph, it is now possible, bywell-known statistical association methods, to compute similaritycoefficients between terms, based on co-occurrence characteristics ofthe terms in the documents of the collection.

The similarity coefficient

between each pair of terms can then be made to depend on the frequency
with which the terms are jointly assigned to the documents of a collection.
In Fig. 15, for example, it may be noted that terms
Dboth assigned to documents

and

D^

T,

and Tgare(although with differing weights),

while they are both not assigned to documents

T>and D-. As a result,

the term association process may assign these two terms to a common
thesaurus category.
For the example of Fig. 15 an associative procedure might result in
the formation of three term (thesaurus) groups, consisting respectivelyof terms
andT., andD. ) , terms

Tg

T- andDp ) , and finally terms
toD- and(because of joint assignment to documents D.
TrT-,(because of joint assignment to
T-

and

T-

D-

and

(because of joint assignmentD^ ) . The result of a term association process may then be

displayed as an association map, in which branches between terms represent
term relations, or, alternatively, thesaurus groupings. An excerpt froma typical term association map is shown in Fig. l6.[^,7>8] The thesaurus
groupings suggested by the map of Fig. 16 can be found by inspection.

B)

Semi-Automatic Methods

The methods outlined in the preceding part are based on the assumptionthat term co-occurrences in documents, or joint assignment of terms to
documents are indicative of term siMlarity or relatedness. This assumption

IV-51acceleration

propulsion

chamberfluidgaspressure

Excerpt from Word Association Map
Pig. 16

IV-52
may not always hold, and if it holds, its applicability may be restricted
to a given document collection rather than to a complete subject field.
For this reason, it is of interest to consider also somewhat less radical
procedures which avail themselves of a certain amount of human judgment.
These methods are generally based on various automatic aids, but use subject
experts for the basic task of defining the meaning of each tern being
introduced into the thesaurus.[9*10,11,12]
The basic idea is to start with a word frequency list, as before,
for the words included in a given document collection.

In addition, it isalso useful to have available a listing which exhibits the words in context,
so that a distinction may be made between individual word-uses for ambiguous
terms.

For example, a word such as "base" may be broken down into "base.11,"base ",and "base ", to represent, respectively "army base", "lamp base",and "baseball base" (assuming that those three uses of the term are in fact
present in a given collection). A standard "keyword-in-context" (KWIC)
list may be prepared automatically, to permit a human observer to ascertain
the individual word-uses for the terms included in a collection.

An

example of a typical KWIC index list, used in conjunction with the SMART
system is shown in-Fig. 1?.[13]Fig. 17 shows that the term "spectral" is used in the given collection
in only one sense, namely that of a "spectral norm"; the term "square" is,however, used in two senses in the concordance excerpt, first as a rectangle of equal sides (square matrix), and then as a power of two (squareroot).

The list of word-uses to be constructed would then include asingle instance of the term "spectral", but two separate examples of"square".

IV-5 <

4'mmm$m** m •» •«••»«»••

P.
£:

»»Mf

M»*E

= **

*"
— «*
*S

Ml

8U 4. 8

« l «

MI

S

X X
— Ml Ml

a.
mt
m
X»

M

*> W
MI MI
«*

W
X

v> — X MJM»X*«
W — X*-

z

M«

S

OMI
— A

SSSS

»•*

«- o

jIU
MO

Mb

W

w ^

w

l*• cSs

MI
Ml

^

a-

-i

a
r%

88..S
883S

v>

»"

Ml

W

a

m%

W

^
W
•*

X x
41 a
»MI

Mi

u

Ss Ss

ill
•» ^ •»
H
52

*•
«:MiI

Ml

- x
O
x* w

M

m

Mi

«

a

M»M»

»•
a •*

;88s

•- w

«» W

Mi

25>

*

ft
W»*
X
« » » M W
H ~ — Z>
••Ml
W

w
A

p»
Ml
X

•*» X
«M

—

•* w - «»« w «* >

M.
cj

W
> S
M

«
MI

Ml

>

.

JE
W Ml

wo

MI w

— «<
*

Ml Ml
»» x

Ml *-»

X M.
—U
K

58
•

>-*

. —
W Ml
•» « * Ml

MV «• - Ml

•

*» •»
«M W
• Ml
» ¥» ^1

A|

W

•«
W
«« ^
w
M« —

-. — <->»

X

r»

«•»

— «<
>«

wx

a

VI

m
-i

U

Ml

MIW

>
•»
o

—

W

«

Ml Ml 1 *X » •*»»MtW-^ .-• «« «- *•*v_» -< u. wv v-»

2"3
- x o

9 W
X
- m»
x a- Ml
«
» •

vn o

SSSS"
!«!>!
* * -

m.

•

«•
A.

a •v»
^

«M- o

«

-

MM*

M»«|

*
5W

*"

mi
W

• Wa

MI«
X
m*
«-» X

- £^

•-

M*
•- »•
WW
« «

Mi 9
^ M>

* 9
- o

«->

w

o

s —-.
S88S^
*g8S8

«

« Ml
«
«.U

S55SS
?*55£

0 M M ^« • » WWW - » * «•»
A. -

•

*

--*
m

O
»

-. «» —- ¥ » *a• «*w w«- « M•. *naw
Mi?2tS«i
M> « « * W« 3 « »M»••W9
W

M. w J * Q «Ml 41 Ml M* «M

(M »

U

o

«•»«

sit

§f*

w

88

;iiss*-«Mi

CI Ml X CI

Ml —• - M>MIX••MIW**

•

M. M.

X

X
Ml
» M»

•a
x

—

M.

s «•
w
X **

88
58
83

mw
aw
« M.
CI

aw
w«

«4

«M
Ml
A

>•

W Ml

Ml

X

—•
-X. 3W

— w
X W

O

WW

» M.
4L CI

X M.

w

X
•i w

a<

W» • »

M» M*

a a*

M* M*
Ml Ml

>
•
ml
&
>13

v.
3

•

CI

MM

X W

Ml

X «•» M^M « M «

• -J

W

W

X
K I M #

x a o«

W — » • Ml
M> X ****
M> Ml XWO X X W X
Ml W
• • MlM» — Ml tm m
Ml • - X — X( W 4 I - 0 3
O X w
O Ml X W W
3 X W W CI
M* M>
Ml

*- U.

«

•- X

—

-> m.
a MI

4L X
— MI

X

58

Mi

O • X
• • • «I Ml+- -» m

O

M

S8
Ml -•
-» X

X

Ml

m. o — mt a
« • "

wo
CI

MM

88
48 -#

O

a

M*

9 Ml

oX

O

X
X

«*««•»Mi • •

•« —

MX
X
••
A

X
CI

c*

M< W
«• X

m

a •

9 x wa

—
*n

w
x
w

MM

M* M» M» MJ
—

M*

— Ml

CI

^ wa
•-

«
£

a CIa

«• —

X

—

— A.
•*
•

M* X> W «« M » « «
W
M*

-rf

CI

m\

«-«-.•-

-1

X

MM

- Ml
w
w

W M J
w • • c# •• X X* •»••«
Ml Ml

> •

X

88
It
>
a 9

o «^

MI m x •*V t g « 4•4

• * «M
CI

oo
X «**
M* W

38*°

w
o

%o v .

• Ml Mi Ml
Ml
X ^

1

Mt
Ml
Ml
X

Ml Ml Ml

41 41 41•»*»••^- ^ ^

W M 4 f

|
¥m
W

WW

Ml Ml Mlw

Xs:

VI Ml Ml M» *n

•
Ml

Ml

88

^

•-

B

WW

W Ml Ww
w —•«*
X
M*w

ss

41 41 41 41 41

W W
• M4
W Ml M>

«*
<-»
a.
«

- i Ml»- S—I 8S
8 = *»

^>
••
X

CI

SW

41
- M i

M<
•k

M

Mt X

— —

-1
-J

u

ii
Mi X

Ml 41

a

>
B
«

o«*
«•Ml w

W«*
M»«

X

MM

M» W

to

v> «^»"•*SiMl

W v»o©

X

^ ••
s:^
^

88

M.

W

Ens

M> Ml
MIMl

•»

w
*A «
MI

X

W

a y

Ml

ill!

X
Mi

w

M

a

X

o

X

Ml V»
^ m
m. KJ

-#

41
Ml
X

8

o

^
%
«
%
^
»
«
^
««-»

* •

o

5

W «
«#% M l « X X 3** — X — ^ o¥»M*WM>«> W
Ml • • 9 4 1

X
W

8 8«4

ss

x So w

«o

m
Ml
O

aMl

•w

»2

9 0
41

M

w

N M A M M

Ml

«4
Ml

•» ^

Mf

»

9 9 4 8X M « M
W
MO

o

*<

WW

ir

x>

w
s «*a
X>W"»W

M.
W

Ml

>
-*
«
^
X
«•

8888

W O >MMl 9 M I M
M%M>X
Ml W W
* «
« W

W
41
41

^ ^>

'

w

w 0

«#

»^»
**

•>

•

~

s

«*«»-•- •«#a«* -Ml•«» - •«^- w* —

3

Ml

Ml

MJ Ml
CIO
41 «

•

•• .

W

• o *o

M»M*

o»

W
X

Ml

*•

a

a

;*!*»

M

X

i

Ml

««
^
^ m

48M

X

x-

•

««««««

M>

x
x
2X

iS

- * * •——
—

md

5
Ml

£588
•885

W
»
4fc MY M%

•»
~
X

Ml

x

W J «l -# -* ^

«M

••••«
M> W

u 48 MIM«
X V»^

a
w
«X

«n

w^
?c>
w

I i

Ml
M

O

*
^
«
*«
-

wo ^

•3»

S Ml W W

Ml

Ml

a

— «M.M> W

¥*

s

•a•
->

a
X

« • •»M»M»

w

41

Ml

Ml

»:iii
88..3

I

•

=5

8 M M

w

w
»•

M
W

i"8

Ml

Ml
M>
41

4"

4f 41
MJM/
mm

••
w

W

w
w

w

rsssx

—«»*^•»<«*•*•
««

Ml

>
^•
M
«#
««
M

«

x

a

«

' £

mmmmX

u

w

!•
CI

:i

s

• Mm* V
«
a MI

Ml
rw

«J
Ml
Mt
W
X

o

5 8 gS M
88
"

m
m
rm

•a
¥1

«Ml
^
w

V* «A «Tt

es

•
w
Ma

Ml

-«

sin
5

Ml
3

-rf - J

M. M. M.

5
W
MM•-»-*-

M.M. M. M. M

Ml
-J

X

r cuo ci• -« «« x axx x « «ww www

M>*
WW
MM Ml

»•

Ml

O

m«
w

ill!

88

J[

^

aaaa

Ml

«o

Ml

M. **
U *

m8 .8

I

«

si

Mi Ml — X {

Ml

r»

"S

Ml

•-

MI

«a
•

W

. Ml «

ssr-

X

••a
Ml«

28m

•^ > *• *M>Ml

8— 8— S«>t 2*» Sm

x 9

M!
5!

M-

88

»
MM

a
3 c
W
WMI
W«-

a W f*ox

M* « » M I
X X MM
— W W

Ml
X
CI
mm

»w
—
X

a x

9 Ml
M> Ik*
W
Ml «
Ml Ml

a X 3
P» •» WII

X X MlUl
X
X Ml «w• a^> - «_ixw w
a x

Ml Ml W
M M

mm M» Ml
M- Ml •-I »• X
a -i

aw
w
X

a
w«
wa
• • mt
— X

a

0.
at

Si:

IV-51*After the list of word-uses to be included in the thesaurus isavailable, it becomes necessary to group them into thesaurus classes.
This can be clone in various ways:
1)

an informal judgment can be made for each pair of word-uses
to decide whether in the subject area under consideration, they
are synonymous, and if so, they can be grouped in the same
thesaurus class;2)

a set of "syntactic frames" can be used, and those word-uses
which fit into the same frames can be collected in the same
thesaurus group, or, equivalently, a decision is made basedon whether term A can always replace term E in a given context
X.[9]This decision is of course not mechanized, but thedictionary maker is faced only with local choices withincertain narrow limits;
3)

a set of questions can be prepared designed to elicit answers
about the terms to be grouped, and each term can be identified
by the set of answers obtained in response to the proposedquestions; for example, one might ask "does this term represent
a physical object or process, or does it represent an abstraction,or is this question inapplicable"; a score of 1 may then be
assigned for a physical object, 2 for an abstraction, and 3 if
the question is not applicable.

At the end of such a procedure, each term is then identified by a set ofproperties (in the form of contexts which fit a given term, or in the formof answers to questions about the terms),

and the complete vocabulary

may be represented by a property matrix, as shown in simplified form in
Fig. 18.

It remains, then, to find the semantic distance between terms bycomparing the rows of properties representing the respective word-uses.
Specifically, rows which are completely identical can be coalesced
into a single group immediately; terms which are not identical may beIV-55properties identifying word uses,
word-uses
obtainedfrom collection

P

l

P

2

T

1 0

T2

0

1 0

T

2

0

T^
•

1 2

P

3
0

1

P

1
2

1

0

5

P

6

1 0

1 0

1

2

0

1 0

1

I

0 property inapplicable
1 property applies
somewhat
2 property applies
strongly
Typical Term-Property Matrix
Fig. 18

IV-57for a total frequency ofn/N,equal frequency are wanted.
Passuming that classes of approximately

The process of generatingN

classes frominitial property sets ifiiy now he carx*ie& out as follows:

1)

a

Px M

word-use versus property matrix (similar to thatshown in Fig* 18) is constructed;2)

the property vectors are sorted into numeric order, and theset of3)

Pproperty vectors is reduced to only the distinct

property vectors, say

Q- < P;

since each of the

distinct vectors is to account for aQ>word-use frequency ofn/N,each vector is examined to see

whether the total frequency represented by that vector isapproximately
h)

n/N;

if a given concept vector occurs with a frequency smaller thann/N,

it represents too small a class and should be combinedwith other vectors; this is done "by deleting a sufficientnumber of questions (columns of the property matrix) to obtaina resulting combined concept class of frequency approximately
equal ton/N;

let the number of distinct property vectors

which result be equal to5)Q^ < Q,;

some property vectors account for too large a frequency count,
and ought to be broken up by using the concordance to formulate
additional questions so as to resolve finer shades of meaning;
this eventually produces

6)

Q-

distinct vectors(Q~, > Qp);by alternately using the procedures of parts h) and 5), thefrequency count of each of
approachn/N,

Q* • N

vectors eventually may

at which point the process terminates.

Consider, as an example, the list of word-uses shown in Fig* 19 (&)•
accounting for a total frequency count of 2198 word instances, andassume that it is desired to form a thesaurus with 5 concept classes.
Each concept vector should then cover approximately 2200/5 * V*0 ™>rd

IV-58

Original
Word-Uses

Frequency
in corpus

computer508.

system

263
186
139
130
127
12U
121
112
106
102
98
9k
88

digitaloperatecircuitprogrammachinegeneratefunctiondesignequation
logic
memory
data

2198
i

•

\

1

(a) Original List of Available Word-Uses
Pig. 19

IV-59occurrences.
After applying the three questions of Pig. 19 (b) to the original
corpus, one obtains the set of property vectors shown in Pig. 19 (c).
After ordering the property sets in increasing numeric order, andcombining the word-uses with identical property vectors, a reduced
property matrix is obtained, as shown in Fig. 19 (d). This matrix
contains 9 property vectors instead of the desired ?•In order to reduce the number of vectors, the class with the smallest
frequency count is examined (consisting of the term "logic" with afrequency of 9? instead of the desired kko).

The elimination of question

B will not avail, since the reduced property vector (3,2) does still not
combine with any other row.

Eliminating question A, however, produces

the reduced matrix of Pig. 19 (e), consisting of five classes with frequencies
varying between 2-^8 and 632, close enough to the desired value to terminate
the process.
Whether the suggested process is always manageable remains to beseen; however, in view of the obvious simplifications involved, and theneed for context-limited local decisions only, it seems worthwhile toattempt an implementation in an operational situation.

6.

Semi-Automatic Hierarchy Formation
The need for a hierarchical arrangement of terms, or concept classes,

as part of an information retrieval system is by no means obvious, although
it is easy to find useful applications for a well-constructed hierarchy,
particularly when search strategies are considered which are designed toproceed from more general to more specific search formulations or
vice-versa.

6oQuestion
NumberA.

Formulation

Is this word used in connection with computer
design and construction, or rather in connection
with computer use and programming ?
1. Construction and design
2. Use and programming
3. Both of the abovek. Does not apply

3.

Does this word refer to a physical object or
to an abstraction ?
1. Real, physical object
2. Abstraction or process
3. Does not apply

Vc.

Does the use of this word require that theobject of discussion be multiple, rather
than single: or, equivalently, does it imply
interconnections of some sort ?
1. Subject may be single
2. Multiplicity is implied
3. Does not apply(b) Multiple Choice Questions Applied to Words of Figure
Fig. 19 (continued)

IV-61

Word-Uses

Frequency

Questions
A B C

computersystemdigitaloperatecircuitprogrammachinegeneratefunctiondesignequation
logic
memory
data

508
263
186
139
130
127
12k
121
112
106
102
98
9k
88

3 1 1
1 1 2
3 3 2
2 2 1
1 1 2
2 2 2
3
1 1
2 2 1
4 2 1
1 2 2
k 2 3
3 2 2
1 1 2
2 2 2

(c) Original Set of Property Vectors

A B C

Frequency

Components

1 1 2
1 2
2
2 2 1

k8j
106
26o
215
632
98
186
112
102

system, circuit, memory
designoperate, generate
program, data
computer, machine
logic
digitalfunction
equation

2
3
3
3
\ h
\ k

2 2
1 1
2 2
2 3
2 1
2 3

(d) Ordered Property Vectors
Fig. 19 (continued)

IV-62

Questions
B
C
1

1

1

2

2

1

2

2

2

3

Frequency

632
487
372
>19
288

Components
computer, machine
system, circuit, memory
operate, generate, function
logic, program, design, data
digital, equation(e) Reduced Classes after Elimination of Question A
Fig. 19 (continued)

IV-63It has been remarked in this connection, that when words, or worduses, of unequal frequency are included in a thesaurus, or represented
on an association map of the type shown in Fig. 16, a hierarchicalarrangement results almost inevitably, since frequent words can be madeinto categories, and words of lesser frequency into subcategories.[k]Hierarchical association maps have in fact been constructed, using thefrequency characteristics of the words as a criterion.[15]In any case,no matter what procedure is actually adopted, it would seem that a useful •hierarchy which places general concepts near the top of the tree, andspecific ones near the bottom, must exhibit the expected frequency
characteristics which generally hold between broad and specific terms.
Since the construction of a complete hierarchy without any guidelines
is at the least a thankless task, and at worst an impossible one, methods
must be investigated to generate hierarchical arrangements semi-autamatically.
Three different procedures are outlined, all of which are based on a termproperty matrix of the type shown in Pig. 18, or a term-document matrix
as shown in Fig. 15 (a).
The first process directly uses the questions also used forthesaurus

construction, and breaks down the initial vocabulary as a function of the
responses elicited. An initial question is asked first, and classes ofword-uses are formed based on the responses to this question; the nextquestion is then applied to each of the resulting word classes which are
thereby broken down again, and so on, until the subdivision is sufficiently
fine.
The process is applied to the vocabulary of Fig. 19 (a) in conjunction
with the questions of Fig. 19 (*>)• The resulting hierarchy is shown in
Fig. 20, which shows the word-use frequency attached to each node.

iv-6kQuestion B is first applied to the complete vocabulary, thus forming two
groups of "physical objects" and "abstractions or processes", with afrequency of 1119 and 1079* respectively.
furnish the five classes

Question C is then used toalready shown in Fig. 20.[l^]A somewhat different process operates directly from the word-use
frequencies, and is therefore not based on the thesaurus groupings as is
the previous method.

Instead, the hierarchy is constructed first, andthe thesaurus is later based on the previously available hierarchy.

Astart is made as before, with a concordance and a word frequency list,
and the word-uses are selected for inclusion in the hierarchy.

The two-way

hierarchy is now started by choosing the word-use with highest frequency,
say wordT.,

and letting one node represent wordT

plus all words

like it, the second branch representing all "other" words not related toT..

The word group of highest total frequency is now chosen, and its

high frequency word is again used as a criterion for partitioning; thisprocedure continues until all word groups are small enough to be entered
as concept classes into the thesaurus.
At each point in the partitioning process the following local
decisions must be made;1)

the highest frequency word in the hi#i frequency word group ischosen, and it is used as the "central" word of the subbranch;
the other words in the same word group are then examined to see
if they fall into the same subbranch by being related in one way
or another to the central word; no relations need exist among
the words which form the "other", unrelated class;2)

if a given word cannot properly be placed in one of the twocategories (either related to the central word, or unrelated),
it is left at the present level as a parent of the words in the

C -P
0 ctf

•H TJ
-P

o

|6_
co'c
- o> 5

H

CO C
0) 0

tf
a

«J-P

e, genprogr
tal, e

10

•H

05

ft

a

^
L/*H

"8 cTTo&C

CD fc HS*2
Sii
CD a <*
CO
CD
CO
CO
CD

3s

-tf
O (U

*

&3
CD

ft

y / ^
S H
y j U CD -P
ft

ON O 6

H"y<—>cu
'

CO

ON

15
g
-P
co

^ vx
1.

^

t^

O «H
09

T^

3

£§

S3
CD O

V

CM § §
0

a>

«p

>era

•3

ICVJ

aj

£"8
J-

r^
ita>

•p

•H

CO n-3

ft

co
ON

O

ft

ss
CD

CD
•P

IV-66subbranches;
3)

if all words in a given word group are being placed in the samebranch with the high-frequency word, this word belongs one levelup as a parent of all the remaining words.

Consider again the vocabulary of Fig. 19. The highest frequency wordis "computer" (frequency 508), and two classes are first formed of words
like "computer", and of the "other" words (see Fig. 21). The high frequency
class is the one containing the term "computer", so that it is subdivided
again using the word "computer" as a criterion.

This produces

twoclasses consisting respectively of "computer, program, digital, memory"and "system, circuit, data"; the term "machine" which is generic to thewhole class is left on the second level.

The original "other" category canalso be subdivided, using the included high-frequency word "operate" as a
guide, and producing the complete hierarchy shown in Fig. 21.
A comparison of the hierarchies of Figs. 20 and 21 reveals that theword groups produced by the thesaurus question method of Fig. 20 may be
more reasonable; however, the frequency procedure is more systematic andmay conceivably be easier to apply.
The last hierarchy formation process is also based on a term-document
or a term-property matrix.

In thi3 case, however, the process of forming

the hierarchy is completely automatic, even though the original property
matrix may have been constructed by hand.

Consider two arbitrary' terms

identified by weighted property vectors.

The following conditions may

then obtain:
1)

terms A and B are identified by different properties, and assuch are not related;2)

terms A and B are identified by the same properties, and the17-67EdsoIV-68weights of the properties are reasonably similar for both terms,
so that neither term dominates the other, and they are placed in
the same concept class;3) terms A and B are identified by the same properties, but theproperty weights are higher for term A than for term B; then A
may be said to dominate B, and may be placed on a higher level inthe hierarchy;h)terms A and B are identified by the same properties, and B dominatesA.

In order to be able to make a decision concerning the similarity
between two property vectors, it is necessary to compute a similarity
coefficient between them.

In the present context, it is best to use an

asymmetric coefficient such that the similarity between termi and termji.

is not necessarily the same as between term

property vectors

v

and

V,

j

and term

representing terms

T.

and T.

Given
respec-tively, a possible similarity measure isi«in(4,v£)
S±i

U

Using this measure, a term-term correlation matrix can now be constructed, giving for each pair of terms the similarity measure
be noticed, that if the two vectors
equals 1, and whenvandequals 0. A cut-off value

v

and

v3

£..

may now be applied to the similarity

coefficients, and a hierarchy may be formed based on the following
algorithm: [ 11 ]It mayare identical, thenT T have no common properties, then
K

c.

c..

IV-69ifc.. and-ij
terms iif £..
j

c..
-ji
and

and £..

are both below the cut-off value
j

K,

then

are unrelated;

are both above cut-off, then terms

i andare synonymous and are placed in the same thesaurus

category;
ifc. . is below cut-off and' c..
-ijifinally, if

above cut-off, then term-ji

is a parent of termjin the hierarchical arrangement;c.. is above cut-off and c..
-ij-Jij is a parent of term i.

below cut-off, then termThis system may not generate a true tree structure, since a given
term may have more them one assigned parent.

The method is, however,fully automatic, and a manual revision after the initial generation canbe used to modify the resulting hierarchy to make it acceptable.

This canbe accomplished, for example, by introducing cross-references between terms
in the hierarchy to replace the connections which are not compatible withthe tree organization. A set of sample vectors is treated in the suggested
manner in Fig. 22. It is seen that property vectors which intuitively
appear to be similar will in fact be classified as synonymous (case 1 ) ,vectors which appear unrelated are classified as unrelated (case 2 ) , andvectors for which an inclusion relation is apparent are assigned ahierarchical ranking.
Various procedures have been suggested for updating hierarchies anddictionaries by addition of new terms and deletion of old ones.[11,12]
These must be used in conjunction with the dictionary look-up operationsin any operating situation.

IV-70Case 1 : synonymous terms
I 1 = ( 3, 0, 0, 5, 1, 0 )vd = ( 2, 0, 1, 5, 2, 0 )
c

"

1J

2(2, 0, 0, g, 1, 0) .8" 2(3, 0, 0, 5, 1, 0) " 9_ 2(2, 0, 0, 5, 1, 0) _ _8_c"J1 = 2(2, 0, 1, 5, 2, 0) " 10Assuming cut-off K = 0.7=>£ ii ' and £., > K

Case 2 ': unrelated terms
v1 - ( 3, 0, 0, 5, 1, 0 )f= ( 0, 1, 3,0, 1, 0 )For cut-off K = 0.7=>c. . and c. < K

Oasg 3 : term i is a parent of term j
v1 = ( 3, 0, 0, 5, 1, 0 )v5 = ( 1, 0, 1, 3, 2, 0 )Here £. . < K and c. . > K = > term i is parent of j

Sample Automatic Hierarchy Formation
Fig- 22

IV-71

References[l]G. Salton, Automatic Phrase Matching, 1965 International Congress
on Computational Linguistics, New York, May 1965*[2]

C. Harris, Dictionary and Hierarchy Formation, Information Storageand Retrieval, Report ISR-7* to the National Science Foundation,
Section I H , Harvard Computation Laboratory, June 196^.
\
C. Harris, Dictionary Construction and Updating, Information
Storage and Retrieval, Report No. ISR-8, to the National Science
Foundation, Section VII, Harvard Computation Laboratory, December

[3]

1964.
[k]

L. B. Doyle, Is Automatic Classification a Reasonable Applicationof Statistical Analysis of Text, Journal of the Association for
Computing Machinery, Vol. 12, No. k, October 1965.

[5]

S. F. Dennis, The Construction of a Thesaurus Automatically froma Sample of Text, presented at Symposium on Statistical Association
Methods for Mechanized Documentation, Washington, March 196k.

[6]

G.Salton, Data Manipulation and Programming Problems in Automatic
Information Retrieval, Communications of the ACM, Vol. 9, No. 3,
March 1966.

[7]

L. B. Doyle, Semantic Road Maps for Literature Searchers, Journalof the ACM, Vol. 8, No. k, October 196l.

[8]

L. Rolling, Euratom Thesaurus - Keywords Used within Euratom!s
Nuclear Energy Documentation Project, Report EUR 500.e, Euratom
Center for Information and Documentation, 196^.

[9]

K. Sparck Jones, Experiments in Semantic Classification, MechanicalTranslation, Vol. 8, No. 3-k, October 1965-[10] F. Levery, Organisation et consultation d'un thesaurus, 1965 FID
Congress, Washington, October 1965*[ll] C. T. Abraham, Techniques for Thesaurus Organization and Evaluation,
in Information Science, M. Kochen, editor, Scarecrow Press 1965*[12]

P. Reisner, Semantic Diversity and a Growing Mfcn-machim Thesaurus,
in Information Science, M. Kochen, editor, Scarecrow Press 1965*[13] Guy T. Hochgesang, SOCCER - A Concordance Program, Information
Storage and Retrieval, Report No. ISR-11 to the National Science
Foundation, Section III, Cornell Uhiversity, 1966.

17-72[ih]

M. Leek, Semi-automatic Semantic Classification Systems, Harvard
Computation Laboratory, unpublished manuscript, 1965*[15] L. B» Doyle, Expanding the Editing Function in Language Data
Processing, Communications of the ACM, Vol. 8, No. h, April 1965*