%!PS-Adobe-1.0 %%Creator: aloe:udi (Udi Manber) %%Title: stdin (ditroff) %%CreationDate: Mon Jun 10 12:20:27 1991 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 2.2 87/11/17 16:40:42 byron Rel $ % Psfig RCSID $Header: psdit.pro,v 1.5 88/01/04 17:48:22 trevor Exp $ /$DITroff 180 dict def $DITroff begin /DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap currentlinejoin currentdash currentgray currentmiterlimit ] cvx def %% Psfig additions /startFig { /SavedState save def userdict maxlength dict begin currentpoint transform DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix itransform moveto /ury exch def /urx exch def /lly exch def /llx exch def /y exch 72 mul resolution div def /x exch 72 mul resolution div def currentpoint /cy exch def /cx exch def /sx x urx llx sub div def % scaling for x /sy y ury lly sub div def % scaling for y sx sy scale % scale by (sx,sy) cx sx div llx sub cy sy div ury sub translate /DefFigCTM matrix currentmatrix def /initmatrix { DefFigCTM setmatrix } def /defaultmatrix { DefFigCTM exch copy } def /initgraphics { DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap setlinewidth setmatrix DefFigCTM setmatrix } def /showpage { initgraphics } def } def % Args are llx lly urx ury (in figure coordinates) /clipFig { currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto } def % doclip, if called, will always be just after a `startfig' /doclip { llx lly urx ury clipFig } def /endFig { end SavedState restore } def /globalstart { % Push details about the enviornment on the stack. fontnum fontsize fontslant fontheight % firstpage mh my resolution slotno currentpoint pagesave restore gsave } def /globalend { grestore moveto /slotno exch def /resolution exch def /my exch def /mh exch def % /firstpage exch def /fontheight exch def /fontslant exch def /fontsize exch def /fontnum exch def F /pagesave save def } def %% end XMOD additions /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def ()X 3562(j)X 1 f 3584(,)X 3632(we)X 3754(can)X 3894(start)X 864 2588(matching)N 2 f 1189(t)X 7 s 1211 2604(r)N 1 f 10 s 1266 2588(to)N 2 f 1355(p)X 7 s 2604(i)Y 9 f 1420(+)X 1 f 1451(1)X 10 s 1512 2588(no)N 1619(matter)X 1851(how)X 2016(many)X 2220(characters)X 2573(we)X 2693(skipped.)X 2988(In)X 3081(other)X 3272(words,)X 3514(if)X 3589(at)X 3673(some)X 3868(point)X 864 2708(there)N 1045(is)X 1118(a)X 1174(match)X 1390(up)X 1490(to)X 2 f 1572(p)X 7 s 2724(i)Y 1 f 10 s 1654 2708(then)N 1812(this)X 1947(match)X 2163(is)X 2236(always)X 2479(valid)X 2659(later)X 2822(on)X 2922(\(because)X 3224(all)X 3324(the)X 3442(characters)X 3789(later)X 3952(on)X 864 2828(can)N 996(be)X 1092(considered)X 1460(as)X 1547(part)X 1692(of)X 1779(the)X 1897(`#'\).)X 1064 2981(We)N 1205(can)X 1346(adjust)X 1566(the)X 1693(algorithm)X 2033(for)X 2156(this)X 2301(case)X 2470(as)X 2567(follows.)X 2877(At)X 2987(each)X 3165(step,)X 3344(we)X 3468(apply)X 3676(the)X 3804(regular)X 864 3101(algorithm)N 1201(to)X 1289(compute)X 1591(all)X 1697(the)X 2 f 1821(R)X 1 f 1896(arrays.)X 2158(That)X 2330(is,)X 2428(we)X 2547(compute)X 2 f 2848(R)X 7 s 2905 3117(j)N 1 f 2901 3069(0)N 10 s 2935 3101(,)N 2 f 2974(R)X 7 s 3031 3117(j)N 1 f 3027 3069(1)N 10 s 3061 3101(,)N 2 f 3100(...)X 1 f (,)S 2 f 3199(R)X 7 s 3256 3117(j)N 3252 3069(d)N 1 f 10 s 3311 3101(using)N 3509(\(2.1\).)X 3728(Then,)X 3938(for)X 864 3221(each)N 2 f 1034(i)X 1 f 1056(,)X 1098(1)X 2 f 9 f 1151(\243)X 2 f 1208(i)X 9 f 1249(\243)X 2 f 1306(d)X 1 f (,)S 1388(we)X 1504(set)X 2 f 1615(R)X 7 s 1672 3237(j)N 1668 3189(i)N 1 f 10 s 1717 3221(=)N 2 f 1785(R)X 7 s 1842 3237(j)N 1838 3189(i)N 1 f 10 s 2 f 1884 3221(OR)N 1 f 2017([)X 2 f 2044(R)X 7 s 2101 3237(j)N 9 f 2126(-)X 1 f 2157(1)X 2 f 2097 3189(i)N 1 f 10 s 2 f 2217 3221(AND)N 1 f 2 f 2403(S)X 7 s 2452 3189(#)N 1 f 10 s 2486 3221(].)N 2556(This)X 2721(step)X 2873(corresponds)X 3284(to)X 3369(the)X 3490(action)X 3709(``if)X 3835(at)X 3916(any)X 864 3341(point,)N 1068(there)X 1249(is)X 1322(a)X 1378(1)X 1438(entry)X 1623(in)X 2 f 1705(R)X 7 s 1763 3309(i)N 1 f 10 s 2 f 1805 3341(AND)N 1 f 2 f 1991(S)X 7 s 2040 3309(#)N 1 f 10 s 2074 3341(,)N 2114(then)X 2272(this)X 2407(entry)X 2592(should)X 2825(remain)X 3068(1)X 3128(from)X 3304(now)X 3462(on.'')X 6 f 12 s 864 3581(3.3.)N 1078(Unknown)X 1538(Number)X 1927(of)X 2045(Errors)X 1 f 10 s 864 3821(In)N 972(some)X 1182(cases,)X 1413(we)X 1549(do)X 1671(not)X 1815(know)X 2035(the)X 2175(number)X 2462(of)X 2571(errors)X 2801(a-priori.)X 3124(We)X 3278(would)X 3520(like)X 3682(to)X 3786(\256nd)X 3952(all)X 864 3941 0.3125(occurrences)AN 1283(of)X 1384(the)X 1516(pattern)X 1773(with)X 1949(the)X 2 f 2080(minimal)X 1 f 2375(number)X 2653(of)X 2753(errors)X 2974(possible.)X 3309(The)X 3467(algorithm)X 3811(can)X 3956(be)X 864 4061(extended)N 1178(to)X 1264(this)X 1403(case)X 1567(as)X 1659(follows.)X 1964(We)X 2101(\256rst)X 2250(try)X 2364(to)X 2451(\256nd)X 2600(the)X 2723(pattern)X 2971(with)X 3138(no)X 3243(errors.)X 3496(If)X 3575(we)X 3694(are)X 3818(unsuc-)X 864 4181(cessful,)N 1137(we)X 1261(try)X 1380(with)X 1552(one)X 1698(error,)X 1905(then)X 2073(with)X 2245(three)X 2436(errors,)X 2674(then)X 2842(with)X 3014(7)X 3083(errors,)X 3320(and)X 3465(so)X 3565(on,)X 3694(essentially)X 864 4301(doubling)N 1171(the)X 1292(number)X 1560(of)X 1650(errors)X 1861(\(and)X 2027(adding)X 2269(one\))X 2436(at)X 2518(each)X 2690(attempt.)X 2974(If)X 3052(the)X 3174(number)X 3443(of)X 3534(errors)X 3746(turns)X 3930(out)X 864 4421(to)N 956(be)X 2 f 1062(k)X 1 f 1098(,)X 1148(then)X 1316(the)X 1444(running)X 1723(time)X 1895(will)X 2049(be)X 2 f 2155(O)X 1 f 2226(\(1)X 2306 4397(.)N 2 f 2339 4421(n)N 1 f 2 f 9 f 2405(+)X 1 f 2469(2)X 2522 4397(.)N 2 f 2555 4421(n)N 1 f 2 f 9 f 2621(+)X 1 f 2685(4)X 2738 4397(.)N 2 f 2771 4421(n)N 1 f 2 f 9 f 2837(+)X 1 f 2921 4397(.)N 2961(.)X 3001(.)X 2 f 9 f 3061 4421(+)N 1 f 3125(2)X 2 f 7 s 4389(b)Y 1 f 10 s 3212 4397(.)N 2 f 3245 4421(n)N 1 f 3291(\),)X 3368(where)X 3595(2)X 2 f 7 s 4389(b)Y 1 f 10 s 3699 4421(is)N 3781(the)X 3908(\256rst)X 864 4541(power)N 1086(of)X 1174(2)X 1235(greater)X 1480(than)X 2 f 1640(k)X 1 f 1676(.)X 1738(In)X 1827(the)X 1947(worst)X 2147(case,)X 2328(we)X 2444(perform)X 2725(4)X 2787(times)X 2982(as)X 3071(many)X 3271(operations)X 3627(as)X 3716(we)X 3832(would)X 864 4661(have)N 1042(had)X 1184(we)X 1304(known)X 2 f 1548(k)X 1 f 1610(\(in)X 1725(most)X 1906(cases,)X 2122(the)X 2246(factor)X 2460(is)X 2539(actually)X 2819(2)X 2885(or)X 2978(3\).)X 3091(This)X 3259(is)X 3338(not)X 3466(desirable,)X 3802(but)X 3930(not)X 864 4781(prohibitive.)N 1275(There)X 1483(are)X 1602(other)X 1787(methods)X 2078(to)X 2160(\256nd)X 2304(the)X 2422(minimum)X 2752(number)X 3017(of)X 3104(errors.)X 6 f 12 s 864 5021(3.4.)N 1078(A)X 1174(Combination)X 1789(of)X 1907(Patterns)X 2317(With)X 2553(and)X 2751(Without)X 3137(Errors)X 1 f 10 s 864 5174(Sometimes)N 1241(we)X 1357(do)X 1459(not)X 1583(want)X 1761(to)X 1845(allow)X 2045(parts)X 2223(of)X 2312(the)X 2432(pattern)X 2677(to)X 2761(have)X 2935(errors.)X 3165(For)X 3298(example,)X 3612(we)X 3729(may)X 3890(look)X 864 5294(for)N 981(license)X 1227(plate)X 1406(ABC123,)X 1733(and)X 1872(we)X 1989(know)X 2190(that)X 2333(the)X 2454(letters)X 2673(are)X 2794(correct)X 3040(but)X 3164(the)X 3284(numbers)X 3582(may)X 3742(have)X 3916(one)X 864 5414(error)N 1052(in)X 1145(them.)X 1376(We)X 1519(denote)X 1764(this)X 1910(pattern)X 2165(by)X 2277(123.)X 2723(We)X 2867(can)X 3011(modify)X 3274(the)X 3404(algorithm)X 3747(to)X 3841(shield)X 864 5534(parts)N 1043(of)X 1133(the)X 1253(pattern)X 1498(from)X 1676(having)X 1916(any)X 2054(errors)X 2264(in)X 2348(them.)X 2570(Let's)X 2757(assume)X 3015(that)X 2 f 3157(I)X 1 f 3206(is)X 3281(the)X 3401(set)X 3512(of)X 3601(indices)X 3850(in)X 3934(the)X 864 5654(pattern)N 1115(where)X 1340(no)X 1448(error)X 1633(is)X 1715(allowed,)X 2018(and)X 2163(let)X 2 f 2272(M)X 1 f 2368(be)X 2473(a)X 2538(masking)X 2838(array)X 3033(\(of)X 3156(size)X 2 f 3310(m)X 1 f 3368(\))X 3424(that)X 3573(has)X 3709(a)X 3774(0)X 3843(in)X 3934(the)X 9 p %%Page: 9 10 10 s 10 xH 0 xS 1 f 3 f 2428 696(9)N 1 f 864 984(indices)N 1115(of)X 2 f 1206(I)X 1 f 1257(and)X 1397(a)X 1457(1)X 1521(otherwise.)X 1897(We)X 2033(would)X 2257(like)X 2401(to)X 2486(modify)X 2740(\(2.1\))X 2917(such)X 3087(that)X 3230(insertions,)X 3584(deletions,)X 3916(and)X 864 1104(substitutions)N 1301(can)X 1447(only)X 1623(occur)X 1836(outside)X 2102(of)X 2 f 2204(I)X 1 f 2231(.)X 2306(This)X 2483(is)X 2571(done)X 2762(by)X 2877(masking)X 3183(these)X 3383(cases)X 3588(with)X 2 f 3765(M)X 1 f 3832(.)X 3907(The)X 864 1224(expression)N 1227(in)X 1309(\(2.1\))X 1483(is)X 1556(changed)X 1844(to)X 3878 1416(\(2.2\))N 2 f 1024 1408(R)N 7 s 1081 1424(j)N 9 f 1106(+)X 1 f 1137(1)X 2 f 1077 1376(d)N 10 s 9 f 1217 1408(=)N 1 f 10 f 1314 1368(I)N 1314 1448(L)N 2 f 1354 1408(Rshift)N 1 f 1546([)X 2 f 1573(R)X 7 s 1630 1424(j)N 1626 1376(d)N 1 f 10 s 1660 1408(])N 1707(AND)X 2 f 1901(S)X 7 s 1424(c)Y 1 f 10 s 10 f 1992 1368(M)N 1992 1448(O)N 1 f 2032 1408(OR)N 10 f 2176 1368(I)N 2176 1448(L)N 2 f 2216 1408(Rshift)N 1 f 2408([)X 2 f 2435(R)X 7 s 2492 1424(j)N 2488 1376(d)N 9 f 2525(-)X 1 f 2556(1)X 10 s 2610 1408(OR)N 2 f 2741(R)X 7 s 2798 1424(j)N 9 f 2823(+)X 1 f 2854(1)X 2 f 2794 1376(d)N 9 f 2831(-)X 1 f 2862(1)X 10 s 2902 1408(])N 2949(OR)X 2 f 3080(R)X 7 s 3137 1424(j)N 3133 1376(d)N 9 f 3170(-)X 1 f 3201(1)X 10 s 10 f 3255 1368(M)N 3255 1448(O)N 1 f 3295 1408(AND)N 2 f 3489(M.)X 6 f 12 s 864 1728(3.5.)N 1078(Non-Uniform)X 1692(Costs)X 1 f 10 s 864 1881(The)N 1017(edit)X 1165(distance)X 1456(measure,)X 1772(de\256ned)X 2036(in)X 2126(section)X 2381(1,)X 2469(assumes)X 2765(that)X 2914(insertions,)X 3274(deletions,)X 3612(and)X 3757(substitu-)X 864 2001(tions)N 1043(all)X 1147(have)X 1323(the)X 1445(same)X 1634(cost.)X 1827(But)X 1966(in)X 2052(some)X 2245(cases,)X 2459(we)X 2577(want)X 2757(to)X 2843(allow)X 3044(fewer)X 3251(deletions,)X 3583(say,)X 3733(than)X 3894(sub-)X 864 2121(stitutions.)N 1220(The)X 1369(algorithm)X 1704(can)X 1840(be)X 1941(extended,)X 2276(albeit)X 2479(in)X 2566(a)X 2627(limited)X 2878(way,)X 3057(to)X 3144(the)X 3267(case)X 3431(where)X 3653(each)X 3826(opera-)X 864 2241(tion)N 1011(has)X 1141(a)X 1200(different)X 1500(cost.)X 1692(We)X 1827(illustrate)X 2130(this)X 2268(extension)X 2598(with)X 2762(an)X 2860(example.)X 3194(Suppose)X 3487(that)X 3629(substitutions)X 864 2361(add)N 1000(1)X 1060(to)X 1142(the)X 1261(distance,)X 1565(but)X 1688(insertions)X 2020(and)X 2157(deletions)X 2467(add)X 2604(3)X 2665(each.)X 2874(Insertions)X 3211(and)X 3348(deletions)X 3658(are)X 3778(handled)X 864 2481(in)N 949(cases)X 1142(4)X 1204(and)X 1342(3)X 1404(\(see)X 1556(section)X 1805(2\).)X 1934(Insertions)X 2272(contribute)X 2619(the)X 2739(OR)X 2872(of)X 2 f 2961(R)X 7 s 3018 2497(j)N 3014 2449(d)N 9 f 3051(-)X 1 f 3082(1)X 10 s 3138 2481(and)N 3276(deletions)X 3587(contribute)X 3934(the)X 864 2601(OR)N 996(of)X 2 f 1084(Rshift)X 1 f 1283([)X 2 f 1310(R)X 7 s 1367 2617(j)N 9 f 1392(+)X 1 f 1423(1)X 2 f 1363 2569(d)N 9 f 1400(-)X 1 f 1431(1)X 10 s 1471 2601(])N 1519(\(2.1\).)X 1734(We)X 1867(would)X 2088(like)X 2229(them)X 2410(to)X 2493(cost)X 2643(3)X 2704(times)X 2898(as)X 2986(much.)X 3205(In)X 3293(other)X 3479(words,)X 3716(a)X 3774(deletion)X 864 2721(or)N 956(insertion)X 1261(that)X 1406(leads)X 1596(to)X 1683(a)X 1744(match)X 1965(with)X 2 f 2132(d)X 1 f 2197(errors)X 2410(should)X 2648(come)X 2847(from)X 3028(a)X 3089(match)X 3310(with)X 2 f 3477(d)X 9 f 3530(-)X 1 f 3574(3)X 3638(errors.)X 3890(This)X 864 2841(can)N 1000(be)X 1100(achieved)X 1410(by)X 1514(simply)X 1755(replacing)X 2078(the)X 2 f 2200(d)X 9 f 2253(-)X 1 f 2297(1)X 2361(in)X 2448(both)X 2615(expressions)X 3014(with)X 2 f 3181(d)X 9 f 3234(-)X 1 f 3278(3.)X 3383(This)X 3550(modi\256cation)X 3979(is)X 864 2961(very)N 1038(simple)X 1282(and)X 1429(it)X 1504(does)X 1682(not)X 1815(add)X 1962(to)X 2055(the)X 2184(running)X 2464(time;)X 2679(however,)X 3007(it)X 3082(works)X 3309(only)X 3482(for)X 3606(small)X 3809(integer)X 864 3081(costs.)N 6 f 12 s 864 3321(3.6.)N 1078(A)X 1174(Set)X 1350(of)X 1468(Patterns)X 1 f 10 s 864 3474(If)N 939(we)X 1054(have)X 1227(several)X 1476(patterns)X 1751(and)X 1888(we)X 2004(want)X 2182(to)X 2266(\256nd)X 2412(all)X 2514 0.3125(occurrences)AX 2921(of)X 3010(any)X 3148(of)X 3237(them,)X 3439(then)X 3599(we)X 3715(can)X 3849(either)X 864 3594(search)N 1094(them)X 1278(one)X 1418(at)X 1499(a)X 1558(time)X 1723(or)X 1813(together.)X 2139(The)X 2287(advantage)X 2636(of)X 2726(searching)X 3057(for)X 3174(all)X 3277(of)X 3367(them)X 3550(together)X 3836(is)X 3912(that)X 864 3714(it)N 930(can)X 1064(be)X 1162(done)X 1340(in)X 1424(one)X 1562(scan)X 1727(\(and)X 1892(in)X 1976(one)X 2114(command\).)X 2519(Suppose)X 2812(that)X 2954(we)X 3070(are)X 3191(looking)X 3457(for)X 2 f 3574(P)X 1 f 7 s 3632 3730(1)N 10 s 3666 3714(,)N 2 f 3705(P)X 1 f 7 s 3763 3730(2)N 10 s 3797 3714(,)N 2 f 3836(...)X 1 f (,)S 2 f 3935(P)X 7 s 3984 3730(r)N 1 f 10 s 4012 3714(.)N 864 3834(We)N 1001(concatenate)X 1406(all)X 1511(the)X 1634(patterns)X 1913(and)X 2054(put)X 2181(them)X 2366(in)X 2453(one)X 2594(array)X 2785(\(using)X 3010(as)X 3102(many)X 3305(words)X 3526(as)X 3617(needed\),)X 3916(and)X 864 3954(apply)N 1062(the)X 1180(algorithm)X 1511(on)X 1611(that)X 1751(array)X 1937(with)X 2099(the)X 2217(following)X 2548(modi\256cations.)X 3043(Let)X 2 f 3170(M)X 1 f 3257(be)X 3353(a)X 3409(bit)X 3513(array)X 3700(the)X 3819(size)X 3965(of)X 864 4074(the)N 986(combined)X 1326(pattern,)X 1593(and)X 1733(let)X 1837(bit)X 2 f 1945(i)X 1 f 1991(be)X 2091(1)X 2155(if)X 2228(and)X 2368(only)X 2534(if)X 2 f 2607(i)X 1 f 2653(corresponds)X 3064(to)X 3149(the)X 3270(\256rst)X 3417(character)X 3736(of)X 3826(any)X 3965(of)X 864 4194(the)N 997(patterns.)X 1326(For)X 1472(each)X 2 f 1656(s)X 9 f 1706(\316)X 1776(S)X 1 f 1823(,)X 1879(we)X 2009(build)X 2209(two)X 2365(bit)X 2485(arrays.)X 2758(The)X 2919(\256rst,)X 2 f 3099(S)X 7 s 4210(s)Y 1 f 10 s 3203 4194(is)N 3292(identical)X 3604(with)X 3782(the)X 3916(one)X 864 4314(described)N 1213(in)X 1315(section)X 1582(2.)X 1702(It)X 1791(is)X 1884(used)X 2071(to)X 2173(determine)X 2534(if)X 2623(a)X 2699(match)X 2935(occurs.)X 3225(The)X 3390(second)X 3653(array)X 2 f 3859(S)X 9 f (\242)S 7 s 2 f 3919 4330(s)N 1 f 10 s 3987 4314(=)N 2 f 864 4434(S)N 7 s 4450(s)Y 1 f 10 s 2 f 952 4434(AND)N 1 f 2 f 1138(M)X 1 f 1205(.)X 1266(It)X 1336(indicates)X 1642(whether)X 2 f 1922(s)X 1 f 1974(is)X 2048(the)X 2167(\256rst)X 2312(character)X 2629(of)X 2717(any)X 2854(pattern.)X 3138(If)X 3213(so,)X 3325(then)X 3484(we)X 3599(must)X 3775(start)X 3934(the)X 864 4554(match)N 1082(at)X 1162(that)X 1304(pattern:)X 1571(we)X 1686(do)X 1787(not)X 1910(want)X 2087(to)X 2170(depend)X 2423(on)X 2524(the)X 2643(end)X 2780(of)X 2868(the)X 2987(previous)X 3284(pattern.)X 3568(Thus,)X 3769(after)X 3938(we)X 864 4674(compute)N 2 f 1171(R)X 7 s 1224 4690(j)N 1 f 10 s 1246 4674(,)N 1297(we)X 1422(OR)X 1564(it)X 1639(with)X 2 f 1812(S)X 9 f (\242)S 7 s 2 f 1872 4690(s)N 1 f 10 s 1931 4674(\(where)N 2 f 2186(s)X 9 f 2236(=)X 2 f 2293(t)X 7 s 2319 4690(j)N 1 f 10 s 2341 4674(\).)N 2439(We)X 2582(compute)X 2890(the)X 3020(rest)X 3168(of)X 3267(the)X 2 f 3397(R)X 1 f 3478(arrays)X 3707(as)X 3806(before,)X 864 4794(except)N 1106(that)X 1258(in)X 1352(each)X 1532(step)X 1693(we)X 1819(OR)X 1962(them)X 2153(to)X 2246(a)X 2313(special)X 2567(mask)X 2767(that)X 2918(sets)X 3069(the)X 3198(\256rst)X 2 f 3353(d)X 1 f 3424(bits)X 3570(in)X 2 f 3663(R)X 7 s 3721 4762(d)N 1 f 10 s 3786 4794(of)N 3884(each)X 864 4914(separate)N 1148(pattern)X 1391(to)X 1473(1;)X 1555(this)X 1690(allows)X 2 f 1919(d)X 1 f 1980(initial)X 2187(errors)X 2396(in)X 2479(each)X 2648(pattern.)X 2932(\(This)X 3122(is)X 3196(not)X 3319(the)X 3438(most)X 3614(ef\256cient)X 3898(way)X 864 5034(to)N 947(solve)X 1137(this)X 1273(problem,)X 1581(but)X 1704(it's)X 1827(reasonably)X 2196(simple.\))X 2497(This)X 2660(case)X 2820(is)X 2894(a)X 2951(special)X 3195(case)X 3355(of)X 3443(patterns)X 3717(as)X 3804(regular)X 864 5154(expressions,)N 1278(which)X 1494(we)X 1608(will)X 1752(discuss)X 2003(shortly.)X 10 p %%Page: 10 11 10 s 10 xH 0 xS 1 f 3 f 2408 696(10)N 6 f 12 s 864 984(3.7.)N 1078(Long)X 1341(Patterns)X 1 f 10 s 864 1137(Suppose)N 1170(that)X 1325(the)X 1458(pattern)X 1716(occupies)X 2032(several)X 2295(words)X 2526(and)X 2677(that)X 2832(it)X 2912(is)X 3001(a)X 3073(simple)X 3322(string.)X 3560(The)X 3721(algorithm)X 864 1257(proceeds)N 1184(in)X 1280(the)X 1412(same)X 1611(fashion)X 1881(by)X 1995(computing)X 2371(the)X 2 f 2503(R)X 7 s 2561 1225(d)N 1 f 10 s 2629 1257(arrays)N 2860(for)X 2988(all)X 3102(words.)X 3352(However,)X 3701(unless)X 3934(the)X 864 1377(number)N 1130(of)X 1218(errors)X 1427(is)X 1501(large,)X 1703(the)X 1822(\256rst)X 1967(part)X 2113(of)X 2201(the)X 2320(pattern)X 2564(will)X 2709(not)X 2832(match)X 3049(the)X 3169(text)X 3311(quite)X 3493(often.)X 3720(If)X 3796(there)X 3979(is)X 864 1497(no)N 966(match)X 1184(with)X 2 f 1348(k)X 1 f 1406(errors)X 1616(starting)X 1878(after)X 2048(position)X 2 f 2327(r)X 1 f 2380(of)X 2469(the)X 2589(pattern,)X 2854(then)X 3014(there)X 3197(is)X 3272(no)X 3374(need)X 3548(to)X 3632(maintain)X 3934(the)X 2 f 864 1617(R)N 1 f 938(arrays)X 1160(corresponding)X 1644(to)X 1731(positions)X 2044(larger)X 2257(than)X 2 f 2420(r)X 1 f 2476(\(their)X 2675(values)X 2905(will)X 3054(be)X 3155(0\).)X 3287(Thus,)X 3492(most)X 3673(of)X 3766(the)X 3890(time)X 864 1737(there)N 1046(will)X 1191(be)X 1287(no)X 1387(need)X 1559(to)X 1641(maintain)X 1941(the)X 2 f 2059(R)X 7 s 2117 1705(d)N 1 f 10 s 2171 1737(arrays)N 2388(for)X 2502(the)X 2620(right)X 2791(side)X 2940(of)X 3027(the)X 3145(pattern.)X 3408(We)X 3540(only)X 3702(need)X 3874(to)X 3956(be)X 864 1857(alerted)N 1105(when)X 1301(the)X 1421(last)X 1554(bit)X 1660(of)X 1749(the)X 1869(last)X 2 f 2002(R)X 7 s 2060 1825(d)N 1 f 10 s 2116 1857(array)N 2304(that)X 2446(we)X 2562(maintain)X 2864(gets)X 3015(the)X 3135(value)X 3331(of)X 3420(1.)X 3523(In)X 3613(that)X 3756(case,)X 3938(we)X 864 1977(start)N 1027(maintaining)X 1434(the)X 2 f 1556(R)X 7 s 1605 1993(d)N 1 f 10 s 1663 1977(arrays)N 1884(for)X 2002(the)X 2124(next)X 2286(part)X 2435(of)X 2526(the)X 2648(pattern.)X 2935(This)X 3101(improvement)X 3552(works)X 3772(only)X 3938(for)X 864 2097(simple)N 1097(strings)X 1330(and)X 1466(not)X 1588(for)X 1702(sets)X 1842(of)X 1929(strings)X 2162(or)X 2249(regular)X 2497(expressions.)X 6 f 12 s 864 2337(3.8.)N 1078(Regular)X 1462(Expressions)X 1 f 10 s 864 2490(The)N 1021(algorithm)X 1364(can)X 1508(be)X 1616(extended)X 1938(to)X 2032(allow)X 2242(any)X 2390(regular)X 2650(expression)X 3025(as)X 3124(a)X 3192(pattern.)X 3488(We)X 3633(describe)X 3934(the)X 864 2610(method)N 1130(here)X 1295(only)X 1463(brie\257y.)X 1738(Algorithms)X 2127(for)X 2246(matching)X 2569(regular)X 2822(expressions)X 3221(with)X 3388(errors,)X 3621(based)X 3829(on)X 3934(the)X 864 2730(dynamic-programming)N 1624(approach,)X 1960(appear)X 2196(in)X 2279([MM89].)X 2616(First,)X 2803(we)X 2918(illustrate)X 3219(the)X 3338(algorithm)X 3670(with)X 3833(a)X 3890(sim-)X 864 2850(ple)N 984(example.)X 1318(We)X 1452(do)X 1554(not)X 1678(try)X 1789(to)X 1873(optimize)X 2175(the)X 2295(algorithm)X 2628(at)X 2708(this)X 2845(stage;)X 3074(we)X 3190(try)X 3300(to)X 3383(make)X 3578(it)X 3643(as)X 3731(simple)X 3965(as)X 864 2970(possible)N 1153(\(a)X 1243(more)X 1435(detailed)X 1716(discussion)X 2076(and)X 2219(more)X 2411(ef\256cient)X 2701(algorithms)X 3071(will)X 3223(be)X 3327(presented)X 3663(elsewhere\).)X 864 3090(Let)N 997(the)X 1121(pattern)X 1370(be)X 2 f 1472(P)X 9 f 1540(=)X 2 f 1597(ab)X 1 f 1690(\()X 2 f 1717(cd)X 1 f 9 f 1806(|)X 2 f 1835(e)X 1 f 1877(\))X 2 f 7 s 1904 3058(*)N 10 s 1944 3090(fg)N 1 f 2032(\(i.e.,)X 2203(starting)X 2469(with)X 2 f 2637(ab)X 1 f 2743(and)X 2884(ending)X 3127(with)X 2 f 3300(fg)X 1 f 3387(with)X 3554(any)X 3695(number)X 3965(of)X 864 3210(either)N 2 f 1078(cd)X 1 f 1185(or)X 2 f 1283(e)X 1 f 1350(in)X 1443(between\).)X 1809(This)X 1983(regular)X 2243(expression)X 2618(is)X 2703(translated)X 3047(to)X 3141(the)X 3271(non-deterministic)X 3868(\256nite)X 864 3330(automata)N 1181(shown)X 1413(in)X 1498(Fig.)X 1647(3)X 1710(\(for)X 1854(more)X 2042(on)X 2145(such)X 2315(translations)X 2708(see)X 2835([HU79]\).)X 3176(We)X 3312(now)X 3474(assign)X 3698(a)X 3758(bit)X 3866(array)X 864 3450(to)N 947(represent)X 1263(the)X 1382(automata.)X 1736(We)X 1868(number)X 2133(the)X 2251(states)X 2449(including)X 2771(the)X 2889(null)X 3033(states)X 3231(that)X 3371(do)X 3471(not)X 3593(correspond)X 3970(to)X 864 3570(any)N 1000(character)X 1316(\(see)X 1466(Fig.)X 1612(3\).)X 1739(This)X 1901(``linearizes'')X 2337(the)X 2455(automata.)X 2809(Each)X 2990(state)X 3157(corresponds)X 3565(to)X 3647(one)X 3784(entry)X 3970(in)X 864 3690(the)N 984(array.)X 1212(Thus,)X 1414(for)X 2 f 1530(P)X 1 f 1601(we)X 1717(have)X 1891(an)X 1989(array)X 2177(of)X 2266(size)X 2413(11.)X 2555(Notice)X 2791(that)X 2933(all)X 3035(the)X 3155(non-)X 2 f 9 f 3302(e)X 1 f 3359(moves)X 3590(go)X 3692(to)X 3775(the)X 3894(next)X 864 3810(state)N 1032(and)X 1169(thus)X 1323(can)X 1456(be)X 1553(handled)X 1828(by)X 1929(essentially)X 2288(a)X 2345(shift)X 2508(and)X 2645(an)X 2742(AND)X 2937(operation.)X 3302(We)X 3436(need)X 3610(to)X 3694(\256nd)X 3840(a)X 3898(way)X 3 f 3695 4448(10)N 3298(9)X 2900(8)X 2503 4846(7)N 2106(6)X 2702 4051(5)N 2304(4)X 1907(3)X 1709 4448(2)N 1311(1)X 914(0)X 3670 4523 MXY 49 Dc 1 f 2466 4026(d)N 2081 4039(c)N 3471 4622(g)N 3087(f)X 2 f 9 f 1882 4337(e)N 2851 4275(e)N 2578 4697(e)N 1932 4635(e)N 1 f 2292 5019(e)N 2 f 9 f 2292 5206(e)N 1 f 1473 4635(b)N 1076(a)X 1733 MX -8 39 Dl 16 -19 Dl 25 4 Dl -33 -24 Dl 2876 MX -33 24 Dl 25 -4 Dl 16 19 Dl -8 -39 Dl 2702 5119 MXY 198 -547 Dl 1907 5119 MXY 795 0 Dl 1709 4572 MXY 198 547 Dl 1994 4833 MXY -2 -40 Dl -11 23 Dl -25 2 Dl 38 15 Dl 1833 4212 MXY -29 29 Dl 24 -7 Dl 18 17 Dl -13 -39 Dl 2789 4597 MXY -38 15 Dl 25 3 Dl 10 23 Dl 3 -41 Dl 2826 4423 MXY 13 -38 Dl -18 17 Dl -25 -6 Dl 30 27 Dl 3596 4523 MXY -35 -22 Dl 13 22 Dl -13 22 Dl 35 -22 Dl 3347 MX 298 0 Dl 2751 4126 MXY 100 397 Dl 2553 4920 MXY 298 -397 Dl 2156 4920 MXY 297 0 Dl 1758 4523 MXY 298 397 Dl 1758 4523 MXY 100 -397 Dl 3645 4523 MXY 99 Dc 2453 4920 MXY 99 Dc 2056 MX 99 Dc 3198 4523 MXY -34 -22 Dl 12 22 Dl -12 22 Dl 34 -22 Dl 2602 4126 MXY -34 -22 Dl 13 22 Dl -13 21 Dl 34 -21 Dl 2205 MX -34 -22 Dl 12 22 Dl -12 21 Dl 34 -21 Dl 1609 4523 MXY -34 -22 Dl 13 22 Dl -13 22 Dl 34 -22 Dl 1212 MX -34 -22 Dl 12 22 Dl -12 22 Dl 34 -22 Dl 2950 MX 298 0 Dl 2354 4126 MXY 298 0 Dl 1957 MX 298 0 Dl 1361 4523 MXY 298 0 Dl 964 MX 298 0 Dl 3248 MX 99 Dc 2851 MX 99 Dc 2652 4126 MXY 99 Dc 2255 MX 99 Dc 1858 MX 99 Dc 1659 4523 MXY 99 Dc 1262 MX 99 Dc 864 MX 99 Dc 1262 5446(Figure)N 1491(3:)X 1593(The)X 1738(non-deterministic)X 2323(automata)X 2637(corresponding)X 3116(to)X 2 f 3198(ab)X 1 f 3291(\()X 2 f 3318(cd)X 1 f 9 f 3407(|)X 2 f 3436(e)X 1 f 3478(\))X 2 f 3505(*)X 3551(fg)X 1 f 3613(.)X 11 p %%Page: 11 12 10 s 10 xH 0 xS 1 f 3 f 2408 696(11)N 1 f 864 984(to)N 948(deal)X 1104(with)X 1268(arbitrary)X 1567(jumps)X 1784(required)X 2074(by)X 2176(the)X 2 f 9 f 2296(e)X 1 f 2353(moves)X 2584(\(e.g.,)X 2770(from)X 2949(state)X 3119(2)X 3182(to)X 3267(state)X 3437(8\))X 3527(and)X 3666(with)X 3831(``non-)X 864 1104(jumps'')N 1138(that)X 1282(happen)X 1538(to)X 1624(be)X 1724(in)X 1810(consecutive)X 2213(states)X 2415(\(e.g.,)X 2602(from)X 2782(state)X 2953(5)X 3017(to)X 3103(state)X 3274(6\).)X 3405(The)X 3554(non-jumps)X 3920(can)X 864 1224(be)N 967(handled)X 1248(easily)X 1462(with)X 1631(a)X 1694(mask.)X 1930(The)X 2082(arbitrary)X 2386(jumps)X 2608(are)X 2735(harder)X 2969(to)X 3059(handle.)X 3341(The)X 3494(meaning)X 3798(of)X 3893(an)X 2 f 9 f 3997(e)X 1 f 864 1344(move)N 1071(from)X 1256(state)X 2 f 1432(i)X 1 f 1483(to)X 1574(state)X 2 f 1756(j)X 1 f 1807(is)X 1889(that)X 2038(if,)X 2136(at)X 2223(any)X 2368(point,)X 2581(we)X 2704(match)X 2928(up)X 3036(to)X 3126(state)X 2 f 3301(i)X 1 f 3351(then)X 3517(the)X 3643(same)X 3836(match)X 864 1464(holds)N 1057(also)X 1206(up)X 1306(to)X 1388(state)X 2 f 1561(j)X 1 f 1583(.)X 1643(In)X 1730(other)X 1915(words,)X 2151(if)X 2220(there)X 2401(is)X 2474(a)X 2531(1)X 2592(corresponding)X 3072(to)X 3155(state)X 2 f 3323(i)X 1 f 3366(in)X 3449(the)X 3568(array,)X 3775(then)X 3934(the)X 2 f 9 f 864 1584(e)N 1 f 921(move)X 1121(from)X 2 f 1299(i)X 1 f 1343(to)X 2 f 1433(j)X 1 f 1477(implies)X 1734(that)X 1876(there)X 2059(should)X 2294(be)X 2392(a)X 2450(1)X 2511(corresponding)X 2991(to)X 3074(state)X 2 f 3248(j)X 1 f 3270(.)X 3331(The)X 3477(main)X 3658(observation)X 864 1704(is)N 937(that)X 1077(a)X 1133(given)X 1331(bit)X 1435(array)X 1621(and)X 1757(set)X 1866(of)X 2 f 9 f 1953(e)X 1 f 2008(moves)X 2237(completely)X 2613(determine)X 2954(the)X 3072(value)X 3266(of)X 3354(the)X 3473(bit)X 3578(array)X 3765(after)X 3934(the)X 2 f 9 f 864 1824(e)N 1 f 925(moves)X 1160(are)X 1285(taken.)X 1545(Thus,)X 1751(the)X 1875(set)X 1990(of)X 2 f 9 f 2083(e)X 1 f 2144(moves)X 2379(de\256nes)X 2631(a)X 2692(function)X 2984(that)X 3129(maps)X 3323(a)X 3384(bit)X 3493(array)X 3684(to)X 3771(another.)X 864 1944(We)N 996(need)X 1168(to)X 1250(be)X 1346(able)X 1500(to)X 1582(implement)X 1944(this)X 2079(function)X 2366(ef\256ciently.)X 1064 2097(Let)N 2 f 1197(f)X 1 f 1239(denote)X 1473(the)X 1591(function)X 1878(that)X 2018(maps)X 2207(one)X 2343(bit)X 2447(array)X 2633(to)X 2715(another)X 2976(by)X 3076(applying)X 3376(all)X 3476(the)X 2 f 9 f 3594(e)X 1 f 3650(moves.)X 3920(We)X 864 2217(divide)N 1087(the)X 1208(bit)X 1315(array)X 1504(into)X 1651(bytes,)X 1863(i.e.,)X 2004(groups)X 2245(of)X 2335(8)X 2398(bits)X 2536(each.)X 2747(Consider)X 3059(the)X 3180(\256rst)X 3327(8)X 3390(bits)X 3528(of)X 3618(the)X 3739(bit)X 3846(array.)X 864 2337(The)N 1010(values)X 1236(of)X 1324(these)X 1510(bits)X 1646(determine)X 1988(which)X 2206(1's)X 2326(should)X 2561(be)X 2659(set)X 2770(when)X 2966(we)X 3082(apply)X 3282(the)X 2 f 9 f 3402(e)X 1 f 3459(moves)X 3690(on)X 3792(states)X 3992(1)X 864 2457(to)N 951(8.)X 1036(Since)X 1239(there)X 1425(are)X 1549(only)X 1716(256)X 1860(\()X 2 f 9 f 1887(=)X 1 f 1944(2)X 7 s 2425(8)Y 10 s 2018 2457(\))N 2069(possible)X 2355(values)X 2584(for)X 2702(8)X 2766(bits,)X 2925(we)X 3043(can)X 3179(preprocess)X 3547(all)X 3651(possibilities)X 864 2577(and)N 1003(construct)X 1320(a)X 1379(table)X 1558(of)X 1648(size)X 1796(256)X 1939(which)X 2158(will)X 2306(hold,)X 2492(for)X 2610(each)X 2782(possible)X 3068(byte,)X 3250(the)X 3372(whole)X 3592(bit)X 3700(array)X 3890(with)X 864 2697(1's)N 984(only)X 1148(in)X 1232(places)X 1455(corresponding)X 1936(to)X 2020(the)X 2 f 9 f 2140(e)X 1 f 2197(moves.)X 2468(\(We)X 2629(need)X 2803(the)X 2923(whole)X 3141(array)X 3329(and)X 3467(not)X 3591(just)X 3728(the)X 3847(\256rst)X 3992(8)X 864 2817(bits,)N 1022(because)X 1300(there)X 1484(might)X 1693(be)X 1792(forward)X 2070(jumps.\))X 2355(We)X 2490(can)X 2625(do)X 2728(that)X 2871(for)X 2988(each)X 3160(byte.)X 3362(Given)X 3582(now)X 3744(a)X 3804(current)X 864 2937(value)N 1071(of)X 2 f 1171(R)X 1 f 1220(,)X 1273(we)X 1400(\256rst)X 1557(apply)X 1768(the)X 1899(regular)X 2160(algorithm,)X 2524(taking)X 2757(care)X 2925(of)X 3025(regular)X 3286(non)X 2 f 9 f 3439(e)X 1 f 3507(moves,)X 3768(then)X 3938(we)X 864 3057(divide)N 1096(the)X 1226(array)X 1424(into)X 1580(bytes,)X 1801(\256nd)X 1957(the)X 2087(corresponding)X 2578(arrays)X 2807(in)X 2901(the)X 3032(tables)X 3252(\(we)X 3406(have)X 3591(one)X 3740(table)X 3929(per)X 864 3177(byte\),)N 1075(and)X 1217(OR)X 1354(all)X 1460(of)X 1553(them)X 1739(to)X 2 f 1827(R)X 1 f 1876(.)X 1942(This)X 2110(implements)X 2509(all)X 2615(the)X 2739(jumps,)X 2980(and)X 3122(if)X 3197(the)X 3320(pattern)X 3568(is)X 3646(occupies)X 3952(no)X 864 3297(more)N 1054(than)X 1217(32)X 1322(bits)X 1462(\(as)X 1581(is)X 1659(often)X 1849(the)X 1972(case\),)X 2183(only)X 2350(4)X 2415(more)X 2605(steps)X 2790(are)X 2914(required.)X 3247(\(If)X 3353(the)X 3477(text)X 3623(is)X 3702(large,)X 3909(it)X 3979(is)X 864 3417(worthwhile)N 1249(to)X 1331(preprocess)X 1695(16)X 1795(bits)X 1930(for)X 2044(a)X 2100(table)X 2276(of)X 2363(size)X 2508(65536)X 2728(and)X 2864(half)X 3009(as)X 3096(many)X 3294(steps.\))X 1064 3570(The)N 1215(algorithm)X 1552(sketched)X 1859(above)X 2077(is)X 2156(not)X 2284(the)X 2408(most)X 2589(ef\256cient)X 2878(algorithm,)X 3235(but)X 3364(it)X 3435(is)X 3515(reasonably)X 3890(sim-)X 864 3690(ple.)N 1022(More)X 1216(ef\256cient)X 1499(algorithms)X 1861(will)X 2005(be)X 2101(described)X 2429(elsewhere.)X 6 f 12 s 864 3930(3.9.)N 1078(Very)X 1312(Large)X 1600(Alphabets)X 1 f 10 s 864 4083(Sometimes)N 1247(the)X 1373(alphabet)X 1673(is)X 1754(very)X 1925(large.)X 2154(For)X 2293(example,)X 2613(the)X 2740(pattern)X 2992(can)X 3133(be)X 3238(a)X 3303(segment)X 3599(of)X 3695(a)X 3760(program)X 864 4203(which)N 1081(we)X 1196(want)X 1373(to)X 1456(\256nd)X 1601(inside)X 1813(a)X 1870(large)X 2052(program.)X 2385(Instead)X 2638(of)X 2726(counting)X 3027(each)X 3195(text)X 3335(character)X 3651(as)X 3738(a)X 3794(charac-)X 864 4323(ter)N 972(in)X 1057(the)X 1178(pattern,)X 1444(we)X 1561(may)X 1722(wish)X 1896(to)X 1982(count)X 2184(each)X 2356(line)X 2500(as)X 2591(a)X 2651(character)X 2971(\(this)X 3137(is)X 3214(done,)X 3414(for)X 3532(example,)X 3848(in)X 3934(the)X 864 4443(program)N 2 f 1156(diff)X 1 f 1282(which)X 1498(is)X 1571(used)X 1738(to)X 1820(compare)X 2117(\256les\).)X 2337(The)X 2482(problem)X 2769(we)X 2883(have)X 3055(with)X 3217(large)X 3398(alphabets)X 3721(is)X 3794(that)X 3934(the)X 864 4563(preprocessing)N 1340(stage,)X 1555(where)X 1782(all)X 1892(the)X 2 f 2020(S)X 7 s 4579(s)Y 1 f 10 s 2119 4563(arrays)N 2347(are)X 2477(constructed,)X 2898(will)X 3053(take)X 3218(too)X 3351(long)X 3524(and)X 3671(require)X 3930(too)X 864 4683(much)N 1064(space)X 1265(\(the)X 1412(set)X 1523(of)X 1612(all)X 1714(possible)X 1998(program)X 2292(lines)X 2465(is,)X 2560(for)X 2676(all)X 2778(practical)X 3077(purposes,)X 3403(in\256nite\).)X 3717(However,)X 864 4803(we)N 986(can)X 1126(use)X 1261(hashing)X 1538(to)X 1628(map)X 1794(the)X 1920(alphabet)X 2220(to)X 2310(a)X 2374(reasonable)X 2746(size.)X 2939(We)X 3079(\256rst)X 3232(decide)X 3471(the)X 3598(hashing)X 3876(table)X 864 4923(size,)N 1042(which)X 1271(should)X 1517(be)X 1626(large)X 1820(enough)X 2089(to)X 2184(avoid)X 2395(many)X 2606(collisions)X 2944(but)X 3078(not)X 3212(too)X 3346(large)X 3539(so)X 3642(that)X 3794(we)X 3920(can)X 864 5043(afford)N 1088(the)X 1213(space)X 1419(\(e.g.,)X 1609(1024\).)X 1863(The)X 2015(alphabet)X 2314(becomes)X 2622(the)X 2747(set)X 2863(of)X 2957(integers)X 3238(from)X 3421(1)X 3488(to)X 3577(the)X 3703(table)X 3887(size.)X 864 5163(The)N 1020(algorithm)X 1362(is)X 1446(applied)X 1713(to)X 1806(the)X 1935(hash)X 2113(values.)X 2388(At)X 2498(the)X 2626(end,)X 2792(all)X 2902(matches)X 3195(should)X 3438(be)X 3544(checked)X 3838(again,)X 864 5283(however,)N 1186(to)X 1274(remove)X 1541(matchings)X 1896(that)X 2042(result)X 2246(from)X 2428(collisions.)X 2800(We)X 2938(do)X 3044(not)X 3172(support,)X 3458(at)X 3542(this)X 3683(time,)X 3871(large)X 864 5403(alphabets)N 1187(in)X 2 f 1269(agrep)X 1 f 1456(.)X 12 p %%Page: 12 13 10 s 10 xH 0 xS 1 f 3 f 2408 696(12)N 6 f 14 s 864 984(4.)N 1019(Experim)X 1460(ental)X 1752(Results)X 1 f 10 s 864 1137(We)N 1000(have)X 1176(implemented)X 1618(the)X 1740(algorithm)X 2075(and)X 2215(many)X 2417(of)X 2508(its)X 2607(extensions)X 2969(and)X 3109(tested)X 3320(them)X 3504(against)X 3756(previous)X 864 1257(algorithms.)N 1272(All)X 1400(tests)X 1568(were)X 1751(run)X 1884(on)X 1990(a)X 2051(SUN)X 2236(SparcStation)X 2670(II)X 2749(running)X 3023(UNIX.)X 3289(A)X 3372(description)X 3753(of)X 2 f 3845(agrep)X 1 f 864 1377(\320)N 968(a)X 1028(tool)X 1176(for)X 1294(approximate)X 1719(string)X 1925(matching)X 2247(based)X 2454(on)X 2558(this)X 2697(algorithm,)X 3052(which)X 3272(we)X 3390(used)X 3562(for)X 3681(the)X 3804(experi-)X 864 1497(ments)N 1082(\320)X 1189(is)X 1269(given)X 1474(in)X 1563(the)X 1687(next)X 1851(section.)X 2144(In)X 2237(almost)X 2476(all)X 2582(the)X 2706(cases,)X 2922(our)X 3055(algorithm)X 3392(beat)X 3552(the)X 3676(other)X 3867(algo-)X 864 1617(rithms,)N 1108(sometimes)X 1470(by)X 1570(a)X 1626(wide)X 1802(margin.)X 1064 1770(The)N 1222(numbers)X 1531(given)X 1742(here)X 1914(should)X 2160(be)X 2269(taken)X 2476(with)X 2651(caution.)X 2960(Any)X 3131(such)X 3311(results)X 3554(depend)X 3820(on)X 3934(the)X 864 1890(architecture,)N 1296(the)X 1426(operating)X 1761(system,)X 2035(and)X 2183(the)X 2313(compilers)X 2661(used.)X 2879(We)X 3022(probably)X 3338(put)X 3471(more)X 3667(efforts)X 3908(into)X 864 2010(optimizing)N 1233(our)X 1363(algorithm)X 1697(than)X 1858(we)X 1975(did)X 2100(for)X 2218(other)X 2407(algorithms)X 2773(\(although)X 3104(we)X 3222(put)X 3348(signi\256cant)X 3705(effort)X 3908(into)X 864 2130(that)N 1006(too\),)X 1177(and)X 1315(we)X 1431(did)X 1555(not)X 1679(test)X 1812(all)X 1914(possible)X 2198(scenarios.)X 2559(However,)X 2896(we)X 3012(tried)X 3181(not)X 3304(only)X 3467(to)X 3550(be)X 3647(fair)X 3780(but)X 3903(also)X 864 2250(to)N 946(be)X 1042(conservative.)X 1508(We)X 1640(used)X 1807(the)X 1925(\256nal)X 2087(agrep)X 2286(program)X 2578(for)X 2693(all)X 2794(our)X 2922(tests)X 3085(even)X 3258(though)X 3501(it)X 3566(contains)X 3854(many)X 864 2370(options)N 1126(that)X 1273(slow)X 1451(it)X 1521(down)X 1725(and)X 1867(are)X 1992(not)X 2120(available)X 2436(in)X 2524(the)X 2648(other)X 2839(programs)X 3168(\(e.g.,)X 3357(the)X 3481(fact)X 3628(that)X 3774(agrep)X 3979(is)X 864 2490(record)N 1093(oriented)X 1379(\320)X 1482(see)X 1608(next)X 1769(section)X 2020(\320)X 2124(slows)X 2330(it)X 2398(down)X 2600(considerably\).)X 3101(For)X 3236(the)X 3358(simple)X 3595(cases)X 3789(that)X 3933(are)X 864 2610(listed)N 1065(in)X 1155(the)X 1281(tables)X 1496(below,)X 1740(we)X 1862(sometimes)X 2232(obtained)X 2536(20-30%)X 2818(faster)X 3025(running)X 3302(times)X 3502(with)X 3671(versions)X 3965(of)X 864 2730(the)N 982(program)X 1274(that)X 1414(has)X 1541(only)X 1703(the)X 1821(tested)X 2028(options.)X 2323(We)X 2455(believe)X 2707(that)X 2847(the)X 2965(main)X 3145(strength)X 3423(of)X 3511(this)X 3647(algorithm)X 3979(is)X 864 2850(that)N 1015(it)X 1090(is)X 1174(more)X 1370(\257exible,)X 1661(general,)X 1949(and)X 2096(convenient)X 2479(than)X 2648(all)X 2759(previous)X 3066(algorithms.)X 3479(The)X 3635(fact)X 3787(that)X 3938(for)X 864 2970(most)N 1046(of)X 1140(the)X 1265(common)X 1573(applications)X 1988(of)X 2083(it,)X 2175(agrep)X 2382(is)X 2463(also)X 2620(signi\256cantly)X 3043(faster)X 3250(than)X 3416(other)X 3609(algorithms)X 3979(is)X 864 3090(nice,)N 1038(but)X 1160(speed)X 1363(is)X 1436(mostly)X 1673(a)X 1729(secondary)X 2075(issue)X 2255(here;)X 2456(other)X 2641(algorithms)X 3003(are)X 3122(reasonably)X 3490(fast)X 3626(already.)X 1064 3243(First,)N 1252(we)X 1368(tested)X 1577(searching)X 1907(without)X 2173(errors)X 2384(vs.)X 2498(the)X 2619(grep)X 2785(family)X 3017(of)X 3107(programs)X 3433(available)X 3746(in)X 3831(UNIX)X 864 3363(and)N 1003(against)X 1253(an)X 1351(implementation)X 1875(of)X 1964(the)X 2084(Boyer-Moore)X 2543(algorithm.)X 2916(The)X 3063(text)X 3205(was)X 3352(a)X 3410(bibliography)X 3841(\256le)X 3965(of)X 864 3483(size)N 1012(one)X 1151(Megabytes.)X 1567(We)X 1703(used)X 1874(5)X 1938(patterns)X 2216(of)X 2307(varying)X 2576(sizes)X 2756(\(4-10\))X 2981(and)X 3121(averaged)X 3436(the)X 3558(results.)X 3831(Agrep)X 864 3603(consistently)N 1284(beats)X 1487(the)X 1623(grep)X 1804(family,)X 2071(but)X 2211(it)X 2293(is)X 2383(not)X 2522(as)X 2626(fast)X 2779(as)X 2883(the)X 3018(Boyer-Moore)X 3492(algorithm.)X 3880(\(The)X 864 3723(Boyer-Moore)N 1321(algorithm)X 1652(cannot)X 1886(be)X 1982(used,)X 2169(as)X 2256(far)X 2366(as)X 2453(we)X 2567(know,)X 2785(for)X 2899(most)X 3074(of)X 3161(the)X 3279(extensions)X 3638(in)X 3721(the)X 3840(previ-)X 864 3843(ous)N 1002(section;)X 1298(even)X 1477(\256nding)X 1730(line)X 1877(numbers)X 2180(for)X 2301(all)X 2408(the)X 2533(matches)X 2823(is)X 2902(not)X 3030(trivial)X 3247(and)X 3389(slows)X 3597(the)X 3721(algorithm)X 864 3963(down)N 1062(considerably.\))X 1064 4116(We)N 1196(then)X 1354(tested)X 1561(the)X 1679(approximate)X 2100(string-matching)X 2627(algorithm)X 2958(against)X 3206(two)X 3347(other)X 3533(algorithms,)X 3916(one)X 864 4236(by)N 969(Ukkonen)X 1288([Uk85a])X 1581(\(which)X 1829(we)X 1948(implemented\))X 2418(and)X 2559(one)X 2699(by)X 2803(Galil)X 2987(and)X 3127(Park)X 3298([GP90])X 3558(\(labeled)X 3841(MN2;)X 864 4356(the)N 983(program)X 1276(was)X 1422(provided)X 1728(to)X 1811(us)X 1903(by)X 2004(W.)X 2121(I.)X 2189(Chang\))X 2446(which)X 2663(is)X 2737(based)X 2941(on)X 3042(another)X 3304(technique)X 3637(by)X 3738(Ukkonen)X 864 4476([Uk85b].)N 1200(The)X 1349(last)X 1484(algorithm)X 1818(was)X 1966(found)X 2176(by)X 2279(Chang)X 2511(and)X 2650(Lawler)X 2901([CL90])X 3160(to)X 3245(be)X 3344(the)X 3465(fastest)X 3693(among)X 3934(the)X 864 4596(algorithms)N 1227(they)X 1386(tested.)X 1635(We)X 1769(used)X 1938(random)X 2205(text)X 2347(\(of)X 2463(size)X 2610(1,000,000\))X 2979(and)X 3117(pattern)X 3362(\(of)X 3478(size)X 3625(20\),)X 3774(and)X 3912(two)X 864 4716(different)N 1166(alphabet)X 1463(sizes.)X 1684(In)X 1776(this)X 1916(case,)X 2099(since)X 2288(we)X 2406(use)X 2537(the)X 2659(idea)X 2817(of)X 2908(partitioning)X 3305(the)X 3427(pattern,)X 3694(the)X 3816(size)X 3965(of)X 864 4836(the)N 983(alphabet)X 1276(makes)X 1502(a)X 1560(big)X 1684(difference.)X 2073(A)X 2153(large)X 2336(alphabet)X 2630(leads)X 2817(to)X 2901(very)X 3066(few)X 3209(accidental)X 3557(exact)X 3749(matches,)X 10 f 1632 5005(i)N 1663(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1 f 1680 5125(BM)N 1932(agrep)X 2231(egrep)X 2530(grep)X 2793(fgrep)X 3106(wc)X 10 f 1632 5165(i)N 1663(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1 f 1672 5285(0.21)N 1951(0.35)X 2250(0.79)X 2531(1.22)X 2808(1.61)X 3083(1.19)X 10 f 1632 5325(i)N 1663(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1632(c)X 5245(c)Y 5165(c)Y 5085(c)Y 3263 5325(c)N 5245(c)Y 5165(c)Y 5085(c)Y 1 f 1758 5478(Table)N 1961(1:)X 2063(Exact)X 2266(matching)X 2584(of)X 2671(simple)X 2904(strings.)X 13 p %%Page: 13 14 10 s 10 xH 0 xS 1 f 3 f 2408 696(13)N 1 f 864 984(thus)N 1017(the)X 1135(running)X 1404(time)X 1566(is)X 1639(essentially)X 1997(the)X 2115(same)X 2300(as)X 2387(the)X 2505(one)X 2641(for)X 2755(exact)X 2945(matching.)X 3303(A)X 3381(small)X 3574(alphabet)X 3867(leads)X 864 1104(to)N 953(many)X 1158(matches)X 1447(and)X 1589(the)X 1713(algorithm's)X 2108(performance)X 2541(degrades.)X 2893(The)X 3044(case)X 3209(of)X 3302(binary)X 3533(alphabet)X 3831(serves)X 864 1224(as)N 952(the)X 1071(worst)X 1270(case)X 1430(for)X 1545(this)X 1681(purpose.)X 1976(Results)X 2232(are)X 2352(shown)X 2582(in)X 2666(Table)X 2871(2.)X 2973(The)X 3120(\256nal)X 3284(test)X 3417(was)X 3564(for)X 3680(more)X 3867(com-)X 864 1344(plicated)N 1146(patterns,)X 1448(including)X 1778(some)X 1974(of)X 2068(the)X 2193(extensions)X 2558(discussed)X 2892(in)X 2981(the)X 3106(previous)X 3409(section.)X 3703(\(Anything)X 864 1464(within)N 1093(the)X 1216()X 1331(brackets)X 1624(must)X 1804(match)X 2025(exactly;)X 2305(a)X 2367(`#')X 2487(stands)X 2713(for)X 2833(a)X 2895(wild)X 3063(card)X 3228(of)X 3321(arbitrary)X 3624(length;)X 3872(A)X 3956(`;')X 864 1584(serves)N 1088(as)X 1178(the)X 1299(Boolean)X 1589(AND)X 1786(operation,)X 2132(namely)X 2391(all)X 2494(patterns)X 2771(must)X 2949(appear)X 3187(within)X 3413(the)X 3533(same)X 3720(line;)X 3904(a)X 3962(`)X 9 f 3989(|)X 1 f (')S 864 1704(is)N 937(the)X 1055(regular)X 1303(expression)X 1666(union)X 1868(operation;)X 2213(and)X 2349(a)X 2405(`*')X 2519(is)X 2592(the)X 2710(Kleene)X 2958(closure.\))X 3277(The)X 3422(results)X 3651(are)X 3771(given)X 3970(in)X 864 1824(Table)N 1068(3)X 1129(\(the)X 1275(\256le)X 1398(was)X 1544(the)X 1663(same)X 1849(bibliographic)X 2297(\256le)X 2420(used)X 2588(in)X 2671(Table)X 2874(1\).)X 3001(The)X 3146(best)X 3295(algorithm)X 3626(we)X 3740(know)X 3938(for)X 864 1944(approximate)N 1291(matching)X 1615(to)X 1703(arbitrary)X 2006(regular)X 2260(expressions)X 2660(is)X 2739(by)X 2846(Myers)X 3078(and)X 3221(Miller)X 3448([MM89].)X 3791(Its)X 3898(run-)X 864 2064(ning)N 1034(times)X 1235(for)X 1357(the)X 1483(cases)X 1681(we)X 1803(tested)X 2018(were)X 2203(more)X 2396(than)X 2562(an)X 2666(order)X 2864(of)X 2959(magnitude)X 3325(slower)X 3567(than)X 3733(our)X 3867(algo-)X 864 2184(rithm,)N 1083(but)X 1211(this)X 1352(is)X 1431(not)X 1559(a)X 1621(fair)X 1759(test,)X 1916(because)X 2197(Myers)X 2428(and)X 2570(Miller's)X 2854(algorithm)X 3191(can)X 3329(handle)X 3569(arbitrary)X 3872(costs)X 864 2304(\(which)N 1120(we)X 1246(cannot)X 1492(handle\))X 1765(and)X 1913(its)X 2020(running)X 2301(time)X 2475(is)X 2560(independent)X 2984(of)X 3083(the)X 3213(number)X 3490(of)X 3589(errors)X 3809(\(which)X 864 2424(makes)N 1089(it)X 1153(high)X 1315(for)X 1429(small)X 1622(errors\).)X 10 f 1381 2746(i)N 1394(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1 f 1726 2866(agrep)N 2501(MN2)X 3111(Uk85a)X 9 f 1706 2986(S)N 1 f 1773(=)X 1838(2)X 9 f 1998(S)X 1 f 2065(=)X 2130(30)X 9 f 2334(S)X 1 f 2401(=)X 2466(2)X 9 f 2630(S)X 1 f 2697(=)X 2762(30)X 9 f 2966(S)X 1 f 3033(=)X 3098(2)X 9 f 3262(S)X 1 f 3329(=)X 3394(30)X 10 f 1381 3026(i)N 1394(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1 f 1421 3146(k)N 1481(=)X 1546(0)X 1722(0.35)X 2034(0.35)X 2350(1.21)X 2666(0.98)X 2982(2.36)X 3298(0.90)X 1421 3266(k)N 1481(=)X 1546(1)X 1722(0.52)X 2034(0.38)X 2350(3.03)X 2666(2.42)X 2982(5.01)X 3298(2.06)X 1421 3386(k)N 1481(=)X 1546(2)X 1722(1.78)X 2034(0.38)X 2350(4.94)X 2666(3.87)X 2982(7.93)X 3298(3.19)X 1421 3506(k)N 1481(=)X 1546(3)X 1722(2.56)X 2034(0.39)X 2350(6.68)X 2666(5.33)X 2962(11.80)X 3298(4.38)X 1421 3626(k)N 1481(=)X 1546(4)X 1722(3.83)X 2034(0.41)X 2350(8.72)X 2666(6.89)X 2962(13.40)X 3298(5.55)X 1421 3746(k)N 1481(=)X 1546(5)X 1722(4.42)X 2034(0.42)X 2330(10.41)X 2666(8.28)X 2962(15.45)X 3298(6.77)X 1421 3866(k)N 1481(=)X 1546(6)X 1722(5.13)X 2034(0.73)X 2330(11.83)X 2666(9.75)X 2962(17.07)X 3298(7.99)X 10 f 1381 3906(i)N 1394(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1381(c)X 3866(c)Y 3786(c)Y 3706(c)Y 3626(c)Y 3546(c)Y 3466(c)Y 3386(c)Y 3306(c)Y 3226(c)Y 3146(c)Y 3066(c)Y 2986(c)Y 2906(c)Y 2826(c)Y 1646 3906(c)N 3826(c)Y 3746(c)Y 3666(c)Y 3586(c)Y 3506(c)Y 3426(c)Y 3346(c)Y 3266(c)Y 3186(c)Y 3106(c)Y 2270 3906(c)N 3866(c)Y 3786(c)Y 3706(c)Y 3626(c)Y 3546(c)Y 3466(c)Y 3386(c)Y 3306(c)Y 3226(c)Y 3146(c)Y 3066(c)Y 2986(c)Y 2906(c)Y 2826(c)Y 2902 3906(c)N 3866(c)Y 3786(c)Y 3706(c)Y 3626(c)Y 3546(c)Y 3466(c)Y 3386(c)Y 3306(c)Y 3226(c)Y 3146(c)Y 3066(c)Y 2986(c)Y 2906(c)Y 2826(c)Y 3514 3906(c)N 3866(c)Y 3786(c)Y 3706(c)Y 3626(c)Y 3546(c)Y 3466(c)Y 3386(c)Y 3306(c)Y 3226(c)Y 3146(c)Y 3066(c)Y 2986(c)Y 2906(c)Y 2826(c)Y 1 f 1537 4123(Table)N 1740(2:)X 1842(Approximate)X 2285(string)X 2487(matching)X 2805(of)X 2892(simple)X 3125(strings.)X 10 f 1335 4292(i)N 1361(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1 f 1375 4412(pattern)N 2501(k)X 2561(=)X 2626(0)X 2786(k)X 2846(=)X 2911(1)X 3071(k)X 3131(=)X 3196(2)X 3356(k)X 3416(=)X 3481(3)X 10 f 1335 4452(i)N 1361(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1 f 1375 4572(Homogenious)N 2513(0.35)X 2798(0.39)X 3083(0.41)X 3368(0.47)X 1375 4692(ogenious)N 2513(0.53)X 2798(1.10)X 3083(1.42)X 3368(1.74)X 1375 4812(JACM;)N 1630(1981;)X 1832(Graph)X 2513(0.53)X 2798(1.10)X 3083(1.43)X 3368(1.75)X 1375 4932(Prob#tic;)N 1688(Algo#m)X 2513(0.55)X 2798(1.10)X 3083(1.42)X 3368(1.76)X 1375 5052(;)N 1827(Prob#tic;)X 2140(trees)X 2513(0.54)X 2798(1.11)X 3083(1.43)X 3368(1.75)X 1375 5172(\(\\)N 9 f 1648(-)X 1 f 1692([23]*)X 9 f 1866(|)X 1 f (\).*ees)S 2513(0.66)X 2798(1.53)X 3083(2.19)X 3368(2.83)X 10 f 1335 5212(i)N 1361(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X 1335(c)X 5172(c)Y 5092(c)Y 5012(c)Y 4932(c)Y 4852(c)Y 4772(c)Y 4692(c)Y 4612(c)Y 4532(c)Y 4452(c)Y 4372(c)Y 3561 5212(c)N 5172(c)Y 5092(c)Y 5012(c)Y 4932(c)Y 4852(c)Y 4772(c)Y 4692(c)Y 4612(c)Y 4532(c)Y 4452(c)Y 4372(c)Y 1 f 1528 5429(Table)N 1731(3:)X 1833(Approximate)X 2276(matching)X 2594(of)X 2681(complicated)X 3093(patterns.)X 14 p %%Page: 14 15 10 s 10 xH 0 xS 1 f 3 f 2408 696(14)N 6 f 14 s 864 984(5.)N 1019(A)X 1131(Description)X 1777(of)X 1914(agrep)X 2 f 10 s 864 1137(agrep)N 1 f 1078(is)X 1158(used)X 1332(similarly)X 1643(to)X 1732(egrep)X 1938(and)X 2082(it)X 2154(supports)X 2453(most)X 2636(of)X 2731(the)X 2857(features)X 3140(of)X 3235(egrep)X 3442(\(although)X 3777(it)X 3849(is)X 3930(not)X 864 1257(100%)N 1079(compatible\))X 1490(and)X 1634(many)X 1840(additional)X 2188(features.)X 2511(One)X 2673(notable)X 2936(difference)X 3290(between)X 3585(agrep)X 3791(and)X 3934(the)X 864 1377(grep)N 1042(family)X 1286(\(besides)X 1584(the)X 1717(additional)X 2072(features\))X 2389(is)X 2477(that)X 2632(agrep)X 2846(is)X 2 f 2934(record)X 3184(oriented)X 1 f 3487(\(rather)X 3738(than)X 3912(line)X 864 1497(oriented\).)N 1230(A)X 1324(record)X 1566(is)X 1655(de\256ned)X 1927(by)X 2043(the)X 2176(user)X 2345(\(with)X 2549(the)X 2682(default)X 2940(being)X 3153(a)X 3224(line\).)X 3446(Agrep)X 3682(outputs)X 3952(all)X 864 1617(records)N 1135(that)X 1289(match)X 1519(the)X 1651(query)X 1868(\(see)X 2032(also)X 2195(the)X 2327(-d)X 2428(option)X 2666(described)X 3008(below\).)X 3305(Agrep)X 3540(is)X 3627(available)X 3952(by)X 864 1737(anonymous)N 1253(ftp)X 1362(from)X 1538(cs.arizona.edu)X 2018(\(IP)X 2136(number)X 2401(192.12.69.5\).)X 3 f 1008 1921(agrep)N 1 f 2 f 1250(pattern)X 1 f 1527(\256le-name)X 1856(\320)X 1962(\256nds)X 2143(all)X 2249 0.3125(occurrences)AX 2661(of)X 2 f 2755(pattern)X 1 f 3013(\(that)X 3187(is,)X 3287(output)X 3518(all)X 3625(records)X 3889(con-)X 864 2041(taining)N 2 f 1107(pattern)X 1 f 1338(\))X 1386(in)X 1469(the)X 1588(text)X 1729(\256le)X 1852(\256le-name)X 2176(without)X 2441(errors.)X 2690(The)X 2836(pattern)X 3080(can)X 3213(be)X 3310(a)X 3367(string)X 3570(or)X 3658(an)X 3755(arbitrary)X 864 2161(regular)N 1114(expression.)X 1519(We)X 1653(describe)X 1943(below)X 2162(the)X 2283(unusual)X 2555(features)X 2833(of)X 2923(agrep)X 3125(that)X 3268(are)X 3390(not)X 3515(found)X 3725(in)X 3810(similar)X 864 2281(programs.)N 1227(A)X 1305(complete)X 1619(description)X 1995(is)X 2068(given)X 2266(in)X 2348(the)X 2466(manual)X 2722(pages)X 2925(distributed)X 3287(with)X 3449(agrep.)X 864 2434(-)N 2 f 891(k)X 1 f 1064(\256nds)X 1240(all)X 1341 0.3125(occurrences)AX 1747(with)X 1910(at)X 1989(most)X 2 f 2165(k)X 1 f 2222(errors)X 2431(\(insertions,)X 2810(deletions,)X 3141(or)X 3230(substitutions\),)X 3702(where)X 2 f 3921(k)X 1 f 3979(is)X 1064 2554(a)N 1120(positive)X 1393(integer.)X 864 2707(-D)N 2 f 949(c)X 1 f 1064(each)X 1232(deletion)X 1510(counts)X 1739(as)X 2 f 1826(c)X 1 f 1882(errors;)X 2 f 2112(c)X 1 f 2168(must)X 2343(be)X 2439(a)X 2495(non-negative)X 2934(integer;)X 3199(the)X 3317(default)X 3560(value)X 3754(of)X 2 f 3841(c)X 1 f 3897(is)X 3970(1)X 864 2860(-I)N 2 f 918(c)X 1 f 1064(each)X 1232(insertion)X 1532(counts)X 1761(as)X 2 f 1848(c)X 1 f 1904(errors;)X 2 f 2134(c)X 1 f 2190(must)X 2365(be)X 2461(a)X 2517(non-negative)X 2956(integer;)X 3221(the)X 3339(default)X 3582(value)X 3776(of)X 2 f 3863(c)X 1 f 3919(is)X 3992(1)X 864 3013(-S)N 2 f 935(c)X 1 f 1064(each)X 1234(substitution)X 1628(counts)X 1859(as)X 2 f 1948(c)X 1 f 2006(errors;)X 2 f 2238(c)X 1 f 2296(must)X 2474(be)X 2573(a)X 2632(non-negative)X 3074(integer;)X 3342(the)X 3463(default)X 3709(value)X 3906(of)X 2 f 3996(c)X 1 f 1064 3133(is)N 1137(1)X 864 3286(-d)N 951(`)X 3 f 978(delim)X 1 f 1169(')X 3 f 1064 3406(delim)N 1 f 1282(is)X 1362(a)X 1425(user-de\256ned)X 1849(symbol)X 2111(\(or)X 2232(string\))X 2468(for)X 2589(record)X 2823(delimiter)X 3140(\(the)X 3293(default)X 3544(is)X 3625(the)X 3751(new-line)X 1064 3526(symbol\).)N 1386(This)X 1548(enables)X 1809(searching)X 2137(paragraphs)X 2510(\(in)X 2619(which)X 2835(case)X 3 f 2994(delim)X 1 f 3205(=)X 3270(2)X 3330(new)X 3484(lines)X 3655(in)X 3737(a)X 3793(row\))X 3965(or)X 1064 3646(mail)N 1239(messages)X 1575(\()X 3 f 1602(delim)X 1 f 1826(=)X 1904('\303From)X 2151('\).)X 2278(This)X 2453(feature)X 2710(makes)X 2948(agrep)X 3160(a)X 3230(record-oriented)X 3760(program)X 1064 3766(rather)N 1272(than)X 1430(just)X 1565(a)X 1621(line-oriented)X 2051(program.)X 2383(We)X 2515(believe)X 2767(that)X 2907(it)X 2971(will)X 3115(be)X 3211(very)X 3374(useful.)X 6 f 12 s 864 3919(Examples)N 2 f 10 s 864 4072(agrep)N 1 f 1071(-3)X 1158(-D2)X 1064 4192(\256nds)N 1250(all)X 1361 0.3125(occurrences)AX 1777(with)X 1950(at)X 2039(most)X 2225(3)X 2297(errors)X 2517(where)X 2746(a)X 2814(deletion)X 3104(counts)X 3345(as)X 3444(2)X 3516(errors)X 3736(and)X 3884(each)X 1064 4312(insertion)N 1364(or)X 1451(substitution)X 1843(counts)X 2072(as)X 2159(one)X 2295(error.)X 2 f 864 4465(agrep)N 1 f 1071(-4)X 1158(-I5)X 1064 4585(\256nds)N 1246(all)X 1353 0.3125(occurrences)AX 1765(with)X 1934(at)X 2019(most)X 2201(4)X 2268(errors)X 2483(but)X 2612(no)X 2719(insertions)X 3057(allowed)X 3338(\(because)X 3647(their)X 3822(cost)X 3979(is)X 1064 4705(prohibited\).)N 864 4858(agrep)N 1063(-d)X 1150('\303From)X 1397(')X 1444('breakdown;)X 1870(\(inter)X 9 f 2044(|)X 1 f (arpa)S 9 f 2199(|)X 1 f (bit\)net')S 1064 4978(outputs)N 1324(all)X 1429(mail)X 1596(messages)X 1924(\(the)X 2074(pattern)X 2322('\303From)X 2569(')X 2621(separates)X 2942(mail)X 3110(messages)X 3439(in)X 3527(a)X 3589(mail)X 3757(\256le\))X 3912(that)X 1064 5098(contain)N 1320(breakdown)X 1697(and)X 1833(one)X 1969(of)X 2056(either)X 2259(internet,)X 2544(arpanet,)X 2821(or)X 2908(bitnet.)X 2 f 864 5251(agrep)N 1 f 1071(-d)X 1158('$$')X 1312(-1)X 1399(')X 1761(')X 1064 5371(\256nds)N 1248(all)X 1357(paragraphs)X 1739(that)X 1888(contain)X 2153(word1)X 2387(followed)X 2701(by)X 2810(word2)X 3044(with)X 3215(one)X 3360(error)X 3546(in)X 3637(place)X 3837(of)X 3934(the)X 1064 5491(blank)N 1264(between)X 1554(the)X 1673(words)X 1890(\(the)X 2036()X 2147(indicate)X 2422(that)X 2563(no)X 2664(error)X 2842(is)X 2916(allowed)X 3191(inside;)X 3425(see)X 3549(section)X 3797(3.4\).)X 3965(In)X 1064 5611(particular,)N 1412(if)X 1481(word1)X 1706(is)X 1779(the)X 1897(last)X 2028(word)X 2213(in)X 2295(a)X 2351(line)X 2491(and)X 2627(word2)X 2852(is)X 2925(the)X 3043(\256rst)X 3187(word)X 3372(in)X 3455(the)X 3574(next)X 3733(line,)X 3894(then)X 15 p %%Page: 15 16 10 s 10 xH 0 xS 1 f 3 f 2408 696(15)N 1 f 1064 984(the)N 1187(space)X 1391(will)X 1540(be)X 1641(substituted)X 2012(by)X 2117(a)X 2178(newline)X 2457(symbol)X 2716(and)X 2856(it)X 2924(will)X 3072(match.)X 3332(Thus,)X 3536(this)X 3675(is)X 3752(a)X 3812(way)X 3970(to)X 1064 1104(overcome)N 1407(separation)X 1763(by)X 1869(a)X 1931(newline.)X 2251(Note)X 2433(that)X 2579(-d)X 2672('')X 2752(\(or)X 2873(another)X 3141(delim)X 3350(that)X 3497(spans)X 3702(more)X 3894(than)X 1064 1224(one)N 1200(line\))X 1367(is)X 1440(necessary,)X 1793(because)X 2068(otherwise)X 2400(agrep)X 2599(searches)X 2892(only)X 3054(one)X 3190(line)X 3330(at)X 3408(a)X 3464(time.)X 6 f 14 s 864 1496(6.)N 1019 -0.3063(Conclusions)AX 1 f 10 s 864 1649(Searching)N 1208(text)X 1351(in)X 1436(the)X 1557(presence)X 1862(of)X 1952(errors)X 2163(is)X 2239(commonly)X 2604(done)X 2783(`by)X 2914(hand')X 3121(\320)X 3225(one)X 3365(tries)X 3527(all)X 3631(possibilities.)X 864 1769(This)N 1033(is)X 1113(frustrating,)X 1494(slow,)X 1692(and)X 1834(with)X 2002(no)X 2108(guarantee)X 2447(of)X 2540(success.)X 2847(The)X 2998(new)X 3158(algorithm)X 3495(presented)X 3829(in)X 3917(this)X 864 1889(paper)N 1073(for)X 1197(searching)X 1535(with)X 1707(errors)X 1925(can)X 2068(alleviate)X 2371(this)X 2517(problem)X 2815(and)X 2962(make)X 3167(searching)X 3506(in)X 3599(general)X 3867(more)X 864 2009(robust.)N 1127(It)X 1198(also)X 1349(makes)X 1576(searching)X 1906(more)X 2093(convenient)X 2467(by)X 2569(not)X 2693(having)X 2933(to)X 3017(spell)X 3190(everything)X 3555(precisely.)X 3907(The)X 864 2129(algorithm)N 1195(is)X 1268(very)X 1431(fast)X 1567(and)X 1703(general)X 1960(and)X 2096(it)X 2160(should)X 2393(\256nd)X 2537(numerous)X 2873(applications.)X 1064 2282(There)N 1273(is)X 1347(one)X 1484(important)X 1816(area)X 1972(of)X 2060(searching)X 2389(with)X 2552(errors)X 2761(that)X 2902(we)X 3017(did)X 3140(not)X 3263(address)X 3525(\320)X 3626(searching)X 3956(an)X 864 2402(indexed)N 1147(\256le.)X 1318(Throughout)X 1725(the)X 1852(paper)X 2060(we)X 2183(assumed)X 2488(that)X 2637(the)X 2764(\256les)X 2926(are)X 3054(not)X 3185(indexed)X 3468 0.2500(\(preprocessed\))AX 3970(in)X 864 2522(any)N 1000(way,)X 1174(thus)X 1327(a)X 1383(sequential)X 1728(scan)X 1891(through)X 2160(them)X 2340(is)X 2413(necessary.)X 2786(We)X 2918(believe)X 3170(that)X 3311(the)X 3430(problem)X 3718(of)X 3806(\256nding)X 864 2642(good)N 1060(indexing)X 1376(schemes)X 1684(that)X 1840(allow)X 2053(approximate)X 2489(search)X 2730(is)X 2818(the)X 2951(main)X 3146(open)X 3337(problem)X 3639(is)X 3727(this)X 3877(area.)X 864 2762(Unfortunately,)N 1355(we)X 1470(do)X 1571(not)X 1694(know)X 1893(of)X 1981(any)X 2118(satisfactory)X 2509(solution)X 2787(at)X 2866(this)X 3002(point.)X 3228(However,)X 3565(with)X 3729(the)X 3849(speed)X 864 2882(of)N 957(current)X 1211(computers,)X 1590(scanning)X 1900(large)X 2086(\256les)X 2244(\(up)X 2376(to)X 2463(tens)X 2617(of)X 2709(megabytes\))X 3104(can)X 3241(be)X 3342(done)X 3523(reasonably)X 3896(fast.)X 864 3002(One)N 1023(can)X 1160(argue)X 1364(that)X 1509(the)X 1632(size)X 1782(of)X 1874(our)X 2006(data)X 2165(increases)X 2485(as)X 2577(our)X 2709(speed)X 2918(of)X 3011(processing)X 3380(it)X 3450(increases.)X 3811(This)X 3979(is)X 864 3122(certainly)N 1173(true)X 1326(for)X 1448(some)X 1645(applications,)X 2079(but)X 2208(not)X 2337(for)X 2458(all.)X 2605(Many)X 2819(applications)X 3233(have)X 3412(an)X 3515(upper)X 3725(bound)X 3952(on)X 864 3242(size)N 1009(and)X 1145(sequential)X 1490(search)X 1716(for)X 1830(those)X 2019(applications)X 2426(will)X 2570(be)X 2666(realistic.)X 6 f 14 s 864 3482(Acknowledgem)N 1683(ents:)X 1 f 10 s 864 3635(We)N 1000(thank)X 1202(Ricardo)X 1480(Baeza-Yates,)X 1931(Gene)X 2125(Myers,)X 2375(and)X 2516(Chunghwa)X 2888(H.)X 2991(Rao)X 3145(for)X 3264(many)X 3467(helpful)X 3719(conversa-)X 864 3755(tions)N 1051(about)X 1261(approximate)X 1694(string)X 1908(matching)X 2238(and)X 2386(for)X 2512(comments)X 2873(that)X 3025(improved)X 3364(the)X 3493(manuscript.)X 3920(We)X 864 3875(thank)N 1084(Ric)X 1237(Anderson,)X 1611(Cliff)X 1804(Hathaway,)X 2192(and)X 2351(Shu-Ing)X 2652(Tsuei)X 2873(for)X 3010(their)X 3200(help)X 3381(and)X 3540(comments)X 3912(that)X 864 3995(improved)N 1193(the)X 1312(implementation)X 1835(of)X 1923(agrep.)X 2163(We)X 2296(also)X 2446(thank)X 2645(William)X 2928(I.)X 2996(Chang)X 3226(for)X 3341(kindly)X 3566(providing)X 3898(pro-)X 864 4115(grams)N 1080(for)X 1194(some)X 1383(of)X 1470(the)X 1588(experiments.)X 6 f 14 s 864 4355(References)N 1 f 10 s 864 4628([BG89])N 1064 4748(Baeza-Yates)N 1492(R.)X 1586(A.,)X 1705(and)X 1842(G.)X 1941(H.)X 2040(Gonnet,)X 2317(``A)X 2450(new)X 2605(approach)X 2921(to)X 3004(text)X 3145(searching,'')X 2 f 3548(Proceedings)X 3970(of)X 1064 4868(the)N 1192(12th)X 1364(Annual)X 1624(ACM-SIGIR)X 2050(conference)X 2432(on)X 2541(Information)X 2952(Retrieval,)X 1 f 3295(Cambridge,)X 3700(MA)X 3858(\(June)X 1064 4988(1989\),)N 1291(pp.)X 1411(168)X 9 f (-)S 1 f 1575(175.)X 864 5141([BM77])N 1064 5261(Boyer)N 1284(R.)X 1381(S.,)X 1489(and)X 1629(J.)X 1704(S.)X 1793(Moore,)X 2052(``A)X 2189(fast)X 2330(string)X 2537(searching)X 2870(algorithm,'')X 2 f 3280(Communications)X 3847(of)X 3934(the)X 1064 5381(ACM,)N 3 f 1273(20)X 1 f 1373(\(October)X 1679(1977\),)X 1906(pp.)X 2026(762)X 9 f (-)S 1 f 2190(772.)X 864 5534([CL90])N 1064 5654(Chang)N 1294(W.)X 1411(I.,)X 1499(and)X 1636(E.)X 1726(L.)X 1816(Lawler,)X 2085(``Approximate)X 2584(string)X 2788(matching)X 3108(in)X 3192(sublinear)X 3508(expected)X 3816(time,'')X 16 p %%Page: 16 17 10 s 10 xH 0 xS 1 f 3 f 2408 696(16)N 1 f 1064 984(FOCS)N 1283(90,)X 1403(pp.)X 1523(116)X 9 f (-)S 1 f 1687(124.)X 864 1137([GG88])N 1064 1257(Galil)N 1250(Z.,)X 1365(and)X 1507(R.)X 1606(Giancarlo,)X 1969(``Data)X 2201(structures)X 2539(and)X 2682(algorithms)X 3051(for)X 3172(approximate)X 3600(string)X 3809(match-)X 1064 1377(ing,'')N 2 f 1260(Journal)X 1529(of)X 1611(Complexity,)X 3 f 2016(4)X 1 f 2076(\(1988\),)X 2330(pp.)X 2450(33)X 9 f (-)S 1 f 2574(72.)X 864 1530([GP90])N 1064 1650(Galil)N 1247(Z.,)X 1359(and)X 1498(K.)X 1599(Park,)X 1789(``An)X 1964(improved)X 2294(algorithm)X 2628(for)X 2745(approximate)X 3169(string)X 3374(matching,'')X 2 f 3769(SIAM)X 3976(J.)X 1064 1770(on)N 1164(Computing,)X 3 f 1559(19)X 1 f 1659(\(December)X 2037(1990\),)X 2264(pp.)X 2384(989)X 9 f (-)S 1 f 2548(999.)X 864 1923([GB91])N 1064 2043(Gonnet,)N 1360(G.)X 1478(H.)X 1596(and)X 1752(R.)X 1865(A.)X 1983(Baeza-Yates,)X 2 f 2450(Handbook)X 2824(of)X 2926(Algorithms)X 3321(and)X 3482(Data)X 3683(Structures,)X 1 f 1064 2163(Second)N 1320(Edition,)X 1595(Addison-Wesley,)X 2174(Reading,)X 2481(MA,)X 2650(1991.)X 864 2316([HD80])N 1064 2436(Hall,)N 1250(P.)X 1343(A.)X 1450(V.,)X 1577(and)X 1722(G.)X 1829(R.)X 1931(Dowling,)X 2260(``Approximate)X 2766(string)X 2977(matching,'')X 2 f 3378(Computing)X 3762(Surveys,)X 1 f 1064 2556(\(December)N 1442(1980\),)X 1669(pp.)X 1789(381)X 9 f (-)S 1 f 1953(402.)X 864 2709([HU79])N 1064 2829(Hopcroft,)N 1396(J.E.,)X 1558(and)X 1696(J.D.)X 1847(Ullman,)X 2 f 2129(Introduction)X 2551(to)X 2635(Automata)X 2968(Theory,)X 3237(Languages,)X 3631(and)X 3774(Compu-)X 1064 2949(tation)N 1 f 1250(,)X 1290(Addison-Wesley,)X 1869(Reading,)X 2176(Mass)X 2365(\(1979\).)X 864 3102([KMP77])N 1064 3222(Knuth)N 1287(D.)X 1388(E.,)X 1501(J.)X 1576(H.)X 1678(Morris,)X 1940(and)X 2080(V.)X 2182(R.)X 2279(Pratt,)X 2474(``Fast)X 2685(pattern)X 2932(matching)X 3254(in)X 3340(strings,'')X 2 f 3651(SIAM)X 3858(Jour-)X 1064 3342(nal)N 1186(on)X 1286(Computing,)X 3 f 1681(6)X 1 f 1741(\(June)X 1935(1977\),)X 2162(pp.)X 2282(323)X 9 f (-)S 1 f 2446(350.)X 864 3495([LV88])N 1064 3615(Landau)N 1326(G.)X 1425(M.,)X 1557(and)X 1694(U.)X 1793(Vishkin,)X 2087(``Fast)X 2295(string)X 2499(matching)X 2819(with)X 2983(k)X 3045 0.2692(differences,'')AX 2 f 3499(Journal)X 3770(of)X 3854(Com-)X 1064 3735(puter)N 1253(and)X 1393(System)X 1636(Sciences,)X 3 f 1953(37)X 1 f 2053(\(1988\),)X 2307(pp.)X 2427(63)X 9 f (-)S 1 f 2551(78.)X 864 3888([LV89])N 1064 4008(Landau)N 1338(G.)X 1449(M.,)X 1593(and)X 1742(U.)X 1853(Vishkin,)X 2159(``Fast)X 2379(parallel)X 2653(and)X 2802(serial)X 3009(approximate)X 3444(string)X 3660(matching,'')X 2 f 1064 4128(Journal)N 1333(of)X 1415(Algorithms,)X 3 f 1810(10)X 1 f 1910(\(1989\).)X 864 4281([Le66])N 1064 4401(Levenshtein,)N 1509(V.)X 1620(I.,)X 1720(``Binary)X 2025(codes)X 2241(capable)X 2520(of)X 2621(correcting)X 2981(deletions,)X 3324(insertions,)X 3689(and)X 3839(rever-)X 1064 4521(sals,'')N 2 f 1278(Sov.)X 1434(Phys.)X 1630(Dokl.,)X 1 f 1846(\(February)X 2183(1966\),)X 2410(pp.)X 2530(707)X 9 f (-)S 1 f 2694(710.)X 864 4674([My86])N 1064 4794(Myers,)N 1309(E.)X 1398(W.,)X 1534(``An)X 1706(O\(ND\))X 1954(difference)X 2301(algorithm)X 2632(and)X 2768(its)X 2863(variations,'')X 2 f 3274(Algorithmica,)X 3 f 3737(1)X 1 f 3798(\(1986\),)X 1064 4914(pp.)N 1184(251)X 9 f (-)S 1 f 1348(266.)X 864 5067([MM89])N 1064 5187(Myers,)N 1321(E.)X 1422(W.,)X 1570(and)X 1719(W.)X 1848(Miller,)X 2101(``Approximate)X 2611(matching)X 2942(of)X 3042(regular)X 3303(expressions,'')X 2 f 3784(Bull.)X 3970(of)X 1064 5307(Mathematical)N 1529(Biology)X 1 f 1778(,)X 3 f 1818(51)X 1 f 1918(\(1989\),)X 2172(pp.)X 2292(5)X 9 f (-)S 1 f 2376(37.)X 864 5460([TU90])N 1064 5580(Tarhio)N 1322(J.,)X 1437(and)X 1597(E.)X 1710(Ukkonen,)X 2068(``Approximate)X 2589(Boyer-Moore)X 3071(string)X 3298(matching,'')X 3715(Technical)X 1064 5700(Report)N 1302(#A-1990-3,)X 1694(Dept.)X 1890(of)X 1977(Computer)X 2317(Science,)X 2607(University)X 2965(of)X 3052(Helsinki)X 3343(\(March)X 3600(1990\))X 17 p %%Page: 17 18 10 s 10 xH 0 xS 1 f 3 f 2408 696(17)N 1 f 864 984([Uk85a])N 1064 1104(Ukkonen)N 1387(E.,)X 1505(``Finding)X 1836(approximate)X 2266(patterns)X 2549(in)X 2640(strings,'')X 2 f 2956(Journal)X 3234(of)X 3325(Algorithms,)X 3 f 3729(6)X 1 f 3798(\(1985\),)X 1064 1224(pp.)N 1184(132)X 9 f (-)S 1 f 1348(137.)X 864 1377([Uk85b])N 1064 1497(Ukkonen)N 1382(E.,)X 1495(``Algorithms)X 1938(for)X 2057(approximate)X 2483(string)X 2690(matching,'')X 2 f 3087(Information)X 3494(and)X 3639(Control,)X 3 f 3932(64)X 1 f (,)S 1064 1617(\(1985\),)N 1318(pp.)X 1438(100)X 9 f (-)S 1 f 1602(118.)X 18 p %%Trailer xt xs