VI-I

VI.

T e m p l a t e A n a l y s i s and its A p p l i c a t i o n to Natural Language Processing S tephen F. Weis s

Abs trac t The basic first section of and this paper the introduces basics the of prethree

types of

templates

theoretical

template sents

analysis.

Building

on t h i s ,

the second

section

some practical

considerations analysis

needed

for the

implementathe of

tion of a general concept template uses of

template

s c h e m e , including

template

keywords.

An actual in Section

implementation 3 . of The

analysis

is presented for

scheme

template

analysis

the extraction text. Basic

bibliographic

phrases

from natural

language

implementation presented.

techniques

as well as experimental

results are

1.

The Basics A)

of Template

Analysis

Introduction analysis is a technique for partial semantic

Template analysis natural of

of natural language

language. string

It consists against

of matching a set words in

input

a predetermined of one or more will become

templates.

A template

is a string

or special

symbols. that

Its exact meaning If a match

clear a

the examples template and

follow.

occurs between

complete

some part of

the input, a specified

set of

VI-2

actions change data. single

is p e r f o r m e d . the input string

These may

involve direct

effects

which

or side effects which work on terminate after the discovery

other of a it con-

The process may template match

as in ELIZA

[ 3 ] , but more often in the input have performed.

tinues until all located and Each

template m a t c h e s actions

been

the associated template

is a string, usually made up of very the framework of a natural little language, meaning. words which

common w o r d s , which phrase. They may fit The

forms

template w o r d s generally

convey

d o , h o w e v e r , create a context fit and into the thus form a m e a n i n g f u l template and bear

into which other phrase.

These words of

the crux of the meaning environment.

the phrase are called the template of phrase template

the template

The words type

ir

thus indicate

the existence

of a specific The

as well

as qualifying gives

the e n v i r o n m e n t . to that

environment

specific meaning

phrase. First, gives

T e m p l a t e analysis the input

is basically with

a two step p r o c e s s . set.

is compared

the template

A match

an i n d i c a t i o n Second,

that a certain

type of phrase

is p r e s e n t . of the of input the ex-

the environment This either

of the matched provides

segment

is c h e c k e d .

the exact meaning

phrase or rejects amples serve

the original a n a l y s i s . the meaning template:

The following

to clarify the

of templates and

template

analysis.

Consider

VI-3

BETWEEN The zeros indicate

0_

AND

() one and only one word may

" h o l e s " where

occur.

This

template matches

phrases A, B and the holes

C in Figure 1 the wrong

It will not m a t c h D or E because number of w o r d s .

contain

A. B. C. D. E.

BETWEEN A AND Z BETWEEN HERE AND THERE BETWEEN 1950 AND 1965 BETWEEN AND BEYOND BETWEEN LAST YEAR AND NOW Sample input phrases Figure 1

A match

of

this

template with an input To verify

string this

provides it remains

an only in

indication

of a date p h r a s e . if the words

to d e t e r m i n e this case If such

in the template

environment,

the two words

in the h o l e s , are date in C, appropriate action

indicators. is taken in

is the case as

such as passing A and The

the dates

to a search program. f a i l s , the phrase

If as is

B the environment check

check

rejected. by the

environment

can sometimes template. template:

be eliminated the

use of a more version of

complete

Consider

modified

the previous

BETWEEN

19////

AND

19##

VI-4

The pound the inputs further

signs

indicate

the presence of any d i g i t . only C.

Of No and

in Figure of

1, this template m a t c h e s is needed

testing

the environment can be taken

in this case

appropriate

actions

immediately.

B)

Types of

templates types of t e m p l a t e s . required They are

There are distinguished in the

three basic

by the processing template

and results

achieved

two step 1.

analysis Under all

process. certain circumstances the information the to

Certainty

(CI).

template match determine

phase provides

required test the is

the meaning

of a p h r a s e .

The environment is

thus not n e e d e d . second of

An example of such a template examples:

the above

BETWEEN 19////

AND

19////

The

template

is complete w i t h i n

itself

and

the

environment in usable to

test may be o m i t t e d . analysis is expected The

While a high degree of accuracy from them, CI templates of templates are not required

in p r a c t i c e . provide with

large number

any degree of generality task of creating

in allowable

i n p u t s , along CI

the huge

the template

l i s t , makes

templates 2. of

impractical

for all but a few c a s e s . (C2-C1). by 0 the The second following: type

Conjecture-Certainty

t e m p l a t e , the C 2 - C 1 ,

is typified 0 AND

BETWEEN

VI-5

where

the zeros match

any

single word.

In this case a type of

template m a t c h phrase. This 1.

is not a guarantee example

of a particular matches

in particular thus only

inputs A, B, and the to existence

C in Figure

The system phrase.

conjectures is subject

of a specific rejection

This decision

possible template

depending

on further

examination

of the of

environment.

Environment words

testing may

consist

determining

if the environment Or it may table. produces consist

are of a specified environment

type or t y p e s .

of testing

words against a match by

In all cases of C2-C1 a c o n j e c t u r e which test, hence final

t e m p l a t e s , the template

is then completely the name

resolved

the environment Because nearly of this

"conjecture-certainty". templates provide

certainty,

the C2-C1

the same high degree of accuracy The analysis complex

as do the CI matches, needed C2-C1 be is greatly phrase

templates. however,

of the C2-C1 template due to the extra

is more

testing of the

to p r o v i d e templates specified. eased type small and

cortainty. is that only The job the number

The prime advantage

the frame of a phrase need the template required set

of determing of templates

for each

is significantly system

reduced. for

As an e x a m p l e , in study, journal

the phrase and a alone

implemented

this

detection journal

is accomplished

using

18 C2-C1

templates

list.

To do the same job with

CI templates

VI-6

requires Savings

450 t e m p l a t e s , each in search effort

longer

than

the present

18.

t i m e , storage are

space as well as

template

preparation 3. template only ture ment case

substantial. (C2-C2). The third type of of

Conjecture-Conjecture similar

is quite

to the C2-C1

in that yields

it consists

the frame of a p h r a s e , and a match that a phrase test exists. after Also

only a c o n j e c environin the is a seC2-C2 this

like the C 2 - C 1 , an is found.

is performed

the match

But

the environment conjecture. probably

test merely The result

weakens is not

or supports c e r t a i n , but the

original cond, and

b e t t e r , conjecture

and hence of the

designation.

It is apparent

that because these

uncertainty cannot be

in the final r e s u l t , analyses with expected The C2-C2 to be as accurate

templates

as those of the CI or C2-C1 whenever the

types.

templates are necessitated too large

environment use is the

for a phrase becomes of a look-up

or varied testing

for practical rules. Such

table or environment

case of author of all author as :

phrases w h e r e a list of all possible names is prohibitively large.

forms such

A template

WRITTEN

BY

may

give an indication

of a possible author

p h r a s e ; and (see is

there

exist 3, part

certain rules which may help C). But the final decision

the decision of phrase

Section still

type

VI-V

only

an educated

guess. thus

