« back to all changes in this revision
Viewing changes to debian/doc/agrep.ps.2
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Daniel Baumann
- Date: 2006-07-05 13:29:00 UTC
- mfrom: (3.1.1 dapper)
- Revision ID: james.westby@ubuntu.com-20060705132900-j24rz8zdk4xqdmoz
Tags: 4.17-3
* New email address.
* Some packaging style changes.
* Some packaging style changes.
- files added:
- Makefile.NeXT
- debian/doc
- debian/patches
- save
- files removed:
- agrep.ps.1
- files modified:
- COPYRIGHT
added
removed
debian/doc/agrep.ps.2
1
%!PS-Adobe-1.0
2
%%Creator: optima:sw (Sun Wu)
3
%%Title: stdin (ditroff)
4
%%CreationDate: Thu Jan 9 13:58:28 1992
5
%%EndComments
6
% Start of psdit.pro -- prolog for ditroff translator
7
% Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved.
8
% GOVERNMENT END USERS: See Notice file in TranScript library directory
9
% -- probably /usr/lib/ps/Notice
10
% RCS: $Header: psdit.pro,v 2.2 87/11/17 16:40:42 byron Rel $
11
% Psfig RCSID $Header: psdit.pro,v 1.5 88/01/04 17:48:22 trevor Exp $
12
/$DITroff 180 dict def $DITroff begin
13
14
/DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap
15
currentlinejoin currentdash currentgray currentmiterlimit ] cvx def
16
17
%% Psfig additions
18
/startFig {
19
/SavedState save def
20
userdict maxlength dict begin
21
currentpoint transform
22
23
DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap
24
setlinewidth setmatrix
25
26
itransform moveto
27
28
/ury exch def
29
/urx exch def
30
/lly exch def
31
/llx exch def
32
/y exch 72 mul resolution div def
33
/x exch 72 mul resolution div def
34
35
currentpoint /cy exch def /cx exch def
36
37
/sx x urx llx sub div def % scaling for x
38
/sy y ury lly sub div def % scaling for y
39
40
sx sy scale % scale by (sx,sy)
41
42
cx sx div llx sub
43
cy sy div ury sub translate
44
45
/DefFigCTM matrix currentmatrix def
46
47
/initmatrix {
48
DefFigCTM setmatrix
49
} def
50
/defaultmatrix {
51
DefFigCTM exch copy
52
} def
53
54
/initgraphics {
55
DocumentInitState setmiterlimit setgray setdash
56
setlinejoin setlinecap setlinewidth setmatrix
57
DefFigCTM setmatrix
58
} def
59
60
/showpage {
61
initgraphics
62
} def
63
64
} def
65
% Args are llx lly urx ury (in figure coordinates)
66
/clipFig {
67
currentpoint 6 2 roll
68
newpath 4 copy
69
4 2 roll moveto
70
6 -1 roll exch lineto
71
exch lineto
72
exch lineto
73
closepath clip
74
newpath
75
moveto
76
} def
77
% doclip, if called, will always be just after a `startfig'
78
/doclip { llx lly urx ury clipFig } def
79
/endFig {
80
end SavedState restore
81
} def
82
/globalstart {
83
% Push details about the enviornment on the stack.
84
fontnum fontsize fontslant fontheight
85
% firstpage
86
mh my resolution slotno currentpoint
87
pagesave restore gsave
88
} def
89
/globalend {
90
grestore moveto
91
/slotno exch def /resolution exch def /my exch def
92
/mh exch def
93
% /firstpage exch def
94
/fontheight exch def
95
/fontslant exch def /fontsize exch def /fontnum exch def
96
F
97
/pagesave save def
98
} def
99
100
%% end XMOD additions
101
102
/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
103
/xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
104
/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
105
/pagesave save def}def
106
/PB{save /psv exch def currentpoint translate
107
resolution 72 div dup neg scale 0 0 moveto}def
108
/PE{psv restore}def
109
/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
110
/tan{dup sin exch cos div}bind def
111
/point{resolution 72 div mul}bind def
112
/dround {transform round exch round exch itransform}bind def
113
/xT{/devname exch def}def
114
/xr{/mh exch def /my exch def /resolution exch def}def
115
/xp{}def
116
/xs{docsave restore end}def
117
/xt{}def
118
/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
119
{fonts slotno fontname findfont put fontnames slotno fontname put}if}def
120
/xH{/fontheight exch def F}bind def
121
/xS{/fontslant exch def F}bind def
122
/s{/fontsize exch def /fontheight fontsize def F}bind def
123
/f{/fontnum exch def F}bind def
124
/F{fontheight 0 le {/fontheight fontsize def}if
125
fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
126
fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
127
makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def
128
/X{exch currentpoint exch pop moveto show}bind def
129
/N{3 1 roll moveto show}bind def
130
/Y{exch currentpoint pop exch moveto show}bind def
131
/S /show load def
132
/ditpush{}def/ditpop{}def
133
/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def
134
/AN{4 2 roll moveto 0 exch ashow}bind def
135
/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def
136
/AS{0 exch ashow}bind def
137
/MX{currentpoint exch pop moveto}bind def
138
/MY{currentpoint pop exch moveto}bind def
139
/MXY /moveto load def
140
/cb{pop}def % action on unknown char -- nothing for now
141
/n{}def/w{}def
142
/p{pop showpage pagesave restore /pagesave save def}def
143
/abspoint{currentpoint exch pop add exch currentpoint pop add exch}def
144
/dstroke{currentpoint stroke moveto}bind def
145
/Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def
146
/arcellipse{oldmat currentmatrix pop
147
currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
148
rad 0 rad -180 180 arc oldmat setmatrix}def
149
/Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke
150
grestore diamh 0 rmoveto}def
151
/De{gsave /diamv exch def /diamh exch def arcellipse dstroke
152
grestore diamh 0 rmoveto}def
153
/Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def
154
/cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def
155
/ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add
156
2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def
157
/Barray 200 array def % 200 values in a wiggle
158
/D~{mark}def
159
/D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop
160
/Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and
161
{Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def
162
Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put
163
Bcontrol Blen 2 sub 2 copy get 2 mul put
164
Bcontrol Blen 1 sub 2 copy get 2 mul put
165
/Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub
166
{/i exch def
167
Bcontrol i get 3 div Bcontrol i 1 add get 3 div
168
Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div
169
Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div
170
/Xbi Xcont Bcontrol i 2 add get 2 div add def
171
/Ybi Ycont Bcontrol i 3 add get 2 div add def
172
/Xcont Xcont Bcontrol i 2 add get add def
173
/Ycont Ycont Bcontrol i 3 add get add def
174
Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto
175
}for dstroke}if}def
176
end
177
/ditstart{$DITroff begin
178
/nfonts 60 def % NFONTS makedev/ditroff dependent!
179
/fonts[nfonts{0}repeat]def
180
/fontnames[nfonts{()}repeat]def
181
/docsave save def
182
}def
183
184
% character outcalls
185
/oc {/pswid exch def /cc exch def /name exch def
186
/ditwid pswid fontsize mul resolution mul 72000 div def
187
/ditsiz fontsize resolution mul 72 div def
188
ocprocs name known{ocprocs name get exec}{name cb}
189
ifelse}def
190
/fractm [.65 0 0 .6 0 0] def
191
/fraction
192
{/fden exch def /fnum exch def gsave /cf currentfont def
193
cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
194
fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
195
grestore ditwid 0 rmoveto} def
196
/oce {grestore ditwid 0 rmoveto}def
197
/dm {ditsiz mul}def
198
/ocprocs 50 dict def ocprocs begin
199
(14){(1)(4)fraction}def
200
(12){(1)(2)fraction}def
201
(34){(3)(4)fraction}def
202
(13){(1)(3)fraction}def
203
(23){(2)(3)fraction}def
204
(18){(1)(8)fraction}def
205
(38){(3)(8)fraction}def
206
(58){(5)(8)fraction}def
207
(78){(7)(8)fraction}def
208
(sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def
209
(is){gsave 0 .15 dm rmoveto(\362)show oce}def
210
(->){gsave 0 .02 dm rmoveto(\256)show oce}def
211
(<-){gsave 0 .02 dm rmoveto(\254)show oce}def
212
(==){gsave 0 .05 dm rmoveto(\272)show oce}def
213
end
214
% DIThacks fonts for some special chars
215
50 dict dup begin
216
/FontType 3 def
217
/FontName /DIThacks def
218
/FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def
219
/FontBBox [-220 -280 900 900] def% a lie but ...
220
/Encoding 256 array def
221
0 1 255{Encoding exch /.notdef put}for
222
Encoding
223
dup 8#040/space put %space
224
dup 8#110/rc put %right ceil
225
dup 8#111/lt put %left top curl
226
dup 8#112/bv put %bold vert
227
dup 8#113/lk put %left mid curl
228
dup 8#114/lb put %left bot curl
229
dup 8#115/rt put %right top curl
230
dup 8#116/rk put %right mid curl
231
dup 8#117/rb put %right bot curl
232
dup 8#120/rf put %right floor
233
dup 8#121/lf put %left floor
234
dup 8#122/lc put %left ceil
235
dup 8#140/sq put %square
236
dup 8#141/bx put %box
237
dup 8#142/ci put %circle
238
dup 8#143/br put %box rule
239
dup 8#144/rn put %root extender
240
dup 8#145/vr put %vertical rule
241
dup 8#146/ob put %outline bullet
242
dup 8#147/bu put %bullet
243
dup 8#150/ru put %rule
244
dup 8#151/ul put %underline
245
pop
246
/DITfd 100 dict def
247
/BuildChar{0 begin
248
/cc exch def /fd exch def
249
/charname fd /Encoding get cc get def
250
/charwid fd /Metrics get charname get def
251
/charproc fd /CharProcs get charname get def
252
charwid 0 fd /FontBBox get aload pop setcachedevice
253
40 setlinewidth
254
newpath 0 0 moveto gsave charproc grestore
255
end}def
256
/BuildChar load 0 DITfd put
257
%/UniqueID 5 def
258
/CharProcs 50 dict def
259
CharProcs begin
260
/space{}def
261
/.notdef{}def
262
/ru{500 0 rls}def
263
/rn{0 750 moveto 500 0 rls}def
264
/vr{20 800 moveto 0 -770 rls}def
265
/bv{20 800 moveto 0 -1000 rls}def
266
/br{20 770 moveto 0 -1040 rls}def
267
/ul{0 -250 moveto 500 0 rls}def
268
/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
269
/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
270
/sq{80 0 rmoveto currentpoint dround newpath moveto
271
640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
272
/bx{80 0 rmoveto currentpoint dround newpath moveto
273
640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
274
/ci{355 333 rmoveto currentpoint newpath 333 0 360 arc
275
50 setlinewidth stroke}def
276
277
/lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
278
/lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
279
/rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
280
/rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
281
/lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub
282
currentpoint stroke moveto
283
20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def
284
/rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub
285
currentpoint stroke moveto
286
20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def
287
/lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def
288
/rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
289
/lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def
290
/rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
291
end
292
293
/Metrics 50 dict def Metrics begin
294
/.notdef 0 def
295
/space 500 def
296
/ru 500 def
297
/br 0 def
298
/lt 250 def
299
/lb 250 def
300
/rt 250 def
301
/rb 250 def
302
/lk 250 def
303
/rk 250 def
304
/rc 250 def
305
/lc 250 def
306
/rf 250 def
307
/lf 250 def
308
/bv 250 def
309
/ob 350 def
310
/bu 350 def
311
/ci 750 def
312
/bx 750 def
313
/sq 750 def
314
/rn 500 def
315
/ul 500 def
316
/vr 0 def
317
end
318
319
DITfd begin
320
/s2 500 def /s4 250 def /s3 333 def
321
/a4p{arcto pop pop pop pop}def
322
/2cx{2 copy exch}def
323
/rls{rlineto stroke}def
324
/currx{currentpoint pop}def
325
/dround{transform round exch round exch itransform} def
326
end
327
end
328
/DIThacks exch definefont pop
329
330
ditstart
331
(psc)xT
332
576 1 1 xr
333
1(Times-Roman)xf 1 f
334
2(Times-Italic)xf 2 f
335
3(Times-Bold)xf 3 f
336
4(Times-BoldItalic)xf 4 f
337
5(Helvetica)xf 5 f
338
6(Helvetica-Bold)xf 6 f
339
7(Courier)xf 7 f
340
8(Courier-Bold)xf 8 f
341
9(Symbol)xf 9 f
342
10(DIThacks)xf 10 f
343
10 s
344
1 f
345
xi
346
%%EndProlog
347
348
%%Page: 1 1
349
10 s 10 xH 0 xS 1 f
350
3 f
351
12 s
352
1025 816(AGREP)N
353
1385(\320)X
354
1505(A)X
355
1598(FAST)X
356
1867(APPROXIMATE)X
357
2616(PATTERN-MATCHING)X
358
3679(TOOL)X
359
1 f
360
10 s
361
2147 1000(\(Preliminary)N
362
2572(version\))X
363
2064 1200(Sun)N
364
2208(Wu)X
365
2344(and)X
366
2480(Udi)X
367
2620(Manber)X
368
7 s
369
2870 1168(1)N
370
10 s
371
1953 1384(Department)N
372
2352(of)X
373
2439(Computer)X
374
2779(Science)X
375
2139 1504(University)N
376
2497(of)X
377
2584(Arizona)X
378
2189 1624(Tucson,)N
379
2465(AZ)X
380
2592(85721)X
381
2073 1744(\(sw)N
382
9 f
383
2209(|)X
384
1 f
385
2245(udi\)@cs.arizona.edu)X
386
4 f
387
2287 2194(ABSTRACT)N
388
1 f
389
648 2447(Searching)N
390
995(for)X
391
1115(a)X
392
1178(pattern)X
393
1428(in)X
394
1517(a)X
395
1580(text)X
396
1727(\256le)X
397
1856(is)X
398
1936(a)X
399
1999(very)X
400
2169(common)X
401
2476(operation)X
402
2806(in)X
403
2895(many)X
404
3100(applications)X
405
3514(ranging)X
406
3786(from)X
407
3969(text)X
408
4116(editors)X
409
648 2557(and)N
410
796(databases)X
411
1136(to)X
412
1230(applications)X
413
1649(in)X
414
1743(molecular)X
415
2096(biology.)X
416
2412(In)X
417
2511(many)X
418
2721(instances)X
419
3047(the)X
420
3177(pattern)X
421
3432(does)X
422
3611(not)X
423
3745(appear)X
424
3992(in)X
425
4085(the)X
426
4214(text)X
427
648 2667(exactly.)N
428
943(Errors)X
429
1167(in)X
430
1252(the)X
431
1373(text)X
432
1516(or)X
433
1606(in)X
434
1691(the)X
435
1812(query)X
436
2018(can)X
437
2153(result)X
438
2354(from)X
439
2533(misspelling)X
440
2925(or)X
441
3016(from)X
442
3196(experimental)X
443
3639(errors)X
444
3851(\(e.g.,)X
445
4038(when)X
446
4236(the)X
447
648 2777(text)N
448
796(is)X
449
877(a)X
450
941(DNA)X
451
1143(sequence\).)X
452
1533(The)X
453
1686(use)X
454
1821(of)X
455
1916(such)X
456
2091(approximate)X
457
2520(pattern)X
458
2771(matching)X
459
3096(has)X
460
3230(been)X
461
3409(limited)X
462
3662(until)X
463
3835(now)X
464
4000(to)X
465
4089(speci\256c)X
466
648 2887(applications.)N
467
1099(Most)X
468
1287(text)X
469
1431(editors)X
470
1673(and)X
471
1813(searching)X
472
2145(programs)X
473
2472(do)X
474
2576(not)X
475
2702(support)X
476
2966(searching)X
477
3298(with)X
478
3464(errors)X
479
3676(because)X
480
3955(of)X
481
4046(the)X
482
4169(com-)X
483
648 2997(plexity)N
484
896(involved)X
485
1202(in)X
486
1290(implementing)X
487
1760(it.)X
488
1870(In)X
489
1963(this)X
490
2104(paper)X
491
2309(we)X
492
2429(describe)X
493
2723(a)X
494
2785(new)X
495
2945(tool,)X
496
3115(called)X
497
2 f
498
3333(agrep)X
499
1 f
500
3520(,)X
501
3566(for)X
502
3685(approximate)X
503
4111(pattern)X
504
648 3107(matching.)N
505
1014(Agrep)X
506
1243(is)X
507
1325(based)X
508
1537(on)X
509
1646(a)X
510
1711(new)X
511
1874(ef\256cient)X
512
2166(and)X
513
2311(\257exible)X
514
2580(algorithm)X
515
2920(for)X
516
3043(approximate)X
517
3473(string)X
518
3684(matching.)X
519
4051(Agrep)X
520
4281(is)X
521
648 3217(also)N
522
808(competitive)X
523
1217(with)X
524
1390(other)X
525
1586(tools)X
526
1772(for)X
527
1897(exact)X
528
2098(string)X
529
2311(matching;)X
530
2662(it)X
531
2737(include)X
532
3004(many)X
533
3212(options)X
534
3477(that)X
535
3627(make)X
536
3831(searching)X
537
4169(more)X
538
648 3327(powerful)N
539
958(and)X
540
1094(convenient.)X
541
6 f
542
14 s
543
648 3579(1.)N
544
803(Introduction)X
545
1 f
546
10 s
547
648 3754(The)N
548
797(most)X
549
976(common)X
550
1280(string-searching)X
551
1821(problem)X
552
2112(is)X
553
2189(to)X
554
2275(\256nd)X
555
2423(all)X
556
2527 0.3125(occurrences)AX
557
2936(of)X
558
3027(a)X
559
3087(string)X
560
2 f
561
3293(P)X
562
9 f
563
3361(=)X
564
2 f
565
3418(p)X
566
1 f
567
7 s
568
3467 3770(1)N
569
2 f
570
10 s
571
3501 3754(p)N
572
1 f
573
7 s
574
3550 3770(2)N
575
2 f
576
10 s
577
3584 3754(...p)N
578
7 s
579
3770(m)Y
580
1 f
581
10 s
582
3754 3754(inside)N
583
3969(a)X
584
4029(large)X
585
4214(text)X
586
648 3864(\256le)N
587
2 f
588
771(T)X
589
9 f
590
834(=)X
591
2 f
592
891(t)X
593
1 f
594
7 s
595
922 3880(1)N
596
2 f
597
10 s
598
956 3864(t)N
599
1 f
600
7 s
601
987 3880(2)N
602
10 s
603
1041 3840(.)N
604
1081(.)X
605
1121(.)X
606
2 f
607
1161 3864(t)N
608
7 s
609
1183 3880(n)N
610
1 f
611
10 s
612
1217 3864(.)N
613
1258(We)X
614
1391(assume)X
615
1648(that)X
616
1789(the)X
617
1908(string)X
618
2111(and)X
619
2248(the)X
620
2367(text)X
621
2508(are)X
622
2628(sequences)X
623
2975(of)X
624
2 f
625
3063(characters)X
626
1 f
627
3426(from)X
628
3602(a)X
629
3658(\256nite)X
630
3842(character)X
631
4158(set)X
632
2 f
633
9 f
634
4267(S)X
635
1 f
636
4314(.)X
637
648 3974(The)N
638
803(characters)X
639
1160(may)X
640
1328(be)X
641
1434(English)X
642
1708(characters)X
643
2065(in)X
644
2157(a)X
645
2223(text)X
646
2373(\256le,)X
647
2525(DNA)X
648
2729(base)X
649
2902(pairs,)X
650
3108(lines)X
651
3289(of)X
652
3386(source)X
653
3627(code,)X
654
3830(angles)X
655
4066(between)X
656
648 4084(edges)N
657
852(in)X
658
935(polygons,)X
659
1269(machines)X
660
1593(or)X
661
1681(machine)X
662
1974(parts)X
663
2151(in)X
664
2234(a)X
665
2291(production)X
666
2659(schedule,)X
667
2981(music)X
668
3192(notes)X
669
3381(and)X
670
3517(tempo)X
671
3737(in)X
672
3819(a)X
673
3875(musical)X
674
4144(score,)X
675
648 4194(etc.)N
676
811(The)X
677
965(two)X
678
1114(most)X
679
1298(famous)X
680
1564(algorithms)X
681
1936(for)X
682
2060(this)X
683
2205(problem)X
684
2502(are)X
685
2631(the)X
686
2759(Knuth-Morris-Pratt)X
687
3412(algorithm)X
688
3753([KMP77])X
689
4090(and)X
690
4236(the)X
691
648 4304(Boyer-Moore)N
692
1113(algorithm)X
693
1452([BM77])X
694
1738(\(see)X
695
1896(also)X
696
2053([Ba89])X
697
2304(and)X
698
2448([HS91]\).)X
699
2759(There)X
700
2975(are)X
701
3102(many)X
702
3308(extensions)X
703
3673(to)X
704
3762(this)X
705
3904(problem;)X
706
4240(for)X
707
648 4414(example,)N
708
965(we)X
709
1084(may)X
710
1247(be)X
711
1348(looking)X
712
1617(for)X
713
1736(a)X
714
1797(set)X
715
1911(of)X
716
2003(patterns,)X
717
2303(a)X
718
2365(regular)X
719
2619(expression,)X
720
3008(a)X
721
3070(pattern)X
722
3319(with)X
723
3487(``wild)X
724
3709(cards,'')X
725
3979(etc.)X
726
4139(String)X
727
648 4524(searching)N
728
976(in)X
729
1058(Unix)X
730
1238(is)X
731
1311(most)X
732
1486(often)X
733
1671(done)X
734
1847(with)X
735
2009(the)X
736
2 f
737
2127(grep)X
738
1 f
739
2294(family.)X
740
848 4667(In)N
741
936(some)X
742
1126(instances,)X
743
1461(however,)X
744
1779(the)X
745
1898(pattern)X
746
2142(and/or)X
747
2368(the)X
748
2487(text)X
749
2628(are)X
750
2748(not)X
751
2871(exact.)X
752
3102(We)X
753
3235(may)X
754
3394(not)X
755
3518(remember)X
756
3866(the)X
757
3986(exact)X
758
4178(spel-)X
759
648 4777(ling)N
760
794(of)X
761
882(a)X
762
939(name)X
763
1134(we)X
764
1249(are)X
765
1369(searching,)X
766
1718(the)X
767
1837(name)X
768
2032(may)X
769
2191(be)X
770
2288(misspelled)X
771
2651(in)X
772
2734(the)X
773
2853(text,)X
774
3014(the)X
775
3133(text)X
776
3274(may)X
777
3433(correspond)X
778
3811(to)X
779
3894(a)X
780
3951(sequence)X
781
4267(of)X
782
648 4887(numbers)N
783
959(with)X
784
1136(a)X
785
1207(certain)X
786
1461(property)X
787
1768(and)X
788
1919(we)X
789
2048(do)X
790
2163(not)X
791
2300(have)X
792
2487(an)X
793
2598(exact)X
794
2803(pattern,)X
795
3081(the)X
796
3214(text)X
797
3369(may)X
798
3542(be)X
799
3654(a)X
800
3726(sequence)X
801
4057(of)X
802
4160(DNA)X
803
648 4997(molecules)N
804
998(and)X
805
1139(we)X
806
1258(are)X
807
1382(looking)X
808
1651(for)X
809
1770(approximate)X
810
2195(patterns,)X
811
2493(etc.)X
812
2651(The)X
813
2800(approximate)X
814
3225(string-matching)X
815
3756(problem)X
816
4047(is)X
817
4124(to)X
818
4210(\256nd)X
819
648 5107(all)N
820
757(substrings)X
821
1110(in)X
822
2 f
823
1201(T)X
824
1 f
825
1274(that)X
826
1423(are)X
827
2 f
828
1551(close)X
829
1 f
830
1745(to)X
831
2 f
832
1836(P)X
833
1 f
834
1914(under)X
835
2126(some)X
836
2324(measure)X
837
2621(of)X
838
2717(closeness.)X
839
3089(We)X
840
3230(will)X
841
3383(concentrate)X
842
3783(here)X
843
3951(on)X
844
4060(the)X
845
4187(edit-)X
846
648 5217(distance)N
847
936(measure)X
848
1229(\(also)X
849
1410(known)X
850
1653(as)X
851
1744(the)X
852
2 f
853
1866(Levenshtein)X
854
2273(measure)X
855
1 f
856
2545(\).)X
857
2636(A)X
858
2718(string)X
859
2 f
860
2924(P)X
861
1 f
862
2997(is)X
863
3074(said)X
864
3227(to)X
865
3313(be)X
866
3413(of)X
867
3504(distance)X
868
2 f
869
3791(k)X
870
1 f
871
3851(to)X
872
3937(a)X
873
3997(string)X
874
2 f
875
4203(Q)X
876
1 f
877
4285(if)X
878
648 5327(we)N
879
764(can)X
880
898(transform)X
881
2 f
882
1232(P)X
883
1 f
884
1303(to)X
885
1387(be)X
886
1485(equal)X
887
1681(to)X
888
2 f
889
1765(Q)X
890
1 f
891
1845(with)X
892
2009(a)X
893
2067(sequence)X
894
2384(of)X
895
2 f
896
2473(k)X
897
1 f
898
2531(insertions)X
899
2864(of)X
900
2953(single)X
901
3167(characters)X
902
3517(in)X
903
3602(\(arbitrary)X
904
3929(places)X
905
4153(in\))X
906
2 f
907
4265(P)X
908
1 f
909
4314(,)X
910
8 s
911
10 f
912
648 5423(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)N
913
5 s
914
1 f
915
648 5525(1)N
916
8 s
917
684 5550(Supported)N
918
963(in)X
919
1029(part)X
920
1144(by)X
921
1224(an)X
922
1300(NSF)X
923
1434(Presidential)X
924
1753(Young)X
925
1944(Investigator)X
926
2266(Award)X
927
2456(\(grant)X
928
2625(DCR-8451397\),)X
929
3056(with)X
930
3187(matching)X
931
3442(funds)X
932
3601(from)X
933
3742(AT&T,)X
934
3949(and)X
935
4058(by)X
936
4139(an)X
937
4216(NSF)X
938
648 5646(grant)N
939
795(CCR-9002351.)X
940
941
2 p
942
%%Page: 2 2
943
8 s 8 xH 0 xS 1 f
944
10 s
945
3 f
946
1 f
947
648 686(deletions)N
948
958(of)X
949
1046(single)X
950
1258(characters)X
951
1606(in)X
952
2 f
953
1689(P)X
954
1 f
955
1738(,)X
956
1779(or)X
957
1867(substitutions)X
958
2291(of)X
959
2379(characters.)X
960
2767(Sometimes)X
961
3143(one)X
962
3280(wants)X
963
3489(to)X
964
3573(vary)X
965
3738(the)X
966
3858(cost)X
967
4009(of)X
968
4098(the)X
969
4218(dif-)X
970
648 796(ferent)N
971
856(edit)X
972
996(operations,)X
973
1370(say)X
974
1497(deletions)X
975
1806(cost)X
976
1955(3,)X
977
2035(insertions)X
978
2366(2,)X
979
2446(and)X
980
2582(substitutions)X
981
3005(1.)X
982
848 939(Many)N
983
1065(different)X
984
1372(approximate)X
985
1803(string-matching)X
986
2340(algorithms)X
987
2712(have)X
988
2895(been)X
989
3078(suggested)X
990
3425(\(too)X
991
3585(many)X
992
3794(to)X
993
3887(list)X
994
4015(here\),)X
995
4232(but)X
996
648 1049(none)N
997
831(is)X
998
911(widely)X
999
1156(used,)X
1000
1350(mainly)X
1001
1599(because)X
1002
1881(of)X
1003
1975(their)X
1004
2149(complexity)X
1005
2536(and/or)X
1006
2767(lack)X
1007
2927(of)X
1008
3020(generality.)X
1009
3407(We)X
1010
3545(present)X
1011
3803(here)X
1012
3968(a)X
1013
4030(new)X
1014
4190(tool,)X
1015
648 1159(called)N
1016
2 f
1017
863(agrep)X
1018
1 f
1019
1073(\(for)X
1020
2 f
1021
1217(approximate)X
1022
1 f
1023
1646(grep\),)X
1024
1860(which)X
1025
2080(has)X
1026
2211(a)X
1027
2271(very)X
1028
2438(similar)X
1029
2684(user)X
1030
2842(interface)X
1031
3148(to)X
1032
3234(the)X
1033
3356(grep)X
1034
3523(family)X
1035
3756(\(although)X
1036
4087(it)X
1037
4155(is)X
1038
4232(not)X
1039
648 1269(100%)N
1040
858(compatible\),)X
1041
1284(and)X
1042
1423(which)X
1043
1642(supports)X
1044
1936(several)X
1045
2187(important)X
1046
2521(extensions)X
1047
2882(to)X
1048
2967(grep.)X
1049
3173(Version)X
1050
3450(1.0)X
1051
3573(of)X
1052
3663(agrep)X
1053
3865(is)X
1054
3941(available)X
1055
4254(by)X
1056
648 1379(anonymous)N
1057
1055(ftp)X
1058
1182(from)X
1059
1376(cs.arizona.edu)X
1060
1874(\(IP)X
1061
2010(192.12.69.5\))X
1062
2455(as)X
1063
2560 0.1912(agrep/agrep.tar.Z.)AX
1064
3192(It)X
1065
3279(has)X
1066
3424(been)X
1067
3614(developed)X
1068
3982(on)X
1069
4100(a)X
1070
4174(SUN)X
1071
648 1489(SparcStation)N
1072
1080(and)X
1073
1219(has)X
1074
1349(been)X
1075
1524(successfully)X
1076
1939(ported)X
1077
2167(to)X
1078
2252(DECstation)X
1079
2648(5000,)X
1080
2851(NeXT,)X
1081
3094(Sequent,)X
1082
3394(HP)X
1083
3518(9000,)X
1084
3720(and)X
1085
3858(Silicon)X
1086
4106(Graph-)X
1087
648 1599(ics)N
1088
758(workstations.)X
1089
1208(We)X
1090
1341(expect)X
1091
1572(version)X
1092
1829(2.0)X
1093
1950(to)X
1094
2033(be)X
1095
2130(available)X
1096
2441(\(at)X
1097
2547(the)X
1098
2666(same)X
1099
2852(place\))X
1100
3070(by)X
1101
3171(the)X
1102
3290(end)X
1103
3428(of)X
1104
3517(1991;)X
1105
3721(most)X
1106
3898(of)X
1107
3987(the)X
1108
4107(discus-)X
1109
648 1709(sion)N
1110
802(here)X
1111
962(refers)X
1112
1167(to)X
1113
1250(version)X
1114
1507(2.)X
1115
1608(The)X
1116
1754(three)X
1117
1936(most)X
1118
2112(signi\256cant)X
1119
2466(features)X
1120
2741(of)X
1121
2828(agrep)X
1122
3027(that)X
1123
3167(are)X
1124
3286(not)X
1125
3408(supported)X
1126
3744(by)X
1127
3844(the)X
1128
3962(grep)X
1129
4125(family)X
1130
648 1819(are)N
1131
768(1\))X
1132
856(searching)X
1133
1185(for)X
1134
1300(approximate)X
1135
1722(patterns,)X
1136
2017(2\))X
1137
2105(searching)X
1138
2435(for)X
1139
2551(records)X
1140
2810(rather)X
1141
3020(than)X
1142
3180(just)X
1143
3317(lines,)X
1144
3510(and)X
1145
3648(3\))X
1146
3737(searching)X
1147
4067(for)X
1148
4183(mul-)X
1149
648 1929(tiple)N
1150
825(patterns)X
1151
1114(with)X
1152
1291(AND)X
1153
1500(\(or)X
1154
1629(OR\))X
1155
1802(logic)X
1156
1997(queries.)X
1157
2304(\(All)X
1158
2468(3)X
1159
2543(features)X
1160
2833(are)X
1161
2967(available)X
1162
3292(in)X
1163
3389(version)X
1164
3660(1.0.\))X
1165
3862(Other)X
1166
4079(features)X
1167
648 2039(include)N
1168
912(searching)X
1169
1249(for)X
1170
1372(regular)X
1171
1629(expressions)X
1172
2032(\(with)X
1173
2230(or)X
1174
2326(without)X
1175
2599(errors\),)X
1176
2863(ef\256cient)X
1177
3155(multi-pattern)X
1178
3602(search,)X
1179
3857(unlimited)X
1180
4192(wild)X
1181
648 2149(cards,)N
1182
865(limiting)X
1183
1144(the)X
1184
1269(errors)X
1185
1484(to)X
1186
1573(only)X
1187
1742(insertions)X
1188
2080(or)X
1189
2174(only)X
1190
2343(substitutions)X
1191
2773(or)X
1192
2867(any)X
1193
3010(combination,)X
1194
3456(allowing)X
1195
3762(each)X
1196
3936(deletion,)X
1197
4240(for)X
1198
648 2259(example,)N
1199
960(to)X
1200
1042(be)X
1201
1138(counted)X
1202
1412(as,)X
1203
1519(say,)X
1204
1667(2)X
1205
1728(substitutions)X
1206
2152(or)X
1207
2240(3)X
1208
2301(insertions,)X
1209
2653(restricting)X
1210
2999(parts)X
1211
3176(of)X
1212
3264(the)X
1213
3383(query)X
1214
3587(to)X
1215
3670(be)X
1216
3767(exact)X
1217
3958(and)X
1218
4095(parts)X
1219
4272(to)X
1220
648 2369(be)N
1221
744(approximate,)X
1222
1185(and)X
1223
1321(many)X
1224
1519(more.)X
1225
1744(Examples)X
1226
2080(of)X
1227
2167(the)X
1228
2285(use)X
1229
2412(of)X
1230
2499(agrep)X
1231
2698(are)X
1232
2817(given)X
1233
3015(in)X
1234
3097(the)X
1235
3215(next)X
1236
3373(section.)X
1237
848 2512(Agrep)N
1238
1074(not)X
1239
1202(only)X
1240
1370(supports)X
1241
1667(a)X
1242
1729(large)X
1243
1916(number)X
1244
2187(of)X
1245
2280(options,)X
1246
2561(but)X
1247
2689(it)X
1248
2759(is)X
1249
2838(also)X
1250
2993(very)X
1251
3162(ef\256cient.)X
1252
3491(In)X
1253
3584(our)X
1254
3717(experiments,)X
1255
4155(agrep)X
1256
648 2622(was)N
1257
794(competitive)X
1258
1193(with)X
1259
1356(the)X
1260
1475(best)X
1261
1625(exact)X
1262
1815(string-matching)X
1263
2342(tools)X
1264
2517(that)X
1265
2657(we)X
1266
2771(could)X
1267
2969(\256nd)X
1268
3113(\(Hume's)X
1269
3414(gre)X
1270
3537([Hu91])X
1271
3789(and)X
1272
3925(GNU)X
1273
4119(e?grep)X
1274
648 2732([Ha89]\),)N
1275
949(and)X
1276
1091(in)X
1277
1179(many)X
1278
1383(cases)X
1279
1579(one)X
1280
1721(to)X
1281
1810(two)X
1282
1957(orders)X
1283
2185(of)X
1284
2279(magnitude)X
1285
2644(faster)X
1286
2850(than)X
1287
3015(other)X
1288
3207(approximate)X
1289
3635(string-matching)X
1290
4169(algo-)X
1291
648 2842(rithms.)N
1292
913(For)X
1293
1045(example,)X
1294
1358(\256nding)X
1295
1605(all)X
1296
1706 0.3125(occurrences)AX
1297
2112(of)X
1298
2 f
1299
2200(Homogenos)X
1300
1 f
1301
2604(allowing)X
1302
2905(two)X
1303
3046(errors)X
1304
3255(in)X
1305
3338(a)X
1306
3395(1MB)X
1307
3580(bibliographic)X
1308
4028(text)X
1309
4169(takes)X
1310
648 2952(about)N
1311
851(0.2)X
1312
976(seconds)X
1313
1255(on)X
1314
1360(a)X
1315
1421(SUN)X
1316
1606(SparcStation)X
1317
2040(II.)X
1318
2159(\(We)X
1319
2323(actually)X
1320
2602(used)X
1321
2774(this)X
1322
2914(example)X
1323
3211(and)X
1324
3352(found)X
1325
3564(a)X
1326
3626(misspelling)X
1327
4020(in)X
1328
4108(the)X
1329
4232(bib)X
1330
648 3062(\256le.\))N
1331
837(This)X
1332
999(is)X
1333
1072(almost)X
1334
1305(as)X
1335
1392(fast)X
1336
1528(as)X
1337
1615(exact)X
1338
1805(string)X
1339
2007(matching.)X
1340
848 3205(This)N
1341
1010(paper)X
1342
1209(is)X
1343
1282(organized)X
1344
1619(as)X
1345
1706(follows.)X
1346
2006(We)X
1347
2138(start)X
1348
2296(by)X
1349
2396(giving)X
1350
2620(examples)X
1351
2943(of)X
1352
3030(the)X
1353
3148(use)X
1354
3276(of)X
1355
3364(agrep)X
1356
3564(that)X
1357
3705(illustrate)X
1358
4006(how)X
1359
4165(\257exi-)X
1360
648 3315(ble)N
1361
772(and)X
1362
914(general)X
1363
1177(it)X
1364
1247(is.)X
1365
1366(We)X
1366
1504(then)X
1367
1668(brie\257y)X
1368
1903(describe)X
1369
2197(the)X
1370
2321(main)X
1371
2507(ideas)X
1372
2698(behind)X
1373
2942(the)X
1374
3066(algorithms)X
1375
3434(and)X
1376
3576(their)X
1377
3749(extensions.)X
1378
4133(\(More)X
1379
648 3425(details)N
1380
884(are)X
1381
1010(given)X
1382
1215(in)X
1383
1304(the)X
1384
1429(technical)X
1385
1746(report)X
1386
1965(and)X
1387
2108(man)X
1388
2273(pages)X
1389
2483(which)X
1390
2706(are)X
1391
2832(available)X
1392
3149(by)X
1393
3256(ftp.\))X
1394
3439(We)X
1395
3578(then)X
1396
3743(give)X
1397
3909(some)X
1398
4106(experi-)X
1399
648 3535(mental)N
1400
886(results,)X
1401
1135(and)X
1402
1271(we)X
1403
1385(close)X
1404
1570(with)X
1405
1732(conclusions.)X
1406
6 f
1407
14 s
1408
648 3787(2.)N
1409
803(Using)X
1410
1144(Agrep)X
1411
1 f
1412
10 s
1413
648 3962(We)N
1414
782(have)X
1415
956(been)X
1416
1130(using)X
1417
1325(agrep)X
1418
1526(for)X
1419
1642(about)X
1420
1842(6)X
1421
1905(months)X
1422
2163(now)X
1423
2324(and)X
1424
2463(\256nd)X
1425
2610(it)X
1426
2677(an)X
1427
2776(indispensable)X
1428
3235(tool.)X
1429
3402(We)X
1430
3537(present)X
1431
3792(here)X
1432
3954(only)X
1433
4119(a)X
1434
4178(sam-)X
1435
648 4072(ple)N
1436
770(of)X
1437
861(the)X
1438
983(uses)X
1439
1145(that)X
1440
1289(we)X
1441
1407(found.)X
1442
1658(As)X
1443
1771(we)X
1444
1889(said)X
1445
2042(in)X
1446
2128(the)X
1447
2249(introduction,)X
1448
2683(the)X
1449
2804(three)X
1450
2988(most)X
1451
3166(signi\256cant)X
1452
3522(features)X
1453
3800(of)X
1454
3890(agrep)X
1455
4092(that)X
1456
4235(are)X
1457
648 4182(not)N
1458
770(supported)X
1459
1106(by)X
1460
1206(the)X
1461
1324(grep)X
1462
1487(family)X
1463
1716(are)X
1464
648 4325(1.)N
1465
3 f
1466
748(the)X
1467
875(ability)X
1468
1112(to)X
1469
1199(search)X
1470
1442(for)X
1471
1565(approximate)X
1472
2021(patterns)X
1473
1 f
1474
848 4435(for)N
1475
967(example,)X
1476
7 f
1477
1313(agrep)X
1478
1607(-2)X
1479
1757(Homogenos)X
1480
2243(bib)X
1481
1 f
1482
2413(will)X
1483
2563(\256nd)X
1484
2713(Homogeneous)X
1485
3202(as)X
1486
3295(well)X
1487
3459(as)X
1488
3552(any)X
1489
3694(other)X
1490
3885(word)X
1491
4076(that)X
1492
4222(can)X
1493
848 4545(be)N
1494
951(obtained)X
1495
1254(from)X
1496
1437(Homogenos)X
1497
1851(with)X
1498
2019(at)X
1499
2103(most)X
1500
2284(2)X
1501
2350(substitutions,)X
1502
2799(insertions,)X
1503
3156(or)X
1504
3249(deletions.)X
1505
3604(It)X
1506
3679(is)X
1507
3758(possible)X
1508
4046(to)X
1509
4134(assign)X
1510
848 4655(different)N
1511
1147(costs)X
1512
1329(to)X
1513
1413(insertions,)X
1514
1766(deletions,)X
1515
2097(or)X
1516
2186(substitutions.)X
1517
2651(For)X
1518
2784(example,)X
1519
7 f
1520
3126(agrep)X
1521
3416(-1)X
1522
3562(-I2)X
1523
3756(-D2)X
1524
3950(555-3217)X
1525
848 4765(phone)N
1526
1 f
1527
1110(will)X
1528
1256(\256nd)X
1529
1402(all)X
1530
1504(numbers)X
1531
1802(that)X
1532
1944(differ)X
1533
2145(from)X
1534
2323(555-3217)X
1535
2652(in)X
1536
2736(at)X
1537
2816(most)X
1538
2993(one)X
1539
3131(digit.)X
1540
3339(The)X
1541
3485(-I)X
1542
3560(\(-D\))X
1543
3720(option)X
1544
3945(sets)X
1545
4086(the)X
1546
4205(cost)X
1547
848 4875(of)N
1548
935(insertions)X
1549
1266(\(deletions\);)X
1550
1651(in)X
1551
1733(this)X
1552
1868(case,)X
1553
2047(setting)X
1554
2280(it)X
1555
2344(to)X
1556
2426(2)X
1557
2486(prevents)X
1558
2778(insertions)X
1559
3109(and)X
1560
3245(deletions.)X
1561
648 5018(2.)N
1562
3 f
1563
748(agrep)X
1564
964(is)X
1565
1037(record)X
1566
1285(oriented)X
1567
1590(rather)X
1568
1829(than)X
1569
2004(just)X
1570
2153(line)X
1571
2297(oriented)X
1572
1 f
1573
848 5128(a)N
1574
907(record)X
1575
1136(is)X
1576
1212(by)X
1577
1315(default)X
1578
1562(a)X
1579
1622(line,)X
1580
1786(but)X
1581
1912(it)X
1582
1980(can)X
1583
2116(be)X
1584
2216(user)X
1585
2374(de\256ned;)X
1586
2656(for)X
1587
2774(example,)X
1588
7 f
1589
3118(agrep)X
1590
3410(-d)X
1591
3558('\303From)X
1592
3898(')X
1593
3998('pizza')X
1594
848 5238(mbox)N
1595
1 f
1596
1066(outputs)X
1597
1327(all)X
1598
1433(mail)X
1599
1601(messages)X
1600
1929(that)X
1601
2074(contain)X
1602
2335(the)X
1603
2458(keyword)X
1604
2764("pizza".)X
1605
3065(Another)X
1606
3353(example:)X
1607
7 f
1608
3700(agrep)X
1609
3993(-d)X
1610
4142('$$')X
1611
848 5348(pattern)N
1612
1232(foo)X
1613
1 f
1614
1396(will)X
1615
1540(output)X
1616
1764(all)X
1617
1864(paragraphs)X
1618
2237(\(separated)X
1619
2588(by)X
1620
2688(an)X
1621
2784(empty)X
1622
3004(line\))X
1623
3171(that)X
1624
3311(contain)X
1625
3567(pattern.)X
1626
648 5491(3.)N
1627
3 f
1628
748(multiple)X
1629
1052(patterns)X
1630
1357(with)X
1631
1528(AND)X
1632
1722(\(or)X
1633
1845(OR\))X
1634
2012(logic)X
1635
2192(queries)X
1636
1 f
1637
848 5601(For)N
1638
982(example,)X
1639
7 f
1640
1325(agrep)X
1641
1616(-d)X
1642
1763('\303From)X
1643
2102(')X
1644
2201('burger,pizza')X
1645
2924(mbox)X
1646
1 f
1647
3140(outputs)X
1648
3399(all)X
1649
3503(mail)X
1650
3669(messages)X
1651
3996(containing)X
1652
848 5711(at)N
1653
932(least)X
1654
1105(one)X
1655
1247(of)X
1656
1340(the)X
1657
1464(two)X
1658
1609(keywords)X
1659
1946(\(`,')X
1660
2072(stands)X
1661
2297(for)X
1662
2416(OR\);)X
1663
7 f
1664
2629(agrep)X
1665
2922(-d)X
1666
3071('\303From)X
1667
3412(')X
1668
3513('good;pizza')X
1669
4142(mbox)X
1670
1671
3 p
1672
%%Page: 3 3
1673
10 s 10 xH 0 xS 7 f
1674
3 f
1675
1 f
1676
848 686(outputs)N
1677
1103(all)X
1678
1203(mail)X
1679
1365(messages)X
1680
1688(containing)X
1681
2046(both)X
1682
2208(keywords)X
1683
2540(\(`;')X
1684
2663(stands)X
1685
2883(for)X
1686
2997(AND\).)X
1687
648 829(Putting)N
1688
898(these)X
1689
1083(options)X
1690
1338(together)X
1691
1621(one)X
1692
1757(can)X
1693
1889(ask)X
1694
2016(queries)X
1695
2268(like)X
1696
7 f
1697
936 939(agrep)N
1698
1224(-d)X
1699
1368('$$')X
1700
1608(-1)X
1701
1752('<CACM>;TheAuthor;Curriculum;<198[5-9]>')X
1702
3720(bib-file)X
1703
1 f
1704
648 1049(which)N
1705
871(outputs)X
1706
1133(all)X
1707
1240(paragraphs)X
1708
1620(referencing)X
1709
2014(articles)X
1710
2273(in)X
1711
2362(CACM)X
1712
2624(between)X
1713
2920(1985)X
1714
3108(and)X
1715
3252(1989)X
1716
3440(by)X
1717
3548(TheAuthor)X
1718
3928(dealing)X
1719
4192(with)X
1720
648 1159(curriculum.)N
1721
1065(One)X
1722
1224(error)X
1723
1405(is)X
1724
1482(allowed)X
1725
1760(in)X
1726
1846(any)X
1727
1986(of)X
1728
2077(the)X
1729
2199(sub-patterns,)X
1730
2635(but)X
1731
2761(it)X
1732
2829(cannot)X
1733
3067(be)X
1734
3167(in)X
1735
3253(either)X
1736
3460(CACM)X
1737
3719(or)X
1738
3810(the)X
1739
3932(year)X
1740
4095(\(the)X
1741
4244(<>)X
1742
648 1269(brackets)N
1743
936(forbid)X
1744
1152(errors)X
1745
1360(in)X
1746
1442(the)X
1747
1560(pattern)X
1748
1803(between)X
1749
2091(them\).)X
1750
848 1412(These)N
1751
1068(features)X
1752
1351(and)X
1753
1495(several)X
1754
1751(more)X
1755
1944(enable)X
1756
2182(users)X
1757
2375(to)X
1758
2465(compose)X
1759
2779(complex)X
1760
3084(queries)X
1761
3345(rather)X
1762
3562(easily.)X
1763
3798(We)X
1764
3939(give)X
1765
4106(several)X
1766
648 1522(examples)N
1767
974(of)X
1768
1064(the)X
1769
1185(daily)X
1770
1368(use)X
1771
1498(of)X
1772
1588(agrep)X
1773
1790(from)X
1774
1969(our)X
1775
2099(experience.)X
1776
2511(For)X
1777
2645(a)X
1778
2704(complete)X
1779
3021(list)X
1780
3140(of)X
1781
3229(options,)X
1782
3506(see)X
1783
3631(the)X
1784
3751(manual)X
1785
4009(pages)X
1786
4214(dis-)X
1787
648 1632(tributed)N
1788
917(with)X
1789
1079(agrep.)X
1790
6 f
1791
12 s
1792
648 1852(2.1.)N
1793
862(Finding)X
1794
1238(words)X
1795
1548(in)X
1796
1661(a)X
1797
1741(dictionary)X
1798
1 f
1799
10 s
1800
648 1995(The)N
1801
799(most)X
1802
980(common)X
1803
1286(tool)X
1804
1436(available)X
1805
1753(in)X
1806
1842(UNIX)X
1807
2070(for)X
1808
2191(\256nding)X
1809
2444(the)X
1810
2569(correct)X
1811
2820(spelling)X
1812
3100(of)X
1813
3194(a)X
1814
3257(word)X
1815
3449(is)X
1816
3529(the)X
1817
3654(program)X
1818
2 f
1819
3953(look)X
1820
1 f
1821
4091(,)X
1822
4138(which)X
1823
648 2105(outputs)N
1824
913(all)X
1825
1023(words)X
1826
1249(in)X
1827
1341(the)X
1828
1469(dictionary)X
1829
1824(with)X
1830
1996(a)X
1831
2062(given)X
1832
2270(pre\256x.)X
1833
2527(We)X
1834
2669(have)X
1835
2851(many)X
1836
3059(times)X
1837
3262(looked)X
1838
3510(for)X
1839
3634(spelling)X
1840
3917(of)X
1841
4014(words)X
1842
4240(for)X
1843
648 2215(which)N
1844
864(we)X
1845
978(did)X
1846
1100(not)X
1847
1222(know)X
1848
1420(a)X
1849
1476(pre\256x.)X
1850
1723(We)X
1851
1855(use)X
1852
1982(the)X
1853
2100(following)X
1854
2431(alias)X
1855
2598(for)X
1856
2712(\256ndword:)X
1857
7 f
1858
792 2325(alias)N
1859
1080(findword)X
1860
1512(agrep)X
1861
1800(-i)X
1862
1944(-!:2)X
1863
2184(!:1)X
1864
2376(/usr/dict/web2)X
1865
1 f
1866
648 2435(\(web2)N
1867
873(is)X
1868
950(a)X
1869
1010(large)X
1870
1196(collection)X
1871
1537(of)X
1872
1629(words,)X
1873
1870(about)X
1874
2073(2.5MB)X
1875
2322(long;)X
1876
2531(one)X
1877
2672(can)X
1878
2809(use)X
1879
2941(/usr/dict/words)X
1880
3446(instead.\))X
1881
3765(For)X
1882
3901(example,)X
1883
4218(one)X
1884
648 2545(of)N
1885
736(the)X
1886
855(authors)X
1887
1112(can)X
1888
1245(never)X
1889
1445(remember)X
1890
1792(the)X
1891
1911(correct)X
1892
2156(spelling)X
1893
2430(of)X
1894
2518 0.3250(bureaucracy)AX
1895
2933(\(and)X
1896
3097(he)X
1897
3194(is)X
1898
3268(irritated)X
1899
3543(enough)X
1900
3800(with)X
1901
3963(it)X
1902
4028(not)X
1903
4151(want-)X
1904
648 2655(ing)N
1905
781(to)X
1906
874(remember\).)X
1907
7 f
1908
1354(findword)X
1909
1797(breacracy)X
1910
2288(2)X
1911
1 f
1912
2367(searches)X
1913
2671(for)X
1914
2796(all)X
1915
2907 0.3125(occurrences)AX
1916
3323(of)X
1917
3421 0.4062(breacracy)AX
1918
3766(with)X
1919
3939(at)X
1920
4028(most)X
1921
4214(two)X
1922
648 2765(errors.)N
1923
896(\(web2)X
1924
1117(contains)X
1925
1404(one)X
1926
1540(more)X
1927
1725(match)X
1928
1941(-)X
1929
1988(squireocracy\).)X
1930
848 2908(One)N
1931
1007(can)X
1932
1144(also)X
1933
1298(use)X
1934
1430(the)X
1935
1553(-w)X
1936
1663(option)X
1937
1892(which)X
1938
2114(matches)X
1939
2403(the)X
1940
2527(pattern)X
1941
2776(to)X
1942
2864(a)X
1943
2926(complete)X
1944
3246(word)X
1945
3437(\(rather)X
1946
3678(than)X
1947
3842(possibly)X
1948
4134(a)X
1949
4196(sub-)X
1950
648 3018(word\).)N
1951
905(In)X
1952
997(the)X
1953
1120(example)X
1954
1417(above,)X
1955
1654(the)X
1956
1777(extra)X
1957
1963(match)X
1958
2184 0.2404(\(squireocracy\))AX
1959
2674(will)X
1960
2823(not)X
1961
2950(be)X
1962
3051(a)X
1963
3112(match,)X
1964
3353(because)X
1965
3633(with)X
1966
3800(the)X
1967
3922(-w)X
1968
4031(option)X
1969
4259(its)X
1970
648 3128(beginning)N
1971
988(\(squi\))X
1972
1195(will)X
1973
1339(count)X
1974
1537(as)X
1975
1624(4)X
1976
1684(extra)X
1977
1865(errors.)X
1978
6 f
1979
12 s
1980
648 3348(2.2.)N
1981
862(Searching)X
1982
1353(a)X
1983
1433(Mail)X
1984
1647(File)X
1985
1 f
1986
10 s
1987
648 3491(We)N
1988
787(found)X
1989
1001(that)X
1990
1148(one)X
1991
1291(of)X
1992
1385(the)X
1993
1510(most)X
1994
1693(frequent)X
1995
1989(uses)X
1996
2155(of)X
1997
2250(agrep)X
1998
2457(is)X
1999
2538(to)X
2000
2628(search)X
2001
2862(inside)X
2002
3081(mail)X
2003
3251(\256les)X
2004
3412(for)X
2005
3534(mail)X
2006
3704(messages)X
2007
4035(using)X
2008
4236(the)X
2009
648 3601(record)N
2010
874(option.)X
2011
1138(We)X
2012
1270(use)X
2013
1397(the)X
2014
1515(following)X
2015
1846(alias)X
2016
7 f
2017
792 3711(alias)N
2018
1080(agmail)X
2019
1416(agrep)X
2020
1704(-!:2)X
2021
1944(-d)X
2022
2088('\303From)X
2023
2424(')X
2024
2520(!:1)X
2025
1 f
2026
648 3821(Notice)N
2027
882(that)X
2028
1022(it)X
2029
1086(is)X
2030
1159(possible)X
2031
1441(with)X
2032
1603(this)X
2033
1738(alias)X
2034
1905(to)X
2035
1987(use)X
2036
2114(complicated)X
2037
2526(queries;)X
2038
2800(for)X
2039
2914(example,)X
2040
7 f
2041
648 3931(agmail)N
2042
984('<pizza>;<great>;Manbar')X
2043
2184(1)X
2044
2280(mail/food,)X
2045
1 f
2046
2780(or)X
2047
7 f
2048
648 4041(agmail)N
2049
997('\\.gov;October;surprise')X
2050
2210(0)X
2051
2319(mail/*,)X
2052
1 f
2053
2689(which)X
2054
2919(searches)X
2055
3226(all)X
2056
3340(mail)X
2057
3516(messages)X
2058
3853(from)X
2059
4043(.gov)X
2060
4217(\(a)X
2061
4314(.)X
2062
648 4151(without)N
2063
912(the)X
2064
1030(\\)X
2065
1072(matches)X
2066
1355(every)X
2067
1554 0.3750(character\))AX
2068
1897(that)X
2069
2037(include)X
2070
2293(the)X
2071
2411(two)X
2072
2551(keywords.)X
2073
6 f
2074
12 s
2075
648 4371(2.3.)N
2076
862(Extracting)X
2077
1358(Procedures)X
2078
1 f
2079
10 s
2080
648 4514(It)N
2081
722(is)X
2082
800(usually)X
2083
1056(possible)X
2084
1343(to)X
2085
1430(easily)X
2086
1643(extract)X
2087
1888(a)X
2088
1950(procedure)X
2089
2298(from)X
2090
2480(a)X
2091
2542(large)X
2092
2729(program)X
2093
3027(by)X
2094
3133(de\256ning)X
2095
3421(a)X
2096
3483(procedure)X
2097
3831(as)X
2098
3924(a)X
2099
3986(record)X
2100
4218(and)X
2101
648 4624(using)N
2102
842(agrep.)X
2103
1082(For)X
2104
1214(example,)X
2105
7 f
2106
1555(agrep)X
2107
1844(-t)X
2108
1989(-d)X
2109
2133('\303}')X
2110
2373('\303routine1')X
2111
2949(prog1/*.c)X
2112
3429(>)X
2113
3525(routine1.c)X
2114
1 f
2115
4025(will)X
2116
4169(work)X
2117
648 4734(assuming)N
2118
975(routines)X
2119
1258(in)X
2120
1345(C)X
2121
1423(always)X
2122
1671(end)X
2123
1813(with)X
2124
1981(})X
2125
2045(at)X
2126
2129(the)X
2127
2253(beginning)X
2128
2599(of)X
2129
2692(a)X
2130
2754(line)X
2131
2900(\(and)X
2132
3069(that)X
2133
3215('\303routine1')X
2134
3589(uniquely)X
2135
3895(identi\256es)X
2136
4214(that)X
2137
648 4844(routine\).)N
2138
966(One)X
2139
1124(should)X
2140
1360(be)X
2141
1459(careful)X
2142
1706(when)X
2143
1903(dealing)X
2144
2162(with)X
2145
2327(other)X
2146
2515(people's)X
2147
2810(programs)X
2148
3136(\(because)X
2149
3441(the)X
2150
3562(conventions)X
2151
3972(may)X
2152
4133(not)X
2153
4258(be)X
2154
648 4954(followed\).)N
2155
1022(Other)X
2156
1227(programming)X
2157
1685(languages)X
2158
2028(have)X
2159
2202(other)X
2160
2389(ways)X
2161
2576(to)X
2162
2660(identify)X
2163
2931(the)X
2164
3051(end)X
2165
3189(\(or)X
2166
3305(beginning)X
2167
3648(of)X
2168
3738(a)X
2169
3797(procedure\).)X
2170
4209(The)X
2171
648 5064(-t)N
2172
720(option)X
2173
947(puts)X
2174
1103(the)X
2175
1224(record)X
2176
1453(delimiter)X
2177
1765(at)X
2178
1846(the)X
2179
1967(end)X
2180
2106(of)X
2181
2196(the)X
2182
2317(record)X
2183
2546(rather)X
2184
2757(than)X
2185
2918(at)X
2186
2999(the)X
2187
3119(beginning)X
2188
3461(\(which)X
2189
3706(is)X
2190
3781(more)X
2191
3968(appropriate)X
2192
648 5174(for)N
2193
762(mail)X
2194
924(messages,)X
2195
1267(for)X
2196
1381(example\).)X
2197
6 f
2198
12 s
2199
648 5394(2.4.)N
2200
862(Finding)X
2201
1238(Interesting)X
2202
1756(Words)X
2203
1 f
2204
10 s
2205
648 5537(At)N
2206
750(some)X
2207
941(point)X
2208
1127(we)X
2209
1243(needed)X
2210
1493(to)X
2211
1577(\256nd)X
2212
1723(all)X
2213
1825(words)X
2214
2043(in)X
2215
2127(the)X
2216
2247(dictionary)X
2217
2594(with)X
2218
2758(4-7)X
2219
2887(characters.)X
2220
3276(This)X
2221
3440(can)X
2222
3574(be)X
2223
3672(done)X
2224
3851(with)X
2225
4016(one)X
2226
4155(agrep)X
2227
648 5647(command)N
2228
7 f
2229
1021(agrep)X
2230
1318(-3)X
2231
1471(-w)X
2232
1624(-D4)X
2233
1824('....')X
2234
2168(/usr/dict/words.)X
2235
1 f
2236
2984(\(The)X
2237
3164(-D4)X
2238
3317(prevents)X
2239
3617(deletions,)X
2240
3954(and)X
2241
4098(the)X
2242
4224(.)X
2243
4272(in)X
2244
648 5757(the)N
2245
766(pattern)X
2246
1009(stands)X
2247
1229(for)X
2248
1343(any)X
2249
1479 0.3375(character.\))AX
2250
2251
4 p
2252
%%Page: 4 4
2253
10 s 10 xH 0 xS 1 f
2254
3 f
2255
1 f
2256
848 686(We)N
2257
981(end)X
2258
1118(this)X
2259
1254(section)X
2260
1502(with)X
2261
1665(a)X
2262
1722(cute)X
2263
1877(example,)X
2264
2190(which)X
2265
2407(although)X
2266
2708(is)X
2267
2782(not)X
2268
2906(important,)X
2269
3259(shows)X
2270
3481(how)X
2271
3641(\257exible)X
2272
3903(agrep)X
2273
4104(can)X
2274
4238(be.)X
2275
648 796(The)N
2276
797(following)X
2277
1132(query)X
2278
1339(\256nds)X
2279
1518(all)X
2280
1622(words)X
2281
1842(in)X
2282
1928(the)X
2283
2050(dictionary)X
2284
2399(that)X
2285
2543(contain)X
2286
2803(5)X
2287
2867(of)X
2288
2958(the)X
2289
3080(\256rst)X
2290
3228(10)X
2291
3332(letters)X
2292
3551(of)X
2293
3641(the)X
2294
3762(alphabet)X
2295
4057(in)X
2296
4142(order:)X
2297
7 f
2298
648 906(agrep)N
2299
942(-5)X
2300
1092('a#b#c#d#e#f#g#h#i#j')X
2301
2154(/usr/dict/words)X
2302
1 f
2303
2900(\(the)X
2304
3051(#)X
2305
3117(symbol)X
2306
3378(stands)X
2307
3605(for)X
2308
3726(a)X
2309
3789(wild)X
2310
3958(card)X
2311
4124(of)X
2312
4218(any)X
2313
648 1016(size)N
2314
794(-)X
2315
842(the)X
2316
961(same)X
2317
1147(as)X
2318
1235(.*\).)X
2319
1383(Try)X
2320
1520(it.)X
2321
1624(The)X
2322
1769(answer)X
2323
2017(starts)X
2324
2206(with)X
2325
2368(the)X
2326
2486(word)X
2327
2 f
2328
2671(academia)X
2329
1 f
2330
3023(and)X
2331
3159(ends)X
2332
3326(with)X
2333
2 f
2334
3488(sacrilegious)X
2335
1 f
2336
3879(;)X
2337
3921(it)X
2338
3985(must)X
2339
4160(mean)X
2340
648 1126(something..)N
2341
6 f
2342
14 s
2343
648 1378(3.)N
2344
803(The)X
2345
1032(Algorithm)X
2346
1561(s)X
2347
1 f
2348
10 s
2349
648 1553(Agrep)N
2350
874(utilizes)X
2351
1130(several)X
2352
1383(different)X
2353
1686(algorithms)X
2354
2054(to)X
2355
2142(optimize)X
2356
2448(the)X
2357
2572(performance)X
2358
3005(for)X
2359
3125(the)X
2360
3249(different)X
2361
3552(cases.)X
2362
3788(For)X
2363
3925(simple)X
2364
4164(exact)X
2365
648 1663(queries)N
2366
916(we)X
2367
1046(use)X
2368
1189(a)X
2369
1261(variant)X
2370
1520(of)X
2371
1623(the)X
2372
1757(Boyer-Moore)X
2373
2230(algorithm.)X
2374
2617(For)X
2375
2764(simple)X
2376
3012(patterns)X
2377
3301(with)X
2378
3478(errors,)X
2379
3721(we)X
2380
3850(use)X
2381
3992(a)X
2382
4063(partition)X
2383
648 1773(scheme,)N
2384
934(described)X
2385
1267(at)X
2386
1350(the)X
2387
1473(end)X
2388
1614(of)X
2389
1706(section)X
2390
1958(3.2,)X
2391
2103(hand)X
2392
2284(in)X
2393
2371(hand)X
2394
2552(with)X
2395
2720(the)X
2396
2844(Boyer-Moore)X
2397
3307(scheme.)X
2398
3614(For)X
2399
3751(more)X
2400
3942(complicated)X
2401
648 1883(patterns,)N
2402
958(e.g.,)X
2403
1130(patterns)X
2404
1420(with)X
2405
1598(unlimited)X
2406
1940(wild)X
2407
2118(cards,)X
2408
2344(patterns)X
2409
2634(with)X
2410
2812(uneven)X
2411
3080(costs)X
2412
3276(of)X
2413
3379(the)X
2414
3513(different)X
2415
3825(edit)X
2416
3980(operations,)X
2417
648 1993(multi-patterns,)N
2418
1140(arbitrary)X
2419
1440(regular)X
2420
1691(expressions,)X
2421
2108(we)X
2422
2225(use)X
2423
2355(new)X
2424
2512(algorithms)X
2425
2877(altogether.)X
2426
3261(In)X
2427
3351(this)X
2428
3490(section,)X
2429
3761(we)X
2430
3879(brie\257y)X
2431
4112(outline)X
2432
648 2103(the)N
2433
768(basis)X
2434
950(for)X
2435
1066(two)X
2436
1208(of)X
2437
1297(the)X
2438
1417(interesting)X
2439
1777(new)X
2440
1933(algorithms)X
2441
2297(that)X
2442
2439(we)X
2443
2555(use,)X
2444
2704(the)X
2445
2824(algorithm)X
2446
3157(for)X
2447
3273(arbitrary)X
2448
3571(patterns)X
2449
3846(with)X
2450
4009(errors)X
2451
4218(and)X
2452
648 2213(the)N
2453
766(algorithm)X
2454
1097(for)X
2455
1211(multi)X
2456
1399(patterns.)X
2457
1713(For)X
2458
1844(some)X
2459
2033(more)X
2460
2218(details)X
2461
2447(on)X
2462
2547(the)X
2463
2665(algorithms)X
2464
3027(see)X
2465
3150([WM91,)X
2466
3444(WM92].)X
2467
6 f
2468
12 s
2469
648 2433(3.1.)N
2470
862(Arbitrary)X
2471
1293(Patterns)X
2472
1703(With)X
2473
1939(Errors)X
2474
1 f
2475
10 s
2476
648 2576(We)N
2477
781(describe)X
2478
1070(only)X
2479
1233(the)X
2480
1352(main)X
2481
1533(idea)X
2482
1688(behind)X
2483
1927(the)X
2484
2046(simplest)X
2485
2333(case)X
2486
2493(of)X
2487
2581(the)X
2488
2700(algorithm,)X
2489
3052(\256nding)X
2490
3299(all)X
2491
3400 0.3125(occurrences)AX
2492
3806(of)X
2493
3894(a)X
2494
3952(given)X
2495
4152(string)X
2496
648 2686(in)N
2497
731(a)X
2498
788(given)X
2499
987(text.)X
2500
1168(The)X
2501
1314(algorithm)X
2502
1646(is)X
2503
1720(based)X
2504
1924(on)X
2505
2025(the)X
2506
2144(`shift-or')X
2507
2455(algorithm)X
2508
2787(of)X
2509
2875(Baeza-Yates)X
2510
3303(and)X
2511
3440(Gonnet)X
2512
3697([BG89].)X
2513
4003(Let)X
2514
2 f
2515
4131(R)X
2516
1 f
2517
4201(be)X
2518
4298(a)X
2519
648 2796(bit)N
2520
757(array)X
2521
948(of)X
2522
1040(size)X
2523
2 f
2524
1190(m)X
2525
1 f
2526
1273(\(the)X
2527
1423(size)X
2528
1573(of)X
2529
1665(the)X
2530
1788(pattern\).)X
2531
2083(We)X
2532
2220(denote)X
2533
2459(by)X
2534
2 f
2535
2564(R)X
2536
7 s
2537
2617 2812(j)N
2538
1 f
2539
10 s
2540
2664 2796(the)N
2541
2787(value)X
2542
2986(of)X
2543
3078(the)X
2544
3202(array)X
2545
2 f
2546
3394(R)X
2547
1 f
2548
3469(after)X
2549
3643(the)X
2550
2 f
2551
3773(j)X
2552
1 f
2553
3821(character)X
2554
4143(of)X
2555
4236(the)X
2556
648 2906(text)N
2557
791(has)X
2558
921(been)X
2559
1096(processed.)X
2560
1476(The)X
2561
1624(array)X
2562
2 f
2563
1813(R)X
2564
7 s
2565
1866 2922(j)N
2566
1 f
2567
10 s
2568
1911 2906(contains)N
2569
2201(information)X
2570
2602(about)X
2571
2803(all)X
2572
2906(matches)X
2573
3192(of)X
2574
3282(pre\256xes)X
2575
3559(of)X
2576
2 f
2577
3649(P)X
2578
1 f
2579
3721(with)X
2580
3885(a)X
2581
3943(suf\256x)X
2582
4147(of)X
2583
4236(the)X
2584
648 3016(text)N
2585
789(that)X
2586
930(ends)X
2587
1098(at)X
2588
2 f
2589
1183(j)X
2590
1 f
2591
1205(.)X
2592
1246(More)X
2593
1441(precisely,)X
2594
2 f
2595
1772(R)X
2596
7 s
2597
1825 3032(j)N
2598
1 f
2599
10 s
2600
1847 3016([)N
2601
2 f
2602
1874(i)X
2603
1 f
2604
1909(])X
2605
2 f
2606
9 f
2607
1949(=)X
2608
1 f
2609
2006(1)X
2610
2067(if)X
2611
2137(the)X
2612
2256(\256rst)X
2613
2 f
2614
2401(i)X
2615
1 f
2616
2444(characters)X
2617
2792(of)X
2618
2880(the)X
2619
2999(pattern)X
2620
3243(match)X
2621
3460(exactly)X
2622
3713(the)X
2623
3832(last)X
2624
2 f
2625
3964(i)X
2626
1 f
2627
4007(characters)X
2628
648 3126(up)N
2629
751(to)X
2630
2 f
2631
842(j)X
2632
1 f
2633
887(in)X
2634
972(the)X
2635
1093(text.)X
2636
1275(These)X
2637
1489(are)X
2638
1610(all)X
2639
1712(the)X
2640
1832(partial)X
2641
2059(matches)X
2642
2344(that)X
2643
2486(may)X
2644
2646(lead)X
2645
2802(to)X
2646
2886(full)X
2647
3019(matches)X
2648
3304(later)X
2649
3469(on.)X
2650
3611(When)X
2651
3825(we)X
2652
3941(read)X
2653
2 f
2654
4102(t)X
2655
7 s
2656
4128 3142(j)N
2657
9 f
2658
4153(+)X
2659
1 f
2660
4184(1)X
2661
10 s
2662
4240 3126(we)N
2663
648 3236(need)N
2664
821(to)X
2665
904(determine)X
2666
1246(whether)X
2667
2 f
2668
1526(t)X
2669
7 s
2670
1552 3252(j)N
2671
9 f
2672
1577(+)X
2673
1 f
2674
1608(1)X
2675
10 s
2676
1663 3236(can)N
2677
1796(extend)X
2678
2031(any)X
2679
2168(of)X
2680
2256(the)X
2681
2375(partial)X
2682
2601(matches)X
2683
2885(so)X
2684
2977(far.)X
2685
3129(The)X
2686
3276(transition)X
2687
3600(from)X
2688
2 f
2689
3778(R)X
2690
7 s
2691
3831 3252(j)N
2692
1 f
2693
10 s
2694
3875 3236(to)N
2695
2 f
2696
3959(R)X
2697
7 s
2698
4012 3252(j)N
2699
9 f
2700
4037(+)X
2701
1 f
2702
4068(1)X
2703
10 s
2704
4124 3236(can)N
2705
4258(be)X
2706
648 3346(summarized)N
2707
1060(as)X
2708
1147(follows:)X
2709
792 3456(Initially,)N
2710
2 f
2711
1085(R)X
2712
1 f
2713
7 s
2714
1143 3472(0)N
2715
10 s
2716
1177 3456([)N
2717
2 f
2718
1204(i)X
2719
1 f
2720
1239(])X
2721
2 f
2722
9 f
2723
1286(=)X
2724
1 f
2725
1350(0)X
2726
1410(for)X
2727
1524(all)X
2728
2 f
2729
1624(i)X
2730
1 f
2731
1646(,)X
2732
1686(1)X
2733
2 f
2734
9 f
2735
1739(\243)X
2736
2 f
2737
1796(i)X
2738
9 f
2739
1837(\243)X
2740
2 f
2741
1894(m)X
2742
1 f
2743
1972(;)X
2744
2 f
2745
2014(R)X
2746
1 f
2747
7 s
2748
2072 3472(0)N
2749
10 s
2750
2106 3456([0])N
2751
2 f
2752
9 f
2753
2220(=)X
2754
1 f
2755
2284(1.)X
2756
2 f
2757
808 3670(R)N
2758
7 s
2759
861 3686(j)N
2760
9 f
2761
886(+)X
2762
1 f
2763
917(1)X
2764
10 s
2765
951 3670([)N
2766
2 f
2767
978(i)X
2768
1 f
2769
1013(])X
2770
2 f
2771
9 f
2772
1080(=)X
2773
1 f
2774
10 f
2775
1177 3590(I)N
2776
1177 3670(K)N
2777
1177 3750(L)N
2778
1 f
2779
1237 3710(0)N
2780
1237 3598(1)N
2781
1317 3710(otherwise)N
2782
1317 3582(if)N
2783
2 f
2784
1386(R)X
2785
7 s
2786
1439 3598(j)N
2787
1 f
2788
10 s
2789
1461 3582([)N
2790
2 f
2791
1488(i)X
2792
9 f
2793
1523(-)X
2794
1 f
2795
1567(1])X
2796
2 f
2797
9 f
2798
1654(=)X
2799
1 f
2800
1718(1)X
2801
1778(and)X
2802
2 f
2803
1914(p)X
2804
7 s
2805
3598(i)Y
2806
10 s
2807
9 f
2808
1989 3582(=)N
2809
2 f
2810
2046(t)X
2811
7 s
2812
2072 3598(j)N
2813
9 f
2814
2097(+)X
2815
1 f
2816
2128(1)X
2817
10 s
2818
792 3900(If)N
2819
2 f
2820
866(R)X
2821
7 s
2822
919 3916(j)N
2823
9 f
2824
944(+)X
2825
1 f
2826
975(1)X
2827
10 s
2828
1009 3900([)N
2829
2 f
2830
1036(m)X
2831
1 f
2832
1107(])X
2833
2 f
2834
9 f
2835
1154(=)X
2836
1 f
2837
1218(1)X
2838
1278(then)X
2839
1436(we)X
2840
1550(output)X
2841
1774(a)X
2842
1830(match)X
2843
2046(that)X
2844
2186(ends)X
2845
2353(at)X
2846
2431(position)X
2847
2 f
2848
2714(j)X
2849
9 f
2850
2749(+)X
2851
1 f
2852
2793(1)X
2853
2853(;)X
2854
848 4043(This)N
2855
1018(transition,)X
2856
1368(which)X
2857
1592(we)X
2858
1714(have)X
2859
1894(to)X
2860
1985(compute)X
2861
2290(once)X
2862
2471(for)X
2863
2594(every)X
2864
2802(text)X
2865
2951(character,)X
2866
3296(seems)X
2867
3521(quite)X
2868
3710(complicated.)X
2869
4151(How-)X
2870
648 4153(ever,)N
2871
828(suppose)X
2872
1107(that)X
2873
2 f
2874
1248(m)X
2875
9 f
2876
1325(\243)X
2877
1 f
2878
1382(32)X
2879
1483(\(which)X
2880
1727(is)X
2881
1801(usually)X
2882
2053(the)X
2883
2172(case)X
2884
2332(in)X
2885
2415(practice\),)X
2886
2738(and)X
2887
2875(that)X
2888
2 f
2889
3016(R)X
2890
1 f
2891
3086(is)X
2892
3160(represented)X
2893
3552(as)X
2894
3640(a)X
2895
3697(bit)X
2896
3802(vector)X
2897
4024(using)X
2898
4218(one)X
2899
648 4263(32-bit)N
2900
860(word.)X
2901
1086(For)X
2902
1218(each)X
2903
1387(character)X
2904
2 f
2905
1704(s)X
2906
7 s
2907
1735 4279(i)N
2908
1 f
2909
10 s
2910
1778 4263(in)N
2911
1861(the)X
2912
1980(alphabet)X
2913
2273(we)X
2914
2388(construct)X
2915
2703(a)X
2916
2760(bit)X
2917
2865(array)X
2918
2 f
2919
3052(S)X
2920
7 s
2921
4279(i)Y
2922
1 f
2923
10 s
2924
3135 4263(of)N
2925
3223(size)X
2926
2 f
2927
3369(m)X
2928
1 f
2929
3449(such)X
2930
3618(that)X
2931
2 f
2932
3760(S)X
2933
7 s
2934
4279(i)Y
2935
1 f
2936
10 s
2937
3822 4263([)N
2938
2 f
2939
3849(r)X
2940
1 f
2941
3893(])X
2942
2 f
2943
9 f
2944
3933(=)X
2945
1 f
2946
3990(1)X
2947
4052(if)X
2948
2 f
2949
4123(p)X
2950
7 s
2951
4279(r)Y
2952
10 s
2953
9 f
2954
4204 4263(=)N
2955
2 f
2956
4261(s)X
2957
7 s
2958
4292 4279(i)N
2959
1 f
2960
10 s
2961
4314 4263(.)N
2962
648 4373(\(It)N
2963
747(is)X
2964
822(suf\256cient)X
2965
1142(to)X
2966
1226(construct)X
2967
1542(the)X
2968
2 f
2969
1662(S)X
2970
1 f
2971
1724(arrays)X
2972
1943(only)X
2973
2107(for)X
2974
2223(the)X
2975
2343(characters)X
2976
2692(that)X
2977
2834(appear)X
2978
3071(in)X
2979
3155(the)X
2980
3275(pattern.\))X
2981
3587(It)X
2982
3658(is)X
2983
3733(easy)X
2984
3898(to)X
2985
3982(verify)X
2986
4196(now)X
2987
648 4483(that)N
2988
797(the)X
2989
924(transition)X
2990
1255(from)X
2991
2 f
2992
1440(R)X
2993
7 s
2994
1493 4499(j)N
2995
1 f
2996
10 s
2997
1544 4483(to)N
2998
2 f
2999
1635(R)X
3000
7 s
3001
1688 4499(j)N
3002
9 f
3003
1713(+)X
3004
1 f
3005
1744(1)X
3006
10 s
3007
1807 4483(amounts)N
3008
2107(to)X
3009
2198(no)X
3010
2308(more)X
3011
2503(than)X
3012
2671(a)X
3013
2 f
3014
2737(right)X
3015
2922(shift)X
3016
1 f
3017
3089(of)X
3018
2 f
3019
3186(R)X
3020
7 s
3021
3239 4499(j)N
3022
1 f
3023
10 s
3024
3291 4483(and)N
3025
3437(an)X
3026
3543(AND)X
3027
3747(operation)X
3028
4080(with)X
3029
2 f
3030
4252(S)X
3031
7 s
3032
4499(i)Y
3033
1 f
3034
10 s
3035
4314 4483(,)N
3036
648 4593(where)N
3037
2 f
3038
876(s)X
3039
7 s
3040
907 4609(i)N
3041
10 s
3042
9 f
3043
942 4593(=)N
3044
2 f
3045
999(t)X
3046
7 s
3047
1025 4609(j)N
3048
9 f
3049
1050(+)X
3050
1 f
3051
1081(1)X
3052
10 s
3053
1115 4593(.)N
3054
1186(So,)X
3055
1321(each)X
3056
1500(transition)X
3057
1833(can)X
3058
1976(be)X
3059
2082(executed)X
3060
2398(with)X
3061
2570(only)X
3062
2742(two)X
3063
2892(simple)X
3064
3135(arithmetic)X
3065
3490(operations,)X
3066
3874(a)X
3067
3940(shift)X
3068
4112(and)X
3069
4258(an)X
3070
648 4719(AND.)N
3071
7 s
3072
842 4687(2)N
3073
10 s
3074
848 4862(Suppose)N
3075
1146(now)X
3076
1311(that)X
3077
1458(we)X
3078
1579(want)X
3079
1762(to)X
3080
1851(allow)X
3081
2056(one)X
3082
2199(substitution)X
3083
2598(error.)X
3084
2822(We)X
3085
2961(introduce)X
3086
3291(one)X
3087
3434(more)X
3088
3626(array,)X
3089
3839(denoted)X
3090
4120(by)X
3091
2 f
3092
4227(R)X
3093
7 s
3094
4284 4878(j)N
3095
1 f
3096
4280 4830(1)N
3097
10 s
3098
4314 4862(,)N
3099
648 4972(which)N
3100
873(indicates)X
3101
1187(all)X
3102
1295(possible)X
3103
1585(matches)X
3104
1876(up)X
3105
1984(to)X
3106
2 f
3107
2074(t)X
3108
7 s
3109
2100 4988(j)N
3110
1 f
3111
10 s
3112
2150 4972(with)N
3113
2320(at)X
3114
2406(most)X
3115
2589(one)X
3116
2733(substitution.)X
3117
3153(The)X
3118
3306(transition)X
3119
3636(for)X
3120
3758(the)X
3121
2 f
3122
3884(R)X
3123
1 f
3124
3961(array)X
3125
4155(is)X
3126
4236(the)X
3127
648 5082(same)N
3128
836(as)X
3129
926(before.)X
3130
1195(We)X
3131
1330(need)X
3132
1505(only)X
3133
1670(to)X
3134
1755(specify)X
3135
2010(the)X
3136
2131(transition)X
3137
2456(for)X
3138
2 f
3139
2573(R)X
3140
1 f
3141
7 s
3142
2631 5050(1)N
3143
10 s
3144
2665 5082(.)N
3145
2728(There)X
3146
2939(are)X
3147
3061(two)X
3148
3204(cases)X
3149
3397(for)X
3150
3514(a)X
3151
3573(match)X
3152
3792(with)X
3153
3957(at)X
3154
4039(most)X
3155
4218(one)X
3156
648 5192(substitution)N
3157
1040(of)X
3158
1127(the)X
3159
1245(\256rst)X
3160
2 f
3161
1389(i)X
3162
1 f
3163
1431(characters)X
3164
1778(of)X
3165
2 f
3166
1865(P)X
3167
1 f
3168
1934(up)X
3169
2034(to)X
3170
2 f
3171
2116(t)X
3172
7 s
3173
2142 5208(j)N
3174
9 f
3175
2167(+)X
3176
1 f
3177
2198(1)X
3178
10 s
3179
2232 5192(:)N
3180
8 s
3181
10 f
3182
648 5280(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)N
3183
5 s
3184
1 f
3185
648 5374(2)N
3186
8 s
3187
686 5399(We)N
3188
792(assume)X
3189
998(that)X
3190
1112(the)X
3191
1208(right)X
3192
1347(shift)X
3193
1479(\256lls)X
3194
1594(the)X
3195
1690(\256rst)X
3196
1808(position)X
3197
2033(with)X
3198
2165(a)X
3199
2211(1.)X
3200
2293(If)X
3201
2353(only)X
3202
2485(0-\256lled)X
3203
2688(shifts)X
3204
2845(are)X
3205
2941(available)X
3206
3190(\(as)X
3207
3283(is)X
3208
3345(the)X
3209
3442(case)X
3210
3570(with)X
3211
3703(C\),)X
3212
3802(then)X
3213
3931(we)X
3214
4024(can)X
3215
4131(add)X
3216
4242(one)X
3217
648 5487(more)N
3218
797(OR)X
3219
904(operation)X
3220
1163(with)X
3221
1295(a)X
3222
1340(mask)X
3223
1492(that)X
3224
1605(has)X
3225
1707(one)X
3226
1816(bit.)X
3227
1933(Alternatively,)X
3228
2303(we)X
3229
2394(can)X
3230
2499(use)X
3231
2601(0)X
3232
2650(to)X
3233
2717(indicate)X
3234
2936(a)X
3235
2981(match)X
3236
3154(and)X
3237
3263(an)X
3238
3340(OR)X
3239
3446(operation)X
3240
3704(instead)X
3241
3902(of)X
3242
3972(an)X
3243
4049(AND;)X
3244
4238(that)X
3245
648 5575(way,)N
3246
791(0-\256lled)X
3247
998(shifts)X
3248
1159(are)X
3249
1258(suf\256cient.)X
3250
1550(This)X
3251
1686(is)X
3252
1751(counterintuitive)X
3253
2178(to)X
3254
2250(explain)X
3255
2460(\(and)X
3256
2595(it)X
3257
2653(is)X
3258
2718(not)X
3259
2822(adaptable)X
3260
3088(to)X
3261
3160(some)X
3262
3317(of)X
3263
3392(the)X
3264
3492(extensions\),)X
3265
3821(so)X
3266
3900(we)X
3267
3996(opted)X
3268
4160(for)X
3269
4256(the)X
3270
648 5663(easier)N
3271
812(de\256nition.)X
3272
3273
5 p
3274
%%Page: 5 5
3275
8 s 8 xH 0 xS 1 f
3276
10 s
3277
3 f
3278
1 f
3279
648 686(S1.)N
3280
848(There)X
3281
1058(is)X
3282
1133(an)X
3283
1231(exact)X
3284
1423(match)X
3285
1641(of)X
3286
1731(the)X
3287
1852(\256rst)X
3288
2 f
3289
1999(i)X
3290
9 f
3291
2034(-)X
3292
1 f
3293
2078(1)X
3294
2141(characters)X
3295
2491(up)X
3296
2594(to)X
3297
2 f
3298
2679(t)X
3299
7 s
3300
2705 702(j)N
3301
1 f
3302
10 s
3303
2750 686(This)N
3304
2915(case)X
3305
3077(corresponds)X
3306
3488(to)X
3307
3573(substituting)X
3308
2 f
3309
3968(t)X
3310
7 s
3311
3994 702(j)N
3312
9 f
3313
4019(+)X
3314
1 f
3315
4050(1)X
3316
10 s
3317
4107 686(with)N
3318
2 f
3319
4272(p)X
3320
7 s
3321
702(i)Y
3322
1 f
3323
10 s
3324
848 796(\(whether)N
3325
1154(or)X
3326
1241(not)X
3327
1363(they)X
3328
1521(are)X
3329
1640(equal)X
3330
1834(\320)X
3331
1934(the)X
3332
2052(equality)X
3333
2330(will)X
3334
2474(be)X
3335
2570(indicated)X
3336
2884(in)X
3337
2 f
3338
2966(R)X
3339
1 f
3340
3015(\))X
3341
3062(and)X
3342
3198(matching)X
3343
3516(the)X
3344
3634(\256rst)X
3345
2 f
3346
3778(i)X
3347
9 f
3348
3813(-)X
3349
1 f
3350
3857(1)X
3351
3917(characters.)X
3352
648 939(S2.)N
3353
848(There)X
3354
1056(is)X
3355
1129(a)X
3356
1185(match)X
3357
1401(of)X
3358
1488(the)X
3359
1606(\256rst)X
3360
2 f
3361
1750(i)X
3362
9 f
3363
1785(-)X
3364
1 f
3365
1829(1)X
3366
1889(characters)X
3367
2236(up)X
3368
2336(to)X
3369
2 f
3370
2418(t)X
3371
7 s
3372
2444 955(j)N
3373
1 f
3374
10 s
3375
2486 939(with)N
3376
2648(one)X
3377
2784(substitution)X
3378
2 f
3379
3176(and)X
3380
3316(t)X
3381
7 s
3382
3342 955(j)N
3383
9 f
3384
3367(+)X
3385
1 f
3386
3398(1)X
3387
2 f
3388
10 s
3389
9 f
3390
3445 939(=)N
3391
2 f
3392
3502(p)X
3393
7 s
3394
955(i)Y
3395
1 f
3396
10 s
3397
3564 939(.)N
3398
848 1082(It)N
3399
925(turns)X
3400
1113(out)X
3401
1243(that)X
3402
1391(both)X
3403
1561(cases)X
3404
1759(can)X
3405
1899(be)X
3406
2003(handled)X
3407
2285(with)X
3408
2455(two)X
3409
2603(arithmetic)X
3410
2957(operations)X
3411
3320(on)X
3412
2 f
3413
3429(R)X
3414
1 f
3415
7 s
3416
3487 1050(1)N
3417
10 s
3418
3521 1082(.)N
3419
3590(If)X
3420
3673(we)X
3421
3796(allow)X
3422
4003(insertions,)X
3423
648 1192(deletions,)N
3424
981(and)X
3425
1121(substitutions,)X
3426
1568(then)X
3427
1730(we)X
3428
1848(will)X
3429
1996(need)X
3430
2171(4)X
3431
2234(operations)X
3432
2591(on)X
3433
2 f
3434
2694(R)X
3435
1 f
3436
7 s
3437
2752 1160(1)N
3438
10 s
3439
2786 1192(.)N
3440
2849(If)X
3441
2926(we)X
3442
3043(want)X
3443
3222(to)X
3444
3307(allow)X
3445
3508(more)X
3446
3696(than)X
3447
3857(one)X
3448
3996(error,)X
3449
4196(then)X
3450
648 1302(we)N
3451
766(maintain)X
3452
1070(more)X
3453
1259(than)X
3454
1421(one)X
3455
1561(additional)X
3456
2 f
3457
1905(R)X
3458
1 f
3459
7 s
3460
1963 1270(1)N
3461
10 s
3462
2021 1302(array.)N
3463
2251(Overall,)X
3464
2536(the)X
3465
2659(number)X
3466
2929(of)X
3467
3021(operations)X
3468
3380(is)X
3469
3458(proportional)X
3470
3879(to)X
3471
3966(the)X
3472
4089(number)X
3473
648 1412(of)N
3474
735(errors.)X
3475
983(But)X
3476
1118(we)X
3477
1232(can)X
3478
1364(do)X
3479
1464(even)X
3480
1636(better)X
3481
1839(than)X
3482
1997(that.)X
3483
848 1587(Suppose)N
3484
1140(again)X
3485
1335(that)X
3486
1476(the)X
3487
1595(pattern)X
3488
2 f
3489
1839(P)X
3490
1 f
3491
1909(is)X
3492
1983(of)X
3493
2071(size)X
3494
2 f
3495
2217(m)X
3496
1 f
3497
2296(and)X
3498
2433(that)X
3499
2574(at)X
3500
2653(most)X
3501
2 f
3502
2829(k)X
3503
1 f
3504
2886(errors)X
3505
3095(are)X
3506
3215(allowed.)X
3507
3530(Let)X
3508
2 f
3509
3658(r)X
3510
1 f
3511
2 f
3512
9 f
3513
3715(=)X
3514
1 f
3515
2 f
3516
10 f
3517
3779(Q)X
3518
2 f
3519
3832 1643(k)N
3520
9 f
3521
3881(+)X
3522
1 f
3523
3925(1)X
3524
2 f
3525
3870 1539(m)N
3526
1 f
3527
10 f
3528
3821 1563(hhhh)N
3529
2 f
3530
10 f
3531
3999 1587(P)N
3532
1 f
3533
(;)S
3534
4063(divide)X
3535
2 f
3536
4285(P)X
3537
1 f
3538
648 1737(into)N
3539
2 f
3540
797(k)X
3541
9 f
3542
846(+)X
3543
1 f
3544
890(1)X
3545
954(blocks)X
3546
1187(each)X
3547
1359(of)X
3548
1450(size)X
3549
2 f
3550
1599(r)X
3551
1 f
3552
1654(and)X
3553
1794(call)X
3554
1934(them)X
3555
2 f
3556
2118(P)X
3557
1 f
3558
7 s
3559
2176 1753(1)N
3560
10 s
3561
2210 1737(,)N
3562
2 f
3563
2249(P)X
3564
1 f
3565
7 s
3566
2307 1753(2)N
3567
10 s
3568
2341 1737(,)N
3569
2 f
3570
2380(...)X
3571
1 f
3572
(,)S
3573
2 f
3574
2479(P)X
3575
7 s
3576
2528 1753(k)N
3577
9 f
3578
2562(+)X
3579
1 f
3580
2593(1)X
3581
10 s
3582
2627 1737(.)N
3583
2691(If)X
3584
2 f
3585
2769(P)X
3586
1 f
3587
2842(matches)X
3588
3129(the)X
3589
3251(text)X
3590
3395(with)X
3591
3561(at)X
3592
3643(most)X
3593
2 f
3594
3822(k)X
3595
1 f
3596
3882(errors,)X
3597
4114(then)X
3598
4276(at)X
3599
648 1847(least)N
3600
818(one)X
3601
957(of)X
3602
1047(the)X
3603
2 f
3604
1168(P)X
3605
7 s
3606
1221 1863(j)N
3607
1 f
3608
10 s
3609
1243 1847('s)N
3610
1324(must)X
3611
1502(match)X
3612
1721(the)X
3613
1842(text)X
3614
1985(exactly.)X
3615
2280(We)X
3616
2415(can)X
3617
2550(search)X
3618
2779(for)X
3619
2896(all)X
3620
2 f
3621
2999(P)X
3622
7 s
3623
3052 1863(j)N
3624
1 f
3625
10 s
3626
3074 1847('s)N
3627
3155(at)X
3628
3236(the)X
3629
3357(same)X
3630
3545(time)X
3631
3710(\(we)X
3632
3855(discuss)X
3633
4110(how)X
3634
4272(to)X
3635
648 1957(do)N
3636
756(that)X
3637
904(in)X
3638
994(the)X
3639
1120(next)X
3640
1286(paragraph\))X
3641
1663(and,)X
3642
1827(if)X
3643
1904(one)X
3644
2047(of)X
3645
2141(them)X
3646
2328(matches,)X
3647
2638(then)X
3648
2803(we)X
3649
2924(check)X
3650
3139(the)X
3651
3264(whole)X
3652
3487(pattern)X
3653
3737(directly)X
3654
4009(\(using)X
3655
4236(the)X
3656
648 2067(previous)N
3657
946(scheme\))X
3658
1237(but)X
3659
1362(only)X
3660
1527(within)X
3661
1754(a)X
3662
1813(neighborhood)X
3663
2281(of)X
3664
2371(size)X
3665
2 f
3666
2519(m)X
3667
1 f
3668
2600(from)X
3669
2779(the)X
3670
2900(position)X
3671
3180(of)X
3672
3270(the)X
3673
3391(match.)X
3674
3650(Since)X
3675
3851(we)X
3676
3968(are)X
3677
4090(looking)X
3678
648 2177(for)N
3679
765(an)X
3680
863(exact)X
3681
1055(match,)X
3682
1293(there)X
3683
1476(is)X
3684
1551(no)X
3685
1653(need)X
3686
1827(to)X
3687
1911(maintain)X
3688
2213(the)X
3689
2333(additional)X
3690
2675(vectors.)X
3691
2969(This)X
3692
3133(scheme)X
3693
3396(will)X
3694
3542(run)X
3695
3671(fast)X
3696
3809(if)X
3697
3880(the)X
3698
4000(number)X
3699
4267(of)X
3700
648 2287(exact)N
3701
838(matches)X
3702
1121(to)X
3703
1203(any)X
3704
1339(one)X
3705
1475(of)X
3706
1562(the)X
3707
2 f
3708
1680(P)X
3709
7 s
3710
1733 2303(j)N
3711
1 f
3712
10 s
3713
1755 2287('s)N
3714
1833(is)X
3715
1906(not)X
3716
2028(too)X
3717
2150(high.)X
3718
848 2430(The)N
3719
1000(main)X
3720
1187(advantage)X
3721
1540(of)X
3722
1634(this)X
3723
1777(scheme)X
3724
2046(is)X
3725
2127(that)X
3726
2275(the)X
3727
2401(algorithm)X
3728
2740(for)X
3729
2862(exact)X
3730
3060(matching)X
3731
3386(can)X
3732
3526(be)X
3733
3630(adapted)X
3734
3908(in)X
3735
3998(an)X
3736
4102(elegant)X
3737
648 2540(way)N
3738
805(to)X
3739
890(support)X
3740
1153(it.)X
3741
1260(We)X
3742
1395(illustrate)X
3743
1698(the)X
3744
1819(idea)X
3745
1976(with)X
3746
2141(an)X
3747
2239(example.)X
3748
2573(Suppose)X
3749
2866(that)X
3750
3008(the)X
3751
3128(pattern)X
3752
3373(is)X
3753
3448(ABCDEFGHIJKL)X
3754
4066(\()X
3755
2 f
3756
4093(m)X
3757
9 f
3758
4170(=)X
3759
1 f
3760
4227(12\))X
3761
648 2650(and)N
3762
2 f
3763
786(k)X
3764
9 f
3765
841(=)X
3766
1 f
3767
898(3.)X
3768
1000(We)X
3769
1134(divide)X
3770
1356(the)X
3771
1476(pattern)X
3772
1721(into)X
3773
2 f
3774
1867(k)X
3775
9 f
3776
1916(+)X
3777
1 f
3778
1960(1)X
3779
2 f
3780
9 f
3781
2013(=)X
3782
1 f
3783
2070(4)X
3784
2132(blocks:)X
3785
2385(ABC,)X
3786
2591(DEF,)X
3787
2784(GHI,)X
3788
2969(and)X
3789
3107(JKL.)X
3790
3307(We)X
3791
3441(need)X
3792
3615(to)X
3793
3699(\256nd)X
3794
3846(whether)X
3795
4128(any)X
3796
4267(of)X
3797
648 2760(them)N
3798
835(appears)X
3799
1108(in)X
3800
1197(the)X
3801
1322(text.)X
3802
1508(We)X
3803
1646(create)X
3804
1865(one)X
3805
2007(combined)X
3806
2349(pattern)X
3807
2598(by)X
3808
2704(interleaving)X
3809
3113(the)X
3810
3237(4)X
3811
3303(blocks:)X
3812
3560(ADGJBEHKCFIL.)X
3813
4222(We)X
3814
648 2870(then)N
3815
811(build)X
3816
1000(the)X
3817
1123(mask)X
3818
1317(vector)X
3819
2 f
3820
1543(R)X
3821
1 f
3822
1617(as)X
3823
1709(usual)X
3824
1903(for)X
3825
2022(this)X
3826
2162(interleaved)X
3827
2544(pattern.)X
3828
2832(The)X
3829
2982(only)X
3830
3149(difference)X
3831
3501(is)X
3832
3579(that,)X
3833
3744(instead)X
3834
3997(of)X
3835
4090(shifting)X
3836
648 2980(by)N
3837
750(one)X
3838
888(in)X
3839
972(each)X
3840
1142(step,)X
3841
1313(we)X
3842
1429(shift)X
3843
1593(by)X
3844
1695(four!)X
3845
1897(There)X
3846
2106(is)X
3847
2180(a)X
3848
2237(match)X
3849
2454(if)X
3850
2524(any)X
3851
2661(of)X
3852
2749(the)X
3853
2868(last)X
3854
3000(four)X
3855
3155(bits)X
3856
3291(is)X
3857
3365(1.)X
3858
3466(\(When)X
3859
3706(we)X
3860
3821(shift)X
3861
3984(we)X
3862
4099(need)X
3863
4272(to)X
3864
648 3090(\256ll)N
3865
756(the)X
3866
874(\256rst)X
3867
1019(four)X
3868
1174(positions)X
3869
1483(with)X
3870
1646(1's,)X
3871
1785(or)X
3872
1873(better)X
3873
2077(yet,)X
3874
2216(use)X
3875
2344(shift-OR.\))X
3876
2712(Thus,)X
3877
2913(the)X
3878
3032(match)X
3879
3249(for)X
3880
3364(all)X
3881
3465(blocks)X
3882
3695(can)X
3883
3828(be)X
3884
3925(done)X
3885
4102(exactly)X
3886
648 3200(the)N
3887
766(same)X
3888
951(way)X
3889
1105(as)X
3890
1192(regular)X
3891
1440(matches)X
3892
1723(and)X
3893
1859(it)X
3894
1923(takes)X
3895
2108(essentially)X
3896
2466(the)X
3897
2584(same)X
3898
2769(running)X
3899
3038(time.)X
3900
848 3343(The)N
3901
996(algorithm)X
3902
1330(described)X
3903
1661(so)X
3904
1755(far)X
3905
1868(is)X
3906
1944(ef\256cient)X
3907
2230(for)X
3908
2347(simple)X
3909
2584(string)X
3910
2790(matching.)X
3911
3152(But)X
3912
3291(more)X
3913
3480(important,)X
3914
3835(it)X
3915
3903(is)X
3916
3980(also)X
3917
4133(adapt-)X
3918
648 3453(able)N
3919
804(to)X
3920
888(many)X
3921
1088(extensions)X
3922
1448(of)X
3923
1537(the)X
3924
1657(basic)X
3925
1844(problem.)X
3926
2173(For)X
3927
2306(example,)X
3928
2620(suppose)X
3929
2900(that)X
3930
3042(we)X
3931
3158(want)X
3932
3336(to)X
3933
3420(search)X
3934
3648(for)X
3935
3763(ABC)X
3936
3948(followed)X
3937
4254(by)X
3938
648 3563(a)N
3939
711(digit,)X
3940
904(which)X
3941
1127(is)X
3942
1207(de\256ned)X
3943
1470(in)X
3944
1559(agrep)X
3945
1765(by)X
3946
1872(ABC[0-9].)X
3947
2264(The)X
3948
2416(only)X
3949
2585(thing)X
3950
2776(we)X
3951
2897(need)X
3952
3076(to)X
3953
3165(do)X
3954
3273(is)X
3955
3354(in)X
3956
3444(the)X
3957
3570(preprocessing,)X
3958
4064(for)X
3959
4186(each)X
3960
648 3673(digit,)N
3961
840(allow)X
3962
1044(a)X
3963
1106(match)X
3964
1328(at)X
3965
1412(position)X
3966
1695(4.)X
3967
1801(Everything)X
3968
2183(else)X
3969
2334(remains)X
3970
2614(exactly)X
3971
2872(the)X
3972
2995(same.)X
3973
3225(Other)X
3974
3433(extensions)X
3975
3796(include)X
3976
4057(arbitrary)X
3977
648 3783(wild)N
3978
813(cards,)X
3979
1026(a)X
3980
1085(combination)X
3981
1508(of)X
3982
1598(patterns)X
3983
1875(with)X
3984
2040(and)X
3985
2179(without)X
3986
2446(errors,)X
3987
2677(different)X
3988
2977(costs)X
3989
3161(for)X
3990
3279(insertions,)X
3991
3634(deletions,)X
3992
3967(and/or)X
3993
4196(sub-)X
3994
648 3893(stitutions,)N
3995
980(and)X
3996
1116(probably)X
3997
1421(the)X
3998
1539(most)X
3999
1714(important,)X
4000
2065(arbitrary)X
4001
2362(regular)X
4002
2610(expressions.)X
4003
3044(We)X
4004
3176(have)X
4005
3348(no)X
4006
3448(room)X
4007
3637(to)X
4008
3719(describe)X
4009
4007(the)X
4010
4125(imple-)X
4011
648 4003(mentation)N
4012
989(of)X
4013
1077(these)X
4014
1263(extensions)X
4015
1622(\(see)X
4016
1774([WM91]\).)X
4017
2144(The)X
4018
2291(main)X
4019
2473(technique)X
4020
2807(is)X
4021
2882(to)X
4022
2966(use)X
4023
3095(additional)X
4024
3437(masking)X
4025
3730(and)X
4026
3868(preprocessing.)X
4027
648 4113(It)N
4028
718(is)X
4029
792(sometimes)X
4030
1155(relatively)X
4031
1479(easy)X
4032
1642(\(as)X
4033
1756(is)X
4034
1829(the)X
4035
1947(case)X
4036
2106(with)X
4037
2268(wild)X
4038
2430(cards\))X
4039
2647(and)X
4040
2783(it)X
4041
2847(sometimes)X
4042
3209(requires)X
4043
3488(clever)X
4044
3705(ideas)X
4045
3890(\(as)X
4046
4004(is)X
4047
4077(the)X
4048
4195(case)X
4049
648 4223(with)N
4050
824(arbitrary)X
4051
1135(regular)X
4052
1397(expressions)X
4053
1805(with)X
4054
1981(errors\).)X
4055
2270(Next,)X
4056
2480(we)X
4057
2608(describe)X
4058
2910(a)X
4059
2980(very)X
4060
3157(fast)X
4061
3307(algorithm)X
4062
3652(for)X
4063
3780(multiple)X
4064
4080(patterns)X
4065
648 4333(which)N
4066
864(also)X
4067
1013(leads)X
4068
1198(to)X
4069
1280(a)X
4070
1336(fast)X
4071
1472(approximate-matching)X
4072
2218(algorithm)X
4073
2549(for)X
4074
2663(simple)X
4075
2896(patterns.)X
4076
6 f
4077
12 s
4078
648 4553(3.2.)N
4079
862(An)X
4080
1017(Algorithm)X
4081
1498(for)X
4082
1653(Multi)X
4083
1905(Patterns)X
4084
1 f
4085
10 s
4086
648 4696(Suppose)N
4087
939(that)X
4088
1079(the)X
4089
1197(pattern)X
4090
1440(consists)X
4091
1713(of)X
4092
1800(a)X
4093
1856(set)X
4094
1965(of)X
4095
2 f
4096
2052(k)X
4097
1 f
4098
2108(simple)X
4099
2341(patterns)X
4100
2 f
4101
2615(P)X
4102
1 f
4103
7 s
4104
2673 4712(1)N
4105
10 s
4106
2707 4696(,)N
4107
2 f
4108
2746(P)X
4109
1 f
4110
7 s
4111
2804 4712(2)N
4112
10 s
4113
2838 4696(,)N
4114
2 f
4115
2877(...)X
4116
1 f
4117
(,)S
4118
2 f
4119
2976(P)X
4120
7 s
4121
3025 4712(k)N
4122
1 f
4123
10 s
4124
3056 4696(,)N
4125
3097(such)X
4126
3265(that)X
4127
3406(each)X
4128
2 f
4129
3575(P)X
4130
7 s
4131
3624 4712(i)N
4132
1 f
4133
10 s
4134
3667 4696(is)N
4135
3741(a)X
4136
3798(string)X
4137
4001(of)X
4138
2 f
4139
4089(m)X
4140
1 f
4141
4168(char-)X
4142
648 4806(acters)N
4143
861(from)X
4144
1042(a)X
4145
1103(\256xed)X
4146
1288(alphabet)X
4147
2 f
4148
9 f
4149
1585(S)X
4150
1 f
4151
1632(.)X
4152
1697(The)X
4153
1847(text)X
4154
1992(is)X
4155
2070(again)X
4156
2269(a)X
4157
2330(large)X
4158
2516(string)X
4159
2 f
4160
2723(T)X
4161
1 f
4162
2792(of)X
4163
2883(characters)X
4164
3234(from)X
4165
2 f
4166
9 f
4167
3414(S)X
4168
1 f
4169
3461(.)X
4170
3525(\(We)X
4171
3688(assume)X
4172
3948(that)X
4173
4092(all)X
4174
4196(sub-)X
4175
648 4916(patterns)N
4176
935(have)X
4177
1120(the)X
4178
1251(same)X
4179
1449(size)X
4180
1607(for)X
4181
1734(simplicity)X
4182
2086(of)X
4183
2186(description)X
4184
2575(only;)X
4185
2772(agrep)X
4186
2985(makes)X
4187
3224(no)X
4188
3338(such)X
4189
3519(assumption.\))X
4190
3984(The)X
4191
2 f
4192
4143(multi-)X
4193
648 5026(pattern)N
4194
899(string)X
4195
1105(matching)X
4196
1423(problem)X
4197
1 f
4198
1710(is)X
4199
1783(to)X
4200
1865(\256nd)X
4201
2009(all)X
4202
2109(substrings)X
4203
2453(in)X
4204
2535(the)X
4205
2653(text)X
4206
2793(that)X
4207
2933(match)X
4208
3149(at)X
4209
3227(least)X
4210
3394(one)X
4211
3530(of)X
4212
3617(the)X
4213
3735(patterns)X
4214
4009(in)X
4215
4091(the)X
4216
4209(set.)X
4217
848 5169(The)N
4218
993(\256rst)X
4219
1137(ef\256cient)X
4220
1420(algorithm)X
4221
1751(for)X
4222
1865(solving)X
4223
2120(this)X
4224
2255(problem)X
4225
2542(is)X
4226
2615(by)X
4227
2715(Aho)X
4228
2874(and)X
4229
3011(Corasick)X
4230
3317([AC75],)X
4231
3603(which)X
4232
3820(solves)X
4233
4041(the)X
4234
4160(prob-)X
4235
648 5279(lem)N
4236
801(in)X
4237
896(linear)X
4238
1112(time.)X
4239
1327(\(This)X
4240
1528(algorithm)X
4241
1871(is)X
4242
1956(the)X
4243
2086(basis)X
4244
2278(of)X
4245
2 f
4246
2383(fgrep)X
4247
1 f
4248
2552(.\))X
4249
2651(Commentz-Walter)X
4250
3280([CW79])X
4251
3575(presented)X
4252
3915(an)X
4253
4023(algorithm)X
4254
648 5389(which)N
4255
865(combines)X
4256
1193(the)X
4257
1313(Boyer-Moore)X
4258
1772(technique)X
4259
2106(with)X
4260
2270(the)X
4261
2390(Aho-Corasick)X
4262
2862(algorithm.)X
4263
3235(The)X
4264
3382(Commentz-Walter)X
4265
4001(Algorithm)X
4266
648 5499(is)N
4267
729(substantially)X
4268
1161(faster)X
4269
1368(than)X
4270
1534(the)X
4271
1660(Aho-Corasick)X
4272
2138(algorithm)X
4273
2477(when)X
4274
2679(the)X
4275
2805(number)X
4276
3077(of)X
4277
3171(patterns)X
4278
3452(is)X
4279
3532(not)X
4280
3661(too)X
4281
3790(big.)X
4282
3959(The)X
4283
4111(pattern)X
4284
648 5609(matching)N
4285
975(tool)X
4286
2 f
4287
1128(gre)X
4288
1 f
4289
1264([Hu91])X
4290
1525(\(which)X
4291
1777(covers)X
4292
2016(almost)X
4293
2258(all)X
4294
2367(functions)X
4295
2694(of)X
4296
2790 0.2109(egrep/grep/fgrep\))AX
4297
3382(developed)X
4298
3741(by)X
4299
3850(Andrew)X
4300
4138(Hume)X
4301
648 5719(has)N
4302
775(incorporated)X
4303
1201(the)X
4304
1319(Commentz-Walter)X
4305
1936(algorithm)X
4306
2267(for)X
4307
2381(the)X
4308
2499(multi-pattern)X
4309
2937(string)X
4310
3139(matching)X
4311
3457(problem.)X
4312
4313
6 p
4314
%%Page: 6 6
4315
10 s 10 xH 0 xS 1 f
4316
3 f
4317
1 f
4318
848 686(Our)N
4319
1008(algorithm)X
4320
1354(uses)X
4321
1527(a)X
4322
1598(hashing)X
4323
1882(technique)X
4324
2229(combined)X
4325
2580(with)X
4326
2757(a)X
4327
2828(different)X
4328
3140(Boyer-Moore)X
4329
3612(technique.)X
4330
3999(Instead)X
4331
4267(of)X
4332
648 796(building)N
4333
936(a)X
4334
994(shift)X
4335
1158(table)X
4336
1336(based)X
4337
1541(on)X
4338
1643(single)X
4339
1856(characters,)X
4340
2225(we)X
4341
2341(build)X
4342
2527(the)X
4343
2647(shift)X
4344
2811(table)X
4345
2989(based)X
4346
3194(on)X
4347
3295(a)X
4348
3352(block)X
4349
3551(of)X
4350
3639(characters.)X
4351
4027(\(The)X
4352
4200(idea)X
4353
648 906(of)N
4354
745(using)X
4355
948(a)X
4356
1014(block)X
4357
1222(of)X
4358
1319(characters)X
4359
1676(was)X
4360
1831(\256rst)X
4361
1985(proposed)X
4362
2309(by)X
4363
2419(Knuth-Morris-Pratt)X
4364
3072(in)X
4365
3164(section)X
4366
3421(8)X
4367
3491(of)X
4368
3588([KMP77].\))X
4369
3992(Like)X
4370
4169(other)X
4371
648 1016(Boyer-Moore)N
4372
1109(style)X
4373
1284(algorithms,)X
4374
1670(our)X
4375
1801(algorithm)X
4376
2135(preprocesses)X
4377
2569(the)X
4378
2690(patterns)X
4379
2967(to)X
4380
3052(build)X
4381
3239(some)X
4382
3431(data)X
4383
3588(structures)X
4384
3923(such)X
4385
4093(that)X
4386
4236(the)X
4387
648 1126(search)N
4388
877(process)X
4389
1141(can)X
4390
1276(be)X
4391
1375(speeded)X
4392
1657(up.)X
4393
1800(Let)X
4394
2 f
4395
1930(c)X
4396
1 f
4397
1989(denote)X
4398
2226(the)X
4399
2347(size)X
4400
2495(of)X
4401
2585(the)X
4402
2706(alphabet,)X
4403
2 f
4404
3021(M)X
4405
1 f
4406
3111(=)X
4407
2 f
4408
3180(k)X
4409
1 f
4410
3235 1102(.)N
4411
2 f
4412
3268 1126(m)N
4413
1 f
4414
3326(,)X
4415
3370(and)X
4416
2 f
4417
3510(b)X
4418
9 f
4419
3569(=)X
4420
10 f
4421
3626(R)X
4422
1 f
4423
3659(log)X
4424
2 f
4425
7 s
4426
3761 1142(c)N
4427
10 s
4428
3792 1126(M)N
4429
10 f
4430
3878(H)X
4431
1 f
4432
(.)S
4433
3962(We)X
4434
4098(assume)X
4435
648 1236(that)N
4436
2 f
4437
791(b)X
4438
9 f
4439
863(\243)X
4440
2 f
4441
933(m)X
4442
997(/)X
4443
1 f
4444
1025(2.)X
4445
1108(In)X
4446
1198(the)X
4447
1319(preprocessing,)X
4448
1808(a)X
4449
1867(shift)X
4450
2032(table)X
4451
2 f
4452
2211(SHIFT)X
4453
1 f
4454
2452(and)X
4455
2591(a)X
4456
2649(hashing)X
4457
2920(table)X
4458
2 f
4459
3098(HASH)X
4460
1 f
4461
3325(are)X
4462
3446(built.)X
4463
3654(We)X
4464
3788(look)X
4465
3952(at)X
4466
4032(the)X
4467
4152(text)X
4468
2 f
4469
4294(b)X
4470
1 f
4471
648 1346(characters)N
4472
995(at)X
4473
1073(a)X
4474
1129(time.)X
4475
1331(The)X
4476
1477(values)X
4477
1703(in)X
4478
1786(the)X
4479
1905(SHIFT)X
4480
2148(table)X
4481
2325(determine)X
4482
2667(how)X
4483
2826(far)X
4484
2937(we)X
4485
3052(can)X
4486
3185(shift)X
4487
3348(forward)X
4488
3624(during)X
4489
3854(the)X
4490
3973(search)X
4491
4200(pro-)X
4492
648 1456(cess.)N
4493
851(The)X
4494
1005(shift)X
4495
1176(table)X
4496
2 f
4497
1361(SHIFT)X
4498
1 f
4499
1608(is)X
4500
1690(an)X
4501
1795(array)X
4502
1990(of)X
4503
2086(size)X
4504
2 f
4505
2240(c)X
4506
7 s
4507
2285 1424(b)N
4508
1 f
4509
10 s
4510
2319 1456(.)N
4511
2388(Each)X
4512
2578(entry)X
4513
2772(of)X
4514
2 f
4515
2867(SHIFT)X
4516
1 f
4517
3113(corresponds)X
4518
3529(to)X
4519
3619(a)X
4520
3683(distinct)X
4521
3946(substring)X
4522
4267(of)X
4523
648 1566(length)N
4524
2 f
4525
872(b)X
4526
1 f
4527
(.)S
4528
956(Let)X
4529
2 f
4530
1087(X)X
4531
1 f
4532
1160(=)X
4533
2 f
4534
1229(x)X
4535
1 f
4536
7 s
4537
1274 1582(1)N
4538
2 f
4539
10 s
4540
1308 1566(x)N
4541
1 f
4542
7 s
4543
1353 1582(2)N
4544
10 s
4545
1407 1542(.)N
4546
1447(.)X
4547
1487(.)X
4548
2 f
4549
1527 1566(x)N
4550
7 s
4551
1563 1582(b)N
4552
1 f
4553
10 s
4554
1621 1566(be)N
4555
1721(a)X
4556
1781(string)X
4557
1987(corresponding)X
4558
2470(to)X
4559
2556(the)X
4560
2 f
4561
2678(i)X
4562
1 f
4563
2700('th)X
4564
2813(entry)X
4565
3003(of)X
4566
2 f
4567
3095(SHIFT)X
4568
1 f
4569
3313(.)X
4570
3378(There)X
4571
3591(are)X
4572
3715(two)X
4573
3860(cases:)X
4574
4077(either)X
4575
2 f
4576
4285(X)X
4577
1 f
4578
648 1676(appears)N
4579
920(somewhere)X
4580
1312(in)X
4581
1400(one)X
4582
1542(of)X
4583
1635(the)X
4584
2 f
4585
1759(P)X
4586
7 s
4587
1812 1692(j)N
4588
1 f
4589
10 s
4590
1834 1676('s)N
4591
1918(or)X
4592
2011(not.)X
4593
2179(For)X
4594
2316(the)X
4595
2440(latter)X
4596
2631(case,)X
4597
2816(we)X
4598
2936(store)X
4599
2 f
4600
3118(m)X
4601
9 f
4602
3182(-)X
4603
2 f
4604
3226(b)X
4605
9 f
4606
3272(+)X
4607
1 f
4608
3316(1)X
4609
3382(in)X
4610
2 f
4611
3470(SHIFT)X
4612
1 f
4613
3701([)X
4614
2 f
4615
3728(i)X
4616
1 f
4617
3763(].)X
4618
3856(For)X
4619
3992(the)X
4620
4115(former)X
4621
648 1786(case,)N
4622
829(we)X
4623
945(\256nd)X
4624
1091(the)X
4625
1211(rightmost)X
4626
1539 0.3611(occurrence)AX
4627
1915(of)X
4628
2 f
4629
2004(X)X
4630
1 f
4631
2075(in)X
4632
2159(any)X
4633
2297(of)X
4634
2386(the)X
4635
2 f
4636
2506(P)X
4637
7 s
4638
2559 1802(j)N
4639
1 f
4640
10 s
4641
2581 1786('s)N
4642
2661(that)X
4643
2803(contain)X
4644
3061(it;)X
4645
3149(suppose)X
4646
3429(it)X
4647
3495(is)X
4648
3570(in)X
4649
2 f
4650
3654(P)X
4651
7 s
4652
3703 1802(y)N
4653
1 f
4654
10 s
4655
3756 1786(and)N
4656
3894(that)X
4657
2 f
4658
4036(X)X
4659
1 f
4660
4107(ends)X
4661
4276(at)X
4662
648 1896(position)N
4663
2 f
4664
925(q)X
4665
1 f
4666
985(of)X
4667
2 f
4668
1072(P)X
4669
7 s
4670
1121 1912(y)N
4671
1 f
4672
10 s
4673
1152 1896(.)N
4674
1212(Then)X
4675
1397(we)X
4676
1511(store)X
4677
2 f
4678
1687(m)X
4679
9 f
4680
1764(-)X
4681
2 f
4682
1821(q)X
4683
1 f
4684
1881(in)X
4685
2 f
4686
1963(SHIFT)X
4687
1 f
4688
2194([)X
4689
2 f
4690
2221(i)X
4691
1 f
4692
2256(].)X
4693
848 2039(If)N
4694
925(the)X
4695
1046(shift)X
4696
1211(value)X
4697
1409(is)X
4698
1486(>)X
4699
1555(0,)X
4700
1639(then)X
4701
1801(we)X
4702
1919(can)X
4703
2055(safely)X
4704
2271(shift.)X
4705
2477(Otherwise,)X
4706
2851(it)X
4707
2919(is)X
4708
2996(possible)X
4709
3282(that)X
4710
3426(the)X
4711
3548(current)X
4712
3800(substring)X
4713
4117(we)X
4714
4235(are)X
4715
648 2149(looking)N
4716
913(at)X
4717
992(in)X
4718
1074(the)X
4719
1192(text)X
4720
1332(matches)X
4721
1615(some)X
4722
1804(pattern)X
4723
2047(in)X
4724
2129(the)X
4725
2247(pattern)X
4726
2490(list.)X
4727
2647(To)X
4728
2756(avoid)X
4729
2954(comparing)X
4730
3317(the)X
4731
3435(substring)X
4732
3748(to)X
4733
3830(every)X
4734
4029(pattern)X
4735
4272(in)X
4736
648 2259(the)N
4737
766(pattern)X
4738
1009(list,)X
4739
1146(we)X
4740
1260(use)X
4741
1387(a)X
4742
1443(hashing)X
4743
1712(technique)X
4744
2044(to)X
4745
2127(minimize)X
4746
2450(the)X
4747
2569(number)X
4748
2835(of)X
4749
2923(patterns)X
4750
3198(to)X
4751
3281(be)X
4752
3378(compared.)X
4753
3756(In)X
4754
3844(the)X
4755
3963(preprocess-)X
4756
648 2369(ing)N
4757
771(we)X
4758
886(build)X
4759
1071(a)X
4760
1128(hash)X
4761
1296(table)X
4762
2 f
4763
1473(HASH)X
4764
1 f
4765
1699(such)X
4766
1867(that)X
4767
2008(a)X
4768
2065(pattern)X
4769
2309(with)X
4770
2472(hash)X
4771
2640(value)X
4772
2 f
4773
2840(j)X
4774
1 f
4775
2882(is)X
4776
2955(put)X
4777
3077(in)X
4778
3159(a)X
4779
3215(linked-list)X
4780
3559(pointed)X
4781
3819(to)X
4782
3901(by)X
4783
2 f
4784
4001(HASH)X
4785
1 f
4786
4219([)X
4787
2 f
4788
4252(j)X
4789
1 f
4790
4287(].)X
4791
648 2479(So,)N
4792
780(in)X
4793
870(the)X
4794
996(search)X
4795
1231(process,)X
4796
1521(whenever)X
4797
1863(we)X
4798
1986(are)X
4799
2114(going)X
4800
2325(to)X
4801
2416(compare)X
4802
2722(current)X
4803
2979(aligned)X
4804
3244(substring)X
4805
3566(to)X
4806
3657(the)X
4807
3784(patterns,)X
4808
4087(we)X
4809
4210(\256rst)X
4810
648 2589(compute)N
4811
948(the)X
4812
1070(hash)X
4813
1241(value)X
4814
1438(of)X
4815
1528(the)X
4816
1649(substring)X
4817
1965(and)X
4818
2104(compare)X
4819
2404(the)X
4820
2525(substring)X
4821
2841(only)X
4822
3006(to)X
4823
3091(those)X
4824
3283(patterns)X
4825
3560(that)X
4826
3703(have)X
4827
3878(the)X
4828
3999(same)X
4829
4187(hash)X
4830
648 2699(value.)N
4831
862(The)X
4832
1007(algorithm)X
4833
1338(for)X
4834
1452(searching)X
4835
1780(the)X
4836
1898(text)X
4837
2038(is)X
4838
2111(sketched)X
4839
2412(in)X
4840
2494(Figure)X
4841
2723(1.)X
4842
848 2842(The)N
4843
993(multi-pattern)X
4844
1431(matching)X
4845
1749(algorithm)X
4846
2080(described)X
4847
2408(above)X
4848
2620(can)X
4849
2752(be)X
4850
2848(used)X
4851
3015(to)X
4852
3097(solve)X
4853
3286(the)X
4854
3405(approximate)X
4855
3827(string-matching)X
4856
648 2952(problem.)N
4857
982(Let)X
4858
2 f
4859
1116(P)X
4860
1 f
4861
1192(=)X
4862
2 f
4863
1263(p)X
4864
1 f
4865
7 s
4866
1312 2968(1)N
4867
10 s
4868
1359 2952(,)N
4869
2 f
4870
1385(p)X
4871
1 f
4872
7 s
4873
1434 2968(2)N
4874
10 s
4875
1481 2952(,)N
4876
2 f
4877
1507(...)X
4878
1 f
4879
(,)S
4880
2 f
4881
1606(p)X
4882
7 s
4883
2968(M)Y
4884
1 f
4885
10 s
4886
1725 2952(be)N
4887
1827(a)X
4888
1889(pattern)X
4889
2138(string,)X
4890
2366(and)X
4891
2508(let)X
4892
2 f
4893
2614(T)X
4894
1 f
4895
2684(=)X
4896
2 f
4897
2755(a)X
4898
1 f
4899
7 s
4900
2804 2968(1)N
4901
10 s
4902
2838 2952(,)N
4903
2 f
4904
2864(a)X
4905
1 f
4906
7 s
4907
2913 2968(2)N
4908
10 s
4909
2947 2952(,)N
4910
2 f
4911
2973(...a)X
4912
7 s
4913
2968(N)Y
4914
1 f
4915
10 s
4916
3142 2952(be)N
4917
3244(a)X
4918
3306(text)X
4919
3452(string.)X
4920
3700(We)X
4921
3838(partition)X
4922
2 f
4923
4135(P)X
4924
1 f
4925
4210(into)X
4926
2 f
4927
648 3062(k)N
4928
9 f
4929
703(+)X
4930
1 f
4931
760(1)X
4932
821(fragments)X
4933
2 f
4934
1163(P)X
4935
1 f
4936
7 s
4937
1221 3078(1)N
4938
10 s
4939
1255 3062(,)N
4940
2 f
4941
1281(P)X
4942
1 f
4943
7 s
4944
1339 3078(2)N
4945
10 s
4946
1373 3062(,)N
4947
2 f
4948
1399(...)X
4949
1 f
4950
(,)S
4951
2 f
4952
1485(P)X
4953
7 s
4954
1534 3078(k)N
4955
9 f
4956
1568(+)X
4957
1 f
4958
1599(1)X
4959
10 s
4960
1633 3062(,)N
4961
1674(each)X
4962
1843(of)X
4963
1931(size)X
4964
2 f
4965
2077(m)X
4966
1 f
4967
2156(=)X
4968
2 f
4969
2223(M)X
4970
2296(/)X
4971
1 f
4972
2324(\()X
4973
2 f
4974
2351(k)X
4975
9 f
4976
2400(+)X
4977
1 f
4978
2444(1\).)X
4979
2573(Let)X
4980
2 f
4981
2702(T)X
4982
7 s
4983
2746 3078 4.8750(ij)AN
4984
1 f
4985
10 s
4986
2810 3062(=)N
4987
2 f
4988
2877(a)X
4989
7 s
4990
3078(i)Y
4991
1 f
4992
10 s
4993
2939 3062(,)N
4994
2 f
4995
2965(...)X
4996
1 f
4997
(,)S
4998
2 f
4999
3051(a)X
5000
7 s
5001
3095 3078(j)N
5002
1 f
5003
10 s
5004
3139 3062(be)N
5005
3237(a)X
5006
3295(substring)X
5007
3610(of)X
5008
2 f
5009
3699(T)X
5010
1 f
5011
3743(.)X
5012
3805(By)X
5013
3920(a)X
5014
3978(pigeonhole)X
5015
648 3172(principle,)N
5016
980(if)X
5017
2 f
5018
1056(T)X
5019
7 s
5020
1100 3188 4.8750(ij)AN
5021
1 f
5022
10 s
5023
1169 3172(differs)N
5024
1406(from)X
5025
2 f
5026
1589(P)X
5027
1 f
5028
1665(by)X
5029
1772(no)X
5030
1879(more)X
5031
2071(than)X
5032
2 f
5033
2236(k)X
5034
1 f
5035
2298(errors,)X
5036
2532(then)X
5037
2696(one)X
5038
2838(of)X
5039
2931(the)X
5040
3055(fragment)X
5041
3371(must)X
5042
3552(match)X
5043
3774(a)X
5044
3836(substring)X
5045
4155(of)X
5046
2 f
5047
4248(T)X
5048
7 s
5049
4292 3188 4.8750(ij)AN
5050
1 f
5051
10 s
5052
648 3282(exactly.)N
5053
848 3425(The)N
5054
998(approximate)X
5055
1425(string)X
5056
1633(matching)X
5057
1957(algorithm)X
5058
2294(is)X
5059
2373(conducted)X
5060
2729(in)X
5061
2817(two)X
5062
2963(phases.)X
5063
3243(In)X
5064
3336(the)X
5065
3460(\256rst)X
5066
3610(phase)X
5067
3819(we)X
5068
3939(partition)X
5069
4236(the)X
5070
648 3535(pattern)N
5071
892(into)X
5072
2 f
5073
1037(k)X
5074
9 f
5075
1092(+)X
5076
1 f
5077
1149(1)X
5078
1210(fragments)X
5079
1552(and)X
5080
1688(use)X
5081
1815(the)X
5082
1933(multi-pattern)X
5083
2371(string)X
5084
2573(matching)X
5085
2891(algorithm)X
5086
3222(to)X
5087
3304(\256nd)X
5088
3448(all)X
5089
3548(those)X
5090
3737(places)X
5091
3958(that)X
5092
4098(contain)X
5093
648 3645(one)N
5094
786(of)X
5095
875(the)X
5096
995(fragments.)X
5097
1378(If)X
5098
1455(there)X
5099
1639(is)X
5100
1715(a)X
5101
1774(match)X
5102
1993(of)X
5103
2083(a)X
5104
2142(fragment)X
5105
2455(at)X
5106
2536(position)X
5107
2 f
5108
2816(i)X
5109
1 f
5110
2861(of)X
5111
2951(the)X
5112
3072(text,)X
5113
3235(we)X
5114
3352(mark)X
5115
3540(the)X
5116
3661(positions)X
5117
2 f
5118
3972(i)X
5119
9 f
5120
4013(-)X
5121
2 f
5122
4070(M)X
5123
9 f
5124
4156(-)X
5125
2 f
5126
4213(k)X
5127
1 f
5128
4272(to)X
5129
2 f
5130
648 3755(i)N
5131
9 f
5132
689(+)X
5133
2 f
5134
746(M)X
5135
9 f
5136
832(+)X
5137
2 f
5138
889(k)X
5139
9 f
5140
944(-)X
5141
2 f
5142
988(m)X
5143
1 f
5144
1077(as)X
5145
1175(a)X
5146
1242('candidate')X
5147
1635(area.)X
5148
1840(After)X
5149
2040(the)X
5150
2168(\256rst)X
5151
2322(phase)X
5152
2535(is)X
5153
2618(done)X
5154
2804(we)X
5155
2928(apply)X
5156
3136(the)X
5157
3264(approximate)X
5158
3695(matching)X
5159
4023(algorithm)X
5160
648 3865(described)N
5161
988(in)X
5162
1082(section)X
5163
1341(3.1)X
5164
1473(to)X
5165
1567(\256nd)X
5166
1724(the)X
5167
1855(actual)X
5168
2080(matches)X
5169
2376(in)X
5170
2471(those)X
5171
2673(marked)X
5172
2947(area.)X
5173
3155(\(If)X
5174
3269(the)X
5175
3400(pattern)X
5176
3656(size)X
5177
3814(is)X
5178
2 f
5179
3900(>)X
5180
1 f
5181
3967(32,)X
5182
4100(we)X
5183
4227(use)X
5184
3 f
5185
648 4071(Algorithm)N
5186
1 f
5187
1024(Multi-Patterns)X
5188
936 4181(Let)N
5189
2 f
5190
1063(p)X
5191
1 f
5192
1123(be)X
5193
1219(the)X
5194
1337(current)X
5195
1585(position)X
5196
1862(of)X
5197
1949(the)X
5198
2067(text)X
5199
2207(;)X
5200
3 f
5201
936 4291(while)N
5202
1 f
5203
1138(\()X
5204
2 f
5205
1165(p)X
5206
1 f
5207
1225(<)X
5208
2 f
5209
1290(N)X
5210
1 f
5211
1343(\))X
5212
1410(/*)X
5213
2 f
5214
1492(N)X
5215
1 f
5216
1565(is)X
5217
1638(the)X
5218
1756(end)X
5219
1892(position)X
5220
2169(of)X
5221
2256(the)X
5222
2374(text)X
5223
2514(*/)X
5224
936 4401({)N
5225
2 f
5226
1108 4511(blk_idx)N
5227
1 f
5228
1364(=)X
5229
2 f
5230
1429(map)X
5231
1 f
5232
1573(\()X
5233
2 f
5234
1600(a)X
5235
7 s
5236
4527(p)Y
5237
9 f
5238
1677(-)X
5239
2 f
5240
1708(b)X
5241
9 f
5242
1745(+)X
5243
1 f
5244
1776(1)X
5245
2 f
5246
10 s
5247
1810 4511(a)N
5248
7 s
5249
4527(p)Y
5250
9 f
5251
1887(-)X
5252
2 f
5253
1918(b)X
5254
9 f
5255
1955(+)X
5256
1 f
5257
1986(2)X
5258
10 s
5259
2040 4487(.)N
5260
2080(.)X
5261
2120(.)X
5262
2 f
5263
2160 4511(a)N
5264
7 s
5265
4527(p)Y
5266
1 f
5267
10 s
5268
2234 4511(\))N
5269
2281(/*)X
5270
2 f
5271
2363(map)X
5272
1 f
5273
2521(transforms)X
5274
2884(a)X
5275
2940(string)X
5276
3142(of)X
5277
3229(size)X
5278
2 f
5279
3374(b)X
5280
1 f
5281
3434(into)X
5282
3578(an)X
5283
3674(integer)X
5284
3917(*/)X
5285
2 f
5286
1108 4621(shift_value)N
5287
1 f
5288
1479(=)X
5289
2 f
5290
1544(SHIFT)X
5291
1 f
5292
1775([)X
5293
2 f
5294
1802(blk_idx)X
5295
1 f
5296
2051(];)X
5297
3 f
5298
1108 4731(if)N
5299
1 f
5300
1177(\()X
5301
2 f
5302
1204(shift_value)X
5303
1 f
5304
1575(>)X
5305
1640(0\))X
5306
2 f
5307
1727(p)X
5308
1 f
5309
1787(=)X
5310
2 f
5311
1852(p)X
5312
1 f
5313
1912(+)X
5314
2 f
5315
1977(shift_value)X
5316
1 f
5317
2328(;)X
5318
3 f
5319
1108 4841(else)N
5320
1 f
5321
1281 4951(compute)N
5322
1577(the)X
5323
1695(hash)X
5324
1862(value)X
5325
2056(of)X
5326
2 f
5327
2143(a)X
5328
7 s
5329
4967(p)Y
5330
9 f
5331
2220(-)X
5332
2 f
5333
2251(m)X
5334
9 f
5335
2300(+)X
5336
1 f
5337
2331(1)X
5338
10 s
5339
2385 4927(.)N
5340
2425(.)X
5341
2465(.)X
5342
2 f
5343
2505 4951(a)N
5344
7 s
5345
4967(p)Y
5346
1 f
5347
10 s
5348
2579 4951(;)N
5349
1281 5061(compare)N
5350
2 f
5351
1578(a)X
5352
7 s
5353
5077(p)Y
5354
9 f
5355
1655(-)X
5356
2 f
5357
1686(m)X
5358
9 f
5359
1735(+)X
5360
1 f
5361
1766(1)X
5362
10 s
5363
1820 5037(.)N
5364
1860(.)X
5365
1900(.)X
5366
2 f
5367
1940 5061(a)N
5368
7 s
5369
5077(p)Y
5370
1 f
5371
10 s
5372
2034 5061(to)N
5373
2116(every)X
5374
2315(pattern)X
5375
2558(that)X
5376
2698(has)X
5377
2825(the)X
5378
2943(same)X
5379
3128(hash)X
5380
3295(value;)X
5381
3 f
5382
1281 5171(if)N
5383
1 f
5384
1350(there)X
5385
1531(is)X
5386
1604(a)X
5387
1660(match)X
5388
3 f
5389
1876(then)X
5390
1 f
5391
2047(reports)X
5392
2 f
5393
2290(a)X
5394
7 s
5395
5187(p)Y
5396
9 f
5397
2367(-)X
5398
2 f
5399
2398(m)X
5400
9 f
5401
2447(+)X
5402
1 f
5403
2478(1)X
5404
10 s
5405
2532 5147(.)N
5406
2572(.)X
5407
2612(.)X
5408
2 f
5409
2652 5171(a)N
5410
7 s
5411
5187(p)Y
5412
1 f
5413
10 s
5414
2726 5171(;)N
5415
2 f
5416
1281 5281(p)N
5417
1 f
5418
1341(=)X
5419
2 f
5420
1406(p)X
5421
1 f
5422
1466(+)X
5423
1531(1;)X
5424
936 5391(})N
5425
3 f
5426
1454 5611(Figure)N
5427
1701(1:)X
5428
1 f
5429
1808(A)X
5430
1886(sketch)X
5431
2111(of)X
5432
2198(the)X
5433
2316(algorithm)X
5434
2647(for)X
5435
2761(multi-pattern)X
5436
3199(searching.)X
5437
5438
7 p
5439
%%Page: 7 7
5440
10 s 10 xH 0 xS 1 f
5441
3 f
5442
1 f
5443
648 686(Ukkonen's)N
5444
2 f
5445
1020(O)X
5446
1 f
5447
1091(\()X
5448
2 f
5449
1118(Nk)X
5450
1 f
5451
1213(\))X
5452
1260(expected-time)X
5453
1735(algorithm)X
5454
2066([Uk85].\))X
5455
848 829(Our)N
5456
1003(algorithm)X
5457
1345(is)X
5458
1429(very)X
5459
1603(fast)X
5460
1750(when)X
5461
1955(the)X
5462
2084(pattern)X
5463
2338(is)X
5464
2422(long)X
5465
2595(and)X
5466
2742(the)X
5467
2871(number)X
5468
3147(of)X
5469
3245(errors)X
5470
3464(is)X
5471
3548(not)X
5472
3681(high)X
5473
3854(\(assuming)X
5474
4214(that)X
5475
2 f
5476
648 939(k)N
5477
703(<)X
5478
770(M)X
5479
843(/)X
5480
1 f
5481
871(log)X
5482
2 f
5483
7 s
5484
973 955(b)N
5485
10 s
5486
1007 939(M)N
5487
1 f
5488
1074(\).)X
5489
1170(Unlike)X
5490
1417(the)X
5491
1544(approximate)X
5492
1974(Boyer-Moore)X
5493
2440(string)X
5494
2650(matching)X
5495
2976(algorithm)X
5496
3315(in)X
5497
3405([TU90],)X
5498
3694(whose)X
5499
3927(performance)X
5500
648 1049(degrades)N
5501
956(greatly)X
5502
1201(when)X
5503
1397(the)X
5504
1517(size)X
5505
1664(of)X
5506
1753(the)X
5507
1873(alphabet)X
5508
2167(set)X
5509
2278(is)X
5510
2353(small,)X
5511
2568(our)X
5512
2697(algorithm)X
5513
3030(is)X
5514
3106(not)X
5515
3231(sensitive)X
5516
3534(to)X
5517
3619(the)X
5518
3740(alphabet)X
5519
4035(size.)X
5520
4223(For)X
5521
648 1159(example,)N
5522
964(for)X
5523
1082(DNA)X
5524
1280(patterns)X
5525
1558(of)X
5526
1648(size)X
5527
1796(500,)X
5528
1959(allowing)X
5529
2262(25)X
5530
2365(errors,)X
5531
2596(our)X
5532
2726(algorithm)X
5533
3060(is)X
5534
3136(about)X
5535
3337(two)X
5536
3480(orders)X
5537
3704(of)X
5538
3794(magnitude)X
5539
4155(faster)X
5540
648 1269(than)N
5541
814(Ukkonen's)X
5542
2 f
5543
1194(O)X
5544
1 f
5545
1265(\()X
5546
2 f
5547
1292(Nk)X
5548
1 f
5549
1387(\))X
5550
1442(expected-time)X
5551
1925(algorithm)X
5552
2264([Uk85])X
5553
2525(and)X
5554
2670(algorithm)X
5555
3010(MN2)X
5556
3208([GP90])X
5557
3473(\(which)X
5558
3725(are)X
5559
3853(the)X
5560
3980(two)X
5561
4129(fastest)X
5562
648 1379(algorithms)N
5563
1017(among)X
5564
1262(the)X
5565
1387(algorithms)X
5566
1756(compared)X
5567
2100(in)X
5568
2189([CL90]\).)X
5569
2518(Experimental)X
5570
2976(results)X
5571
3211(are)X
5572
3336(given)X
5573
3540(in)X
5574
3628(the)X
5575
3752(next)X
5576
3916(section.)X
5577
4209(The)X
5578
648 1489(algorithm)N
5579
979(is)X
5580
1052(very)X
5581
1215(fast)X
5582
1351(for)X
5583
1465(practical)X
5584
1762(applications)X
5585
2169(for)X
5586
2283(searching)X
5587
2611(both)X
5588
2773(English)X
5589
3037(text)X
5590
3177(and)X
5591
3313(DNA)X
5592
3507(data.)X
5593
6 f
5594
14 s
5595
648 1741(4.)N
5596
803(Experim)X
5597
1244(ental)X
5598
1536(Results)X
5599
1 f
5600
10 s
5601
648 1916(We)N
5602
794(present)X
5603
1060(four)X
5604
1228(brief)X
5605
1414(experiments.)X
5606
1860(The)X
5607
2019(numbers)X
5608
2329(given)X
5609
2541(here)X
5610
2714(should)X
5611
2962(be)X
5612
3073(taken)X
5613
3282(with)X
5614
3459(caution.)X
5615
3770(Any)X
5616
3943(such)X
5617
4125(results)X
5618
648 2026(depend)N
5619
910(on)X
5620
1019(the)X
5621
1146(architecture,)X
5622
1575(the)X
5623
1702(operating)X
5624
2034(system,)X
5625
2305(the)X
5626
2432(compilers)X
5627
2777(used,)X
5628
2973(not)X
5629
3104(to)X
5630
3195(mention)X
5631
3486(the)X
5632
3613(patterns)X
5633
3896(and)X
5634
4041(test)X
5635
4181(\256les.)X
5636
648 2136(These)N
5637
862(tests)X
5638
1026(are)X
5639
1147(by)X
5640
1249(no)X
5641
1351(means)X
5642
1578(comprehensive.)X
5643
2126(They)X
5644
2313(are)X
5645
2434(given)X
5646
2634(here)X
5647
2795(to)X
5648
2879(show)X
5649
3070(that)X
5650
3212(agrep)X
5651
3413(is)X
5652
3488(fast)X
5653
3627(enough)X
5654
3886(to)X
5655
3971(be)X
5656
4070(used)X
5657
4240(for)X
5658
648 2246(large)N
5659
832(\256les.)X
5660
1028(Differences)X
5661
1427(of)X
5662
1517(20-30%)X
5663
1794(in)X
5664
1879(the)X
5665
2000(running)X
5666
2272(times)X
5667
2468(are)X
5668
2589(not)X
5669
2713(signi\256cant.)X
5670
3108(Thus,)X
5671
3310(all)X
5672
3412(Boyer-Moore)X
5673
3871(type)X
5674
4031(programs)X
5675
648 2356(are)N
5676
767(about)X
5677
965(the)X
5678
1083(same)X
5679
1268(for)X
5680
1382(simple)X
5681
1615(patterns.)X
5682
1929(Agrep)X
5683
2150(seems)X
5684
2366(better)X
5685
2569(for)X
5686
2684(multi)X
5687
2873(patterns.)X
5688
3188(For)X
5689
3320(approximate)X
5690
3742(matching,)X
5691
4081(agrep)X
5692
4281(is)X
5693
648 2466(one)N
5694
791(to)X
5695
880(two)X
5696
1027(orders)X
5697
1255(of)X
5698
1349(magnitude)X
5699
1714(faster)X
5700
1920(than)X
5701
2085(other)X
5702
2277(programs)X
5703
2607(that)X
5704
2754(we)X
5705
2875(tested.)X
5706
3129(We)X
5707
3268(believe)X
5708
3527(that)X
5709
3673(the)X
5710
3797(main)X
5711
3983(strength)X
5712
4267(of)X
5713
648 2576(agrep)N
5714
847(is)X
5715
920(that)X
5716
1060(it)X
5717
1124(is)X
5718
1197(more)X
5719
1382(\257exible,)X
5720
1662(general,)X
5721
1939(and)X
5722
2075(convenient)X
5723
2447(than)X
5724
2605(all)X
5725
2705(previous)X
5726
3001(programs.)X
5727
848 2719(All)N
5728
973(tests)X
5729
1138(were)X
5730
1318(run)X
5731
1448(on)X
5732
1551(a)X
5733
1611(SUN)X
5734
1795(SparcStation)X
5735
2228(II)X
5736
2306(running)X
5737
2579(UNIX.)X
5738
2844(Two)X
5739
3015(\256les)X
5740
3172(were)X
5741
3353(used,)X
5742
3544(both)X
5743
3710(of)X
5744
3801(size)X
5745
3950(1MB,)X
5746
4158(one)X
5747
4298(a)X
5748
648 2829(sub-dictionary)N
5749
1140(and)X
5750
1285(one)X
5751
1430(a)X
5752
1495(collection)X
5753
1840(of)X
5754
1936(bibliographic)X
5755
2392(data.)X
5756
2595(The)X
5757
2749(numbers)X
5758
3054(are)X
5759
3182(in)X
5760
3273(seconds)X
5761
3556(and)X
5762
3701(are)X
5763
3829(the)X
5764
3956(averages)X
5765
4267(of)X
5766
648 2939(several)N
5767
903(experiments.)X
5768
1362(They)X
5769
1554(were)X
5770
1738(measured)X
5771
2073(by)X
5772
2180(the)X
5773
2305(time)X
5774
2474(facility)X
5775
2728(in)X
5776
2818(UNIX)X
5777
3047(and)X
5778
3191(only)X
5779
3361(user)X
5780
3523(times)X
5781
3724(were)X
5782
3909(taken)X
5783
4111(\(which)X
5784
648 3049(adds)N
5785
815(considerably)X
5786
1245(to)X
5787
1327(their)X
5788
1494(impreciseness\).)X
5789
848 3192(Table)N
5790
1062(1)X
5791
1133(compares)X
5792
1472(agrep)X
5793
1683(against)X
5794
1942(other)X
5795
2139(programs)X
5796
2474(for)X
5797
2 f
5798
2600(exact)X
5799
1 f
5800
2802(string)X
5801
3016(matching.)X
5802
3386(The)X
5803
3543(\256rst)X
5804
3699(three)X
5805
3892(programs)X
5806
4227(use)X
5807
648 3302(Boyer-Moore)N
5808
1107(type)X
5809
1267(algorithms.)X
5810
1671(The)X
5811
1818(original)X
5812
2089(egrep)X
5813
2289(does)X
5814
2457(not.)X
5815
2620(We)X
5816
2753(used)X
5817
2921(50)X
5818
3022(words)X
5819
3239(of)X
5820
3327(varying)X
5821
3593(sizes)X
5822
3770(\(3-12\))X
5823
3992(as)X
5824
4080(patterns)X
5825
648 3412(and)N
5826
784(averaged)X
5827
1095(the)X
5828
1213(results.)X
5829
10 f
5830
1781 3508(i)N
5831
1801(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
5832
1 f
5833
1821 3618(text)N
5834
1961(size)X
5835
2206(agrep)X
5836
2544(gre)X
5837
2806(e?grep)X
5838
3141(egrep)X
5839
10 f
5840
1781 3648(i)N
5841
1801(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
5842
1 f
5843
1821 3758(1Mb)N
5844
2226(0.09)X
5845
2526(0.11)X
5846
2843(0.11)X
5847
3161(0.79)X
5848
1821 3868(200Kb)N
5849
2206(0.028)X
5850
2506(0.024)X
5851
2823(0.038)X
5852
3141(0.218)X
5853
10 f
5854
1781 3898(i)N
5855
1801(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
5856
1781(c)X
5857
3828(c)Y
5858
3748(c)Y
5859
3668(c)Y
5860
3588(c)Y
5861
3361 3898(c)N
5862
3828(c)Y
5863
3748(c)Y
5864
3668(c)Y
5865
3588(c)Y
5866
1 f
5867
1881 4041(Table)N
5868
2084(1:)X
5869
2186(Exact)X
5870
2389(matching)X
5871
2707(of)X
5872
2794(simple)X
5873
3027(strings.)X
5874
848 4217(Table)N
5875
1053(2)X
5876
1115(shows)X
5877
1337(results)X
5878
1568(of)X
5879
1657(searching)X
5880
1987(for)X
5881
2103(multi)X
5882
2293(patterns.)X
5883
2609(In)X
5884
2698(the)X
5885
2819(\256rst)X
5886
2966(line)X
5887
3109(the)X
5888
3230(pattern)X
5889
3476(consisted)X
5890
3797(of)X
5891
3887(50)X
5892
3990(words)X
5893
4209(\(the)X
5894
648 4327(same)N
5895
837(words)X
5896
1057(that)X
5897
1201(were)X
5898
1382(used)X
5899
1553(in)X
5900
1639(Table)X
5901
1846(1,)X
5902
1930(but)X
5903
2056(all)X
5904
2160(in)X
5905
2245(once\))X
5906
2447(searched)X
5907
2752(inside)X
5908
2966(a)X
5909
3025(dictionary;)X
5910
3395(in)X
5911
3480(the)X
5912
3601(second)X
5913
3847(line)X
5914
3990(the)X
5915
4111(pattern)X
5916
648 4437(consists)N
5917
921(of)X
5918
1008(20)X
5919
1108(separate)X
5920
1392(titles)X
5921
1567(\(each)X
5922
1762(two)X
5923
1902(words)X
5924
2118(long\),)X
5925
2327(searched)X
5926
2629(in)X
5927
2711(a)X
5928
2767(bibliographic)X
5929
3214(\256le.)X
5930
10 f
5931
1791 4533(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)N
5932
1 f
5933
1831 4643(pattern)N
5934
2247(agrep)X
5935
2564(gre)X
5936
2806(e?grep)X
5937
3141(fgrep)X
5938
10 f
5939
1791 4673(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)N
5940
1 f
5941
1831 4783(50)N
5942
1931(words)X
5943
2266(1.15)X
5944
2546(2.57)X
5945
2843(6.11)X
5946
3156(8.13)X
5947
1831 4893(20)N
5948
1931(titles)X
5949
2266(0.18)X
5950
2546(0.71)X
5951
2843(1.53)X
5952
3156(5.64)X
5953
10 f
5954
1791 4923(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)N
5955
1791(c)X
5956
4853(c)Y
5957
4773(c)Y
5958
4693(c)Y
5959
4613(c)Y
5960
3351 4923(c)N
5961
4853(c)Y
5962
4773(c)Y
5963
4693(c)Y
5964
4613(c)Y
5965
1 f
5966
1883 5066(Table)N
5967
2086(2:)X
5968
2188(Exact)X
5969
2391(matching)X
5970
2709(of)X
5971
2796(multi)X
5972
2984(patterns.)X
5973
848 5242(Table)N
5974
1053(3)X
5975
1115(shows)X
5976
1337(typical)X
5977
1577(running)X
5978
1848(times)X
5979
2043(for)X
5980
2159(approximate)X
5981
2582(matching.)X
5982
2943(Two)X
5983
3113(patterns)X
5984
3390(were)X
5985
3570(used)X
5986
3740(\320)X
5987
3843(`matching')X
5988
4218(and)X
5989
648 5352(`string)N
5990
888(matching')X
5991
1243(\320)X
5992
1353(and)X
5993
1499(we)X
5994
1623(tested)X
5995
1840(each)X
5996
2018(one)X
5997
2164(with)X
5998
2336(1,)X
5999
2426(2,)X
6000
2516(and)X
6001
2662(3)X
6002
2732(errors)X
6003
2950(\(denoted)X
6004
3261(by)X
6005
3371(Er\).)X
6006
3544(Other)X
6007
3757(programs)X
6008
4090(that)X
6009
4240(we)X
6010
648 5462(tested)N
6011
855(did)X
6012
977(not)X
6013
1099(come)X
6014
1293(close.)X
6015
6016
8 p
6017
%%Page: 8 8
6018
10 s 10 xH 0 xS 1 f
6019
3 f
6020
1 f
6021
10 f
6022
1772 639(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)N
6023
1 f
6024
1812 749(pattern)N
6025
2486(Er)X
6026
2582(=)X
6027
2647(1)X
6028
2807(Er)X
6029
2903(=)X
6030
2968(2)X
6031
3128(Er)X
6032
3224(=)X
6033
3289(3)X
6034
10 f
6035
1772 779(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)N
6036
1 f
6037
1812 889(`string)N
6038
2041(matching')X
6039
2516(0.26)X
6040
2837(0.55)X
6041
3158(0.76)X
6042
1812 999(`matching')N
6043
2516(0.22)X
6044
2837(0.66)X
6045
3158(1.14)X
6046
10 f
6047
1772 1029(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)N
6048
1772(c)X
6049
959(c)Y
6050
879(c)Y
6051
799(c)Y
6052
719(c)Y
6053
3369 1029(c)N
6054
959(c)Y
6055
879(c)Y
6056
799(c)Y
6057
719(c)Y
6058
1 f
6059
1761 1172(Table)N
6060
1964(3:)X
6061
2066(Approximate)X
6062
2509(matching)X
6063
2827(of)X
6064
2914(simple)X
6065
3147(strings.)X
6066
848 1348(Table)N
6067
1058(4)X
6068
1125(shows)X
6069
1352(typical)X
6070
1597(running)X
6071
1873(times)X
6072
2073(for)X
6073
2194(more)X
6074
2386(complicated)X
6075
2805(patterns,)X
6076
3106(including)X
6077
3435(regular)X
6078
3691(expressions.)X
6079
4133(Agrep)X
6080
648 1458(does)N
6081
819(not)X
6082
945(yet)X
6083
1067(use)X
6084
1198(any)X
6085
1337(Boyer-Moore)X
6086
1797(type)X
6087
1958(\256ltering)X
6088
2234(for)X
6089
2351(these)X
6090
2539(patterns.)X
6091
2856(As)X
6092
2968(a)X
6093
3027(result,)X
6094
3248(the)X
6095
3369(running)X
6096
3641(times)X
6097
3837(are)X
6098
3959(slower)X
6099
4196(than)X
6100
648 1568(they)N
6101
810(are)X
6102
933(for)X
6103
1051(simpler)X
6104
1315(patterns.)X
6105
1633(The)X
6106
1782(best)X
6107
1935(algorithm)X
6108
2270(we)X
6109
2388(know)X
6110
2590(for)X
6111
2708(approximate)X
6112
3133(matching)X
6113
3455(to)X
6114
3542(arbitrary)X
6115
3844(regular)X
6116
4097(expres-)X
6117
648 1678(sions)N
6118
835(is)X
6119
911(by)X
6120
1014(Myers)X
6121
1242(and)X
6122
1381(Miller)X
6123
1604([MM89].)X
6124
1943(Its)X
6125
2045(running)X
6126
2316(times)X
6127
2511(for)X
6128
2627(the)X
6129
2747(cases)X
6130
2939(we)X
6131
3055(tested)X
6132
3264(were)X
6133
3443(more)X
6134
3630(than)X
6135
3790(an)X
6136
3888(order)X
6137
4080(of)X
6138
4169(mag-)X
6139
648 1788(nitude)N
6140
870(slower)X
6141
1106(than)X
6142
1266(our)X
6143
1395(algorithm,)X
6144
1748(but)X
6145
1872(this)X
6146
2009(is)X
6147
2084(not)X
6148
2208(a)X
6149
2266(fair)X
6150
2400(test,)X
6151
2553(because)X
6152
2830(Myers)X
6153
3057(and)X
6154
3195(Miller's)X
6155
3476(algorithm)X
6156
3810(can)X
6157
3945(handle)X
6158
4182(arbi-)X
6159
648 1898(trary)N
6160
824(costs)X
6161
1007(\(which)X
6162
1253(we)X
6163
1370(cannot)X
6164
1607(handle\))X
6165
1871(and)X
6166
2010(its)X
6167
2108(running)X
6168
2380(time)X
6169
2545(is)X
6170
2621(independent)X
6171
3036(of)X
6172
3126(the)X
6173
3247(number)X
6174
3515(of)X
6175
3605(errors)X
6176
3816(\(which)X
6177
4062(makes)X
6178
4290(it)X
6179
648 2008(competitive)N
6180
1046(with)X
6181
1208(or)X
6182
1295(better)X
6183
1498(than)X
6184
1656(ours)X
6185
1814(if)X
6186
1883(the)X
6187
2001(number)X
6188
2266(of)X
6189
2353(errors)X
6190
2561(is)X
6191
2634(very)X
6192
2797(large\).)X
6193
10 f
6194
1397 2104(i)N
6195
1425(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
6196
1 f
6197
1437 2214(pattern)N
6198
2541(Er)X
6199
2637(=)X
6200
2702(0)X
6201
2862(Er)X
6202
2958(=)X
6203
3023(1)X
6204
3183(Er)X
6205
3279(=)X
6206
3344(2)X
6207
3504(Er)X
6208
3600(=)X
6209
3665(3)X
6210
10 f
6211
1397 2244(i)N
6212
1425(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
6213
1 f
6214
1437 2354(<Hom>ogenious)N
6215
2571(0.53)X
6216
2892(1.10)X
6217
3213(1.42)X
6218
3534(1.74)X
6219
1437 2464(JACM;)N
6220
1692(1981;)X
6221
1894(Graph)X
6222
2571(0.53)X
6223
2892(1.10)X
6224
3213(1.43)X
6225
3534(1.75)X
6226
1437 2574(Prob#tic;)N
6227
1750(Algo#m)X
6228
2571(0.55)X
6229
2892(1.10)X
6230
3213(1.42)X
6231
3534(1.76)X
6232
1437 2684(<[CJ]ACM>;)N
6233
1889(Prob#tic;)X
6234
2202(trees)X
6235
2571(0.54)X
6236
2892(1.11)X
6237
3213(1.43)X
6238
3534(1.75)X
6239
1437 2794(\(<[23]>)N
6240
9 f
6241
1688(-)X
6242
1 f
6243
1732([23]*)X
6244
9 f
6245
1906(|)X
6246
1 f
6247
(<B>\).*<Tr>ees)S
6248
2571(0.66)X
6249
2892(1.53)X
6250
3213(2.19)X
6251
3534(2.83)X
6252
10 f
6253
1397 2824(i)N
6254
1425(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
6255
1397(c)X
6256
2744(c)Y
6257
2664(c)Y
6258
2584(c)Y
6259
2504(c)Y
6260
2424(c)Y
6261
2344(c)Y
6262
2264(c)Y
6263
2184(c)Y
6264
3745 2824(c)N
6265
2744(c)Y
6266
2664(c)Y
6267
2584(c)Y
6268
2504(c)Y
6269
2424(c)Y
6270
2344(c)Y
6271
2264(c)Y
6272
2184(c)Y
6273
1 f
6274
1651 3031(Table)N
6275
1854(4:)X
6276
1956(Approximate)X
6277
2399(matching)X
6278
2717(of)X
6279
2804(complicated)X
6280
3216(patterns.)X
6281
6 f
6282
14 s
6283
648 3316(5.)N
6284
803 -0.3063(Conclusions)AX
6285
1 f
6286
10 s
6287
648 3491(Searching)N
6288
991(text)X
6289
1133(in)X
6290
1217(the)X
6291
1337(presence)X
6292
1641(of)X
6293
1730(errors)X
6294
1940(is)X
6295
2015(commonly)X
6296
2379(done)X
6297
2557(`by)X
6298
2687(hand')X
6299
2893(\320)X
6300
2996(one)X
6301
3135(tries)X
6302
3296(many)X
6303
3497(possibilities.)X
6304
3941(This)X
6305
4106(is)X
6306
4182(frus-)X
6307
648 3601(trating,)N
6308
902(slow,)X
6309
1098(and)X
6310
1239(with)X
6311
1406(no)X
6312
1511(guarantee)X
6313
1849(of)X
6314
1941(success.)X
6315
2247(Agrep)X
6316
2473(can)X
6317
2610(alleviate)X
6318
2907(this)X
6319
3047(problem)X
6320
3339(and)X
6321
3480(make)X
6322
3679(searching)X
6323
4011(in)X
6324
4097(general)X
6325
648 3711(more)N
6326
835(robust.)X
6327
1098(It)X
6328
1170(also)X
6329
1322(makes)X
6330
1550(searching)X
6331
1881(more)X
6332
2069(convenient)X
6333
2444(by)X
6334
2547(not)X
6335
2672(having)X
6336
2913(to)X
6337
2998(spell)X
6338
3172(everything)X
6339
3538(precisely.)X
6340
3891(Agrep)X
6341
4115(is)X
6342
4191(very)X
6343
648 3821(fast)N
6344
791(and)X
6345
934(general)X
6346
1198(and)X
6347
1341(it)X
6348
1412(should)X
6349
1652(\256nd)X
6350
1803(numerous)X
6351
2146(applications.)X
6352
2600(It)X
6353
2676(has)X
6354
2810(already)X
6355
3074(been)X
6356
3253(used)X
6357
3427(in)X
6358
3516(the)X
6359
3641(Collaboratory)X
6360
4112(system)X
6361
648 3931([HPS90],)N
6362
975(in)X
6363
1064(a)X
6364
1127(new)X
6365
1288(tool)X
6366
1439(\(under)X
6367
1676(development\))X
6368
2144(for)X
6369
2265(locating)X
6370
2550(\256les)X
6371
2710(in)X
6372
2799(a)X
6373
2862(UNIX)X
6374
3090(system)X
6375
3339([FMW92],)X
6376
3711(and)X
6377
3854(in)X
6378
3943(a)X
6379
4007(new)X
6380
4169(algo-)X
6381
648 4041(rithm)N
6382
844(for)X
6383
961(\256nding)X
6384
1210(information)X
6385
1611(in)X
6386
1696(a)X
6387
1755(distributed)X
6388
2120(environment)X
6389
2548([FM92].)X
6390
2860(In)X
6391
2950(the)X
6392
3070(last)X
6393
3203(two)X
6394
3345(applications,)X
6395
3774(agrep)X
6396
3975(is)X
6397
4050(modi\256ed)X
6398
648 4151(in)N
6399
730(a)X
6400
786(novel)X
6401
984(way)X
6402
1138(to)X
6403
1220(search)X
6404
1446(inside)X
6405
1657(specially)X
6406
1962(compressed)X
6407
2361(\256les)X
6408
2 f
6409
2514(without)X
6410
1 f
6411
2773(having)X
6412
3011(to)X
6413
3093(decompress)X
6414
3492(them)X
6415
3672(\256rst.)X
6416
6 f
6417
14 s
6418
648 4371(Acknowledgem)N
6419
1467(ents:)X
6420
1 f
6421
10 s
6422
648 4514(We)N
6423
784(thank)X
6424
986(Ricardo)X
6425
1264(Baeza-Yates,)X
6426
1715(Gene)X
6427
1909(Myers,)X
6428
2158(and)X
6429
2298(Chunghwa)X
6430
2669(Rao)X
6431
2822(for)X
6432
2940(many)X
6433
3142(helpful)X
6434
3393(conversations)X
6435
3859(about)X
6436
4062(approxi-)X
6437
648 4624(mate)N
6438
828(string)X
6439
1034(matching)X
6440
1356(and)X
6441
1496(for)X
6442
1614(comments)X
6443
1967(that)X
6444
2111(improved)X
6445
2442(the)X
6446
2564(manuscript.)X
6447
2984(We)X
6448
3120(thank)X
6449
3322(Ric)X
6450
3457(Anderson,)X
6451
3813(Cliff)X
6452
3988(Hathaway,)X
6453
648 4734(Andrew)N
6454
930(Hume,)X
6455
1169(David)X
6456
1388(Sanderson,)X
6457
1765(and)X
6458
1904(Shu-Ing)X
6459
2186(Tsuei)X
6460
2388(for)X
6461
2506(their)X
6462
2677(help)X
6463
2839(and)X
6464
2979(comments)X
6465
3332(that)X
6466
3476(improved)X
6467
3807(the)X
6468
3929(implementa-)X
6469
648 4844(tion)N
6470
799(of)X
6471
893(agrep.)X
6472
1139(We)X
6473
1278(also)X
6474
1434(thank)X
6475
1639(William)X
6476
1928(Chang)X
6477
2163(and)X
6478
2305(Andrew)X
6479
2590(Hume)X
6480
2812(for)X
6481
2932(kindly)X
6482
3162(providing)X
6483
3499(programs)X
6484
3828(for)X
6485
3948(some)X
6486
4143(of)X
6487
4236(the)X
6488
648 4954(experiments.)N
6489
6490
9 p
6491
%%Page: 9 9
6492
10 s 10 xH 0 xS 1 f
6493
3 f
6494
6 f
6495
14 s
6496
648 686(References)N
6497
1 f
6498
10 s
6499
648 893([AC75])N
6500
848 1003(Aho,)N
6501
1032(A.)X
6502
1136(V.,)X
6503
1260(and)X
6504
1402(M.)X
6505
1519(J.)X
6506
1597(Corasick,)X
6507
1929(``Ef\256cient)X
6508
2286(string)X
6509
2495(matching:)X
6510
2842(an)X
6511
2945(aid)X
6512
3070(to)X
6513
3159(bibliographic)X
6514
3613(search,'')X
6515
2 f
6516
3920(Communica-)X
6517
848 1113(tions)N
6518
1023(of)X
6519
1105(the)X
6520
1223(ACM)X
6521
3 f
6522
1412(18)X
6523
1 f
6524
1512(\(June)X
6525
1706(1975\),)X
6526
1933(pp.)X
6527
2053(333)X
6528
9 f
6529
(-)S
6530
1 f
6531
2217(340.)X
6532
648 1256([Ba89])N
6533
848 1366(Baeza-Yates)N
6534
1290(R.)X
6535
1398(A.,)X
6536
1531(``Improved)X
6537
1932(string)X
6538
2149(searching,'')X
6539
2 f
6540
2566(Software)X
6541
2885(\320)X
6542
2991(Practice)X
6543
3298(and)X
6544
3453(Experience)X
6545
3 f
6546
3850(19)X
6547
1 f
6548
3965(\(1989\),)X
6549
4234(pp.)X
6550
848 1476(257)N
6551
9 f
6552
(-)S
6553
1 f
6554
1012(271.)X
6555
648 1619([BG89])N
6556
848 1729(Baeza-Yates)N
6557
1275(R.)X
6558
1368(A.,)X
6559
1486(and)X
6560
1622(G.)X
6561
1720(H.)X
6562
1818(Gonnet,)X
6563
2094(``A)X
6564
2226(new)X
6565
2380(approach)X
6566
2695(to)X
6567
2777(text)X
6568
2917(searching,'')X
6569
2 f
6570
3319(Proceedings)X
6571
3740(of)X
6572
3822(the)X
6573
3940(12th)X
6574
4103(Annual)X
6575
848 1839(ACM-SIGIR)N
6576
1265(conference)X
6577
1638(on)X
6578
1738(Information)X
6579
2140(Retrieval,)X
6580
1 f
6581
2474(Cambridge,)X
6582
2870(MA)X
6583
3019(\(June)X
6584
3213(1989\),)X
6585
3440(pp.)X
6586
3560(168)X
6587
9 f
6588
(-)S
6589
1 f
6590
3724(175.)X
6591
648 1982([BM77])N
6592
848 2092(Boyer)N
6593
1082(R.)X
6594
1193(S.,)X
6595
1315(and)X
6596
1469(J.)X
6597
1558(S.)X
6598
1660(Moore,)X
6599
1932(``A)X
6600
2082(fast)X
6601
2236(string)X
6602
2456(searching)X
6603
2803(algorithm,'')X
6604
2 f
6605
3227(Communications)X
6606
3808(of)X
6607
3909(the)X
6608
4046(ACM)X
6609
3 f
6610
4254(20)X
6611
1 f
6612
848 2202(\(October)N
6613
1154(1977\),)X
6614
1381(pp.)X
6615
1501(762)X
6616
9 f
6617
(-)S
6618
1 f
6619
1665(772.)X
6620
648 2345([CL90])N
6621
848 2455(Chang)N
6622
1077(W.)X
6623
1193(I.,)X
6624
1280(and)X
6625
1416(E.)X
6626
1505(L.)X
6627
1594(Lawler,)X
6628
1862(``Approximate)X
6629
2359(string)X
6630
2561(matching)X
6631
2879(in)X
6632
2962(sublinear)X
6633
3277(expected)X
6634
3584(time,'')X
6635
2 f
6636
3821(the)X
6637
3940(31th)X
6638
4103(Annual)X
6639
848 2565(Symp.)N
6640
1062(on)X
6641
1162(Foundations)X
6642
1586(of)X
6643
1668(Computer)X
6644
2008(Science,)X
6645
1 f
6646
2294(\(October)X
6647
2600(1990\),)X
6648
2827(pp.)X
6649
2947(116)X
6650
9 f
6651
(-)S
6652
1 f
6653
3111(124.)X
6654
648 2708([CW79])N
6655
848 2818(Commentz-Walter,)N
6656
1493(B,)X
6657
1594(``A)X
6658
1734(string)X
6659
1944(matching)X
6660
2270(algorithm)X
6661
2609(fast)X
6662
2753(on)X
6663
2862(the)X
6664
2989 0.3472(average,'')AX
6665
2 f
6666
3343(Proc.)X
6667
3548(6th)X
6668
3679(International)X
6669
4130(Collo-)X
6670
848 2928(quium)N
6671
1068(on)X
6672
1168(Automata,)X
6673
1519(Languages,)X
6674
1910(and)X
6675
2050(Programming)X
6676
1 f
6677
2519(\(1979\),)X
6678
2773(pp.)X
6679
2893(118)X
6680
9 f
6681
(-)S
6682
1 f
6683
3057(132.)X
6684
648 3071([FM92])N
6685
848 3181(Finkel)N
6686
1076(R.)X
6687
1173(A.,)X
6688
1295(and)X
6689
1435(U.)X
6690
1537(Manber,)X
6691
1831(``The)X
6692
2034(design)X
6693
2267(and)X
6694
2407(implementation)X
6695
2933(of)X
6696
3024(a)X
6697
3084(server)X
6698
3305(for)X
6699
3423(retrieving)X
6700
3759(distributed)X
6701
4126(data,'')X
6702
848 3291(in)N
6703
930(preparation.)X
6704
648 3434([FMW92])N
6705
848 3544(Finkel)N
6706
1072(R.)X
6707
1165(A.,)X
6708
1283(U.)X
6709
1381(Manber,)X
6710
1671(and)X
6711
1807(S.)X
6712
1891(Wu,)X
6713
2047(``Find\256le)X
6714
2369(\320)X
6715
2470(a)X
6716
2527(tool)X
6717
2672(for)X
6718
2787(locating)X
6719
3066(\256les)X
6720
3220(in)X
6721
3303(a)X
6722
3360(large)X
6723
3542(\256le)X
6724
3665(system,'')X
6725
3982(in)X
6726
4065(prepara-)X
6727
848 3654(tion.)N
6728
648 3797([GP90])N
6729
848 3907(Galil)N
6730
1033(Z.,)X
6731
1147(and)X
6732
1288(K.)X
6733
1391(Park,)X
6734
1583(``An)X
6735
1760(improved)X
6736
2092(algorithm)X
6737
2429(for)X
6738
2549(approximate)X
6739
2976(string)X
6740
3184(matching,'')X
6741
2 f
6742
3582(SIAM)X
6743
3791(J.)X
6744
3873(on)X
6745
3979(Computing)X
6746
3 f
6747
848 4017(19)N
6748
1 f
6749
948(\(December)X
6750
1326(1990\),)X
6751
1553(pp.)X
6752
1673(989)X
6753
9 f
6754
(-)S
6755
1 f
6756
1837(999.)X
6757
648 4160([Ha89])N
6758
848 4270(Haertel,)N
6759
1125(M.,)X
6760
1256(``GNU)X
6761
1504(e?grep,'')X
6762
1813(Usenet)X
6763
2056(archive)X
6764
7 f
6765
2341(comp.source.unix,)X
6766
1 f
6767
3177(Volume)X
6768
3455(17)X
6769
3555(\(February)X
6770
3892(1989\).)X
6771
648 4413([HPS90])N
6772
848 4523(Hudson,)N
6773
1142(S.)X
6774
1231(E.,)X
6775
1345(L.)X
6776
1439(L.)X
6777
1533(Peterson,)X
6778
1854(and)X
6779
1995(B.)X
6780
2093(R.)X
6781
2191(Schatz,)X
6782
2450(``Systems)X
6783
2795(Technology)X
6784
3203(for)X
6785
3322(Building)X
6786
3627(a)X
6787
3689(National)X
6788
3991(Collabora-)X
6789
848 4633(tory,'')N
6790
1071(University)X
6791
1429(of)X
6792
1516(Arizona)X
6793
1795(Technical)X
6794
2132(Report)X
6795
2370(#TR)X
6796
2532(90-24)X
6797
2739(\(July)X
6798
2919(1990\).)X
6799
648 4776([HS91])N
6800
848 4886(Hume)N
6801
1074(A.,)X
6802
1202(and)X
6803
1349(D.)X
6804
1458(Sunday,)X
6805
1749(``Fast)X
6806
1967(string)X
6807
2180(searching,'')X
6808
2 f
6809
2593(Software)X
6810
2908(\320)X
6811
3010(Practice)X
6812
3313(and)X
6813
3464(Experience)X
6814
3 f
6815
3857(21)X
6816
1 f
6817
3968(\(November)X
6818
848 4996(1991\),)N
6819
1075(pp.)X
6820
1195(1221)X
6821
9 f
6822
(-)S
6823
1 f
6824
1399(1248.)X
6825
648 5139([Hu91])N
6826
848 5249(Hume)N
6827
1064(A.,)X
6828
1182(personal)X
6829
1474(communication)X
6830
1992(\(1991\).)X
6831
648 5392([KMP77])N
6832
848 5502(Knuth)N
6833
1069(D.)X
6834
1168(E.,)X
6835
1278(J.)X
6836
1350(H.)X
6837
1449(Morris,)X
6838
1708(and)X
6839
1846(V.)X
6840
1946(R.)X
6841
2041(Pratt,)X
6842
2234(``Fast)X
6843
2443(pattern)X
6844
2688(matching)X
6845
3008(in)X
6846
3092(strings,'')X
6847
2 f
6848
3401(SIAM)X
6849
3606(Journal)X
6850
3877(on)X
6851
3979(Computing)X
6852
3 f
6853
848 5612(6)N
6854
1 f
6855
908(\(June)X
6856
1102(1977\),)X
6857
1329(pp.)X
6858
1449(323)X
6859
9 f
6860
(-)S
6861
1 f
6862
1613(350.)X
6863
6864
10 p
6865
%%Page: 10 10
6866
10 s 10 xH 0 xS 1 f
6867
3 f
6868
1 f
6869
648 686([MM89])N
6870
848 796(Myers,)N
6871
1094(E.)X
6872
1184(W.,)X
6873
1322(and)X
6874
1460(W.)X
6875
1578(Miller,)X
6876
1820(``Approximate)X
6877
2319(matching)X
6878
2639(of)X
6879
2728(regular)X
6880
2978(expressions,'')X
6881
2 f
6882
3448(Bull.)X
6883
3623(of)X
6884
3707(Mathematical)X
6885
4174(Biol-)X
6886
848 906(ogy)N
6887
3 f
6888
984(51)X
6889
1 f
6890
1084(\(1989\),)X
6891
1338(pp.)X
6892
1458(5)X
6893
9 f
6894
(-)S
6895
1 f
6896
1542(37.)X
6897
648 1049([TU90])N
6898
848 1159(Tarhio)N
6899
1093(J.)X
6900
1175(and)X
6901
1322(E.)X
6902
1422(Ukkonen,)X
6903
1767(``Approximate)X
6904
2276(Boyer-Moore)X
6905
2745(string)X
6906
2959(matching,'')X
6907
3363(Technical)X
6908
3712(Report)X
6909
3962(#A-1990-3,)X
6910
848 1269(Dept.)N
6911
1044(of)X
6912
1131(Computer)X
6913
1471(Science,)X
6914
1761(University)X
6915
2119(of)X
6916
2206(Helsinki)X
6917
2497(\(March)X
6918
2754(1990\).)X
6919
648 1412([Uk85])N
6920
848 1522(Ukkonen)N
6921
1162(E.,)X
6922
1271(``Finding)X
6923
1593(approximate)X
6924
2014(patterns)X
6925
2288(in)X
6926
2370(strings,'')X
6927
2 f
6928
2677(Journal)X
6929
2946(of)X
6930
3028(Algorithms)X
6931
3 f
6932
3403(6)X
6933
1 f
6934
3463(\(1985\),)X
6935
3717(pp.)X
6936
3837(132)X
6937
9 f
6938
(-)S
6939
1 f
6940
4001(137.)X
6941
648 1665([WM91])N
6942
848 1775(Wu)N
6943
995(S.)X
6944
1090(and)X
6945
1237(U.)X
6946
1346(Manber,)X
6947
1647(``Fast)X
6948
1865(Text)X
6949
2043(Searching)X
6950
2395(With)X
6951
2586(Errors,'')X
6952
2892(Technical)X
6953
3240(Report)X
6954
3489(TR-91-11,)X
6955
3856(Department)X
6956
4267(of)X
6957
848 1885(Computer)N
6958
1188(Science,)X
6959
1478(University)X
6960
1836(of)X
6961
1923(Arizona)X
6962
2202(\(June)X
6963
2396(1991\).)X
6964
648 2028([WM92])N
6965
848 2138(Wu)N
6966
984(S.)X
6967
1068(and)X
6968
1204(U.)X
6969
1302(Manber,)X
6970
1592(``Filtering)X
6971
1941(search)X
6972
2167(approach)X
6973
2482(for)X
6974
2596(some)X
6975
2785(string)X
6976
2987(matching)X
6977
3305(problems,'')X
6978
3697(in)X
6979
3779(preparation.)X
6980
6 f
6981
14 s
6982
648 2358(Biographical)N
6983
1355(Sketches)X
6984
3 f
6985
10 s
6986
648 2578(Sun)N
6987
809(Wu)X
6988
1 f
6989
962(is)X
6990
1044(a)X
6991
1109(Ph.D.)X
6992
1321(candidate)X
6993
1659(in)X
6994
1751(computer)X
6995
2084(science)X
6996
2351(at)X
6997
2439(the)X
6998
2567(University)X
6999
2935(of)X
7000
3032(Arizona.)X
7001
3361(His)X
7002
3502(research)X
7003
3801(interests)X
7004
4098(include)X
7005
648 2688(design)N
7006
877(of)X
7007
964(algorithms,)X
7008
1346(in)X
7009
1428(particular,)X
7010
1776(string)X
7011
1978(matching)X
7012
2296(and)X
7013
2432(graph)X
7014
2635(algorithms.)X
7015
3 f
7016
648 2908(Udi)N
7017
797(Manber)X
7018
1 f
7019
1098(is)X
7020
1176(a)X
7021
1237(professor)X
7022
1561(of)X
7023
1653(computer)X
7024
1981(science)X
7025
2243(at)X
7026
2326(the)X
7027
2449(University)X
7028
2812(of)X
7029
2904(Arizona,)X
7030
3208(where)X
7031
3430(he)X
7032
3532(has)X
7033
3665(been)X
7034
3843(since)X
7035
4034(1987.)X
7036
4240(He)X
7037
648 3018(received)N
7038
944(his)X
7039
1060(Ph.D.)X
7040
1265(degree)X
7041
1503(in)X
7042
1588(computer)X
7043
1914(science)X
7044
2174(from)X
7045
2353(the)X
7046
2474(University)X
7047
2835(of)X
7048
2925(Washington)X
7049
3335(in)X
7050
3420(1982.)X
7051
3643(His)X
7052
3776(research)X
7053
4067(interests)X
7054
648 3128(include)N
7055
921(design)X
7056
1167(of)X
7057
1271(algorithms)X
7058
1650(and)X
7059
1803(computer)X
7060
2143(networks.)X
7061
2514(He)X
7062
2646(is)X
7063
2737(the)X
7064
2873(author)X
7065
3116(of)X
7066
3221(``Introduction)X
7067
3709(to)X
7068
3809(Algorithms)X
7069
4211(-)X
7070
4276(A)X
7071
648 3238(Creative)N
7072
943(Approach'')X
7073
1337(\(Addison-Wesley,)X
7074
1946(1989\).)X
7075
2195(He)X
7076
2311(received)X
7077
2606(a)X
7078
2664(Presidential)X
7079
3064(Young)X
7080
3304(Investigator)X
7081
3709(Award)X
7082
3950(in)X
7083
4034(1985,)X
7084
4236(the)X
7085
648 3348(best)N
7086
806(paper)X
7087
1014(award)X
7088
1240(of)X
7089
1336(the)X
7090
1463(seventh)X
7091
1737(International)X
7092
2176(Conference)X
7093
2576(on)X
7094
2685(Distributed)X
7095
3074(Computing)X
7096
3462(Systems,)X
7097
3777(1987,)X
7098
3986(and)X
7099
4131(a)X
7100
4196(Dis-)X
7101
648 3458(tinguished)N
7102
1001(Teaching)X
7103
1320(Award)X
7104
1559(of)X
7105
1646(the)X
7106
1764(Faculty)X
7107
2024(of)X
7108
2111(Science)X
7109
2381(at)X
7110
2459(the)X
7111
2577(University)X
7112
2935(of)X
7113
3022(Arizona,)X
7114
3321(1990.)X
7115
7116
10 p
7117
%%Trailer
7118
xt
7119
7120
xs
Loggerhead is a web-based interface for Breezy
Version: 2.0.1