tfll- 1

ISR-C,
August, 1965

tfll.

STATISTICAL PHRASE PROCESSING
G. Shapiro

1.

Introduction
The SMART system has capabilities for processing so-called"statistical phrases."

These consist of sets of concept numbers, such thatthe components of each phrase are filed under a single concept number (theconcept number of the phrase).

A statistical phrase is said to occur in a

sentence if all of its components occur at least once.
phrases described by Lemmon

Unlike the syntactic

in a later section of this report, the occurrenceof a statistical phrase in a sentence implies no syntactic relation amongits components.

It should be noted that, though concept clusters are pro-duced by a special algorithm while statistical phrases are determined by alookup process in a man-made dictionary, the procedure for using cluster or
statistical phrase occurrences in a sentence is identical.

For this reason,subroutine PHROCC (described in Part 3 of this section) handles both of these
expansion options.

Part 2 of this section describes the programs used inwriting and maintaining the statistical phrase file on the library tape.

If either the statistical phrase or cluster options are used, the concept
numbers of the phrases found are added to the concept vectors of the documents, and are taken into account (with the weight prescribed) in all
subsequent manipulations of these vectors.

XII-2
2.

Maintenance of the Statistical Phrase File
During an update run, subroutine MAKE writes the statistical phrase

file of the library tape. Up to six components are permitted for a phrase(in practice most phrases have only two). The input card format for MAKE
is as follows:
Column 1

5 6 7P No.

X11 12 13
COMP 1/23 ZU 25 •••17 18 19
GOMP 2X

COMP 3A•••

where P No. is the concept number of the phrase and COMP I, I = 1,...,6 arethe component concept numbers (all in integer format). A

represents anempty field. The list of component concept numbers is assumed to terminate
when the first zero entry is encountered; if no zero entry is found, six
components are assumed. No phrase may have fewer than tv/o components. Theintegers may be justified anywhere in the appropriate field.

If any alpha-betic characters appear or if there are fewer than two components, the cardis ignored during processing and a message and description of the offending
cards are written on the output tape. The input deck must be terminated bya card with the characters NOMOR in columns 1 through 5*
MAKE operates in three different modes, the mode depending on thefirst card of the input deck.

If the first card contains (in columns 1through 6) the word REPLAC, the succeeding cards are written onto the librarytape B5, and a file on A6, the old library tape, is skipped in order toposition A6 correctly for the other programs in the update link. If the firstcard is IGNORE, MAKE acts exactly as it would in the REPLAC case but does
not skip the file on A6 (in case the entire update run is from cards and tapeudi- 3A6 has not been mounted) . If the first card is COPY, MAKE copies thestatistical phrase file from A6 onto B5*

In this case, the input deckshould consist only of the COPY card; the NOMOR card must not appear.
On tape, each phrase takes up four words, of which the first contains
the phrase concept number in the decrement and a weight of 1 in the address(the weight is used to make the statistical phrase processing compatible
with the cluster processing done by PHROCC, since the clusters may haveweights other than 1).

The next three words contain the list of component

concept numbers packed two to a word, with all unused components bein,f ,/etto zero. One hundred phrases (4-00 words) are packed in one physical taperecord. The last record of the statistical phrase file (and only the last)
may contain fewer than 100 items.
MAKE reads the first card of the input deck and, depending on theoption specified, transfers to one of two sections of the code. In theREPLAC or IGNORE cases, MAKE continues reading cards from the input tape A2.
This reading is actually done by a routine named JNCARD which reads the cardin alphabetic format, checks to make sure that the card is valid, and thenconverts the information to binary integers using a FAP-coded routine XDTB.
Alternate half buffers of 100-item length are filled and written out using
the trap-controlled input-output routine INOUT (called through interface
routines WAIT, INPUT, and OUTL).

In the COPY case, a simple double bufferedtape copy, again using INOUT, is performed.
Flowchart 1 describes the operation of MAKE. JNCARD(N,L,F) returns
the first word of the input card to N and the next six words into the arrayL.

If F is less than zero on return, the card was invalid; if F = 0, thecard contained NOMOR; if F is positive, the card was valid. The array NOxn-UENTER