T h i s , h o w e v e r , is better the C2-C2 templates

than

no

guess at a l l , and

serve a useful

purpose when no other method From creation and reason study the standpoint u s e , the C2-C1

is a p p l i c a b l e . of generality templates and ease of For this the three this

seem b e s t . used in

the vast majority are of this type.

of the templates Figure 2 below

summarizes

types of

templates.

Template

type
CI C2-C1 C2-C2

Decision template c ertain

after match

Decision after environment test no t needed certain improved conjecture

conj ec ture conj ec ture

Summary

of

template

types

Figure 2

C)

Applicability

of template

analysis requires an a priori . that is tem-

The use of template analysis knowledge of every type of natural is specified

language

input

to be a n a l y z e d . plates and themselves

This

in the form

of the

as well as e n v i r o n m e n t a l If the input form

testing

rules or used.

look-up

tables.

is quite varied cannot be

unpredictable, In such and

then clearly

template and

analysis

cases more general analysis

complex

forms of

syntactic some

semantic

are required.

But

there are

VI-8

applications for template

in w h i c h analysis. While

the input

structure meets

the

criteria from

One such a p p l i c a t i o n and syntactic

is input

a console. that

the semantic

structures without called his

the average person the language

can understand

are almost uses,

bound,

that a person actually ±s
a

performance grammar, language.

small

subset

of his

understandable when extra

This p e r f o r m a n c e type rather required tend

set is further

restricted The

the user must time and sentence

than speak his input. to compose and type

effort

complicated When the user

structure

to discourage is added

such a c t i o n s . each input

the further is limited become

restriction to a specific

that for

set of input

t y p e s , the

inputs use of the

sufficiently

predictable

to permit

effective

template analysis. uses of tat ion.

The remainder and

of this paper

explores

template analysis

describes

a working

implemen-

2.

An I m p l e m e n t a t i o n Analysis The

of Natural Language A n a l y s i s

by

Template

theoretical

basis of template analysis has section. The present used in the section

been ex-

presented plores

in the previous

the practical

considerations analysis

implementation

of an e x p e r i m e n t a l

template

system.

VI-(J

A)

Keyword

analysis string against a template set can of

Searching often be a very templates

an input

inefficient

process. input

The vast majority s t r i n g , and do not have templates of

do not match

a given

these

nonmatching word

t e m p l a t e s , the majority the input.

even a single thus have it would matching templates by one

in common with

These

no p o s s i b l e

chance of matching to exclude

the given

i n p u t , and

be a d v a n t a g e o u s phrase. For

them from

the template of keyword

this reason This

the

technique

is introduced. Weizenbaum of

is similar [3]. The

to the scheme used

in ELIZA in each

technique

entails assigning As the

the words

template into

to be the keyword. those with all the

templates keywords have been tains of The

are entered are stored

the system, After

identical

in a g r o u p . list

templates The list con-

entered, a keyword for last

is created.

the keyword and

each g r o u p , and template for

the storage

location group. of the in group

the first

that particular

template matching list.

process begins with a search keyword

keyword the

If the particular

is contained template

i n p u t , then each member

of the associated

is searched contain is

for a possible m a t c h . keyword,

If the input does

not set

the particular

the associated scan of the

template

ignored. group

Thus with a single of obviously

i n p u t , an is eliminated

entire

nonmatching

templates

VI-10

from

the set which must be searched. templates is quite

The savings

in

search savings

time by keyword are word word other further

substantial. is the least

These likely

enhanced

if the keyword "Least

in the t e m p l a t e . in the

likely w o r d " least

is defined in

as

that

template w h i c h of

occurs

often

contexts the

than that

the given

template p h r a s e .

Consider

template: DURING O i TO < 0

Clearly

the use of

"DURING" as the keyword attempts than would

leads

to

fewer Thus,

u n s u c c e s s f u l match by eliminating

the use of " T O " . for a

those

templates which

have no chance template

match w i t h a given streamlines process. The keyword function; Without decision

input, the keyword and fairly

facility

greatly

the complex

lengthy

template

matching

template

technique

has a second

useful scheme.

it permits a middle-out

template matching algorithms solution

k e y w o r d s , template matching of where to s t a r t .

require a is to try of the is

The only

every word template. tested long

in the input as a possible If a match

first word of

o c c u r s , the next word template w o r d , and

the input For

against

the second

so on.

input

strings

this can be a time consuming templates

process.

This

is especially

true for nonmatching

since

rejection

VI-11

cannot

occur

until scheme

every

input word those

has been

tested.

Since have keyword)

the keyword

tests only

templates which

at least one word this common word search. For

in common with provides

the input

(i.e., the the of key

an ideal place

to start

inputs with

two or more occurrences as the principal to the left of the

the and

same k e y w o r d , one is designated searching in the begins there. Words

keyword of

template are

tested

against words likewise

to the left

the keyword hence this

in the i n p u t , and

for

the r i g h t ; and in

the m i d d l e - o u t w a r d study have

strategy.

Most

templates used the first in one or

their keyword

as either

last

element, only.

so that most

searching

is actually this

direction is that

But the important seed, that

thing about

technique for the

the search is uniquely nonmatches than after advantage taining

is the starting

point

search, of

determined. to occur after exhaustion

This also permits only a very few

rejection tests

rather A further con-

of the entire process

input

string.

of the keyword

involves

the inputs a given the

more

than one substring

which matches searches of the of

template. left

A normal matching

process the first

input

to right and picks out

substrings. designer

T h i s , h o w e v e r , may not be the intent who in fact may want

the system

the second, or possible

rightmost,, s u b -

VI-12

p h r a s e analyzed

first.

The solution

is easy using

keywords. con-

Inputs with m u l t i p l e m a t c h e s tain m u l t i p l e By simply occurrences

of the same template must for that

of the keyword keyword

template. principal

designating

the desired

as the

key, the proper Thus

substring

is analyzed

first. in template matching which

the keyword

technique helps

on two l e v e l s . must be tested a specific

F i r s t , it narrows against

the set of templates second it

the i n p u t , and

provides for the start

point

in both

the template and the matching

input

of the s e a r c h . faster and m o r e The similar

This permits

process

to run

e f f i c i e n t l y , as required

for on-line u s e . in a manner list is

template matching

process proceeds [13].

to that of a Markov

algorithm

The template the input out. The list.

is scanned found. process

in top down order until a match with actions are then carried

The associated

is then restarted

at the top of the template removal from the input repeated

Of course of matched of that

this n e c e s s i t a t e s substrings

string matching the type in the

in order

to prevent

substring.

This

is generally

done by replacing to the

substring

with a n o n t e r m i n a l

symbol a p p r o p r i a t e

of template m a t c h e d . subsequent end

This n o n t e r m i n a l may The process

then be used

template m a t c h e s .

terminates when finding

of the template list

is reached

without

a match.

VI-13

The a d v a n t a g e specific

of

the Markov

approach and

is that ordering

it enables a of ana lysis a desired to

hierarchy

of templates

be imposed template

in the system, as well as allowing to be maintained.

grouping

B) The

