ISR-7
June 19 6 U

IX-1

IX.

STATISTICAL PHRASE PROCESSING
Michael Lesk and Tom E v s l i n1.

Introduction
A number of procedures have been included in the SMART system forthe manipulation of selected sets of concept numbers. More specifically,
it is desired to obtain frequency counts of the co-occurrences of theseconcept numbers within the sentences of a document.

These concept sets

are termed statistical phrases, by analogy with the structural (criterion)
phrases in which the concepts are syntactically related.
The statistical phrases themselves are not initially derived from.
the texts, but rather are stored as file four of the library tape. Eachstatistical phrase is regarded as a semantic entity, and is provided witha concept number and a BCD name or "index."

The present section deals

with the routine used to construct and update this file, and with theroutines that count the occurrences of the corresponding phrases within
the document collection.

2*

Updating of the Statistical Phrase FileCRITS2 writes the fourth file of the library tape, consisting of adictionary of semantic data about phrases. This file provides part of theinformation needed by the criterion tree routine. It is also used by thestatistical phrase searcher, PHROCC, to find phrases in texts. For eachphrase, this file includes:

IX-2(1) a six-character BCD "identifier1' or "index";(2)

the concept number of the whole phrase, called the"output concept number";(3) up to six "component concept numbers," the co-occurrenceof which in a sentence is counted as a phrase by thestatistical phrase searcher,This information is placed in a four machine-word item.

The first word isthe identifier; the second contains the output concept number in thedecrement, tiach of the last two words holds three twelve-bit component
concept numbers; zeros are used for fill. For example, "parity" is represented by concept number 207, and "check" by 271; the phrase "parity check,"
however, corresponds to concept 300*

The entry for this phrase is shown

below:
WORD 123

1PARCHK

300,207, 271,0

Identifier

OutputConcept
NumberComponent
Concept
Numbers

40,0,0(The numbers, of course, are converted to binary internally.)
To improve efficiency, the items are blocked 100 to a physical record
on tape, the last record being possibly short. A three-word label is prefixed to each record, thus resulting in a length of 403 words for all but
the last record in the file. The last record is 4k + 3 words long, where1< k < 100. The file is stored in ascending order by phrase identifier(index).

IX-3
Subroutine CRITS2 operates by a straightforward merge pass of theold library file on A6 with a set of correction cards on A2. The firstcard on A2 is an update control card, containing one of four code words incolumns 1-6.

The options are:MERGE

Merge correction cards on A2 with the fileon A6.

COPY

Copy old file from A6 to B5; no correction
cards follow.

REP LAC

Replace (the "E" may be punched in column 7
if desired) the old file on A6 with the filethat follows on A2, spacing over the oldfile on A6.

IGNORE

Ignoring tape A6 completely, write a new fileon B5 from the cards following on A2. This
option is used for new starts only, since ina tape update run tape A6 would be leftmispositioned.

The control card may contain either PRINT or PUNCH in columns 7-11,
producing a copy of the new file on either the print or punch tapes,respectively. Random characters should not be punched in column 9 ofthis card, because this may be interpreted as one of the permissiblespecifications.
If any option other than COPY is specified, the control card mustbe followed by a set of correction cards for the file. These are in theform of entries to the file, and are punched in the following format:(1)

six blanks in columns 1-6;(2) the phrase identifier, six BCD characters, incolumns 7-12;

IX-li(3)

the output concept number in columns 17-20, rightjustified;(li) up to six component concept numbers in columns 21-$0,
consisting of five columns each; within each fivecolumn entry, the number must be right-justified.

The control cards should be in ascending order on the phrase name.
special ending sentinel is needed.

NoThe phrase identifier must not consistof six left parentheses, and in the interests of readability should not be
six blanks.
In the MERGE option, if an identifier on A2 does not match anidentifier on A6 it will be inserted in the proper place,

If it does matchan A6 entry it will replace the old item, unless the A2 card has an output
concept number of 9999.

In this case, the phrase is deleted from the file*

CRITS2 makes use of a set of FAP subroutines to perform taperead/writes.

The subroutines call the FMS input-output package, the firstrecord of the system tape.

The entry points to these subroutines are:

BACKA2Backspaces tape A2 one record.

IOP

Loads system input-output package (IOP) from Al.

READA6

Delivers one item from A6 to input area A6BIN,
unblocking as needed. When the current record
is completely processed, the next block is readfrom A6. If all phrases in the old file havebeen read, a phrase name of six left parentheses
is returned, indicating end of file.

WRITB5

Moves one item from output area B^BIN to outputbuffer« When 100 items have accumulated, a record
is written on B$.

ix-$

CRITS 2
Read Control
CardMerge

Examine Columns
1 - 6

copy

Replace

IgnoreSpace A6Forward OneFile*1

Set A6 BIN =Examine Columns
7-12Blanks J Print or Punch
Set Switch
At (A)

nz:

Compare A2BCD PhraseN A6>A2Name WithA6BIN Phrase NameTransfer A2 ItemTo B5 Buffer
Does A2 Output
Concept Number= 9999?
Yes