1

Read c o n t r o l card
C0PY

IGNOREREP LAC»'Skip f i l e on A61 =Zk

1 ;

V t

C a l l JWCARD(N,L,F)

A•<F : 0MIND = 1 0 1 - 1
N0U,IND,IB) = XPACKF(N.,0,1)
Move L ( J ) , J = 1, . . . , 6 i n t o Nj2f_i

1=1 + 4v-

I = ioi\/c>

Write out half buffer
J3 = 3 - JB

J£Write out rest ofbuffer and return-<-V
Double buffered tape copy of
A6 onto B5. Then return.
Subroutine MAKE
Flowchart 1

#11-5(dimensioned U by 100 by 2) contains both havles of the buffer used foroutput.

IL3 is an index which indicates which half of the output buffer iscurrently being filled*3.

Finding Statistical Phrase and Cluster Occurrences
Subroutine PHROCC is the bookkeeping routine for the statisticalphrase finding package in link 1 of SMART.

The actual algorithm for finding

statistical phrases is coded in subroutine WP1IK0C which is called by PHROCC.
The functions of PHROCC are described first.
PHROCC is called by the main program of the lookup link once for eachcore-load of documents, as described in Sec. V of this report by M. lane.
PHROCC first determines whether statistical phrase or cluster expansion, orboth, are requested, and sets several flags accordingly.

If both arerequested, the statistical phrase expansion is performed before the clusterexpansion.
file.

Otherwise, the library tape is positioned before the appropriate

PHROCC also determines whether the first document in this core-load

is a continuation of the last document of the preceding core-load byinterrogating the flag LASINC which is set nonzero by the link 1 supervisor
if and only if the last document of the preceding batch was incomplete.

In

this case, there may be partial results from the last phrase lookup waiting
on a scratch tape.

If there are, PHROCC reads these in and initializes thearray JP, JQ, and KQ accordingly (these are described below).
PHROCC initializes these arrays.

In any event,XII-6The main purpose of PHROCC, however, is to control the doublebuffered trap-controlled input with which the statistical phrase dictionary
is read in from the library tape. The half-buffer size is 400 words,
corresponding to the physical record length on tape. PHROCC also unpacks
the packed information from the library tape into FORTRAN arrays, thereby
speeding up the time-consuming search loops in WPHROC. WPHROC performs thephrase lookups for one dictionary buffer and one document each time it iscalled, and is therefore called many times from the inside of a loop inPHROCC.

Before calling WPHROC for a given document, PHROCC produces anarray 1ST, in which the Ith entry is an index in the array IWDLST pointingto the beginning of the Ith sentence of the current document.

IWDLST is a

10 by 1000 FORTRAN array containing in each 10-word item all the information
for a particular word in one of the documents of the current core-load(see Sec. V of this report).
After calling WPHROC for each document in the current core-loadfor one given buffer load of the dictionary, PHROCC reads in the next bufferload of the dictionary (and switches buffer halves). When the entire
dictionary has been processed, PHROCC proceeds to unwind and possibly towrite out the results of the WPHROC manipulations.
If the SYNTAX option had been requested and a statistical phrase
lookup was just performed, then WPHROC will have produced a list of sentencesin which statistical phrases were found. PHROCC must write out thesesentences on tape A7, to be used as input for the syntax link since, in thepresent version of SMART, syntactic phrases are sought only in sentencesin which statistical phrases had previously occurred.

This saves much time

tflI-7in that sentences in which there are no statistical phrases, arid which
therefore could not possibly contain syntactic phrases are not processed
bj the tii: e-consuming syntactic analyzer.

The whole entry in IWDLST(rearranged slightly) is written out for each such sentence.

LEMl(lD)

contains the number of sentences in the IDth document which are to be
written out.

LftM2(lD,J), J = 1,.•.,LEM1(ID) contains, packed in one word,beginning and end indices in IWDLST of the Jth sentence of document ID/hich is to be written out.

If any sentences of a document are to be

