Boyer-Moore algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 juli 2018; kontroller kräver 28 redigeringar .

Boyer-Moore algoritm
Döpt efter	Robert S. Boyer [d] och J Strother Moore [d]
Författare	Robert S. Boyer [d] och J Strother Moore [d]
ändamål	Effektiv sökning efter en delsträng i en sträng
Datastruktur	Strängar
värsta tiden	$\Theta (n+m)$
Minneskostnad	$\Theta (m+\|\Sigma \|)$ eller $\Theta (m)$
Mediafiler på Wikimedia Commons

Boyer-Moore-strängsökningsalgoritmen är en allmän algoritm utformad för att söka efter en delsträng i en sträng . Designad av Robert Boyeroch Jay Moore1977 [ 1] . Fördelen med denna algoritm är att, till priset av en viss mängd preliminära beräkningar på mallen (men inte på strängen där sökningen görs), jämförs mallen inte med källtexten i alla positioner - vissa av kontrollerna hoppas över eftersom det uppenbarligen inte ger resultat.

En allmän uppskattning av beräkningskomplexiteten hos den moderna versionen av Boyer-Moore-algoritmen är , om stoppteckentabellen inte används (se nedan), och om stoppteckentabellen används, var är längden på strängen som genomsöks , är längden på sökmönstret, är alfabetet , på vilket jämförelsen görs [2] . $O(n+m)$ $O(n+m+|\Sigma |)$ $n$ $m$ $\Sigma$

Beskrivning av algoritmen

Algoritmen bygger på tre idéer.

1. Skanna från vänster till höger, jämför från höger till vänster. Början av texten (raden) och mönstret kombineras, kontrollen börjar från det sista tecknet i mönstret. Om tecknen matchar jämförs mönstrets näst sista tecken osv. Om alla tecken i mönstret matchar de överlappande tecknen i strängen, så har delsträngen hittats och nästa förekomst av delsträngen söks.

Om något tecken i mönstret inte matchar motsvarande tecken i strängen, flyttas mönstret några tecken åt höger, och testet börjar om från det sista tecknet.

Dessa "få" som nämns i föregående stycke beräknas med två heuristiker.

2. Stoppa symbolheuristik. ( Obs: stoppsymbolens heuristik finns i de flesta beskrivningar av Boyer-Moore-algoritmen, inklusive Boyer och Moores originalartikel [1] , men är inte nödvändig för att uppnå uppskattningen av körtid [2] ; dessutom kräver denna heuristik ytterligare minne till arbete och extra tid under förberedelsen av mallen.) $O(n+m)$ $O(|\Sigma |)$ $O(|\Sigma |)$

Anta att vi söker efter ordet "klocka". Den första bokstaven matchade inte - "k" (låt oss kalla den här bokstaven en stoppsymbol ). Sedan kan du flytta mallen till höger till dess sista bokstav "k".

Sträng: * * * * * * till * * * * * * Mall: k o l o k o l Nästa steg: k o l o k o l

Om det inte finns något stopptecken i mönstret förskjuts mönstret förbi det stopptecknet.

Sträng: * * * * * a l * * * * * * * * Mall: k o l o k o l Nästa steg: k o l o k o l

I det här fallet är stopptecknet "a", och mönstret flyttas så att det ligger precis bakom den bokstaven. I Boyer-Moore-algoritmen tittar inte stopp-teckenheuristiken på det matchade suffixet alls (se nedan), så den första bokstaven i mönstret ("k") kommer att vara under "l", och en känd dummy kontroll kommer att göras.

Om stoppsymbolen "k" är bakom en annan bokstav "k", fungerar inte stoppsymbolens heuristik.

Sträng: * * * * till c o l * * * * * Mall: k o l o k o l Nästa steg: k o l o k o l

I sådana situationer kommer den tredje idén med Boyer-Moore-algoritmen till undsättning - den matchande suffixheuristiken.