Implementation templates shown

conventions in the previous examples are While practical require space are quite

m a d e up of words and these are easy for an actual large amounts needed complex

are represented and

alphabetically. they are not templates amount of

to read

understand,

implementation.

Alphabetic

of storage with a v a r i a b l e Second, alphabetic And

for each w o r d . and

searches

time consuming. it necessary individually.

third, the use of a l p h a templates be

betics makes represented all have

that For

even synonymous example

the templates actions.

below

the same meaning

and associated

WRITTEN AUTHORED

BY BY BY

PRESENTED

The use of alphabetic be in the template

templates would From actual in fact many template

require

that all it

three

set.

experimentation such synonymous

appears and

that

there are large

templates,

thus a very

set can r e s u l t .

Clearly a

VI-14

shorthand problems

template

r e p r e s e n t a t i o n which overcomes For this reason numerical The conversion is achieved

these and

is desired.

templates to its

input v e c t o r s are used. associated template composed, numerical

from a word through a

concept

special is is

dictionary. for

The dictionary

is quite small and type w o r d s , that

the most p a r t , of functor

conjunctions, prepositions Words not "999" found

and a few other very are assigned

common w o r d s . the concept used 22

in the dictionary that

to indicate

they are u n k n o w n . contains

The dictionary into

in this concept

implementation numbers.

140 words which map is

The problem

of synonymous words the same concept the same word

solved

by assigning The numeric the natural natural from

to the desired

words

number. as

input vector m a i n t a i n s language input.

order

The example below shows the numeric vector the treatment that

two results and

language

inputs and Note

either

of them.

of synonyms

unknowns.

Input A: Input B:

PAPERS WRITTEN

BY LESK ON BY WEISS

CLUSTERING CONCERNING

A R T I C L E S AUTHORED TEMPLATES Vector: 27 15

Concept

12

999

999

999

Sample natural language and numeric input strings Figure 3

VI-15

Templates addition following templates

are also

stored

in numeric

form with in the

the

of some special paragraphs. and stored

conventions

explained of this

In the remainder input strings

study to be

all numeric.

are assumed

Occasionally, presented

h o w e v e r , some alphabetic of clarity.

examples may

be

for purposes

The use of clearly The

numeric solves the

representation previously reduction number

of inputs and synonymy

templates problem.

mentioned

resultant the 44

in the size of the template

set varies with

of synonymous w o r d s , in the present are required instead of more than

implementation two thousand. easier. amount and

templates Numeric

templates

also make

storage and

searching

U n l i k e an alphabetic of s t o r a g e . faster

string, a number of numbers of variable

uses a fixed easier

Comparison

is also

than comparison

length alphabetic provides and a more more

strings. compact

In general data

the use of numeric and

vectors

representation

facilitates

faster

efficient

processing. numerically in a similar into

Templates are stored manner to that of input in alphabetic

strings. form and

They may be entered

the system

run through a dictionary in numeric form. The form 4. 5, 6

l o o k - u p , or they may latter is used in this is given

be entered

implementation.

The general

of a template The reason for

in the BNF definition of the digits

in Figure in lines

the d i s t i n c t i o n

VI-16

and

7 will b e c o m e

clear

in what

follows.

1. 2. 3. 4.

T e m p l a t e ::= <Parameter element s>

part>

<Template <Key

Parameter part ::= <Action number> position> <Length>

T e m p l a t e elements ::= < T e m p l a t e symbol> <Template symbol> <Template elements> T e m p l a t e symbol ::= <Concept number (i.e., a number _>11)> | Minus sign ^Concept number) Template Template Template symbol symbol symbol ::= ::= ::= 0 (zero) 1-9

5. 6. 7.

digit 10

(ten)

Formal definition of a Figure 4

template

The act ion number routine which is m a t c h e d . action the the numer.

is the i d e n t i f i c a t i o n

number

of an

action

is to be executed More than one

if that particular can have a

template

template

particular within in

The key posit ion indicates And length is merely template -16 11

the keyword

template. template. 55 3

the number

of elements

A general 7 15

is shown 0 18

below: 5 18

The

three p a r a m e t e r s

here

indicate if this

that action template

routine Also is

number

55 is to be called

is m a t c h e d . the keyword

the template in p o s i t i o n

is seven elements

in length and elements

three of the template

(i.e., the 1 1 ) .

VI-17

As shown in Figure of numbers meaning. Figure and The

4 the template

elements

consist

certain of these numbers simplest

have

special in

form of a template sample inputs.

is shown The

5 along with entirely than ten.

several

template integers

consists greater only

of concept

n u m b e r s , that

is positive an input

Such a template m a t c h e s of concept

if and and

if an exact match occurs.

numbers, ordering,

contiguity lined

The sample

template m a t c h e s B

the u n d e r because ordering; example

portion of input A. the concepts D the 15 and

It does not match C has

not all and and in

are p r e s e n t ;

incorrect In this

16 are not a d j a c e n t . template

in all subsequent for

s a m p l e s , the three

parameters

are omitted

simplicity.

Template: 15 Inputs: A. 11 B. 11 D . 15

16 99 9 16

17 15 17 16 16 17 16 17 18

C . 1 7 15 18

Example of the simplest template form Figure 5

VI-18

Most

desired

templates

can be specified

in this

form

but to

there are specify

several

drawbacks.

F i r s t , there

is no way is a

templates with

" h o l e s " in them, And second

that

template of In templates,

with n o n c o n t i g u o u s templates particular required

elements. by

the number large.

this format

is fairly

there is no facility of which

for combining

similar

or templates shorthand combining

one is a subset numeric

of a n o t h e r .

Thus, a By set

for representing

templates

is needed.

some of the t e m p l a t e s , the size of the template search time is also saved since one search

is r e d u c e d , and of the combined

template

replaces

the several

individual

searches . The present template implementation The first allows four options in

specifications.

is the optional a certain

concept. concept an

It is often useful in a template input

to be able

to specify

as being

optional.

The template m a t c h e s If any

if all the required also m a t c h , routines. this

concepts m a t c h . is noted

optional in by a

concepts

for possible concept

use

the action minus below

An optional the concept

is denoted In the

sign preceding (given here

number.

example all

in a l p h a b e t i c )

the template matches

inpu t s shown.

VI-19

Templat e: - PUBLISHED Input s : A. B. C. D. IN PUBLISHED PUBLISHED PUBLISHED

IN -THE -YEAR

IN IN THE YEAR IN YEAR

Example of optional concept Figure 6

facility i

The example combining

indicates

the u s e f u l n e s s This

of this

technique in is also useful

several

templates.

facility

in combining as is seen

the positive

and negative

forms of a phrase

below. Temp late • ,,NOT PUBLISHED IN Inpu ts : A . B. PUBLISHED IN NOT PUBLISHED IN

p O S i t ive and ne gative phrase Fig ur e 7 _

combinati on

The

indicated

template m a t c h e s both

inputs.

The o c c u r r e n c e