written out., then the twelve word BCD identifier of this document iswritten out first.
At this point, PHRGCC unwinds the chained lists JQ and KQ in which
IVPHROC has entered the phrases found together with their weights.

JP(lD)

will contain a pointer to the location in the array JQ in which the firstphrase of document ID has been placed.

KQ is a pointer array for JQ.

K Q U O is the index in JQ of the next phrase found in the document in which
the phrase in JQ(K) was found.

The chained list for a particular document

is sorted in numerical order of the phrase concept number.

No phrase occurs

more than once in the list for any one document (except that occurrences inthe title are treated distinctly from those in the body of a document andli; tinguished by a different tag field).

If one phrase was found. everal times in a document, the weight is set accordingly by WFHROC.
]ist for each document terminates with the word 077777777777^.

The

PHROCC places

the entries from JQ into the FORTRAN array MARK; between the lists for twocuments the word 077777777777g is written (even if these lists'j.re null),

xf the flag INCPLG is nonzero, then the last document of theXII-8

current core-load is incomplete, in which case PHROCC sets a pointer insuch a way that the program VECFM (see Sec. V) ignores the part of MARK
corresponding to the last document.

In this case, PHROCC writes this sectionof MARK cnto a scratch tape. This tape is read in when PHROCC is called forthe next core-load of documents and is- used to initialize JQ correctly.
If both statistical phrase and clustering options were requested,
PHROCC performs the lookup for both before returning to the calling program.
Except for the fact that SYNTAX does not affect the clusters (i.e., nothingis written out on A7), and that the clusters always have negative concept
numbers, the code is the same in either case.
Flowchart 2 describes the operation of PHROCC. NBUFF (which iseither 1 or 2) indicates which half of the dictionary input buffer iscurrently being used.
Consider now the subroutine Y/PHROC. The data left for the calling
program (of PHROCC) in the array MARK must be in the following format

S12 3jI J

17 18-20 21CON NO.

JT i35WEIGHT]

where S = + or - according to whether statistical phrases or clusters are
determined, CON NO. is the concept number of the phrase, and T = 6 if thephrase was found in the first sentence (i.e., title) of the document, and= 2 otherwise. WEIGHT is 12 times the number of occurrences of the phrase
times the weight of the phrase (which is always 1 for statistical phrases,
but may be some other integer in the case of a cluster).

\£l- <
Sta1 phrs or clusters?
Set L0 - 1 or ? resp.
if SYNTAX, Velse L0 = 2.ck JQ into MARK. Set
pointer to last entry in MARK
J= 1,Llize JF, JQ, KQ, if
LAS INC T* 0in scratch
itape first.

i

INCPLG: 0If IfcV = 1, e r a s e LBK1r

NBUFF = 1
Write last document of MARK onto
scratch tape. Set end pointerof MARK back to end of last
document but one.

'usT,tf ? Pr.
Input next half bufferof dictionary
Unpack half buffer'NBUFFof dictionary into IDICTand IDA\IND = 1-L0 = 2II

CLUSPfi: 0Form array 1ST of p o i n t e r sto beginning of sentencesin document n o . IND
IND =; IND + 1:
C a l l WPHR0C (IND)

1"IND : I.D0CS -*<1

RETURN1

NBUFF = 3 - NBUFF1
E0Fl i b r a r y t a \e1

No1~L00 •I i

•Write out document i d e n t i f i e r sland s e n t e n c e s using a r r a y s LEM1
land LEM2
S u b r o u t i n e PHR0CC
Flowchart 2

XII-10

This is also the format used in JQ (except for the sign which would
confuse attempts to order JQ; the sign is added later by PHROCC).
The number of occurrences of a phrase in a sentence is defined tobe the minimum of the number of occurrences of each of its components inthe sentence. Since many words have more than one associated concept number,a check is made to ensure that different components of a phrase are not foundin the same word of a sentence (by keeping a list in the array IW of thosewords in which phrase components have already been found).

One would,