3. Heuristik för det matchade suffixet. Informellt, om suffixet S matchas när mönstret läses från höger till vänster, men tecknet b som föregår S i mönstret (det vill säga mönstret är PbS) inte matchar, då skiftar den matchade suffixheuristiken mönstret det minsta antalet av platser till höger så att strängen S matchar mönstret, och tecknet som föregår den givna matchningen S i mönstret skulle skilja sig från b (om det överhuvudtaget finns ett sådant tecken). Formellt, för denna mall, övervägs en heltalsarray suffshift[0..m], där suffshift[i] är lika med minimitalet så att (om och ) och för vilka som helst och håller (se exempel nedan för förklaring ). Om sedan, när du läser mönstret från höger till vänster , matchade tecknen , men tecknet inte matchade, så flyttas mönstret suffshift[mk]-tecken åt höger. Till exempel: $s[0..m{-}1]$ $j>0$ $s[i{-}j]\neq s[i{-}1]$ $i>0$ $ij\geq 0$ $s[i{-}j{+}k]=s[i{-}1{+}k]$ $k>0$ $0\leq i-j+k<m$ $0\leq i-1+k<m$ $s$ $k{-}1$ $s[m{-}1],s[m{-}2],\ldots ,s[m{-}k{+}1]$ $s[m{-}k]$

Rad: * * * * * * p till en * * * * * Mall: s ka l k a l k a Nästa steg: c a l c a l c a

I det här fallet matchade suffixet "ka" och mönstret flyttas åt höger till närmaste "ka" som inte har ett "l" framför sig.

Sträng: * * to c o l * * * * * Mall: k o l o k o l Nästa steg: k o l o k o l

I det här fallet matchade suffixet "nära" och mallen flyttas till höger till närmaste "nära" som inte har ett "l" framför sig. Om delsträngen "om" inte längre finns i mönstret, men den börjar med "räkna", skiftar till "räkna" osv.

Varning : En bokstavsfelmatchning före den närmaste förekomsten av ett matchande suffix är en förutsättning. Om vi begränsar oss till att flytta till närmaste förekomst av ett matchat suffix, kan algoritmen fungera oacceptabelt långsamt. Till exempel, när man söker efter ett längdmönster i en sträng som innehåller tecknen "a" följt av en sträng med längd , utför en algoritm som använder skift utan att ta hänsyn till teckenfelmatchningar operationer även när man använder heuristiken för stopptecken. Å andra sidan har det bevisats [2] att körtiden för BM-algoritmen, med hänsyn tagen till oöverensstämmelse mellan tecken (det vill säga att använda suffshift-arrayen definierad ovan), är lika även utan att använda stoppteckenheuristiken ( ges i boken av M. Kroshmore och W. Ritter [2] beviset för detta faktum är en modifiering av Coles bevis från 1994 [3] , som endast beaktade fallet med icke-periodiska mönster). $cabababa\ldots ba$ $2n$ $aaa\ldots aababab\ldots ba$ $2n$ $baba\ldotsba$ $2n$ $O(n^{2})$ $O(n+m)$

Båda heuristikerna kräver förberäkningar - beroende på sökmönster fylls två tabeller i. Tabellen med stoppsymboler motsvarar i storlek alfabetet - (om alfabetet till exempel består av 256 tecken, är dess längd 256); suffixtabell - till önskat mönster, det vill säga . $O(|\Sigma |)$ $O(m)$

Låt oss beskriva båda tabellerna mer i detalj.

Stoppsymboltabell

Stoppteckentabellen listar den sista positionen i mönstret ( exklusive den sista bokstaven ) för varje tecken i alfabetet. För alla tecken som inte ingår i , skriver vi 0 om teckennumreringen börjar från 1 (eller −1 om numreringen börjar från 0). Till exempel, om , tabellen med stopptecken StopTable kommer att se ut så här (tabellen ges för fallet med en sträng numrerad från noll; när du numrerar tecken från ett måste du lägga till ett till alla nummer): $s$ $s$ $s=abcdadcd$

Symbol abcd [alla andra] Sista position 4 1 6 5 -1

Observera att för "d" stopptecknet kommer den sista positionen att vara 5, inte 7 - den sista bokstaven tas inte med i beräkningen. Detta är ett känt fel som leder till suboptimalitet. För BM-algoritmen är den inte dödlig (suffixheuristiken räddar situationen), men den är ödesdiger för en förenklad version av BM -algoritmen - Horspool-algoritmen .

Om, när mönstret jämförs med strängen från höger till vänster , missmatchningen inträffade vid position , och stopptecknet är , måste mönstret förskjutas med tecken. $s[0..m{-}1]$ $text[i..i{+}m{-}1]$ $j$ $c=text[j]$ $i'=j-StopTable[c]$