or n o n - o c c u r r e n c e routine always so that tries

of the " N O T " is passed

on to the action The system

the proper

action may be taken. of the optional

to match as many

concepts as

possible

and of course

the keyword

concept may not be

op t ional .

VI-20

It is often desirable in them, that is having

to specify

templates with This is

holes

noncontiguous

elements.

made p o s s i b l e by the use of three The first type, the single This

types of skip

operators.

skip, is indicated that exactly

by a zero in word this

the t e m p l a t e .

specifies The example

one input

is to be skipped. operator^ words

in Figure only

8 illustrates

The template m a t c h e s and

those

inputs with the by one B only.

"COMPUTER" word.

"DEPARTMENT"

separated input

arbitrary

Thus a match

occurs with

Template Inputs: A B C

COMPUTER COMPUTER

0

DEPARTMENT

DEPARTMENT

COMPUTER SCIENCE DEPARTMENT COMPUTER SCIENCE EDUCATION DEPARTMENT

S ingle skip <operator Figure 8

A second This is indicated

type of skip operator by a number i where

is the bounded

skip.

1 £ i < 9 , and

specifies be skipped

that as few as z e r o , or as many as i, words are to at that point in an effort to match the t e m p l a t e . the fewest

If several m a t c h e s number of skipped

are p o s s i b l e , the one involving words is c h o s e n . Figure

9 demonstrates "COMPUTER"

this f a c i l i t y .

The template matches

any input with

VI-21

and

"DEPARTMENT" Matches

in that order

and

separated

by

two

words not

or l e s s .

thus occur with three

inputs A, B and words.

C, but A match that of

with D because also input

there are

separating portion of

occurs with

the underlined occurrence

of E.

Note

in the

E, the second also

"DEPARTMENT" This

instead

first would usefulness

satisfy

the template.

illustrates

the

of skipping

the least

possible

number

of w o r d s .

Template: COMPUTER Input s: A. B. C.

2

DEPARTMENT

COMPUTER DEPARTMENT COMPUTER SCIENCE DEPARTMENT COMPUTER SCIENCE EDUCATION DEPARTMENT
COMPUTER INFORMATION AND SCIENCE DEPARTMENT COMPUTER SCIENCE DEPARTMENT DEPARTMENT

Bounded skip operator Figure 9

The adequate For those

facility

to skip

from used

zero

to nine words

is

for most few

templates

in this

implementation. than nine

templates

for which

a skip greater of

is n e e d e d , no upper is really desired.

bound To

on the number this,

skipped unbounded

words

indicate

the

vi-:}2

skip

is used.

This number

is specified

by the number

ten and in an A

causes effort

an arbitrary to match

of input words Figure input

to be skipped

the t e m p l a t e . occurs with

10 d e m o n s t r a t e s A.

this.

match always a string

The ellipsis

indicates not

of w o r d s

of arbitrary

length but of course

containing

the word

"DEPARTMENT' 1 .

T e m p l a t e : COMPUTER Input: I A. COMPUTER

10 ...

DEPARTMENT DEPARTMENT i ' i j 1

i

—. Unbounded skip operator Figure 10 _

For all

the skip o p e r a t o r s This

a record

is kept of how many can then be used by the

w o r d s are skipped. action routines. reduces

information

The use of the optional concepts and the number of needed templates

skip

operators opposed for this

to 44 as needed

to the more

than 81 which would

otherwise be

implementation. While the previously system, It presented other conventions facilities are adequate

for for that

the present future use.

several

are

suggested specify

is sometimes

useful

to be able to and

a group

of words may appear

in any order

in an

VI-23

assignable in Figure

proximity 11 m a t c h e s

to one a n o t h e r . any input

For

example

the

template

containing

the words group.

"INFORIt to words

M A T I O N " and matches

" P R O C E S S I N G " w i t h i n a three word

inputs A, B and C. sentence

This can be generalized in the same input.

in the same

or words

Template: Inputs: A. B. C.

3 (INFORMATION INFORMATION INFORMATION PROCESSING

PROCESSING) PROCESSING TEXT PROCESSING

OF

INFORMATION

Arbitrary

ordering and Figure 11

proximity

A second

addition

recommended

for

the future

is the

facility by

to indicate any member

that a single of a group

template

spot may be occupied This can be

of c o n c e p t s .

partially desired some

accomplished words into

in the present the same concept

system by mapping number. But

the

there are words

instances different To allow required templates

in which concept

several n o n s y n o n y m o u s n u m b e r s ) may appear would

(i.e., with templates. of two standard

in similar

such a substitution templates. and

reduce

the number 12 shows two.

The example

of Figure

a third which

combines

the first

VI-24

T em plates :

A. B.

COMPUTER

PROGRAM

COMPUTER SYSTEM COMPUTER <PROGRAM, SYSTEM>

A+B.

Com bination of simi.lar templates Figure 12

A third

possible

improvement would rather

render whole

sets of Notice, \

w o r d s as optional for e x a m p l e , that

than single words only. 6 the template matches

in Figure

PUBLISHED PUBLISHED both

IN THE IN YEAR In this case it might as a phrase rather

of which have dubious m e a n i n g . to make

be desired

"THE YEAR" optional

than as individual w o r d s .

This can eliminate For

undesirable these they

m a t c h e s with partial p h r a s e s . suggestions do not add

the most part

any power template

to the t e m p l a t e , but set and more efficient

do allow a more template

compact

searching. This section has described under study. 13. the template system input The analysis is is con-

implementation summarized verted

The complete language

in Figure

Natural

to numeric then

form by

the d i c t i o n a r y .

template If

analyzer

tries

to match a template with

the input.

VI-

a match template

is found,

the action

routine associated results

with

the

is e x e c u t e d . possibly

This process

in a modified variables process

i n p u t , and Control

in the setting

of some side effect and the

then returns

to the template analyzer template m a t c h e s analyzer

continues process be used

until no further The

exist.

The can

then h a l t s . in a number

template

is a tool which application

of a p p l i c a t i o n s . 3,

One such

is discussed

in Section

Natural Language Input

:> Dictionary

Numer ic Inpu t Vec tor

^

ft
1 l

ft

J

•M V a r i a b l e s

Side

Effect

Template Analyzer JL

k.

" Action I
Rout ines

3Z
r • -i Templates

Summary

of

template analysis 13

system

Figure

VI-2b

3.

An I m p l e m e n t a t i o n This

of Template

Analysis of the template

section presents for extraction

an application of various language

analysis graphic analysis

scheme

forms of bibliotext. The template phrases this This

information section

from natural

extracts

d a t e , j o u r n a l , and author convert

from English information system

input; and

the action routines

into a form usable by a search program. as a query processor in an

can be used system

information biblio-

retrieval graphic for

thereby

allowing

the user This

to include is

information

in his query. and study not

system

chosen obvious the

implementation

only because

of its

application techniques analysis

to information used cover

retrieval

but also because of template that the of

the full

spectrum

schemes. and are

It is therefore

expected

problems this

encountered piLot system

results achieved typical of those application. analysis

in the operation to be expected

in any be

template argued

analysis

Thus while facility

it might is not

that

the present information

practical does

for actual

r e t r i e v a l , the implementation of the performance three of

provide a useful analysis

indication

template deal

in g e n e r a l . with and

The following

sections

respectively author

the extraction

of d a t e , j o u r n a l , and problems and techniques.

phrases

their associated

VI-27

The order of phrases

of p r e s e n t a t i o n are isolated

is the order the input.

in which

the

types

from

A)