presumably, not wish to count such an event as an occurrence of a phrase.
In order to save the time of unpacking words from IWDLST each timea test is to be made, WPHROC works one sentence at a time, first unpacking
the words of the current sentence into an array called MSENT. Each phrase
in the current buffer load of the dictionary (which has been unpacked into
the array IDICT by PHROCC) is then searched for in the sentence under consideration. The method is completely straightforward:

the first componentof the phrase is matched against each component of each word in the sentence;the second component is then matched, and so on. The search terminates
when either a zero component concept number of the phrase is reached, or
six components have been processed, or when there are no matches for thepresent component of the phrase.
If a particular phrase is found in a sentence, the appropriate entry
is made in the chained list JQ; if the phrases had been previously found in
this document, no new entry need be made, rather the weight of the old entry
is increased. JQ is always kept in order, eliminating the necessity forperforming a sort before returning the information to either PHROCC or VECFM.

•gdi-nENTER
ISENT = 1
IP = ISTTlSENT)IM = 1ST(ISENT+ 1) - 1
I = IP
M_= Q

MM : 0
KK = 1 I.

i^zr~!J = 1<3ISENT(I,K) : IW(KK). -V H:iLi/.

|MSENT(M,J) = XNUFK(JTOLST(6,l),J !
J = J = 1; M = M + 1|Ii^

'KK = KK + 1 'J:
KK: MMI'. >..

I_= I + 1 :*it.

< I : IM-~-= MM+ 1;IW(MM)=MSENT(J,K)
IIND = 1 'IBETLCJ)""=~IBBL(J) " l 2 " 1A G.
^ ^ —MINW = D: ERASE IBBLi MM = Oj J = l!

I .

X—v—! I = I + 1

IPICT(IND,J) =JQ:
^1:M^-A>

IBBL(J) : ( T l_JuJL,MINN = XMIN OF (IBBLJ), MINWJ= ^ S E N T ( I , K ) : IDICKlMD^J.

S u b r o u t i n e WPHR0C (ID)
Flowchart

3XII-12X

2[ITAG = 6 i f ISENT = 1, e l s e
IITAG = 2

L00

_1

illfi = XPACKF(XPECRF(IDA(IND)),ITAG,0)
I KD = JP(ID)N = IEM1(ID) 1~c

L JD = 0[STF(jQ(KD)TjJh>

O J : 0>>
K= 1! JD = KD
J KD = KQ( ITD !

"XDECRF(I£M2(ID,K)) :JQ(KD) = JQ(KD) + X R S F ( M I N W = X A D D R F ( I D A ( I N D ) ) , 1 8 )

1L

NMN = NMN + 1; KQ(NMN) = KD
JQ_( NMN) • = ILG+XRSFUaNW+XADDRF(lDA( II©)) ,18)!

LEMl(JD) = N + 1
LEM2(ID,N + 1) = XPACKF(IP,0,IM)'!

JD : DkJP(ID) =-V'KQ(JD) = NMN
DFlowcharttS)

3(continued)Vfrl-13
If the syntax option is to be used, and WPHRQC is currently processing
statistical phrases, the appropriate entries are made in LEM1 and LEM2,
provided that the current sentence had not been previously entered (i.e.,^ven if many phrases are found in one sentence, the sentence is written
out on A7 only once) .
Flowchart

3describes subroutine WPHROC in detail: MS is thenumber of sentences in the current document and is set by PHROCC•JNUFK(A,l) gives the decrement or address (according as I is even or odd)of the (l-l)/2 word after A. XMIN0F(A,B) returns the minimum of its
arguments. XPACKF(I,J,K) packs FORTRAN integers I,J,K, respectively, inthe decrement, tag and address of a word; XDECRF(A) and XADDRF(A) returnthe decrement and address, respectively, of their arguments as a FORTRAN
integer. XISTF(A) masks out the 15 low-order bits of its argument.
XRSF(A,l) shifts A right 18 places. ID is the current document number(in this core-load) and is an argument used by WPHROC.

IDA(l) contains

the first word of the four-word entry for the Ith phrase in the current
dictionary buffer, and IDIGT(l,J) J = 1,...,6 contains the Jth componentof the Ith phrase of the current buffer. These last two arrays are preparedby PHROCC.