Snabbt. i Strängmatchning problemet är ett mycket vanligt problem. Vi söker efter en sträng P = PtP2.. "Pro inuti en stor textfil T = tlt2...t., båda sekvenser av tecken från en ändlig teckenuppsättning Z. Karaktärerna kan vara engelska tecken i en textfil, DNA-baspar, rader med källkod, vinklar mellan kanter i polygoner, maskiner eller maskindelar i ett produktionsschema, musiktoner och tempo i en musikalisk poäng och så vidare. Vi vill hitta alla förekomster av P i T; nämligen, vi söker efter uppsättningen av startpositioner F = {i[1 ---i--n -m + 1 sådan att titi+ l"ti+ m -1 = P}" De två mest kända algoritmerna för detta problem är Boyer-Moore algoritm [3] och Knuth Morris Pratt algoritm [10]. Det finns många tillägg till detta problem; till exempel kan vi leta efter en uppsättning mönster, ett mönster med "vilda kort", eller ett reguljärt uttryck. Strängmatchningsverktyg ingår i alla rimliga textredigerare, ordbehandlare och många andra applikationer. I vissa fall är dock mönstret och/eller texten inte exakta. Till exempel, vi kanske inte kommer ihåg den exakta stavningen av ett namn vi söker, namnet kan felstavas i texten, texten kan motsvara en sekvens av tal med en viss egenskap och vi har inte ett exakt mönster, texten kan vara en sekvens av DNA-molekyler och vi letar efter ungefärliga mönster. Den ungefärliga strängmatchande prob -" lem är att hitta alla delsträngar i T som är nära P under något mått av närhet. Det vanligaste måttet på närhet kallas redigeringsavståndet (även Levenshteinmåttet [13] ). En sträng P sägs vara av avstånd k till en sträng Q om vi kan omvandla P till att vara lika med Q med en sekvens av k tillägg av enstaka tecken i (arbiträra platser i) P, raderingar av enstaka tecken i P, eller substitutioner av tecken. I vissa fall kanske vi vill definiera närhet annorlunda. Till exempel, en polis kan söka efter en registreringsskylt ABC123 med vetskap om att bokstäverna är korrekta, men det kan vara ett fel med siffrorna. I detta fall är en sträng av avstånd 1 till ABC123 om bara ett fel uppstår och det är inom siffrorna området. Kanske finns det alltid tre siffror i en registreringsskylt, i vilket fall endast substitutioner är tillåtna. Ibland vill man variera kostnaden för de olika redigeringsåtgärderna, säger raderingar kostnad 3, tillägg 2 och substitutioner 1. Många olika ungefärliga strängmatchande algoritmer har föreslagits ([4, 5, 6, 8, 11, 12, 16, 19, 20] är en partiell lista). I den här artikeln presenterar vi en ny algoritm som är mycket snabb i praktiken, någorlunda enkel att genomföra, och stöder ett stort antal variationer av den ungefärliga strängmatchning problem. Algoritmen är baserad på ett numeriskt schema för exakt strängmatchning utvecklat av KOMMUNIKATIONER AV ACM/oktober 1992/Vol.35, nr 10 83 Baeza-Yates och Gonnet [2]. Algoritmen kan hantera de flesta av de vanligaste typerna av frågor, inklusive godtyckliga reguljära uttryck, och flera variationer av närhet åtgärder. I våra experiment var algoritmen minst dubbelt så snabb som andra algoritmer vi testade (som inte är lika flexibla), och i många fall en storleksordning snabbare. Till exempel, att hitta alla förekomster av Homogenos som tillåter två fel i en 1MB bibliografisk text tar ca 0.4 sek på en SUN SparcStation II. Vi använde faktiskt detta exempel och hittade en felstavning i vår text. Algoritmerna i denna artikel tjänade som grund för ett programvarupaket för Unix kallat agrep, som har använts sedan juni 1991. Agrep, som på dagen för detta skrivande är på version 2.04, finns tillgänglig av anonym ftp från cs.arizona.edu. Vi beskriver agrep kort i slutet av den här artikeln. För mer information se [15, 23, 24]. Vi börjar med att beskriva algoritmen för den rena strängmatchning problem (dvs, mönstret är en enkel sträng). Vi presenterar sedan många variationer och förlängningar av den grundläggande algoritmen, kulminerar med att matcha godtyckliga reguljära uttryck med fel. Experimentella resultat ges, liksom detaljer om agrep. Vi beskriver först fallet med exakt strängmatchning. Algoritmen för detta fall är i huvudsak identisk med den för [2]. Vi presenterar det här för fullständighet och eftersom vi använder en något annorlunda notation. Vi visar sedan hur man utökar algoritmen till att söka med fel. Vi beskriver sedan hur man påskyndar sökningen med fel genom att använda en filtreringssökningsteknik. Låt R vara en bit array av storlek m (storleken på mönstret). Vi betecknar med Rj värdet av array R efter j tecken på texten har varit pro- Tabell lb. Denna diskussion förutsätter naturligtvis att mönstrets storlek inte är mer än ordets storlek, vilket ofta är fallet. Om mönstrets storlek är dubbelt så stor som ordets storlek räcker det med fyra aritmetiska operationer. Om mönstret är mycket stort (t.ex., i vissa biologiska tillämpningar mönsterstorleken kan vara i tusentals), då andra metoder kommer att vara bättre. För de flesta problem med textsökning är små mönster normen. Vi diskuterar denna fråga senare, men för tillfället kommer vi att anta att mönstrets storlek inte är mer än ordets storlek. Denna algoritm är helt klart mycket lätt att genomföra. Dess körtid är helt förutsägbar eftersom den i huvudsak beror på textens storlek (förutsatt att mönstret passar in i ett ord) och inte på själva texten eller alfabetet. Vi visar nu hur man anpassar den tidigare algoritmen för att tillåta fel. (Baeza-Yates och Gonnet [2] visade hur man hanterar endast missmatchningar genom att i huvudsak räkna k av dem med en log2k storleksräknare, men de hanterade inte tillägg eller raderingar.) Vi börjar med ett mycket enkelt fall: endast en insättning är tillåten i mönstret i vilken position som helst. Med andra ord, vi vill hitta alla intervall av storlek som mest m + 1 i texten som innehåller mönstret som en subsekvens. Vi definierar R och S matriser som tidigare, men nu har vi två möjligheter för varje prefix match. Vi kan ha en exakt matchning eller en träff med en insättning. Därför introducerar vi det finns en match med högst en insättning (ibland kommer båda lika 1 på samma gång). Övergången för R-matrisen är densamma som tidigare. Vi behöver bara specificera övergången för R 1. Det finns två fall för en match med högst en insättning av de första i tecken av P upp till tj+l: I 1. Det finns en exakt matchning av de första i tecken upp till tj. I detta fall, infoga tj+ 1 i slutet av den exakta matchen skapar en match med en insättning. I2. Datum för uppförande på FN-förteckningen: 19.7.2011. Det finns en matchning mellan de första i -1 tecken upp till tj med en insättning och tj+ 1 = Pi. I detta fall är införandet någonstans inuti mönstret och inte i slutet. Fall I1 kan hanteras genom att bara kopiera värdet av R till R 1 och fall I2 kan hanteras med en rätt skiftning av R 1 och en AND operation med Si sådan att si= §+l. Så, för att beräkna R] behöver vi ytterligare ett skift (förskjutningen av R är redan klar), en OCH operation och en ELLER operation. Ett exempel (med samma mönster och text som exemplet för exakt matchning) ges i tabell 2. Överväg nu att tillåta en radering från mönstret (och inga tillägg). Vi kommer att definiera R, R 1 (som nu indikerar en radering), och S som tidigare. Det finns återigen två fall för en match med högst en radering av de första i tecken P upp tO /j+l: D1. Det finns en exakt matchning mellan de första i-1-tecken upp till tj+l (vilket visas av det nya värdet på R-matrisen Rj+l [i-1]). Detta fall motsvarar att ta bort pi och matcha de första i -1 tecken. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Det finns en matchning mellan de första i-1 tecken upp till tj med en radering och tj+ x = pi. I detta fall är raderingen någonstans inuti mönstret och inte i slutet. Ärende D2 hanteras som tidigare (det är exakt samma) och ärende D1 hanteras genom en rätt förändring av det nya värdet av Rj+ 1. Slutligen kommer vi att överväga en ersättning. Det vill säga, vi tillåter att ersätta ett tecken av P med ett tecken av T. (Vi kan uppnå substitution med en radering och ett införande, men i många fall vill vi att substitution ska räknas som bara ett fel.) Vi har återigen två fall: S1. Det finns en exakt matchning av de första i -1 tecken upp till tj. Detta fall motsvarar ersättande tj+ l med pi (oavsett om de är tabell I 1"ubbel 2. Ett exempel på ungefärlig matchning med en insättning lika - jämlikheten kommer att anges i R) och matcha de första i-1 tecken. Två dollar. Det finns en matchning mellan de första i -1 tecknen upp till tj med en substitution och tj+ 1 = Pi. I detta fall är substitutionen någonstans inuti mönstret och inte i slutet. Två dollar är samma sak igen. Ärende S1 motsvarar en granskning av Rj [i -1] i motsats till en granskning av Rj+l [i -1] i fall D 1. Det är fortfarande mycket få operationer som även omfattar en ersättning. Vi är nu redo att överväga det allmänna fallet av upp till k fel, där ett fel kan vara antingen en insättning, en radering, eller en ersättning (Levenshtein eller redigerad distans åtgärd). Sammantaget, istället för en ytterligare R 1 matris, kommer vi att upprätthålla k ytterligare matriser R 1, R 2, efter uttryck för Rd+l : R~ = 11..100...000 d en. Sammantaget har vi totalt två skift, en OCH, och tre ORS för varje R d. Tid och utrymme analys av algoritmen är som följer. där m inte är för stor, vilka är de fall algoritmen utformades för, är körtiden ef- En viktig egenskap hos denna algoritm är att den relativt enkelt kan utökas till flera mer komplicerade mönster. Flera sådana förlängningar kommer att beskrivas. Till exempel, om r = 1, då kommer vi att behöva kontrollera när som helst det finns en teckenmatch, vilket förmodligen är alltför ofta. Å andra sidan, om r = 3, m = 12 (vilket innebär k = 3), alfabetets storlek är 26, och texten är jämnt slumpmässig (dvs. varje tecken visas med samma sannolikhet), det förväntade antalet träffar av någon av PJ: s är ungefär 0,02% av tiden. I detta fall är det naturligtvis fördelaktigt att söka efter exakta matchningar och använda det ungefärliga systemet endast för de sällsynta tillfällen då en matchning inträffar. Löptiden i detta fall är i huvudsak densamma som körtiden för en sökning utan fel. (Experiment som använder detta partitionsschema för olika alfabetsstorlekar ges senare.) Den största fördelen med detta system är att algoritmen för exakt matchning presenteras tidigare kan anpassas på ett elegant sätt för att stödja den. Vi illustrerar idén med ett exempel. Antag att mönstret är ABCDEFGHIJKL (m = 12) och k = 3. Vi delar upp mönstret i k + 1 = 4 block: ABC, DEF, GHI och JKL. Vi måste ta reda på om någon av dem finns med i texten. Vi skapar ett kombinerat mönster genom att korsa de fyra blocken: ADGJBEHKCFIL. Vi bygger sedan maskvektorn R som vanligt för detta interleaved mönster (se avsnittet om exakt matchning). Den enda skillnaden är att i stället för att växla med ett i varje steg, vi skiftar med fyra! Det finns en match om någon av de sista fyra bitarna är 1. (När vi skiftar måste vi fylla de fyra första positionerna med ls, eller ännu bättre, använda shift-OR.) Således kan matchen för alla block göras exakt på samma sätt som vanliga matcher och det tar i stort sett samma körtid. Ett viktigt inslag i vår algoritm är dess flexibilitet. Förutom att fråga om en enda sträng stöder algoritmen en rad tecken (t.ex. "0-9"), komplement (t.ex. allt utom tomt), godtyckliga uppsättningar tecken (t.ex. {a,e,i,o,u}), obegränsade "vilda kort" och kombinationer. Att söka efter flera strängar samtidigt är också möjligt, även om storleken på mönstret blir summan av storleken på de olika strängarna (och kan därför kräva mer än ett ord för att representera). Förutom de obegränsade wild-korten utvecklades alla dessa förlängningar av Baeza-Yates och Gonnet [2] för exakt matchning. Vi kan tillämpa dem alla för ungefärlig matchning på ett enkelt sätt. Detta är en stor styrka av algoritmen: de flesta förlängningar (åtminstone alla som vi provat) som arbetar för exakt matchning kan också användas för ungefärlig matchning. Tidigare algoritmer för ungefärlig matchning med komplement eller wildkort, till exempel, var ganska komplicerade (se t.ex. [1, 18] ). Körtiden för alla dessa tillägg är samma som körtiden för den grundläggande algoritmen som gavs tidigare. Utöver dessa tillägg stöder vi också två tillägg som är specifika för ungefärlig matchning. En handlar om mönster där vissa delar måste matcha exakt och andra delar kan innehålla fel. En annan utvidgning motsvarar vissa icke-uniforma kostnader, till exempel kan vi definiera kostnaden för tillägg som är dubbelt så stor som för strykningar. De mest komplicerade mönster vi kan hantera är godtyckliga reguljära uttryck. Förmågan att effektivt matcha reguljära uttryck som tillåter fel gjorde det möjligt för oss att förlänga gripfamiljen och genomföra den ungefärliga mönstrade verktyget agrep. Vi beskriver nu förlängningarna mer i detalj. Oktober 1992/Vo1.35, nr 10/KOMMUNIKATIONER AV ACM Att ersätta ett tecken med en uppsättning tillåtna tecken är mycket lätt att uppnå med denna algoritm (som visades i [2]). Antag att mönstret vi vill hitta är ABC följt av en siffra följt av XYZ, och att vi tillåter upp till k fel. Vi betecknar detta mönster av ABC[0-9]XYZ. Det enda vi behöver göra för att acceptera någon siffra i den fjärde positionen är att sätta 1 i den fjärde positionen i S-matriserna för alla siffror. Det vill säga, i förbehandlingsstadiet, när vi bestämmer för varje tecken positionerna som detta tecken matchar i mönstret, inkluderar vi alla tecken i uppsättningen i den positionen. Resten av algoritmen är identisk med den vanliga algoritmen. Ett komplement av ett tecken är ett specialfall av en uppsättning tecken och det kan naturligtvis hanteras på samma sätt. Ett enda wildkort är en symbol som matchar alla tecken. Som sådan är det ett specialfall av en uppsättning tecken och kan hanteras som vi diskuterade i föregående avsnitt. Ibland vill vi dock indikera att vi tillåter ett obegränsat antal tecken att visas i mitten av mönstret (eller ens göra det flera gånger i mitten av mönstret Vi försöker först att hitta mönstret utan fel. Om vi misslyckas, försöker vi med ett fel, sedan med tre fel, sedan med 7 fel, och så vidare, i huvudsak fördubbla antalet fel (och lägga till ett) vid varje försök. Om antalet fel visar sig vara k, då körtiden kommer att vara O (1-n + 2"n + 4-n+'-'+ 2b.n), där 20 är den första kraften av 2 större än k. I värsta fall utför vi 4 gånger så många operationer som vi skulle ha haft vi känt k (i de flesta fall är faktorn faktiskt 2 eller 3). Ibland vill vi inte tillåta att delar av mönstret har fel. Till exempel kan vi leta efter registreringsskylt ABC123, och vi vet att bokstäverna är korrekta men siffrorna kan ha ett fel i dem. Vi betecknar detta mönster med <ABC>123. Vi kan ändra algoritmen för att skydda delar av mönstret från att ha några fel i dem. Låt oss anta att jag är uppsättningen index i mönstret där inget fel är tillåtet, och låt M vara en maskering array (av storlek m) som har en 0 i indexen för I och en 1 annars. Vi vill ändra (2.1) så att tillägg, raderingar och substitutioner endast kan ske utanför I. Detta görs genom att maskera dessa fall med M. Uttrycket i Om vi har flera mönster och vi vill hitta alla förekomster av någon av dem, då kan vi antingen söka dem en i taget eller tillsammans. Fördelen med att söka efter dem alla tillsammans är att det kan göras i en scan (och i ett kommando). Anta att vi letar efter P1, Pz,.... Pr. Vi konkateterar alla mönster och sätter dem i en uppsättning (med så många ord som behövs), och tillämpa algoritmen på den matrisen med följande ändringar. Låt M vara lite array storleken på den kombinerade mönstret, och låt bit i Antag att mönstret upptar flera ord och det är en enkel sträng. Algoritmen fortsätter på samma sätt genom att beräkna R en matris för alla ord. Men om inte antalet fel är stort, kommer den första delen av mönstret inte att matchas ganska ofta. Om det inte finns någon matchning med k-fel som börjar efter läge r i mönstret, så finns det inget behov av att behålla R-matriserna som motsvarar positioner som är större än r (deras värden kommer att vara 0). Därför kommer det för det mesta inte att finnas något behov av att upprätthålla R en matriser för den högra sidan av mönstret. Vi behöver bara varnas när den sista delen av den sista R en uppsättning som vi underhåller får värdet av 1. I så fall börjar vi underhålla Ra-matriserna för nästa del av mönstret. Denna förbättring fungerar inte för uppsättningar av mönster eller reguljära uttryck. Algoritmen kan utökas för att tillåta alla reguljära uttryck som ett mönster. Vi beskriver metoden här endast kortfattat; för mer information se [23]. Andra algoritmer för ungefärlig matchning till reguljära uttryck finns i [17, 22, 25]. Först illustrerar vi algoritmen med ett enkelt exempel. Vi försöker inte optimera algoritmen här; vi försöker göra det så enkelt som möjligt att beskriva. Låt mönstret vara P = ab(cdle)* fg (dvs. börjar med ab och slutar med fg med något antal antingen cd eller e mellan). Detta reguljära uttryck översätts till den icke-deterministiska finita automaten som visas i figur 1 (för mer om sådana översättningar, se [9] ). Vi tilldelar nu lite array för att representera automaten. Vi numrerar staterna inklusive null-staterna som inte motsvarar någon karaktär. Den här "linjäriserar" automaten. Varje tillstånd motsvarar en post i arrayen. För P har vi alltså ett utbud av storlek I 1. Lägg märke till att alla icke-e rörelser går till nästa tillstånd och därmed kan hanteras genom i huvudsak ett skift och en AND operation. Vi måste hitta ett sätt att hantera godtyckliga hopp som krävs av e flyttar (t.ex. från stat 2 till stat 8) och med "nonjumps" som råkar vara i på varandra följande tillstånd (t.ex., från stat 5 till stat 6). Nonjumps kan hanteras enkelt med en mask. De godtyckliga hoppen är svårare att hantera. Innebörden av en övergång från State i till Statej är att om vi vid något tillfälle matchar upp till State I så håller samma match även upp till Statej. Med andra ord, om det finns en 1 motsvarande staten i i arrayen, då e flytta från i toj innebär att det bör finnas en 1 motsvarande staten j. Den viktigaste observationen är att en given bit array och uppsättning av e flyttar helt bestämma värdet på bit array efter att e flyttar tas. Således, uppsättningen av e flyttar definierar en funktion som kartor lite array till en annan. Vi måste kunna genomföra denna funktion på ett effektivt sätt. Låt f betecknar den funktion som kartlägger en bit array till en annan genom att tillämpa alla e flyttar. Vi delar upp biten i byte (dvs. grupper om 8 bitar vardera). Tänk på de första 8 bitarna av bit array. Värdena på dessa bitar bestämmer vilka l's som ska ställas in när vi använder e flyttar på tillstånd 1 till 8. Eftersom det bara finns 256 (=28 ) möjliga värden för 8 bitar, kan vi förbehandla alla möjligheter och konstruera en tabell av storlek 256 som kommer att hålla, för varje möjlig byte, hela bit array med ls endast på platser som motsvarar e flyttar. (Vi behöver hela arrayen och inte bara de första 8 bitarna, eftersom det kan finnas framåt hopp.) Vi kan göra det för varje byte. Med tanke på nu ett aktuellt värde på R, tillämpar vi först den vanliga algoritmen, tar hand om regelbundna icke-e-rörelser, sedan delar vi upp matrisen i byte, hittar motsvarande matriser i tabellerna (vi har en tabell per byte), och ELLER alla av dem till R. Detta implementerar alla hopp, och om mönstret upptar inte mer än 32 bitar (som ofta är fallet), krävs bara fyra fler steg. (Om texten är stor, är det värt att förbehandla 16 bitar för en tabell i storlek 65536 och hälften så många steg; detta är valet som görs i agrep.) Körtiden för denna algoritm är där p är storleken på det reguljära uttrycket. Om det reguljära uttrycket inte är för stort och n är stort är den effektiva körtiden O(nk). Här presenterar vi några experimentella resultat med de algoritmer som diskuterats i de föregående avsnitten. Syftet med dessa experiment är att visa att våra algoritmer är mycket effektiva för små mönster. Vi använde bara mönster som är mindre än datorns ordstorlek, så jämförelserna med andra algoritmer är inte allmänna och kanske inte rättvisa. Alla tester gjordes på en SUN SparcStation II som körde Unix. Siffrorna som anges här bör tas med försiktighet. Alla sådana återanpassningar beror på arkitekturen, operativsystemet och de kompilatorer som används. Notera också att den nuvarande versionen av agrep använder några nyare algoritmer, så dess nuvarande Vi testade partitionalgoritmen mot två andra algoritmer, en av Ukkonen [20] (som vi implementerade) och en av Galil och Park [6] (märkt MN2; programmet tillhandahölls för oss av W.I. Chang) som bygger på en annan teknik av Ukkonen [21]. Dessa två algoritmer är båda förbättringar av den grundläggande dynamiska programmeringsalgoritmen och deras förväntade körtid är O(nk). Vi använde slumpmässig text (av storlek 1 miljon) och mönster (av storlek 20), och två olika alfabetsstorlekar. I detta fall, eftersom vi använder idén att dela upp mönstret, storleken på alfabetet gör en stor skillnad. Ett stort alfabet leder till mycket få oavsiktliga exakta matchningar, alltså är körtiden i stort sett densamma som den för exakt matchning. Ett litet alfabet leder till många matchningar och algoritmens prestanda försämras. Fallet binärt alfabet tjänar som det värsta fallet för detta ändamål. Resultaten visas i tabell 3. Det andra testet gällde mer komplicerade mönster, inklusive några av de förlängningar som diskuterades i föregående avsnitt. (Allt inom <> parenteser måste matcha exakt; en "#" står för ett wildkort av godtycklig längd; en ";" fungerar som boolesk OCH operation, nämligen alla mönster måste visas inom samma rad; en "] är den reguljära uttryck union operation; och en "*" är Kleene stängning.) Resultaten ges i tabell 4 (filen var en bibliografisk text av storlek 1MB). En annan algoritm för ungefärlig matchning till godtyckliga reguljära uttryck är Myers och Miller [ 17]. (Nyligen har vi förbättrat vissa delar av denna algoritm [25].) Körtiderna för Myers och Miller algoritmer för de fall vi testade, som endast omfattar små reguljära uttryck och små fel, är mer än en storleksordning långsammare än vår algoritm; men detta är inte en rättvis jämförelse eftersom deras algoritm kan hantera mer allmänna kostnadsfunktioner och dess körtid är oberoende av antalet fel. Att ha sådana flexibla algoritmer motiverade oss att utveckla ett ungefärligt matchningsverktyg för Unix. Agrep har varit i stor användning sedan juni 1991, och det har gått igenom två större revideringar. Den innehåller flera nya algoritmer utöver de som beskrivs i denna artikel (t.ex. en ny multipatternalgoritm och en förbättrad ungefärlig strängmatchning för enkla strängar). Det används på liknande sätt till grep/egrep/ fgrep och det stöder de flesta av funktionerna i grep familjen (även om det inte är 100% kompatibel), men det stöder många ytterligare funktioner (mestadels men inte alla relaterade till ungefärlig matchning). Agrep är minst lika snabb och i många fall snabbare än alla andra greps som vi känner till. En anmärkningsvärd skillnad mellan agrep och föregående greps (förutom möjligheten att söka ungefär) är att agrep är rekordorienterad (snarare än linjeorienterad). En post (t.ex. ett stycke, ett brev) definieras av användaren (där standardvärdet är en rad). Agrep skriver ut alla poster som matchar frågan (se alternativet - d som beskrivs nedan). Agrep är gratis tillgänglig av anonym [24] ). -d 'delim' delim är en användardefinierad symbol (eller sträng) för postavgränsare (standarden är den nya raden). Detta gör det möjligt att söka i stycken (i vilket fall delim = '$$') eller brev (delim = '^From'). -k finner alla förekomster med som mest k fel (insättningar, raderingar eller substitutioner), där k är ett positivt heltal. -B hittar alla matcher med minsta antal fel (t.ex. om den bästa matchen har 2 fel, är det samma som att köra agrep med -2, men naturligtvis 2 är okänt). -Dc varje radering räknas som c fel; c måste vara ett icke-negativt heltal; standardvärdet för c är 1 -Ic varje insättning räknas som c fel; c måste vara ett icke-negativt heltal; standardvärdet för c är 1 -Sc varje substitution räknas som c fel; c måste vara ett icke-negativt heltal; standardvärdet för c är 1 agrep -1 -I2 -D2 555-1234 telefonlista hittar alla nummer som skiljer sig från 555-1234 i högst en siffra; ställa in kostnaden för tillägg och raderingar till 2 förhindrar dem i detta fall. agrep -B -d '$$' Shmidth adresslista hittar alla adresser (förutsatt att adresserna är åtskilda av en tom rad) som innehåller den bästa matchningen till Shmidth. agrep - d "Från ''breakdown;arpanet' e- post- fil utdata alla brev (mönstret '^From' separerar brev i en e- postfil) som innehåller uppdelning och arpanet (symbolen ; står för Booleska OCH). agrep - B - w otomaton/ usr/ dict/ ord finner de närmaste orden i ordboken till otomaton; - w alternativet tvingar matchen att vara mot hela ordet snarare än en del av det. (Den bästa matchen har två fel och det finns två av dem: automaton och tomat.) agrep -d "$$" -1 " <wordl > <word2>" finner alla punkter som innehåller ord 1 följt av ord 2 med högst ett fel i stället för det tomma mellan orden ( <> anger att inget fel tillåts inuti). I synnerhet, om wordl är det sista ordet i en rad och word2 är det första ordet i nästa rad, då utrymmet kommer att ersättas med en ny rad symbol och det kommer att matcha. Detta är således ett sätt att övervinna separationen genom en ny linje. Observera att -d "$$" (eller en annan delim som spänner över mer än en rad) är nödvändigt, eftersom annars agrep söker bara en rad i taget. agrep -5 'a#b#c#d#e#f#g#h#i#j' /usr/dict/words hittar alla ord som har minst 5 av de första 10 bokstäverna i alfabetet i ordning; #-tecknet signalerar obegränsat vilda kort, vilket betyder här att varje insättning är gratis (det finns faktiskt ett speciellt alternativ -p för det ändamålet). Försök; svaret börjar med akademin och slutar med sakrilegiösa, vilket måste betyda något. Att söka text i närvaro av fel görs ofta för hand – man försöker alla möjligheter. Detta är frustrerande, långsamt och utan någon garanti för framgång. Den nya algoritm som presenteras i denna artikel för att söka med fel kan lindra detta problem och göra sökning i allmänhet mer robust. Det gör också sökandet mer bekvämt genom att inte behöva stava allt exakt. Algoritmen är mycket snabb och allmän och den bör hitta många tillämpningar. Det finns ett viktigt område för att söka med fel som vi inte adresserade--söka en indexerad fil. Genom hela artikeln antog vi att filerna inte indexeras (förbehandlas) på något sätt, vilket en sekventiell genomsökning genom dem är nödvändig. Vi anser att problemet med att hitta bra indexeringssystem som tillåter ungefärlig sökning är det olösta problemet på detta område. Vi noterar dock att med hastigheten på nuvarande datorer, scanning stora filer (upp till tiotals MB) kan göras någorlunda snabbt. Man kan hävda att eftersom storleken på våra data ökar när vår processhastighet ökar, kommer det inte att hjälpa att vänta på snabbare datorer och indexering kommer alltid att vara nödvändigt. Detta gäller förvisso för vissa tillämpningar, men inte för alla. Vissa applikationer har en rimlig övre gräns på sin storlek och sekventiell sökning efter dessa program är (och kommer att förbli) realistiska. Tillstånd att utan avgift kopiera hela eller delar av detta material beviljas under förutsättning att kopiorna inte görs eller distribueras för direkt kommersiell fördel, ACM-upphovsrättsmeddelandet och titeln på publikationen och dess datum visas, och meddelande ges om att kopiering sker genom tillstånd från Föreningen för datormaskiner. För att kopiera på annat sätt, eller för att återpublicera, krävs en avgift och/eller ett särskilt tillstånd. ©ACM0002-0782/92/1000-083 $1.50 CARE planterar de mest underbara fröna på jorden. Utsäde av självförsörjning som hjälper stai'ving människor att bli friska, produktiva människor. Och vi gör det by efter by efter by. Hjälp oss att vända rop på hjälp till hoppets skratt.
I REF presenterar författarna en algoritm som stöder hämtning av sekvenser som matchar ett reguljärt uttryck, med eventuella fel.
Fast text searching: allowing errors
{'venue': 'CACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}