Date

phrases system a date phrase is defined of y e a r s . to be any

In this phrase w h i c h date phrases date phrases in Figure 1 4 .

specifies contain contain

a year or group

Single double shown

only one date reference while two. Examples

of date phrases are

Single date phrases IN 1965 NOT IN 1964 BEFORE 1967 SINCE 1960 Double date phrases FROM 1955 TO 1967 NOT BETWEEN 1957 AND 1960 DURING 1950-1955

Examples of date Figure 14

phrases

The

somewhat more complex or specific days

problem

of date phrases here.

involving To handle

months phrases look-up

is not

considered of

a slight m o d i f i c a t i o n procedure is employed.

the template

dictionary used

The general procedure

VI-2K

is a binary into

search

on the first

character

of a w)rd followed

to get by a slightly When of that to with is number This all

the proper search

section of the d i c t i o n a r y , the whole word. with This

linear

for

is altered one.

in the case of words beginning such a word section of

the number

is found, and before the dictionary

the linear

search

is started, a check of exactly a nine.

is made

determine the first assumed 1900.

if the word one being

consists

four numbers

a one and

If so, the word the date concept continues.

to be a date and If n o t , normal provides

is assigned

dictionary

procedure

actually

a quick and

compact way of storing with the

dates from nunber

1900 to 1999

in the dictionary

concept

1900 for

e\ery one. templates for date phrases are the shown position symbol

The alphabetic in A p p e n d i x A. of the date

Tie word 1900.

" D A T E " in quotes denotes The "ppM

concept

is a nonterminal analysis

deroting

a single

date p h r a s e . bottom-up

Template

is much

like c o n t e x t - f r e e phrase being

analysis with each

isolated the

replaced

by a n o n t e r m i n a l . enters

In this case into the

nonterminal for two,

for single date phrase

analysis the the last date

the double date p h r a s e . the 1900 concept templates

In a L1 templates

except of

is the key.

Thus a search

phrase

is performed

only when a word a good indication template

of the of the

form presence

19 ij a p p e a r s ; t h i F provides of a date p h r a s e .

When a date phrase

is m a t c h e d ,

VI-29

no further

tests need

to be made

to v a l i d a t e

the

decision. to has

It of course remains necessary determine no bearing phrase. match exactly what on whether year or not

to look at the

input

is specified; the matched

this however phrase at

is a date template or CI easiest the

The date phrase

decision

is certain

t i m e , and

thus is an example For

of a certainty

template m a t c h . to r e c o g n i z e least

this reason date phrases are three phrase

among for

the

types, and provide the date phrase an

potential first

error.

Performing

analysis input phrase

p r o v i d e s a way units which

to accurately facilitates

break up easier

into

smaller

subsequent

isolation. Once the date phrase of storing has been r e c o g n i z e d , the indicated there is in a single date

still useful

the problem way. For

information in either

the most

part dates appear It thus Each

or doubJe

date

phrases. in p a i r s . and

seems natural of

to store

specifications

element

the pair part

can conthe

tain an operator specified operators Figure 15.

a date.

The operator each d a t e .

indicates

requirement

concerning

Internally shown in

the

are represented

numerically

and are

VI-30

Operator

Numer ical Equivalent 3 -3

< >

2 -2 1 -1

>
<

O p e r a t o r s and their numerical equivalents F igure 15

Single while date gives pair

date phrases double date

use only

the

first

element

of

the p a i r , of 16 date

phrases

use both.

More

than one pair Figure

elements may some

be filled of

by a single and

input.

examples

input phrases

the resultant

element s.
m

he

date ra.'r form specif ' ed above by i search program. There out

is one

that

can one the for

easily further

be used process

is, however,

th it must be carried

to coordinate not be applied

dat (i s p e c i f i c a t i o n s . those for inputs which that these use

This process need

fill no more

than one date p a i r .

But may Lie act

those and

two or m o r e , three possible

relations of

occur date in

necessitate

appropriate m o d i f i c a t i o n s

specifications.

F i r s t , two that

single date phrases may date

i bounding

capacity,

is they act as a double

VI-31

Inpu t General form IN 1965 BEFORE 1965 BETWEEN 1964-1967 op 3 2 -2 -1 NOT DURING 1950-1951 2 1 DURING 1950-1955 OR DURING 1960-1965

Result date 1965 1965 1964 1967 1950 1951

. -2 . -1 -2 -1

1950 1
1955 j 1960 | 1965 |

Sample date

representations

Figure 16

phrase. into

In this case

the single date phrases double specification. a date

are combined

the a p p r o p r i a t e

Second, one lying comdate

double pletely phrase, only may

date phrase may specify inside an interval Here the enclosed remains.

interval by another

specified date Third,

double

interval

is discarded and date phrases

the larger specify

two double

overlapping intervals

date

intervals.

In this case the interval date

overlapping which

are combined

into a single

is the union

of its c o n s t i t u e n t s .

The final

VI-32

specification main after Figure phrase

is tlie union of those

specifications have been

which r e performed

the a p p r o p r i a t e

coordinations

17 summarizes analysis

this coordination some

phrase

of the date

and provides

examples.

Type

Example

Act ion

Result

Bounding single date phrases

AFTER

1965

Combine

into

1 2

1956 1968 !

BEFORE 1968

one double

IN 1965-1967 Inclus ive IN 1960-1968

Use larger one only

|-2 |-1

1960 1968

IN 1965-1969 Overlapping IN 1963-1967

Take the union

1-2 |-1

1963 1969

Summary of date phrase Figure 17

coordination

B)

Journal

phrases of journal phrases is a more that

The d e t e r m i n a t i o n difficult several user task than

that of date be m a d e .

p h r a s e s , and requires

assumptions

F i r s t , it is assumed relates

that any rathe

request

for a p u b l i c a t i o n edition

to a periodical

than to a single This knows seems

such as a book or specific assumption

paper.

to be a realistic

since a user who of the

the specific

publication

he wants has no need

VI-33

retrieval only with

system

at a l l .

This

section names.

is therefore

concerned

extraction

of journal

The d e t e r m i n a t i o n two p a r t s . The first The

of journal phrases

consists phrase

of

is a search templates

for a journal

template m a t c h . and are for

are shown form:

in Appendix A

the most part of the

PUBLISHED FOUND IN

IN

NOT PUBLISHED etc,

IN

Clearly

a match

of one of these The actual

templates decision

is no

guarantee

of a j o u r n a l j o u r n a l name part table of

phrase. table

is made using a the second name collecFor included.

look-up which