Suffixtabell

För varje möjligt suffix av det givna mönstret anger vi den minsta mängd som mönstret behöver förskjutas åt höger så att det matchar igen och samtidigt skulle tecknet som föregår denna förekomst inte matcha tecknet som föregår suffixet . Om en sådan förskjutning inte är möjlig, sätt (i båda numreringssystemen). Till exempel kommer att vara: $t$ $s$ $t$ $t$ $t$ $|s|=m$ $s=aaccbccbcc$

Suffix [tomt] c cc bcc ... aaccbccbcc Offset 2 1 6 10 ... 10 Illustration Det var ? ?c ?cc ?bcc ... aaccbccbcc blev aaccbccbcc aaccbccbcc aaccbccbcc aaccbccbcc ... aaccbccbcc

För "klocka": $s=$

Suffix [blank] l ol kol ... okol bell Skift 1 7 7 4 ... 4 4 Illustration Det var ? ?l ?ol ?kol ... ?ring i klockan blev en klocka klocka klocka ... klockklocka

Det finns en algoritm för att beräkna suffixtabellen suffshift[0..m] med körtid . [2] Denna algoritm är baserad på samma idéer som algoritmerna för att beräkna prefixfunktionen och strängen Z-funktionen [4] [5] . Implementeringen av denna algoritm i C++ är som följer: $O(m)$

std :: vektor < int > suffshift ( m + 1 , m ); std :: vektor < int > z ( m , 0 ); för ( int j = 1 , maxZidx = 0 , maxZ = 0 ; j < m ; ++ j ) { if ( j <= maxZ ) z [ j ] = std :: min ( maxZ- j + 1 , z [ j - maxZidx ] ); medan ( j + z [ j ] < m && s [ m - 1 - z [ j ]] == s [ m - 1 - ( j + z [ j ])]) z [ j ] ++ ; if ( j + z [ j ] - 1 > maxZ ) { maxZidx = j ; maxZ = j + z [ j ] -1 ; _ } } för ( int j = m - 1 ; j > 0 ; j -- ) suffshift [ m - z [ j ]] = j ; //loop #1 för ( int j = 1 , r = 0 ; j <= m - 1 ; j ++ ) //loop #2 if ( j + z [ j ] == m ) för (; r <= j ; r ++ ) if ( suffshift [ r ] == m ) suffshift [ r ] = j ;

I den första slingan i koden återges koden för att beräkna den så kallade Z-funktionen , men för den inverterade strängen . [5] Nämligen, för alla sådana att , elementet innehåller längden på det längsta suffixet av strängen , vilket också är suffixet för hela strängen . Med hjälp av arrayen beräknas sedan önskad array suffshift[0..m] (se beskrivning nedan). Vid varje iteration av den sista slingan minskar den med 1, och vid varje iteration av slingan som är kapslad i den, minskar den med 1. Därför, eftersom , , och algoritmen för att beräkna Z-funktionen fungerar för (se t.ex. , motsvarande artikel , såväl som artikel [5] ), den totala körtiden för denna algoritm är . $z[1..m{-}1]$ $s[0..m-1]$ $j$ $0\leq j<m-1$ $z[m-1-j]$ $s[0..j]$ $s$ $z$ $j$ $k$ $j\geq 0$ $k\geq 0$ $O(m)$ $O(m)$

För att bevisa riktigheten av den presenterade koden är det bekvämt att föreställa sig att strängen är tolkad , vilket är lika med den omvända strängen . Enligt definitionen av suffshift har vi suffshift[ ] , där är det minsta positiva talet så att antingen 1) strängen är ett prefix för strängen , eller 2) strängen är lika med och tecknen och är olika. I fall 2), per definition , är nödvändigtvis uppfyllt . Således, genom att gå från till 1, hittar loop #1 alla suffshift-värden som erhålls av regel 2). För att beräkna suffshift-värdena som erhålls av regel 1), noterar vi att för det första, om är ett prefix , så är det nödvändigtvis uppfyllt , och för det andra, om suffshift[ ] = för vissa , så är det nödvändigtvis . Baserat på dessa två observationer, beräknar loop #2 de återstående oinitierade suffshift-värdena (dvs så att suffshift[k] = m). $s'[0..m{-}1]$ $s$ $mk$ ${\displaystyle=j}$ $j$ $s'[j..m{-}1]$ $s'[0..k{-}1]$ $s'[j..j{+}k{-}1]$ $s'[0..k{-}1]$ $s'[j{+}k]$ $s'[k]$ $z$ $z[j]=k$ $j$ $m-1$ $s'[j..m{-}1]$ $s'[0..k{-}1]$ $j+z[j]=m$ $r$ $j$ $r$ $r\leq j$

