Boyer-Moore algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. juli 2018; checks kræver 28 redigeringer .

Boyer-Moore algoritme
Opkaldt efter	Robert S. Boyer [d] og J Strother Moore [d]
Forfatter	Robert S. Boyer [d] og J Strother Moore [d]
formål	Effektiv søgning efter en understreng i en streng
Datastruktur	Strenge
værste tid	$\Theta (n+m)$
Hukommelsesomkostninger	$\Theta (m+\|\Sigma \|)$ eller $\Theta (m)$
Mediefiler på Wikimedia Commons

Boyer-Moore-strengsøgningsalgoritmen er en generel algoritme designet til at søge efter en understreng i en streng . Designet af Robert Boyerog Jay Moorei 1977 [1] . Fordelen ved denne algoritme er, at på bekostning af en vis mængde foreløbige beregninger på skabelonen (men ikke på den streng, hvori søgningen foretages), sammenlignes skabelonen ikke med kildeteksten i alle positioner - nogle af kontrollerne springes over, da det åbenbart ikke giver resultat.

Et generelt estimat af den beregningsmæssige kompleksitet af den moderne version af Boyer-Moore-algoritmen er , hvis stopkaraktertabellen ikke bruges (se nedenfor), og hvis stopkaraktertabellen bruges, hvor er længden af den streng, der søges i. , er længden af søgemønsteret, er alfabetet , som sammenligningen er foretaget på [2] . $O(n+m)$ $O(n+m+|\Sigma |)$ $n$ $m$ $\Sigma$

Beskrivelse af algoritmen

Algoritmen er baseret på tre ideer.

1. Scan fra venstre mod højre, sammenlign fra højre mod venstre. Begyndelsen af teksten (linjen) og mønsteret kombineres, kontrollen starter fra det sidste tegn i mønsteret. Hvis tegnene matcher, sammenlignes mønsterets næstsidste karakter osv. Hvis alle tegnene i mønsteret matcher strengens overlappende tegn, så er understrengen fundet, og den næste forekomst af understrengen søges.

Hvis et eller andet tegn i mønsteret ikke matcher strengens tilsvarende karakter, flyttes mønsteret et par tegn til højre, og testen starter igen fra det sidste tegn.

Disse "få" nævnt i det foregående afsnit er beregnet af to heuristika.

2. Stop symbol heuristik. ( Bemærk: stopsymbol-heuristikken er til stede i de fleste beskrivelser af Boyer-Moore-algoritmen, inklusive Boyer og Moores originale artikel [1] , men er ikke nødvendig for at opnå køretidsestimatet [2] ; desuden kræver denne heuristik yderligere hukommelse til arbejde og ekstra tid under udarbejdelsen af skabelonen.) $O(n+m)$ $O(|\Sigma |)$ $O(|\Sigma |)$

Antag, at vi søger efter ordet "klokke". Det første bogstav matchede ikke - "k" (lad os kalde dette bogstav et stopsymbol ). Så kan du flytte skabelonen til højre til dens sidste bogstav "k".

Streng: * * * * * * til * * * * * * Skabelon: k o l o k o l Næste trin: k o l o k o l

Hvis der ikke er noget stoptegn i mønsteret, flyttes mønsteret forbi det stopkarakter.

Streng: * * * * * a l * * * * * * * * Skabelon: k o l o k o l Næste trin: k o l o k o l

I dette tilfælde er stoptegnet "a", og mønsteret forskydes, så det er lige bag det bogstav. I Boyer-Moore-algoritmen ser stop-karakterheuristikken slet ikke på det matchede suffiks (se nedenfor), så det første bogstav i mønsteret ("k") vil være under "l", og en kendt dummy check vil blive foretaget.

Hvis stopsymbolet "k" er bag et andet bogstav "k", virker stopsymbolets heuristik ikke.

Streng: * * * * til c o l * * * * * Skabelon: k o l o k o l Næste trin: k o l o k o l