Read a Phrase
From A2 If No
More on A2,
Set A2 = ((((((Transfer A6 toB5 Buffer
Read a Phrase
From A64>

Print/Punch

Nd

Read a Phrase
From A6

Read a Phrase
From A2

Statistical Phrase Update Procedures
flowchart 1

Copy B5
Buffer toA3 or B4IX -6COMPAR

Compares identifiers in input areas A6BINand A2BCD• Control is returned to the first,
second, or third location after the calling
instruction if the A2 identifier is respectively less than, equal to, or greaterthan the A6 identifier*

GREATR

Compares its first and second arguments andsets accumulator to zero if the first isgreater than the second; nonzero otherwise.

TCOB or YfEFB (equivalent) writes out any material
waiting in B5 buffer and writes end of fileen B55PACE6Forwards tape A6 one file.

Note that on the 7094 six left parentheses, corresponding to theoctal number 747474747474a * constitute the highest-sorting combination ofsix BCD characters.
A flowchart of the CRIT82 routine appears as Flowchart 1.

3•

Statistical Phrase Counting
PHROCC is a FORTRAN subroutine to count the occurrences of statisti-

cal phrases in a given document. EVSINP is a short FAP subroutine calledby PHROCC to provide binary input.
The phrases appear as records of 403 words each on B5, terminatedby an end of file. The first three words of each record are not processed.
The remainder of the record is made up of 100 or less four-word items asshown in Part 2 of this section.
EVSINP reads one record at a time into an array whose FORTRAN
address is given by the second parameter in the calling sequence. If lessIX-7

than 100 four-v/ord phrases were found in the record, EVSINP repositions thephrases in core so that they will be in the proper place for the indicated
FORTRAN array.

The number of words in the record, excluding the three junkwords at the beginning, is returned to the location indicated by the firstparameter in the calling sequence.

This parameter is made negative toindicate that an E#F was found while reading the current record, and thatno further phrases are present on tape.
PHROGC takes each phrase in its buffer and compares its component
concepts to the concept numbers associated with the words of the document
stored in YfflLST. Each word in the document consists of three computer words
as follows:

Associated Concepts'lord hi umber

Sentence Number

Each concept number of the phrase is compared to the concept numbersof each sentence word, and matches are counted.

Whether or not a match isfound, all concepts of the phrase are compared to the concept numbers of
the next sentence word iteratively until the sentence is exhausted.

Thefrequency of occurrence of a given phrase in a given sentence is defined as
the number of matches made by the least matched concept of the phrase.

This

process is repeated sentence by sentence until the entire text has beenscanned•The occurrence counts of each phrase in each sentence are added
together to give the total frequency for the particular phrase in the current8PHR0CCzxz

Coll EVSINP

to Read in Phrases From B5X•Use IEXTRC to Set up Array JAR Containing
L.First t-*-6 Concepts in Phrase Terminated by Zero |Xk •*- 1I{Does JAR(l,k) = Any of The Concepts|No~~\ Yes
JAR(2,k)*—JAR(2,k) + 1

k-*-k+1
No/

In Word?\~Is JAR Empty?")-

ZZXTZ

Yes

Is Next Word In Same Sente nce'A

Yes

~\ No
Calculate frequency of Phrase In
This Sentence And Add It to TheFrequency Count For This Phrase
In I C R I T S/End ofLDocumen[YesHas Phrase Occurred
In Document ?

3CLur Frequency
TNO
Counters In JAR

NoYes. .
(Are.
,Y^^There More Phrases In Core?)- 1 ^—i Are|No
There More Phrases on Tape?)| No[~RETURN~]I EVSINP~]
Get Address For Endof ArrayI

Read B5 Until 4 0 3
Words or End ot Filei

4 0 0 Wds

Return The Number
4 0 0 1, 4

E0C Move Items to F0RTRAN
Top of Array
Return Number of Words
Actually Read Less 3 1,4[_RETURN JS t a t i s t i c a l Phrase Countingl/lowchart 21'[jRETURN jDIX-9CRITSI/is Sense Light One on?VNo

Call HEADR, LINE2
Write First Line A3ISet up Output Line For Phrase.
Change Internal to External Concept
Numbers With R0NAME.

iCall LINE 1Write Line on A3
Yes / A r e There More Phrases
In ICRITS?
jNo~(Is Sense Light Two on?>BK
Off All Sense Lights

NoI
Erase MAKPLS, CLNUMS
Reestablish Arrays With KC0UNTa

Fill Arrays From ICRITS Data
RETURN

Output of Statistical Phrase Count
Flowchart 3

Update Arrays WithICRITS Data•IX-10
document. If a given phrase occurs at all, it will be entered into theFORTRAN array ICR1TS along with its frequency count*
After all the phrases on the tape are processed, PHROCC returns
control to CHIEF. A flowchart appears as Flowchart 2.

4.

Output of Phrase Counts
CRITS is a FORTRAN subroutine which prints the list of phrases

detected and adds the frequency counts to the document's concept-vector.
Printing is controlled by sense light 1. If it is on, the phrases
stored in array 1CRIB are listed in the following format:

BCD identifier,output concept identifier, component concept identifier.
Addition of phrase data to the concept-vector of the document canbe done in two ways if statistical clustering was used.

The new phrase

data may add to or supersede the old statistical data. If sense light 2is on, the new data replaces the old. The statistical clusters are"forgotten" and the concepts recounted by subroutine KCOUNT. If senselight 2 is off, the new phrases are added to the existing counts in KLSOCC,
the array of concept occurrences, without first erasing the clustering data.
The output procedure is shown in Flowchart 3*