Implementering av algoritmen

Låt arrayen av skift suffshift[0..m] för den givna mallen räknas. Då är C++-implementeringen av Boyer-Moore-algoritmen för att hitta den första förekomsten i en text i tid utan att använda stoppteckenheuristik som följer [2] : $s[0..m{-}1]$ $s$ $text[0..n{-}1]$ $O(n+m)$

för ( int i = 0 , j = 0 ; i <= n - m && j >= 0 ; i += suffshift [ j + 1 ]) { för ( j = m - 1 ; j >= 0 && s [ j ] == text [ i + j ]; j- ) ; if ( j < 0 ) report_occurrence ( i ); }

En sådan algoritm är inte lämplig för att hitta alla förekomster av ett mönster i en text i tid. Om vi tar bort villkoret "j >= 0" från den yttre slingan, kommer algoritmen att hitta alla förekomster, men i värsta fall kan den utföra operationer, vilket enkelt kan ses genom att betrakta en sträng som endast består av bokstäverna " a". För att söka efter alla förekomster används följande modifiering, som fungerar tid på grund av den så kallade Galil-regeln [6] : $O(m+n)$ $O(mn)$ $O(n+m)$

int j , bunden = 0 ; //alltid antingen bunden = 0 eller bunden = m - suffshift[0] för ( int i = 0 ; i <= n - m ; i += suffshift [ j + 1 ]) { för ( j = m - 1 ; j >= bunden && s [ j ] == text [ i + j ]; j- ) ; if ( j < bundet ) { report_occurrence ( i ); bunden = m - suffshift [ 0 ]; j = -1 _ //set j som om vi läser hela mönstret s, inte bara upp till bunden } else { bunden = 0 ; } }