I sådanne situationer kommer den tredje idé om Boyer-Moore-algoritmen til undsætning - den matchende suffiksheuristik.

3. Heuristik af det matchede suffiks. Uformelt, hvis suffikset S matches, mens mønsteret læses fra højre mod venstre, men tegnet b foran S i mønsteret (det vil sige mønsteret er PbS) ikke stemmer overens, så flytter den matchede suffiksheuristik mønsteret det mindste tal af steder til højre, så strengen S matcher med mønsteret, og tegnet forud for det givne match S i mønsteret ville være forskelligt fra b (hvis der overhovedet er et sådant tegn). For denne skabelon betragtes formelt et heltal array suffshift[0..m], hvor suffshift[i] er lig med minimumsantallet, således at (hvis og ) og for alle for hvilke og holder (se eksempler nedenfor for forklaring ). Så, hvis tegnene matchede under læsning af mønsteret fra højre mod venstre , men tegnet ikke matchede, så flyttes mønsteret suffshift[mk] tegn til højre. For eksempel: $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]$

Linje: * * * * * * p til en * * * * * Skabelon: s ka l k a l k a Næste trin: c a l c a l c a

I dette tilfælde matchede "ka"-suffikset, og mønsteret flyttes til højre til den nærmeste "ka", der ikke har et "l" foran sig.

String: * * to c o l * * * * * Skabelon: k o l o k o l Næste trin: k o l o k o l

I dette tilfælde matchede "nær"-suffikset, og skabelonen flyttes til højre til den nærmeste "nær", der ikke har et "l" foran sig. Hvis delstrengen "om" ikke længere er i mønsteret, men den starter med "tæl", skifter til "tæller" osv.

Advarsel : Et bogstavmismatch før den nærmeste forekomst af et matchende suffiks er en forudsætning. Hvis vi begrænser os til at skifte til den nærmeste forekomst af et matchet suffiks, så kan algoritmen arbejde uacceptabelt langsomt. Når du f.eks. søger efter et længdemønster i en streng, der indeholder tegnene "a" efterfulgt af en streng med længde , udfører en algoritme, der bruger skift uden at tage hensyn til uoverensstemmelser mellem tegn , operationer, selv når du bruger stoptegnheuristikken. På den anden side er det blevet bevist [2] , at køretiden for BM-algoritmen, under hensyntagen til uoverensstemmelsen mellem tegn (det vil sige ved at bruge suffshift-arrayet defineret ovenfor), er ens , selv uden brug af stopkarakterheuristiken ( givet i bogen af M. Kroshmore og W. Ritter [2] er beviset for dette faktum en modifikation af Coles bevis fra 1994 [3] , som kun betragtede tilfældet med ikke-periodiske mønstre). $cabababa\ldots ba$ $2n$ $aaa\ldots aababab\ldots ba$ $2n$ $baba\ldotsba$ $2n$ $O(n^{2})$ $O(n+m)$

Begge heuristika kræver forudberegninger - afhængigt af søgemønsteret udfyldes to tabeller. Tabellen med stopsymboler svarer i størrelse til alfabetet - (hvis for eksempel alfabetet består af 256 tegn, så er dets længde 256); suffiksetabel - til det ønskede mønster, det vil sige . $O(|\Sigma |)$ $O(m)$

Lad os beskrive begge tabeller mere detaljeret.

Stop symbol tabel

Stoptegntabellen viser den sidste position i mønsteret ( eksklusive det sidste bogstav ) af hvert tegn i alfabetet. For alle tegn, der ikke er inkluderet i , skriver vi 0, hvis tegnnummereringen starter fra 1 (eller −1, hvis nummereringen starter fra 0). For eksempel, hvis , vil tabellen med stoptegn StopTable se sådan ud (tabellen er givet for tilfælde af en streng nummereret fra nul; når du nummererer tegn fra en, skal du tilføje en til alle tal): $s$ $s$ $s=abcdadcd$

Symbol abcd [alle andre] Sidste position 4 1 6 5 -1

Bemærk, at for stoptegnet "d" vil den sidste position være 5, ikke 7 - det sidste bogstav tages ikke i betragtning. Dette er en kendt fejl, der fører til suboptimalitet. For BM-algoritmen er den ikke fatal (suffiksheuristikken redder situationen), men den er fatal for en forenklet version af BM -algoritmen - Horspool-algoritmen .

Hvis, når man sammenligner mønsteret med strengen fra højre mod venstre , opstod mismatchet ved position , og stoptegnet er , så skal mønsteret forskydes med tegn. $s[0..m{-}1]$ $text[i..i{+}m{-}1]$ $j$ $c=tekst[j]$ $i'=j-StopTabel[c]$

Suffiksetabel

For hvert muligt suffiks af det givne mønster angiver vi den mindste mængde, hvormed mønsteret skal flyttes til højre, så det matcher igen, og samtidig ville tegnet forud for denne forekomst ikke matche tegnet forud for suffikset . Hvis en sådan forskydning ikke er mulig, skal du sætte (i begge nummersystemer). For vil for eksempel være: $t$ $s$ $t$ $t$ $t$ $|s|=m$ $s=aaccbccbcc$

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

For "klokke": $s=$

Suffiks [blank] l ol kol ... okol bell Skift 1 7 7 4 ... 4 4 Illustration Det var ? ?l ?ol ?kol ... ?ring på klokken blev en klokke klokke klokke klokke ... klokke klokke

Der er en algoritme til at beregne suffikstabellen suffshift[0..m] med køretid . [2] Denne algoritme er baseret på de samme ideer som algoritmerne til beregning af præfiksfunktionen og strengen Z-funktionen [4] [5] . Implementeringen af denne algoritme i C++ er som følger: $O(m)$

std :: vektor < int > suffshift ( m + 1 , m ); std :: vektor < int > z ( m , 0 ); for ( int j = 1 , maxZidx = 0 , maxZ = 0 ; j < m ; ++ j ) { if ( j <= maxZ ) z [ j ] = std :: min ( maxZ - j + 1 , z [ j - maxZidx ]); mens ( 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 ; _ } } for ( int j = m - 1 ; j > 0 ; j -- ) suffshift [ m - z [ j ]] = j ; //løkke #1 for ( int j = 1 , r = 0 ; j <= m - 1 ; j ++ ) //løkke #2 if ( j + z [ j ] == m ) for (; r <= j ; r ++ ) hvis ( suffshift [ r ] == m ) suffshift [ r ] = j ;

I den første løkke i koden gengives koden til beregning af den såkaldte Z-funktion , men for den inverterede streng . [5] Nemlig for enhver sådan at , elementet indeholder længden af det længste suffiks af strengen , som også er suffikset af hele strengen . Ved at bruge arrayet beregnes den ønskede array suffshift[0..m] (se beskrivelse nedenfor). Ved hver iteration af den sidste løkke falder den med 1, og ved hver iteration af løkken, der er indlejret i den, falder den med 1. Derfor, da , , og algoritmen til at beregne Z-funktionen virker for (se f.eks. , den tilsvarende artikel , samt artikel [5] ), den samlede køretid for denne algoritme er . $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)$

For at bevise rigtigheden af den præsenterede kode er det praktisk at forestille sig, at strengen er parset , hvilket er lig med den omvendte streng . Ved definitionen af suffshift har vi suffshift[ ] , hvor er det mindste positive tal, således at enten 1) strengen er et præfiks for strengen , eller 2) strengen er lig med og tegnene og er forskellige. I tilfælde 2) er per definition nødvendigvis opfyldt . Løfte #1 finder således alle suffshift-værdier opnået af regel 2 , når du løber fra til 1). For at beregne suffshift-værdierne opnået af regel 1), bemærker vi, for det første, hvis er et præfiks , så er det nødvendigvis opfyldt , og for det andet, hvis suffshift[ ] = for nogle , så er det nødvendigvis . Baseret på disse to observationer beregner loop #2 de resterende uinitialiserede suffshift-værdier (dvs. sådan, at 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 af algoritmen

Lad rækken af skift suffshift[0..m] for den givne skabelon tælles. Så er C++-implementeringen af Boyer-Moore-algoritmen til at finde den første forekomst i en tekst i tide uden brug af stop-tegnheuristik som følger [2] : $s[0..m{-}1]$ $s$ $text[0..n{-}1]$ $O(n+m)$

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

En sådan algoritme er ikke egnet til at finde alle forekomster af et mønster i en tekst i tide. Hvis vi fjerner betingelsen "j >= 0" fra den ydre sløjfe, vil algoritmen finde alle forekomster, men i værste fald kan den udføre operationer, som let kan ses ved at betragte en streng, der kun består af bogstaverne " en". For at søge efter alle forekomster bruges følgende modifikation, som virker tid på grund af den såkaldte Galil-regel [6] : $O(m+n)$ $O(mn)$ $O(n+m)$

int j , bundet = 0 ; //altid enten bundet = 0 eller bundet = m - suffshift[0] for ( int i = 0 ; i <= n - m ; i += suffshift [ j + 1 ]) { for ( j = m - 1 ; j >= bundet && s [ j ] == tekst [ i + j ]; j- ) ; if ( j < bundet ) { report_occurrence ( i ); bundet = m - suffshift [ 0 ]; j = -1 _ //sæt j som om vi læser hele mønsteret s, ikke kun op til bundet } else { bundet = 0 ; } }