constitutes

the j o u r n a l

phrase a n a l y s i s .

The journal

contains

the names of all a unique

the journals number

in the

tion and

assigns

reference

to each.

each journal For

all anticipated of

forms of

its name are for

e x a m p l e , the "Journal is listed JACM ACM as

the A s s o c i a t i o n

Computing

Machinery"

JOURNAL of the ACM

JOURNAL

in a d d i t i o n journal

to the full n a m e . names which

The list also

contains

some

famiJy

can specify

a group

of j o u r n a l s .

VI-34

In this way an input which

specifies

IN AN ACM

PUBLICATION

is taken Clearly

to m e a n both

the ACM

" J o u r n a l " and

"Communications". journal

in an o p e r a t i o n a l

system

there will be some

r e f e r e n c e s w h i c h have not been a n t i c i p a t e d . added would to the j o u r n a l quickly list p e r i o d i c a l l y After

These can be the list

and hopefully template are looked is

stabilize.

a journal

matched

the w o r d s following table.

the template is found,

up

in number

the journal of

If a match

the reference

the specified

journal

is placed

in a journal

specification not

list along with an operator equals). This list may of

(3 for equals and

-3 for

then be used by a search table

program. is

If the search assumed not

the journal

f a i l s , the phrase While

to be a journal r e f e r e n c e . miss a proper of journal keyed

this method does which some journal

will o c c a s i o n a l l y prevent searches

r e f e r e n c e , it on journals eliminating

the collection

do not appear wasted

in the c o l l e c t i o n , Figure

thereby

searches. their

18 includes entries

some examples of in the journal names rather

phrases and tion table.

resultant

specificathan

For clarity are

the journal

reference

numbers

shown

in the specification is a good

table.

The j o u r n a l phrase analysis C2-C1 p r o c e s s

example of a match

(conjecture-certainty).

The template

VI-35

Input

Resulting journal specification

IN

JACM 3 3 3 3

JACM JACM CACM JACM CACM JACM

IN JACM AND CACM IN AN ACM PUBLICATION NOT IN JACM

J o u r n a l phrases and Figure 18

specifications

provides and name

an indication

that a journal phrase may be p r e s e n t ; against the journal

then a check of the environment table d e t e r m i n e s the final

decision.

C) At looks

Author first

phrases of determining phrases. and author Template phrases matches table

the problem

similar

to that of journal author phrases

indicate look-up analysis feasible. subject small. journals

possible

then an author H o w e v e r , upon list

can finalize

the d e c i s i o n . that

further

it is determined In a typical

the author

is not specific fairly present infrequent. time.

collection

dealing with a included is of

a r e a , the number Furthermore and both

of journals

the d i s c o n t i n u a t i o n of new ones

the creation list

is quite

Thus a j o u r n a l

is compact

and varies

little with

VI-35

Author authors which

l i s t s , h o w e v e r , have different produce more than ten papers documents

properties. per y e a r . each year A

Few collection have

grows by

ten thousand

can thus

thousands and

of a u t h o r s . a given

Also people

are continually list would

entering too

leaving

field.

An author

thus be in an schemes

large and would information exist.

require

too much

file m a i n t e n a n c e alternate

retrieval

system.

Several

One such method in extracting centers

developed personal

by Borkowsky names

[5] is text.

successful The method and etc. study. of the

from newspaper

on the r e c o g n i t i o n titles

of capitalized

words

on finding

personal

such as M r . , M i s s ,

President, particular

This m e t h o d , h o w e v e r , is not applicable User input case). a user input is entered used in a single and

to this

type case

because only

devices Thus

(keypunches

teletypes have is

upper Also

recognition

of capitalization his author

impossible.

is unlikely title

to preface because

specification input

by a personal work and method

simply

it represents more of the input.

adds nothing

to the meaning for.

Another

is therefore The method

called

developed

for author dictionary.

phrase This

determination is the large and in

m a k e s use of dictionary is not

the collection in a query with

used

and

document text

analysis used

to be confused analysis.

the small dictionary requires a slight

template

The method

modification

VI-37

in the d i c t i o n a r y of the author following

structure.

The m o t i v a t i o n

and

development in the

phrase

extraction method

is presented

paragraphs. types of personal includes names are d e f i n e d . The

Two first type

those which are used

only as n a m e s . etc.

Some examples

are J o n e s , D a t t o l a , B o r k o w s k i , F r e d r i c k , not found in the collection are

T h e s e w o r d s are generally dictionary, classified author author and thus

if they occur

in the query,

as u n k n o w n s .

If all names were of this be relatively of a string

type, An words

phrase d e t e r m i n a t i o n would name would simply consist

easy.

of unknown a

following

an author

template m a t c h .

Unfortunately those names

second that can

type of p e r s o n a l be used

name e x i s t s , including other than that

in c a p a c i t i e s

of a n a m e .

These words

include R o s e , B r o w n , Fox, L i t t l e , S m i t h , etc. may be found be classified shows in the dictionary as u n k n o w n . and thus would of the ADI

These not

necessarily

Analysis

dictionary included

that very

few words of this

type are actually

in the d i c t i o n a r y . that words around the p e r f o r m a n c e only would tagging

There are e n o u g h , h o w e v e r , to of a name extractor which The

indicate unknown

uses

not be a c c e p t a b l e .

solution

centers When looked

certain w o r d s into

in the d i c t i o n a r y .

documents up

are entered

the system to compose

each word must be the document

in a dictionary

in order

vector.

VI-3'3

There must at this

also be a facility to ensure that

to perform

a dictionary is adequate

update to fits

time

the dictionary

handle within

the new m a t e r i a l . this framework and

The dictionary thus imposes

tagging

process

no new

dictionary up in up.

processing.

The names of document in which is found During

authors

are looked

the same process If an author update ary name

the document

words are

looked

in the d i c t i o n a r y , a dictionary this update author the specified name. This dictioncan be for

is required. is tagged

entry

as a possible

done by considering the word entry. or or by

the tag as an extra part tag bit contain

of speech in the

the use of a special does not

dictionary name

If the dictionary is ilready

the author

if the name

tagged, no update nhrase

is r a quired. uses both

The algorithm unknown and is found, tagged

for author

extraction

words.

When a match

of an author following

template the template words by

the string A string

of words of

immediately

is tested. is taken the first

initials name.

and unknown and The string

tagged

to be the author known and

is terminated

untagged

word.

If the terminating test of the for

word

is a c o n j u n c t i o n following multiple great shown

or a c o m m a , a second is made

string

the conjunction authors or

to test

possible The

inverted

ordering

(i.e., B r o w n , T . ) .

variety

of possible ways used 19, presents

in specifying

a n a m e , as in author

in Figure

a considerable

problem

VI-39

det erminat ion.

J ohn Alan J ones J ohn A . J o n e s J .A. J o n e s J ohn Jones J . Jone s J . Alan Jones

J ones , John J ones , J .A.

Examp le o f

name v a r i a t i o n s

F igur e 19

The one author

invariant extractor

is the s u r n a m e . tries to isolate

For

this reason

the It uses

the last n a m e . for the

the given names and name. Figure

initials some

for m o d i f i e r s sample analyses

last by

20 shows

performed

the author

extractor.

Input Surname John Jones Jones Jones Jones Jones Smith Jones Jones Smith Brown

O u t put

Mod if iers John J J A J S J S F

J . Jones J.A, Jones and

J . Jones S. Smith Jones, Jones, and F. J.

S. Smi th Brown

Sampl e au th o r analys es Fi gur e 20

VI-' 0

The

templates the Last

for author

phrases appear name

in Appendix A to of

In ill except follow the the

two, the author The last

is assumed

tempa.ltc

two deal with

posse ssives

form:

SMITH1S JONES!

The

template

keyword

is the a p o s t r o p h e , and here As with the journal

the

author

name p r e c e e d s match

the t e m p l a t e . template

phrases, a of a possitle envir-

of an author

is only an indication

p h r a s e , not a g u a r a n t e e . onmental decision testing

But unlike

the j o u r n a l s , the the

for an author This but

phrase does not mike can reject guarantee or

a certainty. conjecture

testing cannot

support Thus the

the original author phrase

it.

extraction

is an example

of a C2-C2

(conjecture-

conjecture)

process. is chosen because a useful large and require that by the author conadding

The above method name list would become

excessively

tinuous tags

file m a i n t e n a n c e .

It may be argued and

to the dictionary new author

structure

updating

dictionary is gained This,

whenever over

names are

entered, no advantage author tags list method. themselves This It may

the more

straightforward the case. The

however, maximum

is not

occupy a is quite even be small possible

of one bit

per dictionary the dictionary

entry. size.

in c o m p a r i s o n with

VI-41

to i n c o r p o r a t e no increase dictionary an a n a l y s i s

the tags into

existing

dictionary

fields in

with the

in s i z e . is not of

Furthermore

the number

of words

increased

by the tagging shows

process.

Also, very

the ADI dictionary function need

that

there are names.

few w o r d s which since name

as possible author be altered updates

Thus author The

the dictionary

only when a new

is found, dictionary method

are very

infrequent. for exand

proposed

thus provides names

a useful p r o c e d u r e language

traction of author requires a minimum

from natural storage

text file

of extra

space and

processing.

D) The