Galils regel bygger på följande enkla observation. Om en förekomst hittas vid position , då kommer nästa sökning att försöka hitta en förekomst av mönstret vid position suffshift[0] och, enligt definitionen av suffshift, är tecknen redan kända för att matcha de för suffshift[0] . Så när du gör en höger-till-vänster-sökning för att avgöra om mönstret förekommer vid position , är det ingen idé att kontrollera tecknen suffshift[0] . Det är vad den "bundna" variabeln är till för. Det har bevisats att en sådan heuristik hjälper till att få tid att söka efter alla förekomster av mönstret i strängen [6] . $s$ $i$ $i'=i+$ $s[i'],s[i'{+}1],\ldots ,s[i{+}m{-}1]$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $jag'$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $O(n+m)$

För att aktivera stoppsymbolens heuristik räcker i += suffshift[j+1]det att ersätta raden " " med följande uttryck i slutet av huvudslingan:

if ( j < bundet ) i += suffshift [ j + 1 ]; else i += max ( suffshift [ j + 1 ], j - StopTable [ text [ i + j ]]);

Ett exempel på hur algoritmen fungerar

Det önskade mönstret är " abbad". Stoppsymboltabellen kommer att se ut så här (i det här exemplet är det bekvämare att använda numrering från en)

Symbol abd [andra] Position 4 3 5 0

Suffixtabellen för alla möjliga suffix (utom tomma) ger en maximal förskjutning på 5.

abeccaabadbabbad abbad

Vi lägger ett prov på linjen. Det finns ingen suffixmatchning - suffixtabellen ger en förskjutning med en position. För det felaktiga tecknet i källsträngen " с" (5:e position), skrivs 0 i stoppteckentabellen. Flytta mönstret åt höger efter 5-0=5positioner.

abeccaabadbabbad abbad

Symbolerna 3-5 matchade, men den andra gjorde det inte. Heuristiken för " а" fungerar inte ( 2-4=-2). Men eftersom några av karaktärerna matchade, kommer heuristiken för det matchade suffixet in i bilden, vilket förskjuter mönstret med fem positioner på en gång!

abeccaabadbabbad abbad

Återigen, det finns inget matchande suffix. I enlighet med tabellen med stopptecken flyttar vi provet med en position och får önskad förekomst av provet:

abeccaabadbabbad abbad

Bevis på riktighet

För att bevisa riktigheten av algoritmen räcker det att visa att om en eller annan heuristik föreslår en förskjutning med mer än en position åt höger, kommer mönstret inte att hittas i de saknade positionerna.

Så låt suffixet S matcha , mallsträngen är lika med PbS , stopptecknet är a (hädanefter är små bokstäver symboler, stora bokstäver är strängar).

Sträng: * * * * * * * a [-- S --] * * * * Mönster: [--- P ---] b [-- S --]

Stoppa symbolheuristik. Fungerar när det inte finns något tecken i strängen V. Om P=WaV och det inte finns något tecken i strängen V , så föreslår stoppteckenheuristiken en förskjutning med | V |+1 position.

Sträng: * * * * * * * * * * * * en [-- S --] * * * * * * * * Mönster: [- W -] a [--- V ---] b [-- S --] Hoppa över: [- W -] a [--- V ---] b [-- S --] Nytt steg: [- W -] a [--- V ---] b [-- S --]

Faktum är att om strängen V inte innehåller bokstaven a , finns det inget att försöka för den saknade | v | positioner.

Om det inte finns något tecken i mönstret , föreslår stoppteckenheuristiken en förskjutning med | P |+1 position - och det är inte heller meningsfullt att prova den saknade | P |.

Sträng: * * * * * * * * en [-- S --] * * * * * * * * Mönster: [--- P ---] b [-- S --] Hoppa över: [--- P ---] b [-- S --] Nytt steg: [--- P ---] b [-- S --]

Matchat suffix heuristik. Den informella frasen i sig - "den minsta mängd som mönstret behöver flyttas åt höger för att matcha S igen, men tecknet före den givna matchningen med S (om en sådan karaktär finns) skulle skilja sig från b" - säger att mindre skift är värdelösa.

Alternativ

Boyer-Moore-Horspool algoritm

Boyer-Moore-Horspool (ABMH)-algoritmen fungerar bättre än Boyer-Moore-algoritmen (ABM) på slumpmässiga texter - den genomsnittliga uppskattningen är bättre för den.

ABMX använder bara stoppsymbolen heuristik; stopptecknet tas som tecknet i inmatningssträngen som matchar det sista tecknet i mönstret, oavsett var felmatchningen inträffade .

Eftersom riktiga sökprov sällan har en enhetlig fördelning kan ABMS ge både vinst och förlust jämfört med ABM.

Zhu-Takaoka-algoritmen

På korta alfabet (till exempel när man jämför DNA- segment, består alfabetet av endast fyra tecken: A , T , G , C ) misslyckas stopp-teckenheuristiken redan på korta suffix. Det enklaste sättet att förbättra prestandan för ABM under sådana förhållanden är att bygga en tabell för ett par tecken istället för ett stopptecken: det som inte matchade och det som kommer före det [7] . En sådan algoritm kallades Zhu-Takaoka-algoritmen.

Förbehandling tar tid. $O(m+|\Sigma |^{2})$

Turbo-Boyer-Moore algoritm

Turbo-Boyer-Moore-algoritmen utvecklades av en grupp forskare under ledning av M. Kroshmore , erbjuder ett annat förhållningssätt till korta alfabet och löser samtidigt det andra problemet - kvadratisk komplexitet i värsta fall.

Förutom stoppkaraktärsheuristiken och den matchade suffixheuristiken, tillämpas en tredje heuristik, turboshiftheuristiken [8] .

Låt suffixet UV matcha första gången (och suffixheuristiken fungerade, vilket ger en fullständig överlappning av detta suffix), andra gången - ett kortare V (möjligen V = ∅).

! ! inmatningssträng: * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * * 1. Matchad UV: * [-U-] [V] * * * * [-U-] [V] 2. Sedan matchade V: * [-U-] [V] * * * * * * [-U-] [V] Suffix heuristisk skiftning: * [-U-] [V] * * * * * * [-U-] [V] Turboshift: * [-U-] [V] * * * * * * [-U-] [V]

Figuren visar att minsta möjliga förskjutning är | U |. Annars är de två tecknen som anges med utropstecken olika i inmatningssträngen, men desamma i mönstret. Detta är turboshift-heuristiken.

Algoritmen gör sitt jobb för jämförelser med första matchen i värsta fall. $2n$

Jämförelse med andra algoritmer

Fördelar

Boyer-Moore-algoritmen är mycket snabb på "bra" data.[ förtydliga ] , och sannolikheten för uppkomsten av "dåliga" data är extremt liten. Därför är det optimalt i de flesta fall när det inte går att förbearbeta den text som sökningen görs i [9] . Såvida inte på korta texter kommer vinsten inte att motivera preliminära beräkningar.

Nackdelar

Algoritmerna för familjen Boyer-Moore expanderar inte till en ungefärlig sökning, sökningen efter valfri sträng från flera.

Jämförelsen är inte en " svart låda " (endast om stopp-teckenheuristiken används), så när du implementerar den snabbaste sökningen måste du antingen lita på att optimeraren fungerar framgångsrikt eller manuellt optimera sökningen i assemblerspråk.

Om texten ändras sällan och sökningen utförs ofta (till exempel av en sökmotor ), kan du indexera texten. Indexsökningsalgoritm är snabbare[ förtydliga ] Boyer-Moore-algoritmen.

På stora alfabet (som Unicode ) kan stoppteckentabellen ta upp mycket minne. I sådana fall utelämnas antingen hash-tabeller eller så delas alfabetet, med tanke på till exempel ett 4-byte-tecken som ett par två-byte, eller (vilket är det enklaste) de använder en variant av Boyer -Moore-algoritm utan heuristik av stopptecken.

Det finns ett antal modifieringar av Boyer-Moore-algoritmen som syftar till ännu större acceleration - till exempel turboalgoritmen, den omvända Colussi-algoritmen [10] och andra.

Se även

Anteckningar

↑ 12 Boyer , Moore, 1977 .
↑ 1 2 3 4 5 6 Crochemore, Rytter, 2002 .
↑ Cole, 1994 .
↑ Gasfield, 2003 .
↑ 1 2 3 MAXimal :: algo :: String Z-funktion och dess beräkning . Hämtad 14 mars 2017. Arkiverad från originalet 26 april 2017. (obestämd)
↑ 12 Galil , 1979 .
↑ Zhu-Takaoka-algoritmen Arkiverad 16 december 2008 på Wayback Machine
↑ Turbo-BM-algoritm Arkiverad 16 december 2008 på Wayback Machine
↑ Exakt strängmatchningsalgoritmer - Introduktion Arkiverad 16 december 2008 på Wayback Machine
↑ Omvänd Colussi-algoritm Arkiverad 9 mars 2016 på Wayback Machine

Litteratur

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / ed. S. N. Triguba ; per. från engelska. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2:a uppl. - M. : Williams, 2005. - 801 sid. — ISBN 5-8459-0857-4 .
Crochemore M. , Rytter W. Jewels of Stringology. Singapore: World Publishing Scientific Co. Pte. Ltd., 2002. - 310 sid. — ISBN 981-02-4782-6 .
Boyer RS , Moore JS En snabb strängsökningsalgoritm // ACM: s kommunikation . - 1977. - T. 20 , nr 10 . - S. 762-772 . doi :/ 359842.359859 .
Cole R. Snäva gränser för komplexiteten hos Boyer-Moores strängmatchningsalgoritm // SIAM Journal on Computing . - 1994. - T. 23 , nr 5 . - S. 1075-1091 . - doi : 10.1137/S0097539791195543 .
Galil Z. Om att förbättra den värsta körtiden för Boyer-Moore-strängmatchningsalgoritmen // Communications of the ACM . - 1979. - T. 22 , nr 9 . - S. 505-508 . - doi : 10.1145/359146.359148 .
Gasfield D. Strängar, träd och sekvenser i algoritmer: datavetenskap och beräkningsbiologi = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology / transl. från engelska. I. V. Romanovsky . - St Petersburg. : Nevsky Dialect, 2003. - 654 sid. — ISBN 5-7940-0103-8 .

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likheter
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen