Suffiks array

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 6. november 2021; checks kræver 2 redigeringer .

Suffiksarrayet er en leksikografisk sorteret matrix af alle strengens suffikser . Denne datastruktur blev designet af Eugene Myers og Udy Manber som et mere økonomisk alternativ til suffikstræet med hensyn til hukommelseskrav. Det bruges ofte, hvor der er behov for hurtige substring-opslag, såsom i Burrows-Wheeler Transform (BWT), og som en datastruktur i et søgeindeks .

Eksempel

Overvej strengen "abracadabra" 11 tegn lang.

abrakadabra 1 2 3 4 5 6 7 8 9 10 11

Sorteret liste over dens suffikser:

-en abra abrakadabra acadabra adabra bh bracadabra cadabra dabra ra racadabra

Suffiksarrayet for denne streng er {11,8,1,4,6,9,2,5,7,10,3}, fordi "a"-suffikset starter med det 11. tegn, "abra"-suffikset starter med det 8. tegn. go, og så videre, op til det sidste suffiks "racadabra", som begynder med det tredje tegn i det oprindelige ord.

Nu, ved at bruge dette array, kan du nemt finde alle understrenge. Hvis du for eksempel skal finde understrengen "ab", er det nok at finde alle de suffikser, der starter med "ab". Ved at sortere alfabetisk ligger de ved siden af hinanden. Ved at bruge binær søgning finder vi 2. og 3. suffikser "abra" og "abracadabra", som matcher 2. og 3. element i suffiksarrayet (8 og 1). Det betyder, at den søgte understreng "ab" forekommer på det første og ottende tegn i det oprindelige ord.

Bygning

Et suffiksarray kan bygges med eller uden et suffikstræ ved at udfylde en streng til en cyklisk længde af en potens på to og anvende en specifik algoritme til den.

Gennem suffikstræet

Vi bygger et suffikstræ for strengen T$. Hvor T er tekst.
I dette suffikstræ kører vi en dybde-først-søgning med prioritet at vælge leksigrafisk minimale kanter.
Under søgningen vurderer vi, at $ (sentinel) er det leksikografisk mindste tegn.
Ankomst i arket når et eller andet leksikografisk mindste suffiks, der endnu ikke er overvejet i øjeblikket, hvis værdi i arket, med startindeks i, skal skrives til den aktuelle celle i suffiksarrayet.
Dette resulterer i et suffiksarray for hele teksten.

Konstruktionens kompleksitet er , linjen omfatter konstruktionen af et suffikstræ og en dybde-først-søgning. $O(|T|)$

Søg

En søgning i et suffiksarray kan udføres gennem en binær søgning. Hans dårligste vurdering . Men du kan speede op til . $O(n\log {m})$ $O(n+\log _{2}{m})$

Naiv binær søgning

Ideen med søgningen er, at hvis mønsteret forekommer i teksten, vil alle suffikser, der starter med i suffiksarrayet , være placeret ved siden af hinanden. $P$ $Pos$
Vi kører en binær søgning på suffiks-arrayet og finder det mindste indeks : starter ikke med og det største indeks : starter heller ikke med . $P$ $Pos$ $jeg$ $Pos(i-1)$ $P$ $jeg'$ $Pos(i'+1)$ $P$
Så kommer prøven i positioner op til . $Pos(i)$ $Pos(i')$
Hvis der er mange mønsterpræfikser, falder scoren til . $O(n\log {m})$

Simpel acceleration

$L$ , — grænser for søgeintervallet. I begyndelsen ,. $R$ $L=1$ $R=m$
Vi husker længden af præfikserne , , der falder sammen med præfikset . $Pos(L)$ $Pos(R)$ $P:l,r$
$mlr=min(l,r)$ .
Ved den næste sammenligning i position begynder vi at behandle tegn ikke fra den første position, men fra . $M={\frac {L+R}{2))$ $mlr(l,r)+1$
Normalt arbejdstid , men den værste arbejdstid er stadig . $O(n+\log {m})$ $O(n\log {m})$

Acceleration via LCP

Det største fælles præfiks ( eng. Largest Common Prefix ) - for to strenge , - længden af det største matchende præfiks. $S_{1}$ $S_{2}$ $LCP(S_{1},S_{2})$

I denne algoritme vil vi antage, at for to suffikser beregnes for . Funktionen beregnes på forbehandlingsstadiet, når et træ bygges. Følgende udsagn er også sandt : $LCP$ $O(1)$ $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$

Takket være denne funktion kan du optimere den binære søgning efter et suffiksarray.

Lemma : Hvis de første tegn i suffikset falder sammen på venstre og højre grænser ( henholdsvis indeksene for suffikset) , så vil det samme antal tegn matche for alle suffikser på segmentet . $L$ $R$ $k$ $[L,R]$

$L=1$ , , , . Følgende tilfælde er mulige $R=|T|$ $l=LCP(P,L)$ $r=LCP(P,R)$
1. $l=r$ .
  1. Sammenlign suffikset i med mønsteret i position . $M={\frac {L+R}{2))$ $l+1$
  2. Suffikset er leksikografisk større end eller lig , og der opstod en mismatch ved positionen i suffikset (hvis der er et leksikografisk match og , så betragter vi det som lig med ), så ændrer vi søgegrænserne: . $P$ $jeg$ $M$ $P$ $jeg$ $|P|+1$ $L=M,R=R,l=i-1$
  3. Ellers skal du ændre grænserne sådan: . $L=L,R=M,r=i-1$
2. $l>r$ . Vi tjekker . $LCP(L,M),M={\frac {L+R}{2))$
  1. $LCP(L,M)>l$ . I dette tilfælde, efter positionen i suffikset på position , følger der en række af de samme tegn som i , som ikke matcher mønsteret (hvis de gjorde det, ville der være flere). Så du skal ændre grænserne som følger: . $l$ $M$ $L$ $l$ $L=M,R=R,l=l$
  2. $LCP(L,M)<l$ , betyder det, at efter positionen i suffikset efterfølges positionen af en mismatch med nogle tegn i præfikset , og størstedelen af matchningen med mønsteret er indeholdt i segmentet - det betyder , at der absolut ikke vil være forekomster af mønsteret i segmentet. Du skal ændre grænserne som følger: . $LCP(L,M)$ $M$ $L$ $L$ $[M,R]$ $L=L,R=M,r=LCP(L,M)$
  3. $LCP(L,M)=l$ Det betyder, at på segmentet falder de første tegn i alle suffikser sammen , og det er umuligt umiddelbart at sige, hvilket undersegment man skal gå til. For at løse dette er det nødvendigt at sammenligne tegnene efter positionen i suffikset med mønsteret . Hvis det leksikografisk er mindre end eller lig med, og der er et misforhold ved den te position (hvis der er et leksikografisk match og, så betragter vi som lig ), så ændrer vi grænserne som følger:, ,; ellers ( leksikografisk større): , ,. $[L,M]$ $l$ $P$ $l$ $M$ $M$ $P$ $jeg$ $M$ $P$ $jeg$ $|P|+1$ $L=M$ $R=R$ $l=i-1$ $M$ $R=M$ $L=L$ $r=i-1$
3. $l<r$ . Vi tjekker og sammenligner med som i forrige trin, men skifter til og til . $LCP(R,M),M={\frac {L+R}{2))$ $r$ $L$ $R$ $l$ $r$
Algoritmen virker indtil og bliver lige . Det betyder, at der er et segment af tilfældigheder. Hvis invarianten ikke er opfyldt , er der ikke noget mønster som en understreng i teksten. $l$ $r$ $|P|$ $L<P<R$

En sådan superacceleration giver tid , da iterationer over suffiksarrayet udføres. $O(|P|+\log _{2}{|T|})$ $\log _{2}{|T|}$

Relaterede algoritmer

Kasai's algoritme til at konstruere en række af de største almindelige præfikser.

Se også

suffiks træ

Litteratur

Gasfield D. Strenge, træer og sekvenser i algoritmer: Informatik og beregningsbiologi / Pr. fra engelsk. I. V. Romanovsky. - 2. udg. - Sankt Petersborg. : Nevsky Dialect, 2003. - 654 s.
Smith B. Metoder og algoritmer til beregning på strenge = Computing Patterns in Strings. - M. : Williams, 2006. - 496 s. - ISBN 5-8459-1081-1 , 0-201-39839-7.

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