Experiments system

and

results the following operations; a is

performs

query which may entered. author subject process,

contain b i b l i o g r a p h i c is analyzed and

information

The query

the d a t e , j o u r n a l , and leaving in only this taken be the

phrases are identified part. Three

and

removed,

types of errors

can occur

F i r s t , a phrase of one

type may be improperly

to be of another missed; words one. of and

type; second, a b i b l i o g r a p h i c o c c u r , that

phrase may

third, a false drop may a bibliographic experiments

i s , a set of as test of

not denoting The following

phrase may be taken as an initial

are used for

the system. from

F i r s t , to check collection

false d r o p s , a set These 35 thus

queries queries

the ADI

is entered.

contain no b i b l i o g r a p h i c

i n f o r m a t i o n , and

any

VI-42

such phrases queries

found

by the system found

are clearly

in error.

The

contain many words tagged

1n the template

dictionary and

as well as w o r d s Will). However

as possible names of author

(such as Field and journal

T h e s e result

in m a t c h e s

templates.

they were all rejected indicate

by the environmental

tests. are

The final results found, and is

that no bibliographic

phrases

in every

case the query which

remains after that the

analysLs system

identical

to the o r i g i n a l , thus to false d r o p s . second experiment

indicating

is not prone The

involves

the use of the

same

ADI queries but modified These queries were

to include bibliographic by the author

information. several The to

constructed of

and by

others who knew nothing i n f o r m a n t s were merely rewrite them

the structure

of the system. told

given

some ADI queries and

incorporating

bibliographic typing

i n f o r m a t i o n , and console.

to phrase

them as

if they were

at a teletype

31 such queries were used, graphic located phrases

including

a total of 63 b i b l i o extractor correctly The

in this set.

The phrase

60 of these p h r a s e s , and made no false d r o p s . are all journal p h r a s e s . is unable to read The the

three p h r a s e s m i s s e s are caused because and

errors journal

the system thus cannot

list b a c k w a r d s which occur

cope with journal

templates

to the right of a journal n a m e .

Thus a journal

VI-H3

phrase

such

as

DATAMATION

ARTICLES

is m i s s e d .

This problem

is corrected name

by slight

modification be

in the structure implemented

of the journal

l i s t , and will system. ADI

in a future

edition of the using

A second makes use of what

experiment remains

the modified

queries phrases By comparing

after

the b i b l i o g r a p h i c SMART the run.

are removed

from a query

for a normal

these results with queries, quality several

those achieved

using

unmodified retrieval For

it can be determined is hurt reasons of by the added

how m u c h , if any, the information

and p r o c e s s i n g . First, the

this experiment the system

was a b a n d o n e d . that

performance

is such

the processed And

modified second, either in the vectors

queries are almost nearly high all

identical

to the u n m o d i f i e d .

the words

in the bibliographic are

phrases are ignored

frequency

or u n k n o w n , and

therefore Thus

construction resulting to are need based

of concept

vectors.

the concept

from

the processed queries.

modified Obviously

queries are

identical results test

the unmodified the same

the retrieval

in both

c a s e s , so that

an actu.il retrieval the results indicate are

not be p e r f o r m e d . on a fairly

Thus although set, they

small data

that

it is

possible

to extract

bibliographic

information

from

natural

VI-44

language loss

queries via

template analysis with of the query.

little or no

in r e t r i e v a l

power

E)

Conelus ion that extraction language queries of bibliographic

It may be argued information facility working from natural

is not a useful system. Many

in an actual systems

i n f o r m a t i o n retrieval

such as RECON

[12] successfully

use a more of

structured the query an by to input

input method

which requires individually. 22. From

the v a r i o u s parts An example of

to be specified is shown

such

in Figure

the results

obtained object

the RECON

study, only a small p e r c e n t a g e input.

of users

the structured

AUTHOR: JONES AUTHOR: SMITH JOURNAL: JACM SUBJECT: INFORMATION RETRIEVAL DATE: AFTER 1965 S truetured input format Figure 22

This

is probably

due to the fact in his head

that a user

generally

struc-

tures his query structured study

in much

the same way as it is this

in the input

format.

Be that as it m a y , information

indicates

that b i b l i o g r a p h i c language

can be of

extracted

from natural

text with a high degree

VI-45

accuracy.

Of more

importance

is the fact

that

this

study schemes

is a s u c c e s s f u l and it indicates

test of the general that

template has

analysis definite

template analysis language analysis.

potential

in natural

M6 -

Bibliography M. R u b i n o f f , S. B e r g m a n , W. F r a n k s , E. R u b i n o f f , " E x p e r i m e n t a l E v a l u a t i o n of Information R e t r i e v a l through a T e l e t y p e w r i t e r " , CACM, V o l . 1 1 , N o . 9, Sept. 1 9 6 8 . M. R u b i n o f f , S. B e r g m a n , H. C a u t i n , F. R a p p , "Easy E n g l i s h , A Language for Information Retrieval through a Remote T e l e t y p e w r i t e r C o n s o l e " , CACM, Vol. 11, No. 10, Oct. 1968. J. W e i z e n b a u m , "ELIZA - A Computer Program for the Study of Natural L a n g u a g e C o m m u n i c a t i o n s between Man and M a c h i n e " , CACM, V o l . 9, N o . 1, J a n . 1 9 6 6 . J. W e i z e n b a u m , "Contextual U n d e r s t a n d i n g by p u t e r s " , CACM, V o l . 1 0 , N o . 8, A u g . 1 9 6 7 . Com-

C. B o r k o w s k i , "An E x p e r i m e n t a l System for A u t o matic I d e n t i f i c a t i o n of Personal Titles in Newspaper Text", American Documentation, Vol. 18, N o . 3, July 1 9 6 7 . B. L a m p s o n , B. D i m s d a l e , "A Natural Language I n f o r m a t i o n R e t r i e v a l System", P r o c e e d i n g s of the I E E E , V o l . 5 4 , N o . 1 2 , D e c . 1 9 6 6 . IBM S y s t e m s / 3 6 0 D o c u m e n t Processing System; A p p l i c a t i o n s Descriptions. IBM Document H 2 0 - 0 3 1 5 - 0 , 1 9 6 7 . M. H a l p e r n , "Foundations of the Case for Natural P r o g r a m m i n g " , IEEE Spectrum, V o l . 4, N o . 3 , March Language 1967.

W. D. M a t h e w s , "TIP R e f e r e n c e M a n u a l " , T I P - T M - 1 0 4 , T e c h n i c a l I n f o r m a t i o n P r o g r a m , The L i b r a r i e s , M a s s a c h u s e t t s I n s t i t u t e of T e c h n o l o g y , Cambridge M a s s . , 1 9 6 8 . E. P a r k e r , "SPIRES User's M a n u a l " , Stanford Physics I n f o r m a t i o n R e t r i e v a l S y s t e m , Institute of C o m m u n i c a t i o n R e s e a r c h , Stanford U n i v e r s i t y , Palo A l t o , C a l i f o r n i a . R. W i l l i a m s o n , "A P r o t o t y p e Document unpublished. Retrieval System",

D. M e i s t e r , D. J. S u l l i v a n , "Evaluation of User R e a c t i o n to a P r o t o t y p e On Line Information Retrieval System" (Appendix: "Recon User's M a n u a l " ) , Report N A S A - C R - 9 1 8 . Prepared by B u n k e r - R a m o Corp. Canagn P a r k , C a l i f o r n i a . E. M e n d e l s o n , Introduction to M a t h e m a t i c a l Nostrand C , New Y o r k , 1 9 6 4 . L o g i c , D. Van

VI-H7

Templates Appendix A

The

templates part

shown below

are in alphabet .c form words are of the the in

with

the parameter keywords.

omitted.

The underlined

The word 1900.

" D A T E " indicates The order are

the position

date concept which

shown here

is the order

the templates

scanned

in the analysis

process.

I.

Housekeeping

templates THAN THAN

OTHER LATER

II.

Date phrase A.

templates phrases "DATE" "DATE"

D o u b l e date DP
1

UNTIL

DP AND DP

-THE -YEAR

"DATE"

B.

Negative NOT DDP 1

double date DPP2

phrases

EXCLUDED

C.

Negative NOT DP 1

single date DP^

phrases

EXCLUDED

1. 2.

DP DDP

is a n o n t e r m i n a l date p h r a s e . is a n o n t e r m i n a l dat e p h r a s e .

which which

replaces replaces

an analyzed an analyzed

single double

VI-43

Appendix A (Cont'd) Single date phrases -WRITTEN IN -THE -YEAR "DATE" -WRITTEN BEFORE -THE -YEAR "DATE" -WRITTEN AFTER -THE -YEAR "DATE" -WRITTEN BETWEEN -THE -YEAR "DATE"

Current year phrases -WRITTEN IN 1 PRESENT YEAR -WRITTEN BEFORE 1 PRESENT YEAR

III.

Journal phrase templates A. Multiple journals JP 3 AND

Journal phrases EXCEPT THOSE -PUBLISHED I N _ -PUBLISHED NOT ^N NOT -PUBLISHED I N _ WHICH ARE -NOT I N _ -PUBLISHED LN EXCEPT THOSE -PUBLISHED . Y B -PUBLISHED NOT . Y B NOT -PUBLISHED B Y _ WHICH ARE -NOT JBY -PUBLISHED _BY DP DDP

3.

JP is a nonterminal which replaces an analyzed journal phrase.

VI-49

Appendix

A

(Cont'd)

IV.

Author phrase templates A. Author name follows template -ARTICLES NOT -PUBLISHED BY_ -MR. -ARTICLES -PUBLISHED NOT BY; -MR. ARTICLES -PUBLISHED BT -PUBLISHED BY_ MR. B. Author name occurs inside template WHAT HAS 10 WRITTEN WHAT HAS 10 DP WHAT HAS 10 DDP WHAT HAS 10 JP WHAT HAS C. Author name precedes NOT 10 J S ^
f

MR.

template

S -NOT

VI-E'O

Template dictionary used for implementation in Section 3

Appendix B

Concept No

Word ABOUT AROUND DURING FROM IN OF WITH |

Concep t No 15(cont T d)

Word PRESENT PRESENTED PRINTED PUBLICATION PUBLISHED SEEN WRITTEN WROTE

11

12

BY BEFORE PRIOR AFTER FOLLOWING LATER BETWEEN SINCE APPEAR APPEARED APPEARING AUTHORED DEVELOPED FOUND 1 9 AND BUT OR , (comma) TO TILL UNTIL - (dash) 1 7 EXCLUDED EXCEPTED 16 EXCLUDING EXCEPT NOT NOTHING

13

14

15

VI-51

Appendix

B(Cont

T

d)

Concept No.

Word CURRENT PRESENT THIS

Concept No . 27(Cont f d)

Word

20

REPORTS THESES THESIS

21

YEAR YEARS

28

HAD HAS HAVE

25

WHAT WHICH

DID DO DOES

26

ARE BE BEEN IS WERE 51
Any ini t i

50

A AN THE

27

ARTICLE ARTICLES BOOK BOOKS DATA INFORMATION PAPER PAPERS PRESENTATION PUBLICATION PUBLICATIONS 53
52

A . . . Z or A. ... Z.

Personal titles; MR. MRS . PROF etc,

OTHER

VI-1. 2

Appendix

B (Cont ' d)

Concept

No

Word

54

THAN

55

1

(apostrophe)

1900

Any word of the form 19ij where i and j are digits

Nonterminal Concep t N o .

Phrase T ype

100

Single date

phrase

101

Double

date

phrase

110

Journal phra se

120

Author

phrase