Galils regel er baseret på følgende simple observation. Hvis en forekomst findes ved position , så vil den næste søgning forsøge at finde en forekomst af mønsteret ved position suffshift[0], og ved definitionen af suffshift er tegnene allerede kendt for at matche tegnene for suffshift[0] . Så når du udfører en højre-til-venstre-søgning for at afgøre, om der er en forekomst af mønsteret ved position , er det ingen mening i at kontrollere tegnene suffshift[0] . Det er hvad den "bundne" variabel er til. Det er bevist, at en sådan heuristik hjælper med at få tid til at søge efter alle forekomster af mønsteret i strengen [6] . $s$ $jeg$ $i'=i+$ $s[i'],s[i'{+}1],\ldots ,s[i{+}m{-}1]$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $jeg'$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $O(n+m)$

For at aktivere stopsymbol-heuristikken er det nok i += suffshift[j+1]at erstatte linjen " " med følgende udtryk i slutningen af hovedløkken:

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

Et eksempel på, hvordan algoritmen fungerer

Det ønskede mønster er " abbad". Stopsymboltabellen vil se sådan ud (i dette eksempel vil det være mere praktisk at bruge nummerering fra én)

Symbol abd [andre] Position 4 3 5 0

Suffikstabellen for alle mulige suffikser (undtagen tomme) giver et maksimalt skift på 5.

abeccaabadbabbad abbad

Vi pålægger en prøve på linjen. Der er ingen suffiksmatch - suffikstabellen giver et skift med én position. For det uoverensstemmende tegn i kildestrengen " с" (5. position) skrives 0 i stoptegntabellen. Skift mønsteret til højre efter 5-0=5positioner.

abeccaabadbabbad abbad

Symbolerne 3-5 matchede, men det andet gjorde det ikke. Heuristikken for " а" virker ikke ( 2-4=-2). Men da nogle af karaktererne matchede, kommer heuristikken i det matchede suffiks i spil, og flytter mønsteret med fem positioner på én gang!

abeccaabadbabbad abbad

Igen er der ikke noget matchende suffiks. I overensstemmelse med tabellen med stoptegn flytter vi prøven med en position og får den ønskede forekomst af prøven:

abeccaabadbabbad abbad

Bevis for rigtighed

For at bevise rigtigheden af algoritmen er det tilstrækkeligt at vise, at hvis en eller anden heuristik foreslår et skift med mere end én position til højre, vil mønsteret ikke blive fundet i de manglende positioner.

Så lad suffikset S matche , skabelonstrengen er lig med PbS , stoptegnet er a (herefter er små bogstaver symboler, store bogstaver er strenge).

Streng: * * * * * * * a [-- S --] * * * * Mønster: [--- P ---] b [-- S --]

Stop symbolheuristik. Fungerer, når der ikke er et tegn i strengen V. Hvis P=WaV , og der ikke er et tegn i strengen V , så foreslår stopkarakterens heuristik et skift med | V |+1 position.

Streng: * * * * * * * * * * * * en [-- S --] * * * * * * * * Mønster: [- W -] a [--- V ---] b [-- S --] Spring over: [- W -] a [--- V ---] b [-- S --] Nyt trin: [- W -] a [--- V ---] b [-- S --]

Faktisk, hvis strengen V ikke indeholder bogstavet a , er der intet at prøve for den manglende | v | stillinger.

Hvis der ikke er et tegn i mønsteret , så foreslår stoptegnheuristikken et skift med | P |+1 position - og det giver heller ingen mening at prøve den manglende | P |.

Streng: * * * * * * * * en [-- S --] * * * * * * * * Mønster: [--- P ---] b [-- S --] Spring over: [--- P ---] b [-- S --] Nyt trin: [--- P ---] b [-- S --]

Matchende suffiks heuristik. Selve den uformelle sætning - "den mindste mængde, som mønsteret skal flyttes til højre for at matche S igen, men tegnet før det givne match med S (hvis et sådant tegn eksisterer) ville være forskelligt fra b" - siger, at mindre skift er ubrugelige.

Indstillinger

Boyer-Moore-Horspool algoritme

Boyer-Moore-Horspool (ABMH)-algoritmen fungerer bedre end Boyer-Moore-algoritmen (ABM) på tilfældige tekster - det gennemsnitlige estimat er bedre for det.

ABMX bruger kun stopsymbolet heuristik; stoptegnet tages som tegnet af inputstrengen, der matcher det sidste tegn i mønsteret, uanset hvor uoverensstemmelsen opstod .

Da rigtige søgeprøver sjældent har en ensartet fordeling , kan ABMS give både en gevinst og et tab sammenlignet med ABM.

Zhu-Takaoka-algoritmen

På korte alfabeter (for eksempel, når man sammenligner DNA- segmenter, består alfabetet kun af fire tegn: A , T , G , C ) svigter stop-karakter-heuristikken allerede ved korte suffikser. Den enkleste måde at forbedre ydeevnen af ABM under sådanne forhold er at bygge en tabel for et par tegn i stedet for et stopkarakter: det, der ikke matchede, og det, der kommer før det [7] . En sådan algoritme blev kaldt Zhu-Takaoka-algoritmen.

Forbehandling tager tid. $O(m+|\Sigma |^{2})$

Turbo-Boyer-Moore algoritme

Turbo-Boyer-Moore-algoritmen er udviklet af en gruppe forskere ledet af M. Kroshmore , tilbyder en anden tilgang til korte alfabeter og løser samtidig det andet problem - kvadratisk kompleksitet i værste fald.

Ud over stopkarakterheuristikken og den matchede suffiksheuristik anvendes en tredje heuristik, turboshiftheuristikken [8] .

Lad suffikset UV matche første gang (og suffikset heuristik virkede, hvilket giver et fuldstændigt overlap af dette suffiks), anden gang - et kortere V (muligvis V = ∅).

! ! inputstreng: * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * * 1. Matchet UV: * [-U-] [V] * * * * [-U-] [V] 2. Så matchede V: * [-U-] [V] * * * * * * [-U-] [V] Suffiks heuristisk skift: * [-U-] [V] * * * * * * [-U-] [V] Turboshift: * [-U-] [V] * * * * * * [-U-] [V]

Figuren viser, at den mindst mulige forskydning er | U |. Ellers er de to tegn, der er angivet med udråbstegn, forskellige i inputstrengen, men ens i mønsteret. Dette er turboshift-heuristikken.

Algoritmen gør sit arbejde for sammenligninger med den første kamp i værste fald. $2n$

Sammenligning med andre algoritmer

Fordele

Boyer-Moore algoritmen er meget hurtig på "gode" data.[ afklar ] , og sandsynligheden for, at der opstår "dårlige" data er ekstremt lille. Derfor er det optimalt i de fleste tilfælde, når det ikke er muligt at forbehandle den tekst, hvori søgningen udføres [9] . Medmindre på korte tekster vil gevinsten ikke retfærdiggøre foreløbige beregninger.

Ulemper

Algoritmerne for Boyer-Moore-familien udvides ikke til en omtrentlig søgning, søgningen efter en hvilken som helst streng fra flere.

Sammenligningen er ikke en " sort boks " (kun hvis stop-karakter-heuristikken bruges), så når du implementerer den hurtigste søgning, skal du enten stole på, at optimeringsværktøjet fungerer med succes , eller manuelt optimere søgningen i assemblersprog.

Hvis teksten sjældent ændres, og søgningen udføres ofte (f.eks. af en søgemaskine ), kan du indeksere teksten. Indekssøgningsalgoritme er hurtigere[ klargør ] Boyer-Moore-algoritmen.

På store alfabeter (som Unicode ) kan stopkaraktertabellen optage meget hukommelse. I sådanne tilfælde undlades enten hashtabeller , eller alfabetet opdeles, f.eks. i betragtning af et 4-byte tegn som et par to-byte, eller (hvilket er det enkleste) de bruger en variant af Boyer'en -Moore-algoritme uden heuristik af stopkarakterer.

Der er en række modifikationer af Boyer-Moore-algoritmen, der sigter mod endnu større acceleration - for eksempel turboalgoritmen, den omvendte Colussi-algoritme [10] og andre.

Se også

Noter

↑ 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 og dens beregning . Hentet 14. marts 2017. Arkiveret fra originalen 26. april 2017. (ubestemt)
↑ 12 Galil , 1979 .
↑ Zhu-Takaoka algoritme Arkiveret 16. december 2008 på Wayback Machine
↑ Turbo-BM algoritme Arkiveret 16. december 2008 på Wayback Machine
↑ Præcis streng matchende algoritmer - Introduktion Arkiveret 16. december 2008 på Wayback Machine
↑ Omvendt Colussi-algoritme Arkiveret 9. marts 2016 på Wayback Machine

Litteratur

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / red. S. N. Triguba ; om. fra engelsk. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. udg. - M. : Williams, 2005. - 801 s. — ISBN 5-8459-0857-4 .
Crochemore M. , Rytter W. Jewels of Stringology. Singapore: World Publishing Scientific Co. Pte. Ltd., 2002. - 310 s. — ISBN 981-02-4782-6 .
Boyer RS , Moore JS En hurtig strengsøgningsalgoritme // Communications of the ACM . - 1977. - T. 20 , nr. 10 . - S. 762-772 . doi :/ 359842.359859 .
Cole R. Snævre grænser for kompleksiteten af Boyer-Moores strengmatchningsalgoritme // SIAM Journal on Computing . - 1994. - T. 23 , nr. 5 . - S. 1075-1091 . - doi : 10.1137/S0097539791195543 .
Galil Z. Om at forbedre worst case-løbetiden for Boyer-Moore-strengmatchningsalgoritmen // Communications of the ACM . - 1979. - T. 22 , nr. 9 . - S. 505-508 . - doi : 10.1145/359146.359148 .
Gasfield D. Strenge, træer og sekvenser i algoritmer: datalogi og beregningsbiologi = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology / overs. fra engelsk. I. V. Romanovsky . - Sankt Petersborg. : Nevsky Dialect, 2003. - 654 s. — ISBN 5-7940-0103-8 .

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng