%!PS-Adobe-3.0 %%Creator: psdit %%For: aloe:udi (Udi Manber) %%Title: stdin (ditroff) %%CreationDate: Tue Nov 2 09:22:25 1993 %%DocumentNeededResources: (atend) %%DocumentSuppliedResources: DIThacks %%Pages: (atend) %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: /disks/hobo/vp6/snichols/rel3.0/transcript/lib/RCS/psdit.pro,v 3.0 1991/06/17 17:08:31 snichols Exp $ % Psfig RCSID $Header: psdit.pro,v 1.5 88/01/04 17:48:22 trevor Exp $ /$DITroff 180 dict def $DITroff begin /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def %% Psfig additions /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight % firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def % /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end XMOD additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {72 mul 0 exch translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant neg tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end %%BeginResource: font DIThacks % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop %%EndResource %%EndProlog %%BeginSetup ditstart (psc)xT 576 1 1 xr %%IncludeResource: font Times-Roman 1(Times-Roman)xf 1 f %%IncludeResource: font Times-Italic 2(Times-Italic)xf 2 f %%IncludeResource: font Times-Bold 3(Times-Bold)xf 3 f %%IncludeResource: font Times-BoldItalic 4(Times-BoldItalic)xf 4 f %%IncludeResource: font Helvetica 5(Helvetica)xf 5 f %%IncludeResource: font Helvetica-Bold 6(Helvetica-Bold)xf 6 f %%IncludeResource: font Courier 7(Courier)xf 7 f %%IncludeResource: font Courier-Bold 8(Courier-Bold)xf 8 f %%IncludeResource: font Symbol 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f 11.00 xi %%EndSetup %%Page: 1 1 10 s 10 xH 0 xS 1 f 288 768 MXY 0 0 MXY PB 130 -108 moveto 351 0 rlineto 0 -234 rlineto -351 0 rlineto closepath 1 setlinewidth stroke % draw box outline /ctext { 3 1 roll moveto dup stringwidth pop -2 div 0 rmoveto show } def /Times-Roman findfont 18 scalefont setfont 306 -450 (DEPARTMENT OF COMPUTER SCIENCE) ctext 192 -612 translate % position for wordmark -187 -638 translate % cancel wordmark coordinate system %!PS-Adobe-3.0 EPSF-3.0 %%%Creator: Adobe Illustrator(TM) 3.0 %%%For: (Pat Crowe) (PPSS) %%%Title: (wm) %%%CreationDate: (1/2/91) (8:53 AM) %%%DocumentProcessColors: Black %%%DocumentSuppliedResources: procset Adobe_packedarray 2.0 0 %%%+ procset Adobe_cmykcolor 1.1 0 %%%+ procset Adobe_cshow 1.1 0 %%%+ procset Adobe_customcolor 1.0 0 %%%+ procset Adobe_IllustratorA_AI3 1.0 0 %%%BoundingBox: 187 638 416 733 %%AI3_ColorUsage: Black&White %%AI3_TemplateBox: 306 396 306 396 %%AI3_TileBox: -522 761 30 1491 %%AI3_DocumentPreview: Macintosh_Pic %%%EndComments %%%BeginProlog %%%BeginResource: procset Adobe_packedarray 2.0 0 %%%Title: (Packed Array Operators) %%%Version: 2.0 %%%CreationDate: (8/2/90) () %%%Copyright: ((C) 1987-1990 Adobe Systems Incorporated All Rights Reserved) userdict /Adobe_packedarray 5 dict dup begin put /initialize % - initialize - { /packedarray where { pop } { Adobe_packedarray begin Adobe_packedarray { dup xcheck { bind } if userdict 3 1 roll put } forall end } ifelse } def /terminate % - terminate - { } def /packedarray % arguments count packedarray array { array astore readonly } def /setpacking % boolean setpacking - { pop } def /currentpacking % - setpacking boolean { false } def currentdict readonly pop end %%%EndResource Adobe_packedarray /initialize get exec %%%BeginResource: procset Adobe_cmykcolor 1.1 0 %%%Title: (CMYK Color Operators) %%%Version: 1.1 %%%CreationDate: (1/23/89) () %%%Copyright: ((C) 1987-1990 Adobe Systems Incorporated All Rights Reserved) currentpacking true setpacking userdict /Adobe_cmykcolor 4 dict dup begin put /initialize % - initialize - { /setcmykcolor where { pop } { userdict /Adobe_cmykcolor_vars 2 dict dup begin put /_setrgbcolor /setrgbcolor load def /_currentrgbcolor /currentrgbcolor load def Adobe_cmykcolor begin Adobe_cmykcolor { dup xcheck { bind } if pop pop } forall end end Adobe_cmykcolor begin } ifelse } def /terminate % - terminate - { currentdict Adobe_cmykcolor eq { end } if } def /setcmykcolor % cyan magenta yellow black setcmykcolor - { 1 sub 4 1 roll 3 { 3 index add neg dup 0 lt { pop 0 } if 3 1 roll } repeat Adobe_cmykcolor_vars /_setrgbcolor get exec pop } def /currentcmykcolor % - currentcmykcolor cyan magenta yellow black { Adobe_cmykcolor_vars /_currentrgbcolor get exec 3 { 1 sub neg 3 1 roll } repeat 0 } def currentdict readonly pop end setpacking %%%EndResource %%%BeginResource: procset Adobe_cshow 1.1 0 %%%Title: (cshow Operator) %%%Version: 1.1 %%%CreationDate: (1/23/89) () %%%Copyright: ((C) 1987-1990 Adobe Systems Incorporated All Rights Reserved) currentpacking true setpacking userdict /Adobe_cshow 3 dict dup begin put /initialize % - initialize - { /cshow where { pop } { userdict /Adobe_cshow_vars 1 dict dup begin put /_cshow % - _cshow proc {} def Adobe_cshow begin Adobe_cshow { dup xcheck { bind } if userdict 3 1 roll put } forall end end } ifelse } def /terminate % - terminate - { } def /cshow % proc string cshow - { exch Adobe_cshow_vars exch /_cshow exch put { 0 0 Adobe_cshow_vars /_cshow get exec } forall } def currentdict readonly pop end setpacking %%%EndResource %%%BeginResource: procset Adobe_customcolor 1.0 0 %%%Title: (Custom Color Operators) %%%Version: 1.0 %%%CreationDate: (5/9/88) () %%%Copyright: ((C) 1987-1990 Adobe Systems Incorporated All Rights Reserved) currentpacking true setpacking userdict /Adobe_customcolor 5 dict dup begin put /initialize % - initialize - { /setcustomcolor where { pop } { Adobe_customcolor begin Adobe_customcolor { dup xcheck { bind } if pop pop } forall end Adobe_customcolor begin } ifelse } def /terminate % - terminate - { currentdict Adobe_customcolor eq { end } if } def /findcmykcustomcolor % cyan magenta yellow black name findcmykcustomcolor object { 5 packedarray } def /setcustomcolor % object tint setcustomcolor - { exch aload pop pop 4 { 4 index mul 4 1 roll } repeat 5 -1 roll pop setcmykcolor } def /setoverprint % boolean setoverprint - { pop } def currentdict readonly pop end setpacking %%%EndResource %%%BeginResource: procset Adobe_IllustratorA_AI3 1.0 0 %%%Title: (Adobe Illustrator (R) Version 3.0 Abbreviated Prolog) %%%Version: 1.0 %%%CreationDate: (7/22/89) () %%%Copyright: ((C) 1987-1990 Adobe Systems Incorporated All Rights Reserved) currentpacking true setpacking userdict /Adobe_IllustratorA_AI3 61 dict dup begin put %% initialization /initialize % - initialize - { userdict /Adobe_IllustratorA_AI3_vars 46 dict dup begin put %% paint operands /_lp /none def /_pf {} def /_ps {} def /_psf {} def /_pss {} def /_pjsf {} def /_pjss {} def /_pola 0 def /_doClip 0 def %% paint operators /cf currentflat def % - cf flatness %% typography operands /_tm matrix def /_renderStart [/e0 /r0 /a0 /o0 /i0 /i0 /i0 /i0] def /_renderEnd [null null null null /e1 /r1 /a1 /clip] def /_render -1 def /_rise 0 def /_ax 0 def % x character spacing (_ax, _ay, _cx, _cy follows awidthshow naming convention) /_ay 0 def % y character spacing /_cx 0 def % x word spacing /_cy 0 def % y word spacing /_leading [0 0] def /_ctm matrix def /_mtx matrix def /_sp 16#020 def /_hyphen (-) def /_fScl 0 def /_cnt 0 def /_hs 1 def /_nativeEncoding 0 def /_useNativeEncoding 0 def /_tempEncode 0 def /_pntr 0 def %% typography operators /Tx {} def /Tj {} def %% compound path operators /CRender {} def %% printing /_AI3_savepage {} def %% color operands /_gf null def /_cf 4 array def /_if null def /_of false def /_fc {} def /_gs null def /_cs 4 array def /_is null def /_os false def /_sc {} def /_i null def Adobe_IllustratorA_AI3 begin Adobe_IllustratorA_AI3 { dup xcheck { bind } if pop pop } forall end end Adobe_IllustratorA_AI3 begin Adobe_IllustratorA_AI3_vars begin newpath } def /terminate % - terminate - { end end } def %% definition operators /_ % - _ null null def /ddef % key value ddef - { Adobe_IllustratorA_AI3_vars 3 1 roll put } def /xput % key value literal xput - { dup load dup length exch maxlength eq { dup dup load dup length 2 mul dict copy def } if load begin def end } def /npop % integer npop - { { pop } repeat } def %% marking operators /sw % ax ay string sw x y { dup length exch stringwidth exch 5 -1 roll 3 index 1 sub mul add 4 1 roll 3 1 roll 1 sub mul add } def /swj % cx cy fillchar ax ay string swj x y { dup 4 1 roll dup length exch stringwidth exch 5 -1 roll 3 index 1 sub mul add 4 1 roll 3 1 roll 1 sub mul add 6 2 roll /_cnt 0 ddef {1 index eq {/_cnt _cnt 1 add ddef} if} forall pop exch _cnt mul exch _cnt mul 2 index add 4 1 roll 2 index add 4 1 roll pop pop } def /ss % ax ay string matrix ss - { 4 1 roll { % matrix ax ay char 0 0 {proc} - 2 npop (0) exch 2 copy 0 exch put pop gsave false charpath currentpoint 4 index setmatrix stroke grestore moveto 2 copy rmoveto } exch cshow 3 npop } def /jss % cx cy fillchar ax ay string matrix jss - { 4 1 roll { % cx cy fillchar matrix ax ay char 0 0 {proc} - 2 npop (0) exch 2 copy 0 exch put gsave _sp eq { exch 6 index 6 index 6 index 5 -1 roll widthshow currentpoint } { false charpath currentpoint 4 index setmatrix stroke }ifelse grestore moveto 2 copy rmoveto } exch cshow 6 npop } def %% path operators /sp % ax ay string sp - { { 2 npop (0) exch 2 copy 0 exch put pop false charpath 2 copy rmoveto } exch cshow 2 npop } def /jsp % cx cy fillchar ax ay string jsp - { { % cx cy fillchar ax ay char 0 0 {proc} - 2 npop (0) exch 2 copy 0 exch put _sp eq { exch 5 index 5 index 5 index 5 -1 roll widthshow } { false charpath }ifelse 2 copy rmoveto } exch cshow 5 npop } def %% path construction operators /pl % x y pl x y { transform 0.25 sub round 0.25 add exch 0.25 sub round 0.25 add exch itransform } def /setstrokeadjust where { pop true setstrokeadjust /c % x1 y1 x2 y2 x3 y3 c - { curveto } def /C /c load def /v % x2 y2 x3 y3 v - { currentpoint 6 2 roll curveto } def /V /v load def /y % x1 y1 x2 y2 y - { 2 copy curveto } def /Y /y load def /l % x y l - { lineto } def /L /l load def /m % x y m - { moveto } def } {%else /c { pl curveto } def /C /c load def /v { currentpoint 6 2 roll pl curveto } def /V /v load def /y { pl 2 copy curveto } def /Y /y load def /l { pl lineto } def /L /l load def /m { pl moveto } def }ifelse %% graphic state operators /d % array phase d - { setdash } def /cf {} def % - cf flatness /i % flatness i - { dup 0 eq { pop cf } if setflat } def /j % linejoin j - { setlinejoin } def /J % linecap J - { setlinecap } def /M % miterlimit M - { setmiterlimit } def /w % linewidth w - { setlinewidth } def %% path painting operators /H % - H - {} def /h % - h - { closepath } def /N % - N - { _pola 0 eq { _doClip 1 eq {clip /_doClip 0 ddef} if newpath } { /CRender {N} ddef }ifelse } def /n % - n - {N} def /F % - F - { _pola 0 eq { _doClip 1 eq { gsave _pf grestore clip newpath /_lp /none ddef _fc /_doClip 0 ddef } { _pf }ifelse } { /CRender {F} ddef }ifelse } def /f % - f - { closepath F } def /S % - S - { _pola 0 eq { _doClip 1 eq { gsave _ps grestore clip newpath /_lp /none ddef _sc /_doClip 0 ddef } { _ps }ifelse } { /CRender {S} ddef }ifelse } def /s % - s - { closepath S } def /B % - B - { _pola 0 eq { _doClip 1 eq % F clears _doClip gsave F grestore { gsave S grestore clip newpath /_lp /none ddef _sc /_doClip 0 ddef } { S }ifelse } { /CRender {B} ddef }ifelse } def /b % - b - { closepath B } def /W % - W - { /_doClip 1 ddef } def /* % - [string] * - { count 0 ne { dup type (stringtype) eq {pop} if } if _pola 0 eq {newpath} if } def %% group operators /u % - u - {} def /U % - U - {} def /q % - q - { _pola 0 eq {gsave} if } def /Q % - Q - { _pola 0 eq {grestore} if } def /*u % - *u - { _pola 1 add /_pola exch ddef } def /*U % - *U - { _pola 1 sub /_pola exch ddef _pola 0 eq {CRender} if } def /D % polarized D - {pop} def /*w % - *w - {} def /*W % - *W - {} def %% place operators /` % matrix llx lly urx ury string ` - { /_i save ddef 6 1 roll 4 npop concat userdict begin /showpage {} def false setoverprint pop } def /~ % - ~ - { end _i restore } def %% color operators /O % flag O - { 0 ne /_of exch ddef /_lp /none ddef } def /R % flag R - { 0 ne /_os exch ddef /_lp /none ddef } def /g % gray g - { /_gf exch ddef /_fc { _lp /fill ne { _of setoverprint _gf setgray /_lp /fill ddef } if } ddef /_pf { _fc fill } ddef /_psf { _fc ashow } ddef /_pjsf { _fc awidthshow } ddef /_lp /none ddef } def /G % gray G - { /_gs exch ddef /_sc { _lp /stroke ne { _os setoverprint _gs setgray /_lp /stroke ddef } if } ddef /_ps { _sc stroke } ddef /_pss { _sc ss } ddef /_pjss { _sc jss } ddef /_lp /none ddef } def /k % cyan magenta yellow black k - { _cf astore pop /_fc { _lp /fill ne { _of setoverprint _cf aload pop setcmykcolor /_lp /fill ddef } if } ddef /_pf { _fc fill } ddef /_psf { _fc ashow } ddef /_pjsf { _fc awidthshow } ddef /_lp /none ddef } def /K % cyan magenta yellow black K - { _cs astore pop /_sc { _lp /stroke ne { _os setoverprint _cs aload pop setcmykcolor /_lp /stroke ddef } if } ddef /_ps { _sc stroke } ddef /_pss { _sc ss } ddef /_pjss { _sc jss } ddef /_lp /none ddef } def /x % cyan magenta yellow black name gray x - { /_gf exch ddef findcmykcustomcolor /_if exch ddef /_fc { _lp /fill ne { _of setoverprint _if _gf 1 exch sub setcustomcolor /_lp /fill ddef } if } ddef /_pf { _fc fill } ddef /_psf { _fc ashow } ddef /_pjsf { _fc awidthshow } ddef /_lp /none ddef } def /X % cyan magenta yellow black name gray X - { /_gs exch ddef findcmykcustomcolor /_is exch ddef /_sc { _lp /stroke ne { _os setoverprint _is _gs 1 exch sub setcustomcolor /_lp /stroke ddef } if } ddef /_ps { _sc stroke } ddef /_pss { _sc ss } ddef /_pjss { _sc jss } ddef /_lp /none ddef } def %% locked object operator /A % value A - { pop } def currentdict readonly pop end setpacking %% annotate page operator /annotatepage { } def %%%EndResource %%%EndProlog %%%BeginSetup Adobe_cmykcolor /initialize get exec Adobe_cshow /initialize get exec Adobe_customcolor /initialize get exec Adobe_IllustratorA_AI3 /initialize get exec %%%EndSetup 0 A u 0 O 0 g 0 i 0 J 0 j 1 w 4 M []0 d %%AI3_Note: 0 D 236.1606 721.7052 m 236.1606 720.565 236.1406 719.7848 237.2008 719.1647 c 237.2008 719.1047 L 233.24 719.1047 L 233.24 719.1647 L 234.2402 719.5448 234.1201 721.0051 234.1201 721.9053 c 234.1201 730.8272 L 232.3598 730.8272 L 231.4996 730.8272 230.5994 730.6071 229.9793 730.027 c 229.9192 730.027 L 230.6194 732.4075 L 230.6794 732.4075 L 230.9195 732.3075 231.1795 732.3075 231.4396 732.2675 c 231.9397 732.2675 L 239.4013 732.2675 L 239.7413 732.2675 240.0614 732.2875 240.3215 732.4075 c 240.3815 732.4075 L 239.7413 730.027 L 239.6813 730.027 L 239.4213 730.7272 238.6211 730.8272 237.961 730.8272 c 236.1606 730.8272 L 236.1606 721.7052 l f 242.7238 724.2428 m 242.7238 721.3456 L 242.7238 720.6253 242.6277 719.4568 243.4281 719.1527 c 243.4281 719.1047 L 240.3868 719.1047 L 240.3868 719.1527 L 241.1872 719.4568 241.0911 720.6253 241.0911 721.3456 c 241.0911 727.396 L 241.0911 728.1163 241.2032 729.2848 240.3868 729.5889 c 240.3868 729.6369 L 243.4281 729.6369 L 243.4281 729.5889 L 242.6277 729.2848 242.7238 728.1163 242.7238 727.38 c 242.7238 725.3952 L 248.5021 725.3952 L 248.5021 727.38 L 248.5021 728.1163 248.6142 729.2848 247.7978 729.5889 c 247.7978 729.6369 L 250.8551 729.6369 L 250.8551 729.5889 L 250.0387 729.2848 250.1348 728.1163 250.1348 727.396 c 250.1348 721.3456 L 250.1348 720.6253 250.0387 719.4568 250.8551 719.1527 c 250.8551 719.1047 L 247.7978 719.1047 L 247.7978 719.1527 L 248.6142 719.4568 248.5021 720.6253 248.5021 721.3456 c 248.5021 724.2428 L 242.7238 724.2428 l f 254.4034 720.4492 m 256.4362 720.2572 L 257.4926 720.1611 258.5971 720.4972 259.3974 721.2015 c 259.4454 721.2015 L 258.7251 719.1047 L 252.0504 719.1047 L 252.0504 719.1527 L 252.8668 719.4408 252.7707 720.6253 252.7707 721.3456 c 252.7707 727.38 L 252.7707 728.1163 252.8668 729.2848 252.0504 729.5889 c 252.0504 729.6369 L 257.1725 729.6369 L 257.4446 729.6369 257.7167 729.6049 257.9248 729.717 c 257.9728 729.717 L 257.9728 727.8442 L 257.9248 727.8442 L 257.4286 728.4205 256.7723 728.4845 256.036 728.4845 c 255.4758 728.4845 254.9156 728.4685 254.4034 728.3724 c 254.4034 725.3952 L 256.3081 725.3952 L 256.5643 725.3952 256.8204 725.3952 257.0124 725.4913 c 257.0605 725.4913 L 257.0605 723.7946 L 257.0124 723.7946 L 256.7563 724.2588 256.0841 724.2428 255.5879 724.2428 c 254.4034 724.2428 L 254.4034 720.4492 l f 274.0932 720.425 m 273.2131 719.2647 271.5727 718.7846 270.1724 718.7846 c 268.8521 718.7846 267.4518 719.2047 266.5516 720.1849 c 265.4914 721.3452 265.5314 722.6855 265.5314 724.1258 c 265.5314 729.4669 L 265.5314 730.3671 265.6714 731.8274 264.6512 732.2075 c 264.6512 732.2675 L 268.452 732.2675 L 268.452 732.2075 L 267.4518 731.8274 267.5718 730.3671 267.5718 729.4669 c 267.5718 724.1258 L 267.5718 721.4652 268.6921 720.2249 270.7525 720.2249 c 271.8728 720.2249 273.013 720.685 273.6732 721.6252 c 274.1132 722.2254 274.0932 722.7255 274.0932 723.4456 c 274.0932 729.4669 L 274.0932 730.3671 274.2133 731.8274 273.2131 732.2075 c 273.2131 732.2675 L 277.0139 732.2675 L 277.0339 732.2075 L 276.0137 731.8274 276.1337 730.3671 276.1337 729.4469 c 276.1337 721.9053 L 276.1337 721.0051 276.0137 719.5448 277.0339 719.1647 c 277.0339 719.1047 L 274.0932 719.1047 L 274.0932 720.425 l f 280.2988 721.1855 m 280.2988 720.2892 280.2828 719.6489 281.1311 719.1527 c 281.1311 719.1047 L 278.298 719.1047 L 278.298 719.1527 L 279.1463 719.6489 279.1463 720.2892 279.1463 721.1855 c 279.1463 727.5721 L 279.1463 728.4685 279.1463 729.1087 278.314 729.5889 c 278.314 729.6369 L 280.6509 729.6369 L 280.6509 729.6209 L 280.7149 729.4289 280.779 729.3488 280.891 729.2208 c 281.1151 728.9006 L 286.9735 721.5057 L 286.9735 727.5721 L 286.9735 728.4685 286.9895 729.1087 286.1411 729.5889 c 286.1411 729.6369 L 288.9583 729.6369 L 288.9583 729.5889 L 288.1259 729.1087 288.1259 728.4685 288.1259 727.5721 c 288.1259 718.5925 L 286.9895 718.9766 286.4933 719.5048 285.789 720.4172 c 280.2988 727.38 L 280.2988 721.1855 l f 290.5858 727.38 m 290.5858 728.1163 290.6979 729.2848 289.8815 729.5889 c 289.8815 729.6369 L 292.9228 729.6369 L 292.9228 729.5889 L 292.1224 729.2848 292.2185 728.1003 292.2185 727.38 c 292.2185 721.3456 L 292.2185 720.6253 292.1224 719.4568 292.9228 719.1527 c 292.9228 719.1047 L 289.8815 719.1047 L 289.8815 719.1527 L 290.6819 719.4408 290.5858 720.6253 290.5858 721.3456 C 290.5858 727.38 l f 300.6645 726.7398 m 301.0966 727.8762 301.6408 729.1888 300.6484 729.5889 c 300.6484 729.6369 L 303.0334 729.6369 L 298.8077 718.6245 L 297.6873 719.3608 297.3191 719.4888 296.8549 720.7534 c 294.4379 727.3 L 294.1338 728.1163 293.8937 729.0447 293.1894 729.5889 c 293.1894 729.6369 L 295.5264 729.6369 L 295.5104 729.4449 L 295.5104 729.0927 295.8145 728.3084 295.9425 727.9563 c 298.4876 720.9934 L 300.6645 726.7398 l f 306.0684 720.4492 m 308.1012 720.2572 L 309.1577 720.1611 310.2621 720.4972 311.0624 721.2015 c 311.1105 721.2015 L 310.3902 719.1047 L 303.7155 719.1047 L 303.7155 719.1527 L 304.5318 719.4408 304.4358 720.6253 304.4358 721.3456 c 304.4358 727.38 L 304.4358 728.1163 304.5318 729.2848 303.7155 729.5889 c 303.7155 729.6369 L 308.8375 729.6369 L 309.1096 729.6369 309.3818 729.6049 309.5898 729.717 c 309.6379 729.717 L 309.6379 727.8442 L 309.5898 727.8442 L 309.0936 728.4205 308.4374 728.4845 307.7011 728.4845 c 307.1408 728.4845 306.5806 728.4685 306.0684 728.3724 c 306.0684 725.3952 L 307.9732 725.3952 L 308.2293 725.3952 308.4854 725.3952 308.6775 725.4913 c 308.7255 725.4913 L 308.7255 723.7946 L 308.6775 723.7946 L 308.4214 724.2588 307.7491 724.2428 307.2529 724.2428 c 306.0684 724.2428 L 306.0684 720.4492 l f 315.7934 729.6369 m 317.9383 729.6369 319.1067 728.5165 319.1067 727.0599 c 319.1067 725.6513 317.8742 724.5469 316.5617 724.2428 c 318.8666 721.3456 L 319.5389 720.5133 320.5473 719.6809 321.4597 719.1047 c 319.9871 719.1047 L 319.1387 719.1047 318.6105 719.3128 318.1303 719.905 c 316.1775 722.322 L 314.705 724.5789 L 315.9855 724.771 317.4741 725.3632 317.4741 726.8678 c 317.4741 728.0203 316.4817 728.6926 315.4092 728.6445 c 315.0411 728.6285 314.6889 728.5805 314.3208 728.5165 c 314.3208 721.3456 L 314.3208 720.6093 314.2248 719.4408 315.0411 719.1527 c 315.0411 719.1047 L 311.9839 719.1047 L 311.9839 719.1527 L 312.8002 719.4408 312.6881 720.6253 312.6881 721.3456 c 312.6881 727.38 L 312.6881 728.1163 312.8002 729.2848 311.9839 729.5889 c 311.9839 729.6369 L 315.7934 729.6369 l f 326.8471 727.7322 m 326.2228 728.3724 325.2304 728.7406 324.3341 728.7406 c 323.4217 728.7406 322.2692 728.3884 322.2692 727.284 c 322.2692 725.0911 327.7755 725.1231 327.7755 722.1619 c 327.7755 720.4492 325.9827 718.8486 323.4857 718.8486 c 322.5093 718.8486 321.5329 718.9926 320.6206 719.3288 c 320.1564 721.3296 L 321.1008 720.5133 322.4133 720.001 323.6618 720.001 c 324.5742 720.001 325.9507 720.5453 325.9507 721.6657 c 325.9507 724.1627 320.4445 723.7145 320.4445 727.1079 c 320.4445 729.1247 322.5093 729.893 324.4621 729.893 c 325.2624 729.893 326.0788 729.781 326.8471 729.5409 C 326.8471 727.7322 l f 329.6092 727.38 m 329.6092 728.1163 329.7213 729.2848 328.905 729.5889 c 328.905 729.6369 L 331.9462 729.6369 L 331.9462 729.5889 L 331.1459 729.2848 331.2419 728.1003 331.2419 727.38 c 331.2419 721.3456 L 331.2419 720.6253 331.1459 719.4568 331.9462 719.1527 c 331.9462 719.1047 L 328.905 719.1047 L 328.905 719.1527 L 329.7053 719.4408 329.6092 720.6253 329.6092 721.3456 C 329.6092 727.38 l f 336.8708 721.1855 m 336.8708 720.2732 336.8547 719.6489 337.7031 719.1527 c 337.7031 719.1047 L 334.5338 719.1047 L 334.5338 719.1527 L 335.3341 719.4568 335.2381 720.6253 335.2381 721.3456 c 335.2381 728.4845 L 333.8295 728.4845 L 333.1412 728.4845 332.421 728.3084 331.9248 727.8442 c 331.8767 727.8442 L 332.437 729.749 L 332.485 729.749 L 332.6771 729.669 332.8851 729.669 333.0932 729.6369 c 333.4934 729.6369 L 339.4638 729.6369 L 339.7359 729.6369 339.992 729.6529 340.2001 729.749 c 340.2481 729.749 L 339.7359 727.8442 L 339.6879 727.8442 L 339.4798 728.4044 338.8395 728.4845 338.3113 728.4845 c 336.8708 728.4845 L 336.8708 721.1855 l f 345.1265 721.1855 m 345.1265 720.2251 345.1265 719.7449 345.9428 719.1527 c 345.9428 719.1047 L 342.8216 719.1047 L 342.8216 719.1527 L 343.6059 719.5529 343.4938 720.5933 343.4938 721.3456 c 343.4938 723.7145 L 340.8368 727.9883 L 340.4046 728.6926 340.0845 729.2208 339.3161 729.6369 c 340.7727 729.6369 L 341.2849 729.6369 341.7651 729.5249 341.9732 729.1888 c 344.5343 725.0111 L 346.5191 727.9883 L 346.7912 728.3884 347.1593 729.1567 346.263 729.5889 c 346.263 729.6369 L 349.0641 729.6369 L 345.1265 723.7145 L 345.1265 721.1855 l f 365.0425 724.4829 m 365.0425 721.2175 362.3374 718.8486 359.1521 718.8486 c 355.9829 718.8486 353.3098 721.1215 353.3098 724.4028 c 353.3098 727.4441 355.9508 729.9891 359.3122 729.9091 c 362.6736 729.9251 365.0425 727.364 365.0425 724.4829 c f 1 g 359.2002 728.7566 m 361.7292 728.7566 363.2178 726.4997 363.2178 724.1627 c 363.2178 721.7778 361.6652 720.001 359.2322 720.001 c 356.7192 720.001 355.1345 722.306 355.1345 724.5469 c 355.1345 726.9639 356.7192 728.7566 359.2002 728.7566 c f 0 g 368.3314 721.3456 m 368.3314 720.6253 368.2033 719.4568 369.0036 719.1527 c 369.0036 719.1047 L 365.9784 719.1047 L 365.9784 719.1527 L 366.7947 719.4408 366.6987 720.6253 366.6987 721.3456 c 366.6987 727.38 L 366.6987 728.1163 366.7947 729.2848 365.9784 729.5889 c 365.9784 729.6369 L 371.1005 729.6369 L 371.3726 729.6369 371.6447 729.6049 371.8528 729.717 c 371.9008 729.717 L 371.9008 727.8602 L 371.8528 727.8602 L 371.3566 728.4205 370.7003 728.4845 369.964 728.4845 c 369.4038 728.4845 368.8436 728.4685 368.3314 728.3724 c 368.3314 725.3952 L 370.2521 725.3952 L 370.4922 725.3952 370.7483 725.3952 370.9404 725.4913 c 370.9884 725.4913 L 370.9884 723.7946 L 370.9404 723.7946 L 370.6843 724.2748 370.0121 724.2428 369.5158 724.2428 c 368.3314 724.2428 L 368.3314 721.3456 l f 213.3082 708.0982 m 225.5802 677.8043 L 226.7732 673.7297 228.8982 670.9797 230.96 669.2847 c 230.96 669.1047 L 218.6605 669.1047 L 218.6605 669.2847 L 221.6003 670.6046 221.1204 671.2646 219.5004 675.4644 c 216.2606 683.9241 L 201.1412 683.9241 l 198.0213 675.4644 L 196.7613 672.1046 196.3414 670.3646 199.2212 669.2847 c 199.2212 669.1047 L 188.1817 669.1047 L 188.1817 669.2847 L 191.6616 671.0246 192.6815 674.3845 194.0015 677.8043 c 204.0211 702.8233 L 204.6491 704.4382 205.5119 706.858 205.9074 707.9764 C 209.3357 717.8547 l 213.3082 708.0982 L 213.3082 708.0982 L f 1 g 214.5206 688.3639 m 202.7011 688.3639 L 208.6409 703.4833 l 214.5206 688.3639 L f 0 g 246.0102 702.0067 m 252.7106 702.0067 256.3608 698.5065 256.3608 693.9562 c 256.3608 689.5559 252.5106 686.1057 248.4104 685.1557 c 255.6108 676.1051 L 257.7109 673.505 260.8611 670.9048 263.7113 669.1047 c 259.111 669.1047 L 256.4608 669.1047 254.8107 669.7547 253.3106 671.6048 c 247.2103 679.1553 L 242.61 686.2057 L 246.6102 686.8058 251.2605 688.6559 251.2605 693.3562 c 251.2605 696.9564 248.1603 699.0565 244.8101 698.9065 c 243.6601 698.8565 242.56 698.7065 241.4099 698.5065 c 241.4099 676.1051 L 241.4099 673.805 241.1099 670.1548 243.6601 669.2547 c 243.6601 669.1047 L 234.1095 669.1047 L 234.1095 669.2547 L 236.6596 670.1548 236.3096 673.855 236.3096 676.1051 c 236.3096 694.9563 L 236.3096 697.2564 236.6596 700.9066 234.1095 701.8567 c 234.1095 702.0067 L 246.0102 702.0067 l f 265.5988 694.9563 m 265.5988 697.2564 265.9488 700.9066 263.3987 701.8567 c 263.3987 702.0067 L 272.8992 702.0067 L 272.8992 701.8567 L 270.3991 700.9066 270.6991 697.2064 270.6991 694.9563 c 270.6991 676.1051 L 270.6991 673.855 270.3991 670.2048 272.8992 669.2547 c 272.8992 669.1047 L 263.3987 669.1047 L 263.3987 669.2547 L 265.8988 670.1548 265.5988 673.855 265.5988 676.1051 C 265.5988 694.9563 l f 275.8864 669.1047 m 293.9875 697.9064 L 285.4869 698.4065 L 282.3868 698.6065 280.5867 697.9564 277.9865 696.2563 c 277.8365 696.2563 L 280.3866 702.0067 L 302.488 702.0067 L 284.4869 673.3049 L 294.9875 672.7049 L 298.6378 672.5049 301.7879 673.605 304.8881 675.4551 c 305.0381 675.4551 L 302.238 669.1047 L 275.8864 669.1047 l f 342.1312 685.9057 m 342.1312 675.7051 333.6806 668.3046 323.73 668.3046 c 313.8294 668.3046 305.4789 675.4051 305.4789 685.6557 c 305.4789 695.1563 313.7294 703.1068 324.2301 702.8567 c 334.7307 702.9067 342.1312 694.9063 342.1312 685.9057 c f 1 g 323.88 699.2565 m 331.7805 699.2565 336.4308 692.2061 336.4308 684.9057 c 336.4308 677.4552 331.5805 671.9049 323.9801 671.9049 c 316.1296 671.9049 311.1793 679.1053 311.1793 686.1057 c 311.1793 693.6562 316.1296 699.2565 323.88 699.2565 c f 0 g 349.9185 675.6051 m 349.9185 672.8049 349.8685 670.8048 352.5187 669.2547 c 352.5187 669.1047 L 343.6682 669.1047 L 343.6682 669.2547 L 346.3183 670.8048 346.3183 672.8049 346.3183 675.6051 c 346.3183 695.5563 L 346.3183 698.3565 346.3183 700.3566 343.7182 701.8567 c 343.7182 702.0067 L 351.0186 702.0067 L 351.0186 701.9567 L 351.2186 701.3567 351.4186 701.1066 351.7687 700.7066 c 352.4687 699.7066 L 370.7698 676.6051 L 370.7698 695.5563 L 370.7698 698.3565 370.8198 700.3566 368.1697 701.8567 c 368.1697 702.0067 L 376.9702 702.0067 L 376.9702 701.8567 L 374.37 700.3566 374.37 698.3565 374.37 695.5563 c 374.37 667.5046 L 370.8198 668.7047 369.2697 670.3548 367.0696 673.2049 c 349.9185 694.9563 L 349.9185 675.6051 l f 389.9668 681.4554 m 387.3666 674.405 L 386.3166 671.6048 385.9665 670.1548 388.3667 669.2547 c 388.3667 669.1047 L 379.1661 669.1047 L 379.1661 669.2547 L 382.0663 670.7048 382.9163 673.505 384.0164 676.3551 c 392.3669 697.2064 L 393.067 699.0065 394.017 701.1066 391.6169 701.8567 c 391.6169 702.0067 L 399.5174 702.0067 L 409.918 676.3551 L 411.0681 673.505 411.9681 670.7048 414.8183 669.2547 c 414.8183 669.1047 L 404.5677 669.1047 L 404.5677 669.2547 L 407.0178 670.3548 406.6178 670.9048 405.2677 674.405 c 402.5675 681.4554 L 389.9668 681.4554 l f 1 g 401.1175 685.1557 m 391.2669 685.1557 L 396.2172 697.7564 l 401.1175 685.1557 L f 0 g 237.3542 641.7052 m 237.3542 640.565 237.3342 639.7848 238.3944 639.1647 c 238.3944 639.1047 L 234.4336 639.1047 L 234.4336 639.1647 L 235.4338 639.5448 235.3137 641.0051 235.3137 641.9053 c 235.3137 650.8272 L 233.5534 650.8272 L 232.6932 650.8272 231.793 650.6071 231.1729 650.027 c 231.1128 650.027 L 231.813 652.4075 L 231.873 652.4075 L 232.1131 652.3075 232.3731 652.3075 232.6332 652.2675 c 233.1333 652.2675 L 240.5949 652.2675 L 240.9349 652.2675 241.255 652.2875 241.5151 652.4075 c 241.5751 652.4075 L 240.9349 650.027 L 240.8749 650.027 L 240.6149 650.7272 239.8147 650.8272 239.1546 650.8272 c 237.3542 650.8272 L 237.3542 641.7052 l f 248.9914 640.1611 m 248.2872 639.2327 246.9746 638.8486 245.8542 638.8486 c 244.7977 638.8486 243.6773 639.1847 242.957 639.969 c 242.1087 640.8974 242.1407 641.9698 242.1407 643.1223 c 242.1407 647.396 L 242.1407 648.1163 242.2527 649.2848 241.4364 649.5889 c 241.4364 649.6369 L 244.4776 649.6369 L 244.4776 649.5889 L 243.6773 649.2848 243.7733 648.1163 243.7733 647.396 c 243.7733 643.1223 L 243.7733 640.9934 244.6697 640.001 246.3184 640.001 c 247.2147 640.001 248.1271 640.3692 248.6553 641.1215 c 249.0074 641.6017 248.9914 642.0019 248.9914 642.5781 c 248.9914 647.396 L 248.9914 648.1163 249.0875 649.2848 248.2872 649.5889 c 248.2872 649.6369 L 251.3284 649.6369 L 251.3444 649.5889 L 250.5281 649.2848 250.6241 648.1163 250.6241 647.38 c 250.6241 641.3456 L 250.6241 640.6253 250.5281 639.4568 251.3444 639.1527 c 251.3444 639.1047 L 248.9914 639.1047 L 248.9914 640.1611 l f 260.7827 647.6521 m 259.9024 648.2124 258.8779 648.5645 257.8215 648.5645 c 255.6126 648.5645 254.076 646.9479 254.076 644.6269 c 254.076 642.274 255.6766 640.1771 258.1416 640.1771 c 259.3421 640.1771 260.5426 640.6093 261.551 641.1855 c 261.599 641.1855 L 260.7827 639.3288 L 260.0304 638.9766 259.1981 638.8486 258.3657 638.8486 c 254.5882 638.8486 252.2513 640.9614 252.2513 644.3868 c 252.2513 647.7002 254.5882 649.893 257.8695 649.893 c 258.8459 649.893 259.8383 649.717 260.7827 649.4929 C 260.7827 647.6521 l f 268.3796 647.7322 m 267.7553 648.3724 266.7629 648.7406 265.8665 648.7406 c 264.9542 648.7406 263.8017 648.3884 263.8017 647.284 c 263.8017 645.0911 269.3079 645.1231 269.3079 642.1619 c 269.3079 640.4492 267.5152 638.8486 265.0182 638.8486 c 264.0418 638.8486 263.0654 638.9926 262.153 639.3288 c 261.6889 641.3296 L 262.6332 640.5133 263.9458 640.001 265.1943 640.001 c 266.1066 640.001 267.4832 640.5453 267.4832 641.6657 c 267.4832 644.1627 261.977 643.7145 261.977 647.1079 c 261.977 649.1247 264.0418 649.893 265.9946 649.893 c 266.7949 649.893 267.6112 649.781 268.3796 649.5409 C 268.3796 647.7322 l f 281.9461 644.4829 m 281.9461 641.2175 279.241 638.8486 276.0557 638.8486 c 272.8864 638.8486 270.2133 641.1215 270.2133 644.4028 c 270.2133 647.4441 272.8544 649.9891 276.2158 649.9091 c 279.5771 649.9251 281.9461 647.364 281.9461 644.4829 c f 1 g 276.1037 648.7566 m 278.6327 648.7566 280.1213 646.4997 280.1213 644.1627 c 280.1213 641.7778 278.5687 640.001 276.1357 640.001 c 273.6227 640.001 272.0381 642.306 272.0381 644.5469 c 272.0381 646.9639 273.6227 648.7566 276.1037 648.7566 c f 0 g 284.8508 641.1855 m 284.8508 640.2892 284.8348 639.6489 285.6831 639.1527 c 285.6831 639.1047 L 282.85 639.1047 L 282.85 639.1527 L 283.6983 639.6489 283.6983 640.2892 283.6983 641.1855 c 283.6983 647.5721 L 283.6983 648.4685 283.6983 649.1087 282.866 649.5889 c 282.866 649.6369 L 285.2029 649.6369 L 285.2029 649.6209 L 285.2669 649.4289 285.331 649.3488 285.443 649.2208 c 285.6671 648.9006 L 291.5255 641.5057 L 291.5255 647.5721 L 291.5255 648.4685 291.5415 649.1087 290.6931 649.5889 c 290.6931 649.6369 L 293.5103 649.6369 L 293.5103 649.5889 L 292.6779 649.1087 292.6779 648.4685 292.6779 647.5721 c 292.6779 638.5925 L 291.5415 638.9766 291.0453 639.5048 290.341 640.4172 c 284.8508 647.38 L 284.8508 641.1855 l f 306.5596 652.2675 m 310.7205 642.0053 L 311.1806 640.8651 311.5407 639.7448 312.6809 639.1647 c 312.6809 639.1047 L 308.58 639.1047 L 308.58 639.1647 L 309.5603 639.6048 309.4002 639.8248 308.8601 641.2251 c 307.7799 644.0457 L 302.7388 644.0457 l 301.6986 641.2251 L 301.2785 640.1049 301.1385 639.5248 302.0987 639.1647 c 302.0987 639.1047 L 298.4179 639.1047 L 298.4179 639.1647 L 299.5781 639.7448 299.9182 640.8651 300.3583 642.0053 c 303.699 650.3471 L 305.4607 655.1672 l 306.5596 652.2675 L f 1 g 307.1997 645.5261 m 303.2589 645.5261 L 305.2393 650.5671 l 307.1997 645.5261 L f 0 g 317.1511 649.6369 m 319.2959 649.6369 320.4644 648.5165 320.4644 647.0599 c 320.4644 645.6513 319.2319 644.5469 317.9194 644.2428 c 320.2243 641.3456 L 320.8966 640.5133 321.905 639.6809 322.8173 639.1047 c 321.3448 639.1047 L 320.4964 639.1047 319.9682 639.3128 319.488 639.905 c 317.5352 642.322 L 316.0626 644.5789 L 317.3431 644.771 318.8317 645.3632 318.8317 646.8678 c 318.8317 648.0203 317.8393 648.6926 316.7669 648.6445 c 316.3988 648.6285 316.0466 648.5805 315.6785 648.5165 c 315.6785 641.3456 L 315.6785 640.6093 315.5824 639.4408 316.3988 639.1527 c 316.3988 639.1047 L 313.3415 639.1047 L 313.3415 639.1527 L 314.1578 639.4408 314.0458 640.6253 314.0458 641.3456 c 314.0458 647.38 L 314.0458 648.1163 314.1578 649.2848 313.3415 649.5889 c 313.3415 649.6369 L 317.1511 649.6369 l f 322.9703 647.38 m 322.9703 648.1163 323.0824 649.2848 322.266 649.5889 c 322.266 649.6369 L 325.3073 649.6369 L 325.3073 649.5889 L 324.507 649.2848 324.603 648.1003 324.603 647.38 c 324.603 641.3456 L 324.603 640.6253 324.507 639.4568 325.3073 639.1527 c 325.3073 639.1047 L 322.266 639.1047 L 322.266 639.1527 L 323.0664 639.4408 322.9703 640.6253 322.9703 641.3456 C 322.9703 647.38 l f 325.9741 639.1047 m 331.7685 648.3244 L 329.0474 648.4845 L 328.055 648.5485 327.4787 648.3404 326.6464 647.7962 c 326.5984 647.7962 L 327.4147 649.6369 L 334.4896 649.6369 L 328.7272 640.4492 L 332.0886 640.2572 L 333.2571 640.1931 334.2655 640.5453 335.2579 641.1375 c 335.3059 641.1375 L 334.4095 639.1047 L 325.9741 639.1047 l f 347.5286 644.4829 m 347.5286 641.2175 344.8235 638.8486 341.6382 638.8486 c 338.4689 638.8486 335.7959 641.1215 335.7959 644.4028 c 335.7959 647.4441 338.4369 649.9891 341.7983 649.9091 c 345.1596 649.9251 347.5286 647.364 347.5286 644.4829 c f 1 g 341.6862 648.7566 m 344.2153 648.7566 345.7039 646.4997 345.7039 644.1627 c 345.7039 641.7778 344.1512 640.001 341.7183 640.001 c 339.2052 640.001 337.6206 642.306 337.6206 644.5469 c 337.6206 646.9639 339.2052 648.7566 341.6862 648.7566 c f 0 g 350.4333 641.1855 m 350.4333 640.2892 350.4173 639.6489 351.2656 639.1527 c 351.2656 639.1047 L 348.4325 639.1047 L 348.4325 639.1527 L 349.2808 639.6489 349.2808 640.2892 349.2808 641.1855 c 349.2808 647.5721 L 349.2808 648.4685 349.2808 649.1087 348.4485 649.5889 c 348.4485 649.6369 L 350.7854 649.6369 L 350.7854 649.6209 L 350.8495 649.4289 350.9135 649.3488 351.0255 649.2208 c 351.2496 648.9006 L 357.108 641.5057 L 357.108 647.5721 L 357.108 648.4685 357.124 649.1087 356.2757 649.5889 c 356.2757 649.6369 L 359.0928 649.6369 L 359.0928 649.5889 L 358.2605 649.1087 358.2605 648.4685 358.2605 647.5721 c 358.2605 638.5925 L 357.124 638.9766 356.6278 639.5048 355.9235 640.4172 c 350.4333 647.38 L 350.4333 641.1855 l f 362.9612 643.0583 m 362.1289 640.8014 L 361.7928 639.905 361.6807 639.4408 362.449 639.1527 c 362.449 639.1047 L 359.5038 639.1047 L 359.5038 639.1527 L 360.4322 639.6169 360.7043 640.5133 361.0565 641.4256 c 363.7295 648.1003 L 363.9536 648.6766 364.2578 649.3488 363.4895 649.5889 c 363.4895 649.6369 L 366.0185 649.6369 L 369.3478 641.4256 L 369.716 640.5133 370.0041 639.6169 370.9165 639.1527 c 370.9165 639.1047 L 367.6351 639.1047 L 367.6351 639.1527 L 368.4194 639.5048 368.2914 639.6809 367.8592 640.8014 c 366.9949 643.0583 L 362.9612 643.0583 l f 1 g 366.5307 644.2428 m 363.3774 644.2428 L 364.962 648.2764 l 366.5307 644.2428 L f U %%%PageTrailer gsave annotatepage grestore %% showpage %%%Trailer Adobe_IllustratorA_AI3 /terminate get exec Adobe_customcolor /terminate get exec Adobe_cshow /terminate get exec Adobe_cmykcolor /terminate get exec Adobe_packedarray /terminate get exec %%%EOF PE 3 f 14 s 1740 1344(GLIM)N 2051(PSE:)X 2321(A)X 2430(Tool)X 2675(to)X 2797(Search)X 1758 1536(Through)N 2208(Entire)X 2541(File)X 2749(Systems)X 1 f 12 s 1965 1920(Udi)N 2133(Manber)X 2456(and)X 2619(Sun)X 2792(Wu)X 2262 2208(TR)N 2409(93-34)X 2185 2496(October)N 2519(1993)X 1 p %%Page: 1 2 12 s 12 xH 0 xS 1 f 10 s 3 f 1 f 2664 792(To)N 2773(appear)X 3008(in)X 3090(the)X 2664 912(1994)N 2844(Winter)X 3087(USENIX)X 3401(Technical)X 3738(Conference)X 3 f 12 s 1278 1176(GLIMPSE:)N 1777(A)X 1870(Tool)X 2081(to)X 2185(Search)X 2492(Through)X 2878(Entire)X 3164(File)X 3344(Systems)X 1 f 10 s 2245 1560(Udi)N 2385(Manber)X 8 s 2635 1520(1)N 10 s 1938 1800(Department)N 2337(of)X 2424(Computer)X 2764(Science)X 2124 1920(University)N 2482(of)X 2569(Arizona)X 2175 2040(Tucson,)N 2451(AZ)X 2578(85721)X 2158 2160(udi@cs.arizona.edu)N 2326 2400(Sun)N 2470(Wu)X 1938 2640(Department)N 2337(of)X 2424(Computer)X 2764(Science)X 1925 2760(National)N 2221(Chung-Cheng)X 2690(University)X 1975 2880(Ming-Shong,)N 2419(Chia-Yi,)X 2737(Taiwan)X 2177 3000(sw@cs.ccu.edu.tw)N 3 f 2259 3360(ABSTRACT)N 1 f 648 3600(GLIMPSE,)N 1030(which)X 1246(stands)X 1466(for)X 1580(GLobal)X 1845(IMPlicit)X 2131(SEarch,)X 2403(provides)X 2699(indexing)X 2999(and)X 3135(query)X 3338(schemes)X 3630(for)X 3744(\256le)X 3866(systems.)X 4180(The)X 648 3720(novelty)N 917(of)X 2 f 1013(glimpse)X 1 f 1291(is)X 1373(that)X 1522(it)X 1595(uses)X 1762(a)X 1827(very)X 1999(small)X 2201(index)X 2408(\320)X 2517(in)X 2608(most)X 2791(cases)X 2989(2-4%)X 3191(of)X 3286(the)X 3412(size)X 3565(of)X 3660(the)X 3786(text)X 3934(\320)X 4042(and)X 4186(still)X 648 3840(allows)N 883(very)X 1053(\257exible)X 1320(full-text)X 1605(retrieval)X 1900(including)X 2229(Boolean)X 2523(queries,)X 2802(approximate)X 3230(matching)X 3555(\(i.e.,)X 3727(allowing)X 4034(misspel-)X 648 3960(ling\),)N 843(and)X 983(even)X 1159(searching)X 1491(for)X 1609(regular)X 1861(expressions.)X 2299(In)X 2389(a)X 2448(sense,)X 2 f 2665(glimpse)X 1 f 2937(extends)X 2 f 3205(agrep)X 1 f 3415(to)X 3500(entire)X 3706(\256le)X 3831(systems,)X 4127(while)X 648 4080(preserving)N 1011(most)X 1190(of)X 1281(its)X 1380(functionality)X 1813(and)X 1953(simplicity.)X 2336(Query)X 2561(times)X 2758(are)X 2881(typically)X 3185(slower)X 3423(than)X 3585(with)X 3752(inverted)X 4040(indexes,)X 648 4200(but)N 778(they)X 944(are)X 1071(still)X 1218(fast)X 1362(enough)X 1626(for)X 1748(many)X 1954(applications.)X 2388(For)X 2526(example,)X 2845(it)X 2916(took)X 3085(5)X 3152(seconds)X 3433(of)X 3527(CPU)X 3709(time)X 3878(to)X 3967(\256nd)X 4118(all)X 4225(19)X 648 4320 0.3125(occurrences)AN 1061(of)X 1156(Usenix)X 1411(AND)X 1613(Winter)X 1864(in)X 1955(a)X 2020(\256le)X 2151(system)X 2402(containing)X 2769(69MB)X 3002(of)X 3098(text)X 3247(spanning)X 3565(4300)X 3754(\256les.)X 2 f 3956(Glimpse)X 1 f 4252(is)X 648 4440(particularly)N 1048(designed)X 1363(for)X 1486(personal)X 1787(information,)X 2214(such)X 2390(as)X 2486(one's)X 2689(own)X 2856(\256le)X 2987(system.)X 3278(The)X 3432(main)X 3621(characteristic)X 4079(of)X 4175(per-)X 648 4560(sonal)N 840(information)X 1241(is)X 1317(that)X 1460(it)X 1527(is)X 1603(non-uniform)X 2032(and)X 2172(includes)X 2463(many)X 2665(types)X 2858(of)X 2949(documents.)X 3360(An)X 3482(information)X 3884(retrieval)X 4176(sys-)X 648 4680(tem)N 794(for)X 914(personal)X 1212(information)X 1616(should)X 1855(support)X 2121(many)X 2325(types)X 2520(of)X 2613(queries,)X 2891(\257exible)X 3157(interaction,)X 3545(low)X 3690(overhead,)X 4030(and)X 4171(cus-)X 648 4800(tomization,)N 1030(All)X 1152(these)X 1337(are)X 1456(important)X 1787(features)X 2062(of)X 2 f 2149(glimpse)X 1 f 2398(.)X 8 s 10 f 648 5012(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)N 5 s 1 f 648 5114(1)N 8 s 692 5139(Supported)N 979(in)X 1054(part)X 1178(by)X 1267(an)X 1352(NSF)X 1495(Presidential)X 1822(Young)X 2021(Investigator)X 2351(Award)X 2549(\(grant)X 2726(DCR-8451397\),)X 3165(with)X 3304(matching)X 3567(funds)X 3734(from)X 3883(AT&T,)X 4098(by)X 4187(NSF)X 648 5235(grants)N 824(CCR-9002351)X 1218(and)X 1330(CCR-9301129,)X 1740(and)X 1852(by)X 1936(the)X 2034(Advanced)X 2312(Research)X 2565(Projects)X 2791(Agency)X 3009(under)X 3174(contract)X 3399(number)X 3614(DABT63-93-C-0052.)X 4202(Part)X 648 5331(of)N 717(this)X 826(work)X 973(was)X 1088(done)X 1228(while)X 1386(the)X 1480(author)X 1659(was)X 1774(visiting)X 1983(the)X 2077(University)X 2363(of)X 2432(Washington.)X 648 5523(The)N 763(information)X 1081(contained)X 1346(in)X 1413(this)X 1523(paper)X 1681(does)X 1815(not)X 1914(necessarily)X 2214(re\257ect)X 2390(the)X 2485(position)X 2709(or)X 2779(the)X 2874(policy)X 3051(of)X 3121(the)X 3216(U.S.)X 3347(Government)X 3683(or)X 3753(other)X 3901(sponsors)X 4142(of)X 4212(this)X 648 5619(research.)N 907(No)X 1001(of\256cial)X 1198(endorsement)X 1540(should)X 1727(be)X 1803(inferred.)X 2 p %%Page: 2 3 8 s 8 xH 0 xS 1 f 10 s 3 f 2456 408(2)N 6 f 14 s 648 696(1.)N 803(Introduction)X 1 f 10 s 648 849(With)N 836(the)X 962(explosion)X 1301(of)X 1396(available)X 1714(information,)X 2140(especially)X 2489(through)X 2767(networks,)X 3110(organizing)X 3482(even)X 3663(one's)X 3866(own)X 4033(personal)X 648 969(\256le)N 773(system)X 1018(is)X 1094(becoming)X 1433(dif\256cult.)X 1749(It)X 1821(is)X 1897(hard,)X 2083(even)X 2258(with)X 2423(a)X 2482(good)X 2664(organization,)X 3107(to)X 3191(remember)X 3539(things)X 3756(from)X 3934(a)X 3992(few)X 4135(years)X 648 1089(back.)N 862(\(Now)X 1067(where)X 1286(did)X 1410(I)X 1459(put)X 1583(the)X 1703(notes)X 1894(on)X 1996(that)X 2138(interesting)X 2499(colloquium)X 2886(two)X 3029(years)X 3222(ago?\))X 3444(After)X 3637(a)X 3696(while,)X 3917(not)X 4042(only)X 4207(the)X 648 1209(content)N 905(of)X 993(a)X 1050(piece)X 1241(of)X 1329(information)X 1728(can)X 1861(be)X 1958(forgotten,)X 2293(but)X 2416(also)X 2566(the)X 2 f 2685(existence)X 1 f 3001(of)X 3089(that)X 3230(information.)X 3669(There)X 3877(are)X 3996(two)X 4136(types)X 648 1329(of)N 743(tools)X 926(to)X 1016(search)X 1250(for)X 1373(patterns:)X 1678(grep-like)X 1997(tools,)X 2201(which)X 2426(are)X 2554(fast)X 2699(only)X 2870(if)X 2948(the)X 3075(search)X 3310(is)X 3392(limited)X 3647(to)X 3738(a)X 3803(small)X 4005(area,)X 4189(and)X 648 1449(index-based)N 1062(tools,)X 1263(which)X 1485(typically)X 1791(require)X 2045(a)X 2107(large)X 2294(index)X 2498(that)X 2644(needs)X 2853(to)X 2941(be)X 3043(computed)X 3385(ahead)X 3599(of)X 3692(time.)X 2 f 3899(Glimpse)X 1 f 4191(is)X 4269(a)X 648 1569(combination)N 1068(of)X 1155(the)X 1273(two)X 1414(approaches.)X 1837(It)X 1907(is)X 1981(index-based,)X 2410(but)X 2533(it)X 2598(uses)X 2757(a)X 2814(very)X 2978(small)X 3172(index;)X 3393(it)X 3458(assumes)X 3746(no)X 3847(structure)X 4149(from)X 648 1689(the)N 766(data;)X 942(and)X 1078(it)X 1142(allows)X 1371(very)X 1534(\257exible)X 1794(queries)X 2046(including)X 2368(approximate)X 2789(matching.)X 848 1842(The)N 999(most)X 1180(common)X 1486(data)X 1646(structure)X 1954(used)X 2128(in)X 2217(information)X 2622(retrieval)X 2917(\(IR\))X 3078(systems)X 3358(is)X 3438(an)X 3541(inverted)X 3831(index)X 4036([SM83].)X 648 1962(All)N 772 0.3125(occurrences)AX 1179(of)X 1268(each)X 1438(word)X 1625(are)X 1746(stored)X 1964(in)X 2048(a)X 2106(table)X 2284(indexed)X 2560(by)X 2662(that)X 2804(word)X 2991(using)X 3185(a)X 3242(hash)X 3410(table)X 3587(or)X 3675(a)X 3732(tree)X 3874(structure.)X 4216(To)X 648 2082(reduce)N 883(the)X 1002(size)X 1148(of)X 1236(the)X 1355(table,)X 1552(common)X 1853(words)X 2070(\(e.g.,)X 2 f 2254(the)X 1 f 2373(or)X 2 f 2461(that)X 1 f 2606(in)X 2689(English\))X 2981(are)X 3101(sometimes)X 3464(not)X 3587(indexed)X 3862(\(although)X 4190(this)X 648 2202(cannot)N 892(be)X 997(done)X 1182(when)X 1385(the)X 1512(text)X 1661(is)X 1743(multi-lingual\).)X 2256(Inverted)X 2553(indexes)X 2827(allow)X 3034(very)X 3206(fast)X 3351(queries:)X 3654(There)X 3871(is)X 3953(no)X 4062(need)X 4243(to)X 648 2322(search)N 875(in)X 958(any)X 1095(of)X 1183(the)X 1302(texts,)X 1494(only)X 1657(the)X 1776(table)X 1953(needs)X 2157(to)X 2240(be)X 2337(consulted)X 2665(and)X 2802(the)X 2921(places)X 3143(where)X 3361(the)X 3480(word)X 3666(occurs)X 3898(are)X 4019(retrieved)X 648 2442(immediately.)N 1108(Boolean)X 1395(queries)X 1647(are)X 1766(slower,)X 2020(but)X 2142(are)X 2261(still)X 2400(relatively)X 2723(fast.)X 848 2595(The)N 993(main)X 1173(drawback)X 1506(of)X 1593(inverted)X 1876(indexes)X 2141(for)X 2255(personal)X 2547(\256le)X 2669(systems)X 2942(is)X 3015(their)X 3182(space)X 3381(requirement.)X 3829(The)X 3974(size)X 4119(of)X 4207(the)X 648 2715(index)N 852(is)X 931(typically)X 1237(50%-300%)X 1624(of)X 1717(the)X 1841(size)X 1992(of)X 2085(the)X 2209(text)X 2355([Fa85].)X 2635(This)X 2803(may)X 2967(not)X 3095(be)X 3196(a)X 3257(major)X 3469(drawback)X 3807(for)X 3926(commercial)X 648 2835(text)N 791(databases,)X 1142(because)X 1420(disk)X 1576(space)X 1778(is)X 1854(relatively)X 2180(cheap,)X 2411(but)X 2536(it)X 2603(is)X 2679(a)X 2738(major)X 2948(drawback)X 3285(for)X 3403(personal)X 3699(information.)X 4141(Most)X 648 2955(users)N 838(would)X 1063(not)X 1190(agree)X 1390(to)X 1477(double)X 1720(their)X 1892(disk)X 2050(cost)X 2204(for)X 2323(the)X 2446(bene\256t)X 2689(of)X 2781(indexing.)X 3126(Indeed)X 3370(today)X 3573(most)X 3753(personal)X 4050(\256le)X 4176(sys-)X 648 3075(tems)N 826(are)X 952(not)X 1081(indexed.)X 1402(But,)X 1564(due)X 1707(to)X 1796(an)X 1899(increased)X 2230(availability)X 2617(of)X 2712(digital)X 2944(information)X 3350(through)X 3627(networks,)X 3969(many)X 4175(per-)X 648 3195(sonal)N 839(\256le)X 963(systems)X 1238(are)X 1359(large)X 1542(enough)X 1800(to)X 1884(require)X 2134(IR)X 2236(capabilities.)X 2663(Signatures)X 3022(\256les)X 3176([Fa85,)X 3404(GB91])X 3643(have)X 3816(been)X 3989(suggested)X 648 3315(as)N 741(an)X 843(alternative)X 1208(to)X 1296(inverted)X 1585(indexes)X 1856(with)X 2024(good)X 2210(results.)X 2465(Their)X 2665(indexes)X 2936(are)X 3061(only)X 3229(10%-30%)X 3576(of)X 3669(the)X 3793(text)X 3939(size.)X 4131(Their)X 648 3435(search)N 880(time)X 1048(is)X 1127(slower)X 1366(than)X 1529(with)X 1696(inverted)X 1984(indexes,)X 2274(and)X 2415(since)X 2605(they)X 2768(are)X 2892(based)X 3100(on)X 3205(hashing,)X 3499(their)X 3671(parameters)X 4049(must)X 4229(be)X 648 3555(chosen)N 891(carefully)X 1197(\(especially)X 1565(for)X 1679(many)X 1877(\256les)X 2030(of)X 2117(different)X 2414(sizes\))X 2617(to)X 2699(minimize)X 3021(the)X 3139(false)X 3311(drops)X 3509(probability.)X 848 3708(The)N 998(second)X 1246(weakness)X 1580(of)X 1673(inverted)X 1962(indexes)X 2233(is)X 2312(the)X 2436(need)X 2614(for)X 2734(exact)X 2930(spelling)X 3209(\(due)X 3378(to)X 3466(the)X 3590(use)X 3723(of)X 3816(hashing)X 4091(or)X 4184(tree)X 648 3828(structures)N 1007(to)X 1116(search)X 1369(for)X 1510(keywords)X 1869(in)X 1978(the)X 2123(index)X 2348(ef\256ciently\).)X 2767(If)X 2868(one)X 3031(is)X 3131(looking)X 3422(for)X 3563(all)X 3689(articles)X 3967(containing)X 648 3948(Schwarzkopf)N 1095(for)X 1212(example,)X 1527(any)X 1666(article)X 1890(with)X 2055(a)X 2114(misspelling)X 2505(will)X 2652(be)X 2751(missed)X 2996(\(not)X 3148(to)X 3233(mention)X 3518(that)X 3661(the)X 3782(exact)X 3975(spelling)X 4252(is)X 648 4068(needed)N 907(to)X 1000(form)X 1187(the)X 1316(query\).)X 1596(The)X 1751(typical)X 1999(way)X 2163(to)X 2255(\256nd)X 2409(misspelled)X 2781(words)X 3007(is)X 3090(to)X 3182(try)X 3301(different)X 3608(possibilities)X 4019(by)X 4129(hand,)X 648 4188(which)N 867(is)X 944(frustrating,)X 1322(time)X 1488(consuming,)X 1883(and)X 2023(is)X 2100(not)X 2226(guaranteed)X 2603(to)X 2689(succeed.)X 3008(In)X 3099(some)X 3292(cases,)X 3506(especially)X 3851(in)X 3937(large)X 4122(infor-)X 648 4308(mation)N 895(bases,)X 1114(searching)X 1447(provides)X 1748(the)X 1871(only)X 2038(way)X 2197(to)X 2284(access)X 2515(information.)X 2958(A)X 3041(misspelling)X 3434(can)X 3571(cause)X 3775(a)X 3836(piece)X 4031(of)X 4122(infor-)X 648 4428(mation)N 891(to)X 974(be)X 1071(virtually)X 1363(lost.)X 1539(This)X 1702(is)X 1776(the)X 1895(digital)X 2120(equivalence)X 2525(of)X 2613(dropping)X 2923(a)X 2980(folder)X 3193(behind)X 3432(the)X 3551(\256le)X 3674(cabinet)X 3927(\(except)X 4185(that)X 648 4548(there)N 839(is)X 922(no)X 1032(limit)X 1212(to)X 1304(the)X 1432(room)X 1631(behind)X 1879(this)X 2024(`\256le)X 2182(cabinet,')X 2490(and)X 2635(hardly)X 2869(anyone)X 3130(ever)X 3298(cleans)X 3528(there\).)X 3785(This)X 3956(problem)X 4252(is)X 648 4668(expected)N 954(to)X 1036(become)X 1306(more)X 1491(acute)X 1681(as)X 1768(more)X 1953(information)X 2351(is)X 2424(scanned)X 2703(by)X 2803(OCR)X 2987(\(Optical)X 3271(Character)X 3605(Recognition\))X 4044(devices,)X 648 4788(which)N 864(currently)X 1174(have)X 1346(an)X 1442(error)X 1619(rate)X 1760(of)X 1847(1-5%)X 2041([BN91,)X 2299(RKN92].)X 2 f 848 4941(Glimpse)N 1 f 1147(requires)X 1438(a)X 1506(very)X 1682(small)X 1888(index,)X 2119(in)X 2214(most)X 2402(cases)X 2605(2-4%)X 2812(of)X 2912(the)X 3043(original)X 3325(text,)X 3498(and)X 3647(it)X 3724(supports)X 4028(arbitrary)X 648 5061(approximate)N 1072(matching.)X 1432(As)X 1543(we)X 1659(will)X 1805(describe)X 2095(in)X 2179(detail)X 2379(in)X 2463(the)X 2583(next)X 2743(section,)X 3012(glimpse's)X 3345(engine)X 3581(is)X 2 f 3656(agrep)X 1 f 3843(,)X 3885(a)X 3943(search)X 4171(pro-)X 648 5181(gram)N 843(that)X 993(we)X 1117(developed)X 1477([WM92a,)X 1817(WM92b],)X 2161(which)X 2387(allows)X 2626(the)X 2754(user)X 2918(to)X 3010(specify)X 3272(the)X 3400(number)X 3676(of)X 3774(allowable)X 4117(errors)X 648 5301(\(insertions,)N 1029(deletions,)X 1361(substitutions,)X 1806(or)X 1895(any)X 2033(combination\).)X 2522(The)X 2669(user)X 2825(can)X 2959(also)X 3110(search)X 3338(for)X 3454(the)X 3574(best)X 3725(match,)X 3963(which)X 4181(will)X 648 5421(automatically)N 1114(\256nd)X 1268(all)X 1378(matches)X 1671(with)X 1843(the)X 1971(minimum)X 2311(number)X 2586(of)X 2683(errors.)X 2941(Because)X 3239(we)X 3364(use)X 3502(a)X 3569(small)X 3773(index,)X 4002(our)X 4140(algo-)X 648 5541(rithms)N 876(are)X 999(usually)X 1254(slower)X 1492(than)X 1654(ones)X 1825(using)X 2022(inverted)X 2309(indexes,)X 2598(but)X 2724(their)X 2895(speed)X 3102(is)X 3179(still)X 3321(on)X 3424(the)X 3545(order)X 3738(of)X 3828(a)X 3887(few)X 4031(seconds,)X 648 5661(which)N 864(is)X 937(fast)X 1073(enough)X 1329(for)X 1443(single)X 1654(users.)X 3 p %%Page: 3 4 10 s 10 xH 0 xS 1 f 3 f 2456 408(3)N 1 f 848 696(In)N 937(some)X 1128(sense,)X 2 f 1344(glimpse)X 1 f 1616(takes)X 1804(the)X 1925(opposite)X 2219(extreme)X 2501(to)X 2586(inverted)X 2872(\256les)X 3028(in)X 3113(the)X 3234(time)X 3399(vs.)X 3513(space)X 3715(tradeoff)X 3993(\(with)X 4185(sig-)X 648 816(nature)N 872(\256les)X 1028(being)X 1228(in)X 1312(the)X 1432(middle\).)X 1743(For)X 1876(some)X 2067(applications,)X 2496(such)X 2665(as)X 2754(management)X 3186(of)X 3275(personal)X 3569(information,)X 3989(speed)X 4194(is)X 4269(a)X 648 936(secondary)N 999(issue.)X 1224(Most)X 1413(users)X 1603(would)X 1828(rather)X 2041(wait)X 2204(for)X 2324(10-15)X 2537(seconds,)X 2837(or)X 2930(even)X 3108(longer,)X 3359(for)X 3479(a)X 3541(query)X 3750(than)X 3914(double)X 4158(their)X 648 1056(disk)N 808(space.)X 1054(Even)X 1246(for)X 1367(IR)X 1474(systems,)X 1774(such)X 1948(as)X 2042(library)X 2283(card)X 2449(catalogs,)X 2759(where)X 2983(high)X 3152(throughput)X 3530(is)X 3609(essential,)X 3931(our)X 4064(scheme)X 648 1176(can)N 782(be)X 880(used)X 1049(as)X 1138(a)X 1196(secondary)X 1544(mechanism)X 1931(to)X 2015(catch)X 2207(spelling)X 2482(errors.)X 2732(For)X 2865(example,)X 3179(we)X 3295(found)X 3505(several)X 3756(spelling)X 4032(errors)X 4243(in)X 648 1296(a)N 707(library)X 943(catalog)X 1197(\(see)X 1349(Section)X 1611(4\).)X 1740(We)X 1874(believe)X 2128(that)X 2270(this)X 2407(capability)X 2745(is)X 2820(essential)X 3118(in)X 3202(all)X 3304(applications)X 3713(that)X 3855(require)X 4105(a)X 4163(high)X 648 1416(level)N 824(of)X 911(reliability;)X 1264(for)X 1378(example,)X 1690(medical)X 1964(labs)X 2113(could)X 2311(miss)X 2477(information)X 2875(on)X 2975(patients)X 3244(due)X 3380(to)X 3462(misspelling.)X 848 1569(We)N 981(call)X 1118(our)X 1246(method)X 2 f 1507(two-level)X 1822(searching)X 1 f 2138(.)X 2200(The)X 2347(idea)X 2503(is)X 2578(a)X 2636(hybrid)X 2867(between)X 3157(full)X 3290(inverted)X 3575(indexes)X 3842(and)X 3980(sequential)X 648 1689(search)N 887(with)X 1062(no)X 1175(indexing.)X 1528(It)X 1610(is)X 1696(based)X 1912(on)X 2025(the)X 2155(observation)X 2561(that)X 2713(with)X 2887(current)X 3147(computing)X 3521(performance,)X 3980(sequential)X 648 1809(search)N 880(is)X 960(fast)X 1103(enough)X 1366(for)X 1487(text)X 1634(of)X 1728(size)X 1880(up)X 1987(to)X 2076(several)X 2331(megabytes.)X 2721(Therefore,)X 3086(there)X 3274(is)X 3354(no)X 3461(need)X 3640(to)X 3729(index)X 3934(every)X 4140(word)X 648 1929(with)N 815(an)X 916(exact)X 1111(location.)X 1434(In)X 1526(the)X 1649(two-level)X 1977(scheme)X 2243(the)X 2366(index)X 2569(does)X 2741(not)X 2868(provide)X 3138(exact)X 3333(locations,)X 3667(but)X 3794(only)X 3961(pointers)X 4243(to)X 648 2049(an)N 748(area)X 907(where)X 1128(the)X 1250(answer)X 1502(may)X 1664(be)X 1764(found.)X 2015(Then,)X 2225(a)X 2286(\257exible)X 2551(sequential)X 2901(search)X 3132(is)X 3210(used)X 3382(to)X 3469(\256nd)X 3618(the)X 3741(exact)X 3936(answer)X 4189(and)X 648 2169(present)N 903(it)X 970(to)X 1055(the)X 1176(user.)X 1373(\(Some)X 1605(other)X 1793(IR)X 1896(systems,)X 2192(such)X 2362(as)X 2452(MEDLARS)X 2857([SM83])X 3129(and)X 3268(STATUS)X 3593([Te82],)X 3855(allow)X 4055(sequen-)X 648 2289(tial)N 785(search)X 1026(as)X 1128(a)X 1199(postprocessing)X 1710(step)X 1874(to)X 1972(further)X 2227(\256lter)X 2414(the)X 2548(output)X 2788(of)X 2891(a)X 2963(query,)X 3202(but)X 3340(the)X 3474(search)X 3716(relies)X 3926(on)X 4042(inverted)X 648 2409(indexes.\))N 981(The)X 1127(idea)X 1282(of)X 1370(two-level)X 1694(searching)X 2023(is)X 2097(quite)X 2278(natural,)X 2542(and,)X 2699(although)X 3000(we)X 3115(have)X 3287(not)X 3409(found)X 3616 0.3889(references)AX 3968(to)X 4050(it,)X 4134(it)X 4198(has)X 648 2529(most)N 826(probably)X 1134(been)X 1309(used)X 1479(before.)X 1748(The)X 1896(use)X 2026(of)X 2 f 2116(agrep)X 1 f 2326(for)X 2443(both)X 2608(levels)X 2818(\320)X 2921(searching)X 3252(the)X 3373(index)X 3574(and)X 3713(then)X 3875(searching)X 4207(the)X 648 2649(actual)N 864(\256les)X 1021(\320)X 1125(provides)X 1425(great)X 1610(\257exibility,)X 1964(in)X 2050(particular)X 2382(it)X 2450(allows)X 2683(approximate)X 3108(matching)X 3430(and)X 3570(regular)X 3821(expressions,)X 4238(as)X 648 2769(we)N 762(will)X 906(discuss)X 1157(later.)X 848 2922(We)N 980(have)X 1152(been)X 1324(using)X 2 f 1517(glimpse)X 1 f 1786(for)X 1900(several)X 2148(months)X 2403(and)X 2539(we)X 2653(are)X 2772(\256nding)X 3018(it)X 3082(indispensable.)X 3578(It)X 3647(is)X 3720(so)X 3812(convenient)X 4185(that)X 648 3042(we)N 764(use)X 893(it)X 959(many)X 1159(times)X 1354(even)X 1528(when)X 1724(we)X 1840(know)X 2040(where)X 2259(the)X 2379(information)X 2779(is)X 2854(and)X 2992(can)X 3126(use)X 2 f 3255(agrep)X 1 f 3464(directly:)X 3753(It)X 3824(is)X 3898(just)X 4034(easier)X 4243(to)X 648 3162(quickly)N 920(browse)X 1184(through)X 1465(the)X 1595(output)X 1831(than)X 2001(to)X 7 f 2123(cd)X 1 f 2251(to)X 2345(the)X 2475(right)X 2659(directory,)X 7 f 3030(ls)X 1 f 3159(to)X 3254(\256nd)X 3411(the)X 3542(exact)X 3745(name)X 3952(of)X 4052(the)X 4183(\256le,)X 7 f 648 3282(agrep)N 1 f 910(it,)X 996(and)X 7 f 1162(cd)X 1 f 1280(back.)X 1494(We)X 1628(found)X 1836(ideas)X 2022(that)X 2163(we)X 2278(wrote)X 2482(many)X 2681(years)X 2872(ago,)X 3029(and)X 3166(not)X 3289(only)X 3452(forgot)X 3669(where)X 3887(we)X 4002(put)X 4125(them,)X 648 3402(but)N 773(forgot)X 992(about)X 1193(writing)X 1447(them)X 1630(in)X 1715(the)X 1836(\256rst)X 1983(place.)X 2216(We)X 2351(found)X 2561(that)X 2705(we)X 2823(sometimes)X 3189(save)X 3356(information)X 3758(that)X 3902(we)X 4020(probably)X 648 3522(would)N 882(have)X 1068(discarded)X 1410(without)X 2 f 1688(glimpse)X 1 f 1937(,)X 1991(because)X 2280(we)X 2408(now)X 2580(have)X 2766(some)X 2969(con\256dence)X 3351(of)X 3452(ever)X 3624(\256nding)X 3883(it)X 3960(again.)X 4207(An)X 648 3642(interesting)N 1017(example,)X 1340(conveyed)X 1679(to)X 1772(us)X 1874(by)X 1985(someone)X 2301(who)X 2470(tested)X 2688(a)X 2755(beta)X 2920(version)X 3187(of)X 2 f 3285(glimpse)X 1 f 3534(,)X 3585(was)X 3742(to)X 3836(\256nd)X 3992(an)X 4100(e-mail)X 648 3762(address)N 920(of)X 1018(a)X 1085(friend)X 1308(who)X 1477(moved)X 1726(recently;)X 2 f 2038(glimpse)X 1 f 2318(found)X 2536(it)X 2611(not)X 2744(in)X 2837(any)X 2983(mail)X 3155(messages,)X 3508(but)X 3640(in)X 3732(a)X 3798(call)X 3944(for)X 4068(papers!)X 2 f 648 3882(Glimpse)N 1 f 935(can)X 1067(sometimes)X 1429(truly)X 1600(\256nd)X 1744(a)X 1800(needle)X 2030(in)X 2112(a)X 2168(haystack.)X 6 f 14 s 648 4154(2.)N 803(The)X 1032(Two-Level)X 1609(Query)X 1963(Approach)X 1 f 10 s 648 4307(In)N 737(this)X 874(section,)X 1143(we)X 1259(describe)X 1549(our)X 1678(scheme)X 1941(for)X 2057(two-level)X 2382(indexing)X 2684(and)X 2822(searching.)X 3192(We)X 3326(start)X 3487(with)X 3652(the)X 3773(way)X 3930(the)X 4051(index)X 4252(is)X 648 4427(built.)N 848 4580(The)N 993(information)X 1391(space)X 1590(is)X 1663(assumed)X 1959(to)X 2041(be)X 2137(a)X 2193(collection)X 2529(of)X 2616(unstructured)X 3037(text)X 3177(\256les.)X 3371(A)X 3450(text)X 3591(consists)X 3865(of)X 3953(a)X 4010(sequence)X 648 4700(of)N 2 f 739(words)X 1 f 934(,)X 978(separated)X 1305(by)X 1408(the)X 1529(usual)X 1721(delimiters)X 2064(\(e.g.,)X 2250(space,)X 2472(end-of-line,)X 2872(period,)X 3120(comma\).)X 3446(The)X 3594(\256rst)X 3741(part)X 3889(of)X 3979(the)X 4100(index-)X 648 4820(ing)N 770(process)X 1031(is)X 1104(to)X 1186(divide)X 1406(the)X 1524(whole)X 1740(collection)X 2076(into)X 2220(smaller)X 2476(pieces,)X 2717(which)X 2934(we)X 3049(call)X 2 f 3186(blocks)X 1 f 3391(.)X 3452(We)X 3585(try)X 3695(to)X 3778(divide)X 3999(evenly)X 4234(so)X 648 4940(that)N 792(all)X 896(blocks)X 1129(have)X 1305(approximately)X 1792(the)X 1914(same)X 2103(size,)X 2272(but)X 2398(this)X 2537(is)X 2614(not)X 2740(essential.)X 3080(The)X 3229(only)X 3395(constraint)X 3735(we)X 3853(impose)X 4108(is)X 4185(that)X 648 5060(the)N 770(number)X 1039(of)X 1130(blocks)X 1363(does)X 1534(not)X 1660(exceed)X 1908(2)X 7 s 5028(8)Y 2 f 10 s 9 f 1995 5060(=)N 1 f 2052(256,)X 2216(because)X 2495(that)X 2639(allows)X 2872(us)X 2967(to)X 3053(address)X 3318(a)X 3378(block)X 3580(with)X 3747(8)X 3812(bits)X 3952(\(one)X 4120(byte\).)X 648 5180(This)N 810(is)X 883(not)X 1005(essential,)X 1321(but)X 1443(it)X 1507(appears)X 1773(to)X 1855(be)X 1951(a)X 2007(good)X 2187(design)X 2416(decision.)X 848 5333(We)N 992(scan)X 1167(the)X 1297(whole)X 1526(collection,)X 1895(word)X 2093(by)X 2206(word,)X 2424(and)X 2573(build)X 2770(an)X 2879(index)X 3090(that)X 3243(is)X 3329(similar)X 3584(in)X 3679(nature)X 3913(to)X 4008(a)X 4077(regular)X 648 5453(inverted)N 948(index)X 1163(with)X 1342(one)X 1495(notable)X 1768(exception.)X 2156(In)X 2259(a)X 2331(regular)X 2595(inverted)X 2894(index,)X 3128(every)X 3343 0.3611(occurrence)AX 3733(of)X 3836(every)X 4051(word)X 4252(is)X 648 5573(indexed)N 931(with)X 1102(a)X 1167(pointer)X 1423(to)X 1514(the)X 1641(exact)X 1840(location)X 2127(of)X 2223(the)X 2351 0.3250(occurrence.)AX 2775(In)X 2872(our)X 3009(scheme)X 3280(every)X 3489(word)X 3684(is)X 3767(indexed,)X 4071(but)X 4203(not)X 648 5693(every)N 856 0.3250(occurrence.)AX 1279(Each)X 1469(entry)X 1663(in)X 1754(the)X 1881(index)X 2088(contains)X 2383(a)X 2447(word)X 2640(and)X 2784(the)X 2910(block)X 3116(numbers)X 3420(in)X 3510(which)X 3734(that)X 3882(word)X 4075(occurs.)X 4 p %%Page: 4 5 10 s 10 xH 0 xS 1 f 3 f 2456 408(4)N 1 f 648 696(Even)N 842(if)X 920(a)X 985(word)X 1179(appears)X 1454(many)X 1661(times)X 1863(in)X 1954(one)X 2100(block,)X 2328(only)X 2500(the)X 2628(block)X 2836(number)X 3111(appears)X 3387(in)X 3479(the)X 3607(index)X 3815(and)X 3961(only)X 4133(once.)X 648 816(Since)N 853(each)X 1028(block)X 1233(can)X 1372(be)X 1474(identi\256ed)X 1802(with)X 1970(one)X 2112(byte,)X 2296(and)X 2438(many)X 2642 0.3125(occurrences)AX 3053(of)X 3146(the)X 3270(same)X 3461(word)X 3652(are)X 3777(combined)X 4119(in)X 4207(the)X 648 936(index)N 851(into)X 1000(one)X 1141(entry,)X 1351(the)X 1474(index)X 1677(is)X 1755(typically)X 2060(quite)X 2245(small.)X 2483(Full)X 2636(inverted)X 2924(indexes)X 3194(must)X 3374(allocate)X 3649(at)X 3732(least)X 3905(one)X 4047(word)X 4238(\(4)X 648 1056(bytes\),)N 890(and)X 1032(usually)X 1289(slightly)X 1554(more,)X 1765(for)X 1885(each)X 2058 0.3611(occurrence)AX 2437(of)X 2529(each)X 2702(word.)X 2932(Therefore,)X 3295(the)X 3418(size)X 3568(of)X 3660(an)X 3761(inverted)X 4049(index)X 4252(is)X 648 1176(comparable)N 1044(to)X 1127(the)X 1246(size)X 1392(of)X 1481(the)X 1601(text.)X 1783(But)X 1920(our)X 2049(index)X 2249(contains)X 2538(only)X 2702(the)X 2822(list)X 2941(of)X 3030(all)X 3132(unique)X 3372(words)X 3590(followed)X 3897(by)X 3999(the)X 4119(list)X 4238(of)X 648 1296(blocks)N 887(\320)X 997(one)X 1143(byte)X 1311(for)X 1435(each)X 1613(\320)X 1723(containing)X 2091(each)X 2269(word.)X 2504(For)X 2645(natural)X 2898(language)X 3218(texts,)X 3419(the)X 3546(total)X 3717(number)X 3991(of)X 4087(unique)X 648 1416(words)N 864(is)X 937(usually)X 1188(not)X 1310(too)X 1432(large,)X 1633(regardless)X 1979(of)X 2066(the)X 2184(size)X 2329(of)X 2416(the)X 2534(text.)X 848 1569(The)N 993(search)X 1219(routine)X 1466(consists)X 1739(of)X 1826(two)X 1966(phases.)X 2240(First)X 2406(we)X 2520(search)X 2746(the)X 2864(index)X 3062(for)X 3176(a)X 3232(list)X 3350(of)X 3438(all)X 3539(blocks)X 3769(that)X 3910(may)X 4069(contain)X 648 1689(a)N 710(match)X 932(to)X 1019(the)X 1142(query.)X 1390(Then,)X 1600(we)X 1719(search)X 1950(each)X 2123(such)X 2295(block)X 2498(separately.)X 2889(Even)X 3079(though)X 3326(the)X 3449(\256rst)X 3598(phase)X 3806(can)X 3943(be)X 4044(done)X 4225(by)X 648 1809(hashing)N 923(or)X 1016(B-trees,)X 1294(we)X 1414(prefer)X 1633(sequential)X 1984(search)X 2216(using)X 2 f 2415(agrep)X 1 f 2602(,)X 2648(because)X 2929(of)X 3022(its)X 3123(\257exibility.)X 3499(With)X 3685(hashing)X 3960(or)X 4053(B-trees,)X 648 1929(only)N 813(keywords)X 1148(that)X 1291(were)X 1471(selected)X 1753(to)X 1838(be)X 1937(included)X 2236(in)X 2320(the)X 2440(data)X 2596(structure)X 2899(can)X 3033(be)X 3131(used.)X 3320(With)X 3502(sequential)X 3849(search)X 4077(we)X 4193(can)X 648 2065(get)N 766(the)X 884(full)X 1015(power)X 1236(of)X 2 f 1323(agrep)X 1 f 1510(.)X 1570(Since)X 1768(the)X 1886(index)X 2084(is)X 2157(quite)X 2337(small,)X 2550(we)X 2664(can)X 2796(afford)X 3013(sequential)X 3358(search.)X 7 s 3584 2033(2)N 2 f 10 s 848 2218(Agrep)N 1 f 1069(is)X 1148(similar)X 1396(in)X 1484(use)X 1617(to)X 1705(other)X 1896(grep's,)X 2143(but)X 2271(it)X 2341(is)X 2420(much)X 2624(more)X 2815(general.)X 3118(It)X 3193(can)X 3331(search)X 3563(for)X 3683(patterns)X 3963(allowing)X 4269(a)X 648 2338(speci\256ed)N 956(number)X 1224(of)X 1314(errors)X 1525(which)X 1744(can)X 1879(be)X 1978(insertions,)X 2331(deletions,)X 2662(or)X 2751(substitutions)X 3176(\(or)X 3292(any)X 3430(combination\);)X 3901(it)X 3967(can)X 4101(output)X 648 2458(user-de\256ned)N 1068(records)X 1328(\(e.g.,)X 1515(paragraphs)X 1892(or)X 1983(mail)X 2149(messages\),)X 2523(rather)X 2735(than)X 2897(just)X 3036(lines;)X 3233(it)X 3301(supports)X 3596(Boolean)X 3887(queries,)X 4163(wild)X 648 2578(cards,)N 859(regular)X 1108(expressions,)X 1523(and)X 1660(many)X 1858(other)X 2043(options.)X 2338(Given)X 2554(a)X 2610(pattern,)X 2873(we)X 2987(\256rst)X 3131(use)X 2 f 3258(agrep)X 1 f 3465(to)X 3547(\256nd)X 3691(all)X 3791(the)X 3909(words)X 4125(in)X 4207(the)X 648 2698(index)N 849(that)X 992(match)X 1211(it.)X 1318(Then,)X 1526(using)X 2 f 1722(agrep)X 1 f 1932(again,)X 2149(we)X 2266(search)X 2496(the)X 2618(corresponding)X 3101(blocks)X 3334(to)X 3420(\256nd)X 3568(the)X 3690(particular)X 4022(matches.)X 648 2818(The)N 796(same)X 984(procedure)X 1329(holds)X 1524(for)X 1640(all)X 1742(types)X 1933(of)X 2022(complicated)X 2436(patterns)X 2712(such)X 2881(as)X 2970(ones)X 3139(that)X 3281(contain)X 3539(wildcards)X 3873(\(e.g.,)X 4058(U..nix\),)X 648 2938(a)N 709(set)X 823(of)X 915(characters)X 1267(\(e.g.)X 1435 0.1912(count[A-E]to[W-Z],)AX 2114(where)X 2336([A-E])X 2549(stands)X 2774(for)X 2893(A,)X 2996(B,)X 3094(C,)X 3192(D,)X 3295(or)X 3387(E\),)X 3508(or)X 3600(even)X 3778(a)X 3840(negation)X 4142(\(e.g.,)X 648 3058(U[\303l]..ix,)N 960(where)X 1185([\303l])X 1316(stands)X 1544(for)X 1666(any)X 1810(character)X 2134(except)X 2372(for)X 2494(l\).)X 2611(These)X 2831(kinds)X 3032(of)X 3127(patterns)X 3409(cannot)X 3651(be)X 3755(supported)X 4099(by)X 4207(the)X 648 3178(regular)N 896(hashing)X 1165(scheme)X 1426(that)X 1566(looks)X 1759(up)X 1859(a)X 1915(keyword)X 2216(in)X 2298(the)X 2416(table,)X 2612(because)X 2887(such)X 3054(patterns)X 3329(can)X 3462(correspond)X 3840(to)X 3923(hundreds)X 4238(or)X 648 3298(even)N 820(thousands)X 1160(of)X 1247(possible)X 1529(keywords.)X 848 3451(Boolean)N 1143(queries)X 1403(are)X 1530(performed)X 1893(in)X 1983(a)X 2047(similar)X 2297(way)X 2459(to)X 2549(the)X 2675(regular)X 2931(inverted)X 3222(lists)X 3378(algorithm.)X 3758(Suppose)X 4058(that)X 4207(the)X 648 3571(query)N 860(is)X 942(for)X 2 f 1065(pattern1)X 1 f 1364(AND)X 2 f 1566(pattern2)X 1 f 1837(.)X 1905(We)X 2045(\256nd)X 2197(the)X 2323(list)X 2448(of)X 2543(all)X 2651(blocks)X 2888(containing)X 3254(each)X 3430(pattern)X 3681(and)X 3825(intersect)X 4125(them.)X 648 3691(Then)N 837(we)X 955(search)X 1185(the)X 1307(blocks)X 1540(in)X 1626(the)X 1748(intersection.)X 2166(Notice)X 2404(that)X 2548(even)X 2724(if)X 2797(we)X 2915(\256nd)X 3063(some)X 3256(blocks)X 3489(that)X 3633(contain)X 2 f 3893(pattern1)X 1 f 4189(and)X 2 f 648 3811(pattern2)N 1 f 919(,)X 962(it)X 1029(does)X 1198(not)X 1322(mean)X 1518(that)X 1660(the)X 1780(query)X 1985(is)X 2060(successful,)X 2432(because)X 2 f 2709(pattern1)X 1 f 3002(may)X 3162(be)X 3260(in)X 3344(one)X 3482(part)X 3629(of)X 3718(the)X 3838(block)X 4038(and)X 2 f 4176(pat-)X 648 3931(tern2)N 1 f 837(in)X 919(another.)X 2 f 1220(Glimpse)X 1 f 1507(is)X 1580(not)X 1702(ef\256cient)X 1985(for)X 2099(Boolean)X 2386(queries)X 2639(that)X 2780(contain)X 3037(very)X 3201(common)X 3502(words.)X 3759(The)X 3905(worst)X 4104(exam-)X 648 4051(ple)N 775(of)X 871(this)X 1015(weakness)X 1352(that)X 1501(we)X 1624(encountered)X 2046(was)X 2200(a)X 2265(search)X 2499(for)X 2621(``linear)X 2886(programming.'')X 3444(This)X 3614(term)X 3789(appeared)X 4108(in)X 4198(our)X 648 4171(\256les)N 807(in)X 895(several)X 1149(blocks,)X 1404(but)X 1532(to)X 1620(\256nd)X 1770(it)X 1840(we)X 1960(had)X 2102(to)X 2190(intersect)X 2488(all)X 2594(blocks)X 2829(that)X 2976(contain)X 3239(the)X 3364(word)X 3556(`linear')X 3820(with)X 3989(all)X 4096(blocks)X 648 4291(that)N 788(contain)X 1044(the)X 1162(word)X 1347(`programming')X 1857(which)X 2073(in)X 2155(both)X 2317(cases)X 2507(were)X 2684(almost)X 2917(all)X 3017(blocks.)X 848 4444(The)N 995(idea)X 1151(of)X 1240(using)X 2 f 1435(agrep)X 1 f 1644(to)X 1728(search)X 1957(the)X 2078(index)X 2279(can)X 2414(also)X 2566(be)X 2665(integrated)X 3009(with)X 3174(regular)X 3425(inverted)X 3711(indexes.)X 4019(It)X 4091(is)X 4167(pos-)X 648 4564(sible)N 821(to)X 905(separate)X 1191(the)X 1311(list)X 1430(of)X 1519(words)X 1737(in)X 1821(an)X 1919(inverted)X 2204(index)X 2404(from)X 2582(the)X 2702(rest)X 2840(of)X 2929(the)X 3048(index,)X 3267(then)X 3426(use)X 2 f 3554(agrep)X 1 f 3762(to)X 3845(\256nd)X 3990(the)X 4109(words)X 648 4684(that)N 790(match)X 1009(the)X 1130(query)X 1336(\(e.g.,)X 1522(a)X 1581(query)X 1787(that)X 1930(allows)X 2162(some)X 2354(errors\),)X 2612(then)X 2773(use)X 2903(the)X 3024(regular)X 3275(inverted)X 3561(index)X 3762(algorithm)X 4096(to)X 4181(\256nd)X 648 4804(those)N 837(words.)X 1093(We)X 1225(are)X 1344(not)X 1466(familiar)X 1740(with)X 1902(any)X 2038(system)X 2280(that)X 2420(provides)X 2716(approximate)X 3137(matching)X 3455(in)X 3537(this)X 3672(fashion.)X 848 4957(In)N 937(summary,)X 1277(we)X 1393(list)X 1512(the)X 1632(strengths)X 1943(and)X 2081(weaknesses)X 2478(of)X 2567(our)X 2696(two-level)X 3022(scheme)X 3286(compared)X 3626(with)X 3791(regular)X 4042(inverted)X 648 5077(indexes:)N 8 s 10 f 648 5266(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)N 5 s 1 f 648 5368(2)N 8 s 689 5393(Although)N 952(the)X 1051(index)X 1214(is)X 1278(not)X 1381(an)X 1462(ASCII)X 1650(\256le,)X 1769(because)X 1991(the)X 2090(block)X 2253(numbers)X 2494(use)X 2600(all)X 2685(256)X 2802(byte)X 2933(values,)X 3133(the)X 3232(words)X 3409(themselves)X 3714(are)X 3812(stored)X 3989(in)X 4060(ASCII)X 4248(so)X 2 f 648 5489(agrep)N 1 f 813(can)X 917(\256nd)X 1033(them.)X 5 p %%Page: 5 6 8 s 8 xH 0 xS 1 f 10 s 3 f 2456 408(5)N 648 696(Strengths)N 1 f 648 849(1.)N 848(Very)X 1029(small)X 1222(index.)X 648 1002(2.)N 848(Approximate)X 1291(matching)X 1609(is)X 1682(supported.)X 648 1155(3.)N 848(Fast)X 1001(index)X 1199(construction.)X 648 1308(4.)N 848(No)X 966(need)X 1138(to)X 1220(de\256ne)X 1436(document)X 1772(boundaries)X 2144(ahead)X 2352(of)X 2439(time.)X 2641(It)X 2710(can)X 2842(be)X 2938(done)X 3114(at)X 3192(query)X 3395(time.)X 648 1461(5.)N 848(Easy)X 1024(to)X 1106(customize)X 1451(to)X 1533(user)X 1687 0.3182(preferences.)AX 648 1614(6.)N 848(Easy)X 1024(to)X 1106(adapt)X 1300(to)X 1382(a)X 1438(parallel)X 1699(computer)X 2022(\(different)X 2346(blocks)X 2575(can)X 2707(be)X 2803(searched)X 3105(by)X 3205(different)X 3502(processors\).)X 648 1767(7.)N 848(Easy)X 1024(to)X 1106(modify)X 1357(the)X 1475(index)X 1673(due)X 1809(to)X 1891(its)X 1986(small)X 2179(size.)X 2364(Therefore,)X 2722(dynamic)X 3018(texts)X 3189(can)X 3321(be)X 3417(supported.)X 648 1920(8.)N 848(No)X 969(need)X 1144(to)X 1229(extract)X 1471(stems.)X 1716(Subword)X 2028(queries)X 2283(are)X 2405(supported)X 2744(automatically)X 3204(\(even)X 3407(subwords)X 3738(that)X 3882(appear)X 4121(in)X 4207(the)X 848 2040(middle)N 1090(of)X 1177(words\).)X 648 2193(9.)N 848(Queries)X 1118(with)X 1280(wildcards,)X 1632(classes)X 1875(of)X 1962(characters,)X 2329(and)X 2465(even)X 2637(regular)X 2885(expressions)X 3279(are)X 3398(supported.)X 3 f 648 2377(Weaknesses)N 1 f 648 2530(1.)N 848(Slower)X 1103(compared)X 1448(to)X 1538(inverted)X 1829(indexes)X 2102(for)X 2224(some)X 2421(queries.)X 2721(Not)X 2870(suitable)X 3148(for)X 3271(applications)X 3687(where)X 3913(speed)X 4125(is)X 4207(the)X 848 2650(predominant)N 1273(concern.)X 648 2803(2.)N 848(Too)X 997(slow,)X 1188(at)X 1266(this)X 1401(stage)X 1586(\(but)X 1735(we're)X 1939(working)X 2226(on)X 2326(it\),)X 2437(for)X 2551(very)X 2714(large)X 2895(texts)X 3066(\(more)X 3278(than)X 3436(500MB\).)X 648 2956(3.)N 848(Boolean)X 1135(queries)X 1387(containing)X 1745(common)X 2045(words)X 2261(are)X 2380(slow.)X 6 f 14 s 648 3228(3.)N 803(Usage)X 1169(and)X 1398(Experience)X 1 f 10 s 648 3381(We)N 782(have)X 956(been)X 1130(using)X 2 f 1325(glimpse)X 1 f 1596(for)X 1712(a)X 1770(few)X 1913(months)X 2171(now,)X 2352(mostly)X 2592(on)X 2695(our)X 2825(own)X 2986(\256le)X 3111(systems.)X 3427(We)X 3562(have)X 3737(tried)X 3907(it)X 3974(on)X 4077(several)X 648 3501(other)N 843(data)X 1007(collections,)X 1404(ranging)X 1679(in)X 1771(size)X 1926(from)X 2112(30MB)X 2346(to)X 2438(250MB.)X 2752(In)X 2849(this)X 2994(section,)X 3271(we)X 3395(discuss)X 3656(some)X 3854(of)X 3950(the)X 4077(current)X 648 3621(features)N 923(of)X 2 f 1010(glimpse)X 1 f 1279(and)X 1415(our)X 1542(experience)X 1911(with)X 2073(it.)X 848 3774(The)N 994(current)X 1243(version)X 1500(of)X 2 f 1588(glimpse)X 1 f 1858(is)X 1932(a)X 1990(collection)X 2328(of)X 2417(many)X 2617(programs)X 2942(of)X 3031(about)X 3231(7500)X 3413(lines)X 3586(of)X 3675(C)X 3750(code.)X 3944(It)X 4015(is)X 4090(geared)X 648 3894(towards)N 922(indexing)X 1222(a)X 1278(part)X 1423(of)X 1510(a)X 1566(\256le)X 1688(system.)X 1970(The)X 2115(statement)X 7 f 792 4046(glimpse_index)N 1464([-n])X 1704(dir_name)X 2136([dir_names])X 1 f 648 4198(indexes)N 937(directory)X 1271(dir_name)X 1618(\(or)X 1756(several)X 2028(directories\))X 2438(and)X 2598(everything)X 2985(below)X 3225(it.)X 3333(The)X 3502(most)X 3701(common)X 4025(usage)X 4252(is)X 7 f 648 4318(glimpse_index)N 1326(\304)X 1 f (.)S 1439(The)X 7 f 1617(-n)X 1 f 1738(option)X 1967(indexes)X 2237(numbers)X 2538(as)X 2630(well.)X 2833(Indexing)X 3143(is)X 3221(typically)X 3526(done)X 3707(every)X 3911(night,)X 4120(and)X 4261(it)X 648 4438(takes)N 849(about)X 1063(6)X 1139(minutes)X 1428(\(elapsed)X 1732(time\))X 1937(to)X 2035(index)X 2249(50MB)X 2489(of)X 2592(text)X 2748(or)X 2851(about)X 3065(7-8)X 3208(seconds)X 3498(per)X 3637(1MB)X 3837(\(using)X 4073(a)X 4145(DEC)X 648 4558(5000/240)N 970(workstation\).)X 848 4711(Before)N 1094(indexing)X 1401(a)X 1464(\256le,)X 1613(the)X 1738(program)X 2037(checks)X 2283(whether)X 2569(it)X 2640(is)X 2720(a)X 2783(text)X 2930(\256le.)X 3099(If)X 3180(the)X 3305(\256le)X 3434(is)X 3514(found)X 3728(to)X 3817(have)X 3997(too)X 4127(many)X 648 4831(non-alphanumeric)N 1254(characters)X 1603(\(e.g.,)X 1788(an)X 1886(executable)X 2252(or)X 2341(a)X 2399(compressed)X 2800(\256le\),)X 2971(it)X 3036(is)X 3110(not)X 3233(indexed,)X 3528(and)X 3665(its)X 3761(name)X 3956(is)X 4030(added)X 4243(to)X 648 4951(a)N 7 f 734(.log)X 1 f 948(\256le.)X 1112(Other)X 1317(formats,)X 1604(for)X 1720(example,)X 2034(`uuencoded')X 2458(\256les)X 2614(and)X 2753(`binhexed')X 3124(\256les,)X 3300(are)X 3422(excluded)X 3735(too.)X 3900(Determining)X 648 5071(whether)N 930(a)X 989(\256le)X 1114(is)X 1190(a)X 1249(text)X 1392(\256le)X 1517(is)X 1593(not)X 1718(easy.)X 1924(Texts)X 2125(of)X 2215(languages)X 2559(that)X 2701(use)X 2830(special)X 3075(symbols,)X 3383(such)X 3552(as)X 3641(an)X 3739(umlaut,)X 4003(may)X 4163(look)X 648 5191(like)N 788(binary)X 1014(\256les.)X 1208(There)X 1417(are)X 1537(tools)X 1713(that)X 1854(do)X 1955(a)X 2012(good)X 2193(job)X 2316(of)X 2404(identifying)X 2776(\256le)X 2899(types,)X 3109(for)X 3224(example)X 3517(Essence)X 3797([HS93],)X 4074(and)X 4211(we)X 648 5311(will)N 793(eventually)X 1148(incorporate)X 1535(them)X 1716(in)X 2 f 1799(glimpse)X 1 f 2048(.)X 2109(On)X 2228(the)X 2347(other)X 2533(hand,)X 2730(some)X 2920(ASCII)X 3149(\256les)X 3302(should)X 3535(not)X 3657(be)X 3753(indexed.)X 4067(A)X 4145(good)X 648 5431(example)N 945(is)X 1023(a)X 1084(\256le)X 1211(containing)X 1574(DNA)X 1773(sequences.)X 2164(We)X 2301(actually)X 2580(have)X 2757(such)X 2929(\256les)X 3087(and)X 3228(found)X 3440(them)X 3625(to)X 3712(cause)X 3916(the)X 4039(index)X 4243(to)X 648 5551(grow)N 840(signi\256cantly,)X 1282(because)X 1564(they)X 1729(contain)X 1992(a)X 2055(large)X 2242(number)X 2513(of)X 2606(essentially)X 2970(random)X 3241(strings.)X 3520(We)X 3658(should)X 3897(note)X 4061(that)X 4207(the)X 648 5671(two-level)N 975(scheme)X 1240(is)X 1317(not)X 1443(suitable)X 1716(for)X 1835(typical)X 2078(biological)X 2423(searches,)X 2741(because)X 3021(they)X 3184(require)X 3437(more)X 3627(complicated)X 4044(types)X 4238(of)X 6 p %%Page: 6 7 10 s 10 xH 0 xS 1 f 3 f 2456 408(6)N 1 f 648 696(approximate)N 1074(matching.)X 1437(Indexing)X 1747(numbers)X 2048(is)X 2126(useful)X 2347(for)X 2466(dates)X 2656(and)X 2797(other)X 2986(identifying)X 3361(numbers)X 3661(\(e.g.,)X 3848(\256nd)X 3996(all)X 4100(e-mail)X 648 816(messages)N 988(from)X 1181(a)X 1254(certain)X 1510(person)X 1761(during)X 2007(July)X 2177(1991\).)X 2441(But)X 2594(large)X 2793(\256les)X 2964(with)X 3144(numeric)X 3445(data)X 3617(will)X 3779(make)X 3991(the)X 4127(index)X 648 936(unnecessarily)N 1109(large.)X 2 f 1334(Glimpse)X 1 f 1624(allows)X 1856(the)X 1977(user)X 2134(to)X 2219(specify)X 2474(which)X 2693(\256les)X 2849(should)X 3085(not)X 3210(be)X 3309(indexed)X 3586(by)X 3689(adding)X 3930(their)X 4100(names)X 648 1056(to)N 730(a)X 7 f 814(.prohibit)X 1 f 1266(\256le.)X 1428(We)X 1560(plan)X 1718(to)X 1800(add)X 1936(more)X 2121(customized)X 2506(features)X 2781(to)X 2863(the)X 2981(indexing)X 3281(process.)X 848 1209(The)N 996(partition)X 1290(into)X 1437(blocks)X 1669(is)X 1746(currently)X 2060(done)X 2240(in)X 2326(a)X 2386(straightforward)X 2905(way.)X 3103(The)X 3252(total)X 3418(size)X 3567(of)X 3658(all)X 3762(text)X 3906(\256les)X 4063(is)X 4140(com-)X 648 1329(puted,)N 875(and)X 1020(an)X 1125(estimate)X 1420(on)X 1528(the)X 1654(desired)X 1914(size)X 2067(of)X 2162(a)X 2226(block)X 2432(is)X 2513(derived.)X 2822(Files)X 3005(are)X 3132(then)X 3298(combined)X 3642(until)X 3816(they)X 3982(reach)X 4185(that)X 648 1449(size,)N 823(and)X 969(a)X 1036(new)X 1201(block)X 1410(is)X 1494(started.)X 1779(We)X 1922(plan)X 2091(to)X 2184(improve)X 2482(this)X 2628(scheme)X 2900(in)X 2993(the)X 3122(future)X 3345(in)X 3438(two)X 3589(ways:)X 3807(1\))X 3905(the)X 4034(partition)X 648 1569(should)N 883(be)X 981(better)X 1186(adapted)X 1458(to)X 1542(the)X 1662(original)X 1933(organization)X 2356(of)X 2445(the)X 2565(data,)X 2741(and)X 2879(2\))X 2968(the)X 3088(user)X 3244(should)X 3478(have)X 3651(the)X 3770(ability)X 3995(to)X 4078(control)X 648 1689(how)N 806(the)X 924(partition)X 1215(is)X 1288(done.)X 848 1842(The)N 995(user)X 1151(interface)X 1455(for)X 2 f 1571(glimpse)X 1 f 1842(is)X 1917(similar)X 2161(to)X 2245(that)X 2387(of)X 2 f 2476(agrep)X 1 f 2663(,)X 2705(except)X 2937(that)X 3079(\256le)X 3203(names)X 3430(are)X 3551(not)X 3675(required.)X 4006(The)X 4154(typi-)X 648 1962(cal)N 762(usage)X 965(is)X 7 f 792 2114(glimpse)N 1176(information)X 1 f 648 2266(which)N 864(will)X 1008(output)X 1232(all)X 1332(lines)X 2 f 1503(in)X 1585(all)X 1689(indexed)X 1959(\256les)X 1 f 2108(that)X 2248(contain)X 2 f 2504(information)X 1 f 2881(;)X 7 f 792 2418(glimpse)N 1176(-1)X 1320(HardToSpell)X 1 f 648 2570(will)N 792(\256nd)X 936(all)X 1036 0.3125(occurrences)AX 1441(of)X 2 f 1528(HardToSpell)X 1 f 1961(with)X 2123(one)X 2259(spelling)X 2532(error.)X 7 f 792 2722(glimpse)N 1176(-w)X 1320('t[a-z]j@#uk')X 1 f 648 2874(will)N 795(\256nd)X 942(all)X 1045(email)X 1246(addresses)X 1577(in)X 1662(which)X 1881(a)X 1940(3-letter)X 2195(login)X 2382(name)X 2579(starts)X 2771(with)X 2936(t)X 2981(and)X 3120(ends)X 3290(with)X 3455(j)X 3501(\(it)X 3596(is)X 3673(typical)X 3915(not)X 4041(to)X 4127(know)X 648 2994(the)N 780(user's)X 1006(middle)X 1262(name\))X 1497(and)X 1647(uk)X 1761(is)X 1848(somewhere)X 2248(in)X 2344(the)X 2476(host)X 2643(name)X 2851(\(in)X 2 f 2974(agrep)X 1 f 3195(the)X 3327(symbol)X 3595(#)X 3668(stands)X 3901(for)X 4028(arbitrary)X 648 3114(number)N 913(of)X 1000(wild)X 1162(cards,)X 1372(and)X 1508(the)X 1626(-w)X 1731(option)X 1955(speci\256es)X 2251(that)X 2391(the)X 2509(pattern)X 2752(must)X 2927(match)X 3143(a)X 3199(complete)X 3513(word\).)X 2 f 848 3267(Glimpse)N 1 f 1135(supports)X 1426(Boolean)X 1713(queries)X 1965(the)X 2083(same)X 2268(way)X 2422(that)X 2 f 2562(agrep)X 1 f 2769(does)X 2936(\(with)X 3125(;)X 3167(serving)X 3423(as)X 3510(AND\):)X 7 f 792 3419(glimpse)N 1176(-1)X 1320('Lazoska;Zahorian')X 1 f 648 3571(will)N 792(\256nd)X 936(all)X 1036 0.3125(occurrences)AX 1441(of)X 1528(both)X 1690(names)X 1915(\(allowing)X 2242(one)X 2378(spelling)X 2651(error,)X 2848(which)X 3064(is)X 3137(needed\).)X 7 f 792 3723(glimpse)N 1176('Winter)X 1560(Usenix')X 1 f 648 3875(will)N 799(\256rst)X 950(search)X 1183(the)X 1308(index)X 1513(for)X 1634(the)X 1759(two)X 1907(words)X 2131(separately)X 2485(and)X 2629(\256nd)X 2781(all)X 2889(the)X 3015(blocks)X 3252(containing)X 3618(both)X 3788(words,)X 4032(then)X 4198(use)X 2 f 648 3995(agrep)N 1 f 855(for)X 969(the)X 1087(whole)X 1303(phrase.)X 848 4148(Another)N 1137(nice)X 1297(feature)X 1547(of)X 2 f 1640(glimpse)X 1 f 1915(is)X 1994(to)X 2082(limit)X 2258(the)X 2382(search)X 2614(to)X 2702(\256les)X 2861(whose)X 3092(names)X 3323(match)X 3545(a)X 3608(given)X 3813(regular)X 4068(expres-)X 648 4268(sion.)N 7 f 792 4420(glimpse)N 1176(-F)X 1320('haystack\\.c$')X 2040(needle)X 1 f 648 4572(will)N 792(\256nd)X 936(all)X 1036(needles)X 1297(in)X 1379(all)X 1479(haystack.c)X 1836(\256les.)X 2029(Sometimes,)X 2424(you)X 2564(want)X 2740(to)X 2822(search)X 3048(everywhere)X 3444(for)X 3558(that)X 3698(elusive)X 3945(de\256nition:)X 7 f 792 4724(glimpse)N 1176(-F)X 1320('\\.h$')X 1656(ABC_XYZ)X 1 f 648 4876(will)N 792(search)X 1018(all)X 1118(.h)X 1198(\256les.)X 7 f 792 5028(glimpse)N 1176(-F)X 1320('\\.tex$')X 1752('environment;\303\\\\')X 1 f 648 5180(will)N 793(\256nd)X 938(all)X 1039 0.3125(occurrences)AX 1445(of)X 2 f 1533(environment)X 1 f 1955(in)X 2038(a)X 2096(line)X 2238(that)X 2380(starts)X 2571(with)X 2735(\\)X 2819(\(useful)X 3064(if)X 3135(you)X 3277(want)X 3455(to)X 3539(see)X 3664(environment)X 4091(as)X 4180(part)X 648 5300(of)N 737(a)X 795(de\256nition\).)X 2 f 1189(Glimpse)X 1 f 1477(is)X 1551(in)X 1634(fact)X 1776(so)X 1868(\257exible)X 2129(that)X 2270(it)X 2335(can)X 2468(be)X 2565(used)X 2733(for)X 2848(some)X 3038(\256le)X 3161(management)X 3592(operations;)X 3989(for)X 4104(exam-)X 648 5420(ple,)N 7 f 792 5572(glimpse)N 1176(-F)X 1320(mbox)X 1560(-h)X 1704(-G)X 1896(.)X 1992(>)X 2088(MBOX)X 7 p %%Page: 7 8 10 s 10 xH 0 xS 7 f 3 f 2456 408(7)N 1 f 648 696(will)N 792(concatenate)X 1192(all)X 1292(\256les)X 1445(whose)X 1670(name)X 1864(is)X 1937(mbox)X 2139(into)X 2283(one)X 2419(big)X 2541(one;)X 7 f 792 848(glimpse)N 1176(-c)X 1320(-F)X 1464('pattern\\.h$')X 2136('\\#define')X 1 f 648 1000(will)N 794(provide)X 1061(a)X 1119(list)X 1238(of)X 1327(all)X 1429(pattern.h)X 1734(\256les,)X 1909(each)X 2079(followed)X 2386(by)X 2488(the)X 2609(number)X 2877(of)X 2967(#de\256ne's)X 3284(it)X 3351(has.)X 3521(We)X 3656(even)X 3831(allow)X 4032(errors)X 4243(in)X 648 1120(the)N 766(regular)X 1014(expressions)X 1408(for)X 1522(the)X 1640(\256le)X 1762(names,)X 2007(using,)X 2220(for)X 2334(example,)X 7 f 2674(-F1)X 1 f 2838(for)X 2952(one)X 3088(error.)X 6 f 14 s 648 1392(4.)N 803(Perform)X 1233(ance)X 1 f 10 s 648 1545(All)N 773(the)X 894(performance)X 1324(numbers)X 1623(given)X 1824(below)X 2043(are)X 2165(anecdotal.)X 2536(The)X 2684(point)X 2871(of)X 2961(this)X 3099(section)X 3349(is)X 3425(not)X 3550(to)X 3635(compare)X 3935(the)X 4056(running)X 648 1665(time)N 813(of)X 2 f 903(glimpse)X 1 f 1175(to)X 1260(other)X 1448(systems,)X 1744(but)X 1869(to)X 1954(argue)X 2156(that)X 2299(it)X 2366(is)X 2441(fast)X 2579(enough)X 2837(for)X 2953(its)X 3050(purposes.)X 3397(Query)X 3620(times)X 3815(depend)X 4069(heavily)X 648 1785(on)N 750(the)X 870(type)X 1030(of)X 1119(indexed)X 1395(data)X 1551(and)X 1689(the)X 1809(query)X 2014(itself)X 2196(\(not)X 2347(to)X 2431(mention)X 2715(the)X 2835(architecture)X 3237(and)X 3375(the)X 3495(operating)X 3820(system\).)X 4131(If)X 4207(the)X 648 1905(pattern)N 897(appears)X 1169(in)X 1257(only)X 1425(one)X 1567(block,)X 1791(the)X 1915(search)X 2147(time)X 2315(will)X 2465(be)X 2567(almost)X 2805(always)X 3053(fast)X 3194(no)X 3299(matter)X 3529(how)X 3692(large)X 3878(the)X 4001(data)X 4160(is)X 4238(or)X 648 2025(how)N 822(complex)X 1134(the)X 1268(pattern)X 1527(may)X 1702(be)X 1815(\(an)X 1955(unsuccessful)X 2402(query)X 2622(is)X 2712(the)X 2847(fastest)X 3089(because)X 3381(only)X 3560(the)X 3695(index)X 3910(needs)X 4130(to)X 4229(be)X 648 2145(searched\).)N 1028(If)X 1113(the)X 1242(pattern)X 1496(matches)X 1790(a)X 1857(large)X 2049(portion)X 2311(of)X 2409(the)X 2538(blocks,)X 2798(the)X 2927(query)X 3140(may)X 3308(be)X 3414(slow.)X 3635(Searching)X 3986(in)X 4078(a)X 4144(large)X 648 2265(information)N 1061(space)X 1275(requires)X 1569(a)X 1640(careful)X 1899(design)X 2143(of)X 2245(queries.)X 2552(No)X 2686(matter)X 2927(how)X 3101(fast)X 3253(the)X 3387(search)X 3629(is,)X 3738(if)X 3823(the)X 3957(number)X 4238(of)X 648 2385(matches)N 937(is)X 1016(large,)X 1223(it)X 1293(will)X 1443(take)X 1603(too)X 1731(long)X 1899(to)X 1987(sift)X 2115(through)X 2390(them.)X 2616(However,)X 2957(we)X 3077(found)X 3290(that)X 3436(even)X 3614(matching)X 3938(to)X 4025(common)X 648 2505(patterns)N 925(can)X 1060(be)X 1159(useful,)X 1398(because)X 1676(one)X 1815(starts)X 2007(to)X 2092(see)X 2218(many)X 2420(matchings)X 2773(quite)X 2957(fast,)X 3117(and)X 3257(one)X 3397(can)X 3533(then)X 3695(stop)X 3852(and)X 3992(adjust)X 4207(the)X 648 2625(pattern.)N 932(In)X 1020(some)X 1210(cases,)X 1421(even)X 1593(though)X 1835(there)X 2016(were)X 2193(many)X 2391(matches,)X 2694(the)X 2812(\256rst)X 2956(few)X 3097(ones)X 3264(were)X 3441(suf\256cient)X 3759(to)X 3841(get)X 3959(the)X 4077(answer)X 648 2745(we)N 764(were)X 943(looking)X 1209(for.)X 1365(\(We)X 1526(also)X 1677(added)X 1891(an)X 1989(option)X 2215(-N)X 2322(that)X 2464(tells)X 2619(the)X 2739(user)X 2895(the)X 3015(number)X 3282(of)X 3371(blocks)X 3603(that)X 3746(would)X 3969(need)X 4144(to)X 4229(be)X 648 2865(searched.\))N 848 3018(Below)N 1081(we)X 1199(list)X 1320(some)X 1513(running)X 1786(times)X 1983(\(on)X 2114(a)X 2174(DEC)X 2359(5000/240)X 2686(workstation\))X 3116(for)X 3235(a)X 3296(personal)X 3593(\256le)X 3720(system)X 3967(containing)X 648 3138(69MB)N 881(of)X 977(text)X 1126(in)X 1217(4296)X 1406(different)X 1712(\256les.)X 1914(It)X 1992(took)X 2163(4.9)X 2292(minutes)X 2574(of)X 2670(CPU)X 2854(time)X 3025(\(9)X 3121(minutes)X 3403(of)X 3499(elapsed)X 3768(time\))X 3965(to)X 4055(index)X 4261(it)X 648 3258(\(including)N 1001(the)X 1123(time)X 1289(to)X 1375(determine)X 1720(that)X 1864(857)X 2008(other)X 2198(\256les)X 2356(were)X 2538(not)X 2665(text)X 2810(\256les\))X 2995(and)X 3136(the)X 3259(index)X 3462(size)X 3612(was)X 3762(1.9MB,)X 4031(which)X 4252(is)X 648 3378(2.7%)N 841(of)X 934(the)X 1058(total.)X 1266(205)X 1412(blocks)X 1647(were)X 1830(used.)X 2043(A)X 2127(typical)X 2371(search)X 2603(takes)X 2794(from)X 2975(2-10)X 3147(seconds.)X 3466(For)X 3602(example,)X 3919(a)X 3980(search)X 4211(for)X 2 f 648 3498(biometrics)N 1 f 1011(took)X 1178(1.6)X 1303(seconds.)X 1622(\(The)X 1799(numbers)X 2100(listed)X 2298(here)X 2462(are)X 2586(the)X 2709(sum)X 2867(of)X 2959(the)X 3082(user)X 3241(and)X 3382(system)X 3629(times.\))X 3895(A)X 3979(search)X 4211(for)X 2 f 648 3618(incredible)N 1 f 996(took)X 1161(2.8)X 1284(seconds)X 1561(\(there)X 1772(were)X 1952(27)X 2055(matches)X 2341(in)X 2426(22)X 2529(\256les\).)X 2752(A)X 2833(search)X 3062(for)X 2 f 3179(Checoslovakia)X 1 f 3673(allowing)X 3975(two)X 4117(errors)X 648 3738(took)N 814(3.6)X 938(seconds.)X 1256(A)X 1338(search)X 1568(for)X 2 f 1686(Usenix)X 1 f 1933(took)X 2099(13.9)X 2263(seconds)X 2541(because)X 2820(there)X 3005(were)X 3186(93)X 3290(matches)X 3577(divided)X 3841(among)X 4084(70)X 4189(dif-)X 648 3858(ferent)N 861(blocks.)X 1135(A)X 1218(Boolean)X 1510(search)X 1741(can)X 1878(sometimes)X 2245(help)X 2408(by)X 2513(limiting)X 2790(the)X 2913(number)X 3183(of)X 3275(scanned)X 3559(blocks)X 3793(\(which)X 4040(are)X 4163(only)X 648 3978(those)N 839(that)X 981(match)X 1199(all)X 1301(patterns\),)X 1624(but)X 1748(again)X 1944(it)X 2010(depends)X 2295(on)X 2397(the)X 2517(number)X 2785(of)X 2875(matches.)X 3181(For)X 3315(example,)X 3630(searching)X 3961(for)X 4078(Usenix)X 648 4098(AND)N 850(Winter)X 1101(took)X 1271(only)X 1441(4.5)X 1569(seconds)X 1851(since)X 2044(there)X 2232(were)X 2416(only)X 2585(19)X 2692(matches.)X 3022(A)X 3107(search)X 3340(for)X 3461(Lazowska)X 3814(AND)X 4015(Zahorjan)X 648 4218(with)N 819(one)X 964(error)X 1150(took)X 1321(4.7)X 1450(seconds.)X 1773(A)X 1860(search)X 2095(for)X 2219(protein)X 2476(AND)X 2680(matching)X 3008(took)X 3180(7.7)X 3310(seconds)X 3594(because)X 3879(both)X 4051(patterns)X 648 4338(were)N 826(very)X 990(common.)X 1331(The)X 1477(search)X 1704(for)X 1819(the)X 1938(e-mail)X 2164(address)X 2426(mentioned)X 2785(above)X 2997(\(t[a-z]j@#uk\))X 3462(took)X 3624(30)X 3724(seconds)X 3998(\(although)X 648 4458(we)N 768(believe)X 1026(that)X 1172(some)X 1367(of)X 1460(it)X 1530(is)X 1609(due)X 1751(to)X 1839(a)X 1901(bug)X 2047(that)X 2193(for)X 2313(some)X 2508(complicated)X 2926(regular)X 3180(expressions)X 3580(causes)X 3816(search)X 4048(in)X 4136(some)X 648 4578(unnecessary)N 1061(blocks\),)X 1337(but)X 1459(this)X 1594(is)X 1667(still)X 1806(much)X 2004(better)X 2207(than)X 2365(any)X 2501(alternative.)X 848 4731(For)N 980(a)X 1037(much)X 1236(larger)X 1445(information)X 1844(space,)X 2064(we)X 2179(indexed)X 2454(an)X 2552(old)X 2676(copy)X 2854(of)X 2943(the)X 3063(entire)X 3268(library)X 3504(catalog)X 3758(of)X 3847(the)X 3967(Univeristy)X 648 4851(of)N 742(Arizona.)X 1068(This)X 1237(experiment)X 1625(and)X 1768(the)X 1893(next)X 2058(one)X 2201(were)X 2385(run)X 2519(on)X 2626(a)X 2689(SUN)X 2875(SparcStation)X 3310(10)X 3416(model)X 3642(512)X 3788(running)X 4063(Solaris.)X 648 4971(The)N 804(copy)X 991(we)X 1116(used)X 1294(lists)X 1453(approximately)X 1947(2.5)X 2078(million)X 2339(volumes,)X 2661(divided)X 2932(among)X 3181(440)X 3333(\256les)X 3498(occupying)X 3864(258MB.)X 4180(The)X 648 5091(index)N 849(size)X 997(was)X 1145(8MB,)X 1352(which)X 1571(is)X 1647(3.1%.)X 1877(The)X 2025(index)X 2226(would)X 2449(have)X 2624(been)X 2799(much)X 3000(smaller)X 3258(for)X 3374(regular)X 3624(text;)X 3788(the)X 3908(catalog)X 4162(con-)X 648 5211(tains)N 823(mostly)X 1064(names)X 1293(and)X 1433(terms,)X 1655(in)X 1741(several)X 1993(languages,)X 2358(and)X 2498(since)X 2687(it)X 2755(uses)X 2917(\256xed)X 3101(records,)X 3382(quite)X 3566(a)X 3626(few)X 3771(of)X 3862(the)X 3985(words)X 4206(are)X 648 5331(truncated.)N 1010(It)X 1082(took)X 1247(18)X 1349(minutes)X 1624(\(all)X 1753(times)X 1948(here)X 2109(are)X 2230(elapsed)X 2493(times\))X 2715(to)X 2799(index)X 2999(the)X 3119(whole)X 3337(catalog.)X 3631(A)X 3711(search)X 3939(for)X 4055(Manber)X 648 5451(took)N 812(1)X 874(second)X 1119(\(one)X 1284(match\).)X 1569(A)X 1649(case)X 1810(insensitive)X 2174(\(-i\))X 2299(search)X 2527(for)X 2644(usenix)X 2876(yielded)X 3135(one)X 3274(match)X 3493(in)X 3578(1.8)X 3701(seconds.)X 4018(A)X 4099(search)X 648 5571(for)N 779(UNIX)X 1017(took)X 1196(3.9)X 1333(seconds)X 1624(\(138)X 1808(matches)X 2107(in)X 2205(8)X 2281(blocks\).)X 2593(A)X 2687(search)X 2929(for)X 3059(information)X 3473(AND)X 3683(retrieval)X 3987(took)X 4165(14.9)X 648 5691(seconds;)N 945(there)X 1127(were)X 1305(38)X 1406(matches)X 1690(in)X 1773(9)X 1834(blocks,)X 2084(but)X 2207(31)X 2308(blocks)X 2538(had)X 2675(to)X 2758(be)X 2855(searched)X 3158(\(because)X 3461(they)X 3620(included)X 3917(both)X 4080(terms\).)X 8 p %%Page: 8 9 10 s 10 xH 0 xS 1 f 3 f 2456 408(8)N 1 f 648 696(Searching)N 991(for)X 1107(`algorithm')X 1494(allowing)X 1796(two)X 1937(errors)X 2146(took)X 2309(16.3)X 2470(seconds,)X 2765(\256nding)X 3012(269)X 3153(matches,)X 3457(21)X 3558(of)X 3646(which)X 3863(did)X 3986(not)X 4109(match)X 648 816(the)N 766(pattern)X 1009(exactly)X 1261(due)X 1397(to)X 1479(a)X 1535(misspelling)X 1923(\(alogorithm,)X 2341(Alogrithms\))X 2752(or)X 2839(a)X 2895(foreign)X 3147(spelling)X 3420(\(e.g.,)X 3603(algoritmy\).)X 848 969(An)N 977(example)X 1280(that)X 1431(highlighted)X 1826(the)X 1955(``best)X 2170(case'')X 2395(for)X 2 f 2521(glimpse)X 1 f 2802(was)X 2959(a)X 3027(directory)X 3349(containing)X 3719(the)X 3849(archives)X 4149(from)X 648 1089(comp.dcom.telecom.)N 1364(They)X 1555(occupy)X 1813(about)X 2017(71MB)X 2247(divided)X 2513(among)X 2757(120)X 2903(\256les.)X 3102(The)X 3253(small)X 3452(number)X 3722(of)X 3814(\256les)X 3972(minimizes)X 648 1209(the)N 767(overhead)X 1083(of)X 1171(opening)X 1450(and)X 1587(closing)X 1839(\256les)X 1993(making)X 2 f 2255(agrep)X 1 f 2442(,)X 2484(and)X 2622(as)X 2711(a)X 2769(result)X 2 f 2969(glimpse)X 1 f 3240(very)X 3405(fast.)X 3583(Even)X 3770(without)X 2 f 4036(glimpse)X 1 f 4285(,)X 648 1329(searching)N 986(for)X 1109(Schwarzkopf)X 1562(allowing)X 1871(two)X 2020(misspelling)X 2417(errors)X 2634(took)X 2 f 2805(agrep)X 1 f 3021(only)X 3192(8.5)X 3321(seconds)X 3604(elapsed)X 3874(time.)X 4085(It)X 4163(took)X 2 f 648 1449(glimpse)N 1 f 918(3:38)X 1081(minutes)X 1355(to)X 1438(index)X 1637(the)X 1756(directory)X 2067(and)X 2204(the)X 2323(index)X 2522(size)X 2668(was)X 2814(1.4MB)X 3059(\(about)X 3285(2%)X 3414(of)X 3503(the)X 3623(total\).)X 3854(With)X 2 f 4036(glimpse)X 1 f 4285(,)X 648 1569(the)N 769(Schwarzkopf)X 1216(search)X 1445(took)X 1610(0.4)X 1733(seconds)X 2010(\(all)X 2140(matches)X 2426(were)X 2606(in)X 2691(one)X 2830(\256le\).)X 3022(A)X 3103(search)X 3331(for)X 3447(Usenix)X 3696(\(no)X 3825(error)X 4004(allowed\),)X 648 1689(which)N 864(appeared)X 1175(in)X 1257(5)X 1317(blocks,)X 1566(took)X 1728(0.9)X 1848(seconds.)X 2162(A)X 2240(search)X 2466(for)X 2580(glimpse)X 2853(took)X 3015(3.7)X 3135(seconds)X 3409(\(15)X 3536(matches)X 3819(in)X 3901(9)X 3961(blocks\).)X 6 f 14 s 648 1961(5.)N 803(Future)X 1182(W)X 1288(ork)X 1 f 10 s 648 2114(We)N 780(list)X 897(here)X 1056(brie\257y)X 1285(some)X 1474(avenues)X 1753(that)X 1893(we)X 2007(are)X 2126(currently)X 2436(exploring.)X 6 f 12 s 648 2354(5.1.)N 862(Searching)X 1353(Compressed)X 1960(Text)X 1 f 10 s 648 2507(If)N 724(the)X 844(text)X 986(is)X 1061(kept)X 1221(in)X 1305(a)X 1363(compressed)X 1764(form,)X 1963(it)X 2030(will)X 2177(have)X 2352(to)X 2437(be)X 2536(decompressed)X 3014(before)X 3243(the)X 3364(sequential)X 3712(search)X 3941(can)X 4076(be)X 4175(per-)X 648 2627(formed.)N 948(This)X 1118(will)X 1270(generally)X 1597(slow)X 1776(down)X 1982(the)X 2108(search)X 2342(considerably.)X 2820(But)X 2962(we)X 3083(are)X 3209(developing)X 3592(new)X 3753(text)X 3900(compression)X 648 2747(algorithms)N 1018(that)X 1166(actually)X 2 f 1448(speed)X 1659(up)X 1 f 1767(the)X 1893(search)X 2127(while)X 2333(allowing)X 2641(compression)X 3074(at)X 3160(the)X 3286(same)X 3479(time.)X 3689(The)X 3842(\256rst)X 3994(algorithm)X 648 2867([Ma93])N 911(allows)X 2 f 1142(agrep)X 1 f 1351(\(and)X 1516(most)X 1693(other)X 1880(sequential)X 2226(search)X 2453(algorithms\))X 2843(to)X 2926(search)X 3153(the)X 3272(compressed)X 3672(\256le)X 3795(directly)X 4061(without)X 648 2987(having)N 887(to)X 971(decompress)X 1372(it)X 1438(\256rst.)X 1624(Essentially,)X 2017(instead)X 2266(of)X 2355(restoring)X 2662(the)X 2782(text)X 2924(back)X 3098(to)X 3182(its)X 3279(uncompressed)X 3760(form,)X 3958(we)X 4074(modify)X 648 3107(the)N 2 f 768(pattern)X 1 f 1021(to)X 1105(\256t)X 1193(the)X 1312(compressed)X 1712(form)X 1889(and)X 2026(search)X 2253(for)X 2368(the)X 2487(modi\256ed)X 2792(pattern)X 3036(directly.)X 3342(Searching)X 3684(the)X 3803(compressed)X 4203(\256le)X 648 3227(directly)N 919(improves)X 1243(the)X 1367(search)X 1600(time)X 1769(\(as)X 1890(well)X 2055(as)X 2149(space)X 2355(utilization,)X 2726(of)X 2820(course\),)X 3104(because)X 3386(there)X 3574(is)X 3654(less)X 3801(I/O.)X 3975(In)X 4069(prelim-)X 648 3347(inary)N 838(tests,)X 1025(we)X 1144(achieved)X 1455(about)X 1658(30%)X 1830(reduction)X 2158(in)X 2245(space)X 2449(and)X 2590(25%)X 2762(decrease)X 3065(in)X 3151(search)X 3381(time.)X 3587(This)X 3753(allows)X 3986(\256les)X 4143(to)X 4229(be)X 648 3467(kept)N 807(in)X 890(a)X 947(compressed)X 1347(form)X 1524(inde\256nitely)X 1909(\(unless)X 2157(they)X 2316(are)X 2436(changed\))X 2752(and)X 2889(to)X 2973(be)X 3071(searched)X 3375(at)X 3455(the)X 3575(same)X 3762(time.)X 3966(In)X 4055(particu-)X 648 3587(lar,)N 783(we)X 907(intend)X 1137(to)X 1229(compress)X 1562(the)X 1690(index)X 1898(used)X 2075(in)X 2167(the)X 2294(two-level)X 2626(scheme,)X 2916(because)X 3200(it)X 3273(is)X 3355(searched)X 3666(frequently.)X 4065(We)X 4206(are)X 648 3707(working)N 939(on)X 1043(another)X 1308(compression)X 1737(scheme)X 2002(that)X 2146(will)X 2294(be)X 2394(integrated)X 2739(into)X 2 f 2887(glimpse)X 1 f 3136(.)X 3180(This)X 3346(work)X 3535(is)X 3612(still)X 3755(in)X 3841(a)X 3901(very)X 4069(prelim-)X 648 3827(inary)N 838(stage.)X 1068(The)X 1218(compression)X 1648(rates,)X 1845(for)X 1964(natural)X 2212(language)X 2527(texts,)X 2723(seem)X 2913(to)X 3000(be)X 3101(in)X 3188(the)X 3311(50%)X 3483(range.)X 3727(It)X 3801(also)X 3955(allows)X 4189(fast)X 648 3947(search)N 874(without)X 1138(decompression,)X 1659(although)X 1959(it)X 2023(is)X 2096(too)X 2218(early)X 2399(to)X 2481(predict)X 2724(its)X 2819(speed.)X 6 f 12 s 648 4187(5.2.)N 862(Incremental)X 1427(Indexes)X 1 f 10 s 648 4340(The)N 807(two-level)X 1144(index)X 1356(is)X 1443(easier)X 1665(to)X 1761(modify)X 2026(and)X 2176(adapt)X 2384(to)X 2480(a)X 2551(dynamic)X 2862(environment)X 3302(than)X 3475(a)X 3546(regular)X 3809(inverted)X 4107(index,)X 648 4460(because)N 926(it)X 993(is)X 1069(so)X 1163(much)X 1364(smaller.)X 1663(To)X 1775(add)X 1914(a)X 1973(new)X 2130(\256le)X 2255(to)X 2340(the)X 2461(current)X 2712(index,)X 2933(we)X 3050(\256rst)X 3197(add)X 3336(the)X 3457(\256le)X 3581(to)X 3665(an)X 3763(existing)X 4038(block)X 4238(or)X 648 4580(create)N 863(a)X 921(new)X 1077(block)X 1277(if)X 1348(the)X 1469(\256le)X 1594(is)X 1670(large)X 1854(enough)X 2113(or)X 2203(important)X 2537(enough)X 2796(to)X 2881(deserve)X 3150(it.)X 3257(Then)X 3445(we)X 3562(scan)X 3728(the)X 3849(index)X 4050(and)X 4189(add)X 648 4700(each)N 818(word)X 1005(in)X 1089(the)X 1209(new)X 1365(\256le)X 1489(that)X 1631(does)X 1800(not)X 1924(already)X 2183(appear)X 2420(in)X 2504(the)X 2624(block.)X 2863(Since)X 3062(the)X 3181(index)X 3380(is)X 3454(small,)X 3668(reading)X 3930(it)X 3995(from)X 4172(disk)X 648 4820(and)N 791(writing)X 1049(it)X 1120(back)X 1299(can)X 1438(be)X 1541(done)X 1724(very)X 1894(fast.)X 2077(Deletion)X 2380(of)X 2474(a)X 2537(\256le)X 2666(is)X 2746(slightly)X 3012(more)X 3204(time)X 3373(consuming)X 3752(because)X 4035(for)X 4157(each)X 648 4940(word)N 834(we)X 949(need)X 1122(to)X 1205(check)X 1414(the)X 1533(whole)X 1750(block)X 1949(to)X 2032(determine)X 2374(whether)X 2654(that)X 2794(word)X 2979(appears)X 3245(somewhere)X 3631(else)X 3776(\(and)X 3939(thus)X 4092(should)X 648 5060(not)N 772(be)X 870(deleted\).)X 1191(Fortunately,)X 2 f 1602(agrep)X 1 f 1811(contains)X 2101(a)X 2160(very)X 2326(powerful)X 2639(algorithm)X 2973(for)X 3090(multi-pattern)X 3531(matching.)X 3892(It)X 3964(can)X 4099(search)X 648 5180(for)N 762(a)X 818(large)X 999(collection)X 1335(of)X 1422(words)X 1638(\(up)X 1765(to)X 1847(30,000\))X 2114(concurrently.)X 848 5333(Incremental)N 1264(indexing)X 1576(will)X 1733(be)X 1842(essential)X 2151(for)X 2278(indexing)X 2591(newsfeed.)X 2968(We)X 3113(are)X 3245(considering)X 3652(adapting)X 2 f 3961(glimpse)X 1 f 4243(to)X 648 5453(allow)N 851(searching)X 1184(usenet)X 1414(netnews.)X 1722(Currently,)X 2074(the)X 2197(total)X 2363(size)X 2512(of)X 2603(a)X 2663(typical)X 2905(usenet)X 3134(server)X 3355(is)X 3432(from)X 3612(500-800MB.)X 4067(Quite)X 4269(a)X 648 5573(bit)N 762(of)X 859(it)X 933(is)X 1017(not)X 1150(text)X 1301(but)X 1434(images)X 1692(and)X 1839(programs,)X 2193(so)X 2295(it)X 2370(is)X 2454(a)X 2521(size)X 2677(we)X 2802(can)X 2945(handle.)X 3230(The)X 3386(problem)X 3684(is)X 3768(that)X 3919(this)X 4065(kind)X 4238(of)X 648 5693(newsfeed)N 981(consists)X 1263(of)X 1359(a)X 1424(large)X 1614(number)X 1887(of)X 1982(small)X 2183(\256les)X 2344(\(individual)X 2723(email)X 2929(messages\))X 3287(stored)X 3511(at)X 3597(random)X 3870(places)X 4099(on)X 4207(the)X 9 p %%Page: 9 10 10 s 10 xH 0 xS 1 f 3 f 2456 408(9)N 1 f 648 696(disk.)N 841(A)X 919(better)X 1122(data)X 1276(organization)X 1697(will)X 1841(probably)X 2146(be)X 2242(required)X 2530(for)X 2644(reasonable)X 3008(performance.)X 6 f 12 s 648 936(5.3.)N 862(Customization)X 1 f 10 s 648 1089(There)N 860(are)X 983(several)X 1235(ways)X 1424(to)X 1510(let)X 1614(the)X 1736(user)X 1894(improve)X 2185(the)X 2307(indexing)X 2611(and)X 2751(searching)X 3083(procedures)X 3460(by)X 3565(customizing.)X 4021(The)X 4171(user)X 648 1209(should)N 882(be)X 979(able)X 1134(to)X 1217(decide)X 1448(whether)X 1728(certain)X 1968(patterns)X 2243(are)X 2363(indexed)X 2638(or)X 2726(not.)X 2889(We)X 3022(provide)X 3287(an)X 3383(option)X 3607(to)X 3689(index)X 3887(numbers,)X 4203(but)X 648 1329(we)N 764(should)X 999(allow)X 1199(more)X 1386(\257exibility.)X 1758(One)X 1914(way)X 2070(is)X 2145(to)X 2229(provide)X 2497(a)X 2556(hook)X 2739(to)X 2824(an)X 2923(external)X 3205(\256ltering)X 3481(program,)X 3796(provided)X 4104(by)X 4207(the)X 648 1449(user,)N 825(which)X 1044(will)X 1190(decide)X 1422(what)X 1600(to)X 1684(index)X 1884(based)X 2089(on)X 2191(contents,)X 2500(type)X 2660(of)X 2749(\256le,)X 2893(name)X 3089(of)X 3178(\256le,)X 3322(etc.)X 3478(We)X 3612(also)X 3763(plan)X 3923(to)X 4007(allow)X 4207(the)X 648 1569(user)N 808(to)X 897(store)X 1080(a)X 1143(large)X 1331(set)X 1447(of)X 1541(multi-words)X 1959(phrases)X 2227(\(e.g.,)X 2417("\256ber)X 2624(optics,")X 2895("Jonathan)X 3240(Smith,)X 3477("May)X 3684(1992"\))X 3931(that)X 4078(will)X 4229(be)X 648 1689(indexed)N 924(together,)X 1229(allowing)X 1531(quick)X 1731(search)X 1959(for)X 2075(them)X 2256(without)X 2521(the)X 2640(need)X 2813(for)X 2928(Boolean)X 3216(queries.)X 3509(Another)X 3793(option)X 4018(is)X 4092(to)X 4175(par-)X 648 1809(tition)N 837(the)X 956(collection)X 1294(of)X 1383(\256les)X 1538(into)X 1684(categories)X 2032(and)X 2170(build)X 2356(separate)X 2642(indexes)X 2909(for)X 3025(each)X 3195(\(e.g.,)X 3380 0.2232(correspondence,)AX 3927(information)X 648 1929(from)N 827(servers,)X 1097(program)X 1391(source)X 1623(codes\).)X 1895(This)X 2059(is)X 2134(not)X 2258(needed)X 2508(for)X 2624(small)X 2819(to)X 2903(medium)X 3187(size)X 3334(\256le)X 3458(system,)X 3722(but)X 3846(may)X 4006(be)X 4104(essen-)X 648 2049(tial)N 772(for)X 888(large)X 1071(\256le)X 1195(systems.)X 1510(We)X 1644(also)X 1795(plan)X 1955(to)X 2040(support)X 2303(access)X 2532(to)X 2617(any)X 2756(special)X 3002(structure)X 3306(or)X 3396(additional)X 3739(information)X 4140(asso-)X 648 2169(ciated)N 862(with)X 1026(the)X 1146(text.)X 1328(For)X 1461(example,)X 1775(some)X 1966(searches)X 2261(may)X 2421(specify)X 2675(that)X 2817(the)X 2937(desired)X 3191(information)X 3591(starts)X 3782(at)X 3862(column)X 4124(30)X 4225(on)X 648 2289(the)N 773(line)X 920(or)X 1014(in)X 1103(the)X 1228(second)X 1478(\256eld.)X 1687(The)X 1839(user)X 2000(may)X 2165(want)X 2348(to)X 2437(search)X 2670(only)X 2839(small)X 3039(\256les)X 3200(\(say,)X 3382(below)X 3606(20KB\))X 3852(or)X 3947(recent)X 4172(\256les)X 648 2409(\(say,)N 822(after)X 990(August)X 1241(1992\).)X 848 2562(There)N 1058(should)X 1293(be)X 1391(more)X 1578(ways)X 1766(to)X 1851(view)X 2030(the)X 2151(output.)X 2418(For)X 2552(example,)X 2867(for)X 2984(queries)X 3239(that)X 3382(give)X 3543(many)X 3744(matches,)X 4050(the)X 4171(user)X 648 2682(may)N 816(be)X 922(interested)X 1263(\256rst)X 1416(in)X 1507(a)X 1572(rough)X 1788(idea)X 1951(of)X 2047(where)X 2273(those)X 2471(matches)X 2763(are)X 2891(\(e.g.,)X 3083(only)X 3254(directory)X 3573(names\).)X 3874(We)X 4015(currently)X 648 2802(have)N 821(an)X 918(option)X 1143([-c])X 1281(to)X 1364(list)X 1482(only)X 1645(the)X 1764(\256les)X 1919(containing)X 2279(a)X 2337(match)X 2555(along)X 2755(with)X 2919(the)X 3039(number)X 3306(of)X 3395(matches,)X 3700(and)X 3838(another)X 4101(option)X 648 2922([-N])N 813(to)X 901(output)X 1131(only)X 1299(the)X 1423(number)X 1694(of)X 1787(blocks)X 2022(with)X 2190(potential)X 2496(matches.)X 2824(These)X 3041(options,)X 3321(and)X 3462(many)X 3665(more,)X 3875(can)X 4012(be)X 4113(incor-)X 648 3042(porated)N 909(in)X 2 f 991(glimpse)X 1 f 1260(rather)X 1468(easily.)X 1715(We)X 1847(believe)X 2099(that)X 2239(customization)X 2708(is)X 2781(the)X 2899(key)X 3035(to)X 3117(better)X 3320(search)X 3546(facilities.)X 6 f 14 s 648 3314(Acknowledgem)N 1467(ents)X 1 f 10 s 648 3467(Burra)N 851(Gopal)X 1067(found)X 1274(and)X 1410(corrected)X 1730(several)X 1978(bugs)X 2149(in)X 2231(the)X 2349(code.)X 2561(We)X 2693(thank)X 2891(Greg)X 3072(Andrews,)X 3402(George)X 3659(Forman,)X 3949(and)X 4086(Trevor)X 648 3587(Jenkins)N 908(for)X 1022(comments)X 1371(that)X 1511(improved)X 1838(the)X 1956(manuscript.)X 6 f 14 s 648 3859(References)N 1 f 10 s 648 4012([BN91])N 848 4132(Bradford)N 1168(R.,)X 1291(and)X 1437(T.)X 1536(Nartker,)X 1832(``Error)X 2086(correlation)X 2464(in)X 2556(contemporary)X 3032(OCR)X 3226(systems,'')X 2 f 3583(Proc.)X 3789(of)X 3881(the)X 4010(First)X 4196(Int.)X 848 4252(Conf.)N 1043(on)X 1143(Document)X 1493(Analysis)X 1784(and)X 1924(Recognition,)X 1 f 2351(\(1991\),)X 2605(pp.)X 2725(516)X 9 f (-)S 1 f 2889(523.)X 648 4405([Fa85])N 848 4525(Faloutsos)N 1174(C.,)X 1287(``Access)X 1589(methods)X 1880(for)X 1994(text,'')X 2 f 2208(ACM)X 2397(Computing)X 2772(Surveys,)X 3 f 3062(17)X 1 f 3162(\(March)X 3419(1985\),)X 3646(pp.)X 3766(49)X 9 f (-)S 1 f 3890(74.)X 648 4678([GB91])N 848 4798(Gonnet,)N 1127(G.)X 1228(H.)X 1329(and)X 1468(R.)X 1564(A.)X 1665(Baeza-Yates,)X 2 f 2115(Handbook)X 2472(of)X 2558(Algorithms)X 2937(and)X 3081(Data)X 3265(Structures)X 1 f 3618(\(Chap.)X 3858(7.2.6\))X 4069(Second)X 848 4918(Edition,)N 1123(Addison-Wesley,)X 1702(Reading,)X 2009(MA,)X 2178(1991.)X 648 5071([HS93])N 848 5191(Hardy)N 1076(D.)X 1181(R.,)X 1301(and)X 1444(M.)X 1562(F.)X 1653(Schwartz,)X 1999(``Essence:)X 2361(A)X 2447(resource)X 2748(discovery)X 3088(system)X 3338(based)X 3549(on)X 3657(semantic)X 3970(\256le)X 4100(index-)X 848 5311(ing,'')N 2 f 1044(Proc.)X 1240(of)X 1322(the)X 1440(USENIX)X 1736(Winter)X 1974(Conference,)X 1 f 2384(San)X 2524(Diego)X 2740(\(January)X 3037(1993\),)X 3264(pp.)X 3384(361)X 9 f (-)S 1 f 3548(374.)X 648 5464([Ma93])N 848 5584(Manber)N 1119(U.,)X 1238(``A)X 1371(text)X 1512(compression)X 1938(scheme)X 2200(that)X 2341(allows)X 2571(fast)X 2708(searching)X 3037(directly)X 3303(in)X 3386(the)X 3505(compressed)X 3906(\256le,'')X 4104(techn-)X 848 5704(ical)N 984(report)X 1196(93-07,)X 1423(Department)X 1822(of)X 1909(Computer)X 2249(Science,)X 2539(University)X 2897(of)X 2984(Arizona)X 3263(\(March)X 3520(1993\).)X 10 p %%Page: 10 11 10 s 10 xH 0 xS 1 f 3 f 2436 408(10)N 1 f 648 696([RKN92])N 848 816(Rice,)N 1040(S.)X 1129(V.,)X 1253(J.)X 1330(Kanai,)X 1568(and)X 1710(T.)X 1805(A.)X 1909(Nartker,)X 2201(``A)X 2339(report)X 2557(on)X 2663(the)X 2787(accuracy)X 3100(of)X 3193(OCR)X 3383(devices,'')X 3724(Technical)X 4067(Report,)X 848 936(Information)N 1251(Science)X 1521(Research)X 1836(Institute,)X 2138(University)X 2496(of)X 2583(Nevada,)X 2869(Las)X 3005(Vegas,)X 3246(1992.)X 648 1089([SM83])N 848 1209(Salton)N 1085(G.,)X 1216(and)X 1366(M.)X 1491(J.)X 1576(McGill,)X 2 f 1861(Introduction)X 2295(to)X 2391(Modern)X 2679(Information)X 3095(Retrieval,)X 1 f 3443(McGraw-Hill,)X 3934(New)X 4120(York,)X 848 1329(1983.)N 648 1482([Te82])N 848 1602(Teskey,)N 1120(F.)X 1204(N.,)X 2 f 1322(Principle)X 1640(of)X 1722(Text)X 1880(Processing,)X 1 f 2276(Ellis)X 2442(Horwood)X 2765(Pub.,)X 2949(1982.)X 648 1755([WM92a])N 848 1875(Wu)N 998(S.)X 1096(and)X 1246(U.)X 1358(Manber,)X 1662(``Agrep)X 1951(\320)X 2065(A)X 2157(Fast)X 2324(Approximate)X 2781(Pattern-Matching)X 3376(Tool,'')X 2 f 3635(Usenix)X 3892(Winter)X 4145(1992)X 848 1995(Technical)N 1184(Conference,)X 1 f 1594(San)X 1734(Francisco)X 2066(\(January)X 2363(1992\),)X 2590(pp.)X 2710(153)X 9 f (-)S 1 f 2874(162.)X 648 2148([WM92b])N 848 2268(Wu)N 985(S.,)X 1090(and)X 1227(U.)X 1326(Manber,)X 1617(``Fast)X 1825(Text)X 1994(Searching)X 2337(Allowing)X 2661(Errors,'')X 2 f 2958(Communications)X 3522(of)X 3606(the)X 3726(ACM)X 3 f 3917(35)X 1 f 4019(\(October)X 848 2388(1992\),)N 1075(pp.)X 1195(83)X 9 f (-)S 1 f 1319(91.)X 11 p %%Trailer xt %%Pages: 11 %%DocumentNeededResources: font Times-Roman Times-Italic Times-Bold %%+ Times-BoldItalic Helvetica Helvetica-Bold Courier Courier-Bold Symbol xs .