Suffix array

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 november 2021; kontroller kräver 2 redigeringar .

Suffixmatrisen är en lexikografiskt sorterad matris av alla suffixen i strängen . Denna datastruktur designades av Eugene Myers och Udy Manber som ett mer ekonomiskt alternativ till suffixträdet när det gäller minneskrav. Det används ofta där snabba delsträngssökningar behövs, till exempel i Burrows-Wheeler Transform (BWT), och som en datastruktur i ett sökindex .

Exempel

Tänk på att strängen "abracadabra" är 11 tecken lång.

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

Sorterad lista över dess suffix:

a en bh abrakadabra acadabra adabra behå bracadabra cadabra dabra ra racadabra

Suffixmatrisen för denna sträng är {11,8,1,4,6,9,2,5,7,10,3}, eftersom suffixet "a" börjar med det 11:e tecknet, suffixet "abra" börjar med det 8:e tecknet. go, och så vidare, upp till det sista suffixet "racadabra", som börjar med det tredje tecknet i det ursprungliga ordet.

Nu, med hjälp av denna array, kan du enkelt hitta alla delsträngar. Om du till exempel behöver hitta delsträngen "ab" räcker det med att hitta alla suffix som börjar med "ab". Genom att sortera alfabetiskt ligger de bredvid varandra. Med hjälp av binär sökning hittar vi 2:a och 3:e suffixen "abra" och "abracadabra" som matchar det 2:a och 3:e elementet i suffixmatrisen (8 och 1). Det betyder att den sökta delsträngen "ab" förekommer på det första och åttonde tecknet i det ursprungliga ordet.

Byggnad

En suffixarray kan byggas med eller utan ett suffixträd genom att utfylla en sträng till en cyklisk längd av en potens av två och tillämpa en specifik algoritm på den.

Genom suffixträdet

Vi bygger ett suffixträd för strängen T$. Där T är text.
I detta suffixträd kör vi en djup-först-sökning med prioritet att välja lexigrafiskt minimala kanter.
Under sökningen anser vi att $ (sentinel) är det lexikografiskt minsta tecknet.
Ankomst i arket når något lexikografiskt minsta suffix som ännu inte har beaktats för tillfället, vars värde i arket, med startindex i, måste skrivas till den aktuella cellen i suffixarrayen.
Detta resulterar i en suffixarray för hela texten.

Konstruktionens komplexitet är , raden inkluderar konstruktionen av ett suffixträd och en djup-först-sökning. $O(|T|)$

Sök

En sökning i en suffixarray kan göras genom en binär sökning. Hans sämsta betyg . Men du kan snabba upp till . $O(n\log {m})$ $O(n+\log _{2}{m})$

Naiv binär sökning

Tanken med sökningen är att om mönstret förekommer i texten kommer alla suffix som börjar med i suffixarrayen att vara placerade bredvid varandra. $P$ $Pos$
Vi kör en binär sökning på suffixmatrisen och hittar det minsta indexet : börjar inte med och det största indexet : börjar inte med någondera . $P$ $Pos$ $i$ $Pos(i-1)$ $P$ $jag'$ $Pos(i'+1)$ $P$
Sedan kommer provet i positioner upp till . $Pos(i)$ $Pos(i')$
Om det finns många mönsterprefix sjunker poängen till . $O(n\log {m})$

Enkel acceleration

$L$ , — gränser för sökintervallet. I början ,. $R$ $L=1$ $R=m$
Vi kommer ihåg längden på prefixen , , sammanfallande med prefixet . $Pos(L)$ $Pos(R)$ $P:l,r$
$mlr=min(l,r)$ .
Vid nästa jämförelse i position börjar vi bearbeta tecken inte från den första positionen, utan från . $M={\frac {L+R}{2))$ $mlr(l,r)+1$
Vanligtvis arbetstid , men den värsta arbetstiden är fortfarande . $O(n+\log {m})$ $O(n\log {m})$

Acceleration via LCP

Det största vanliga prefixet ( eng. Largest Common Prefix ) - för två strängar , - längden på det största matchande prefixet. $S_{1}$ $S_{2}$ $LCP(S_{1},S_{2})$

I denna algoritm kommer vi att anta att för vilka två suffix som helst beräknas för . Funktionen beräknas i förbearbetningsstadiet när man bygger ett träd. Följande påstående är också sant : $LCP$ $O(1)$ $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$

Tack vare denna funktion kan du optimera den binära sökningen efter en suffixarray.

Lemma : Om de första tecknen i suffixet sammanfaller på den vänstra och högra gränsen ( , respektive indexen för suffixmatrisen) , så kommer samma antal tecken att matcha för alla suffix i segmentet . $L$ $R$ $k$ $[L,R]$

$L=1$ , , , . Följande fall är möjliga $R=|T|$ $l=LCP(P,L)$ $r=LCP(P,R)$
1. $l=r$ .
  1. Jämför suffixet i med mönstret på plats . $M={\frac {L+R}{2))$ $l+1$
  2. Suffixet är lexikografiskt större än eller lika och en missmatchning inträffade vid positionen i suffixet (om det finns en lexikografisk matchning och , då anser vi att det är lika med ), då ändrar vi sökgränserna: . $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M,R=R,l=i-1$
  3. Annars ändrar du gränserna så här: . $L=L,R=M,r=i-1$
2. $l>r$ . Vi kollar . $LCP(L,M),M={\frac {L+R}{2))$
  1. $LCP(L,M)>l$ . I det här fallet, efter positionen i suffixet på position , följer ett antal av samma tecken som i , som inte matchar mönstret (om de gjorde det skulle det finnas fler). Så du måste ändra gränserna enligt följande: . $l$ $M$ $L$ $l$ $L=M,R=R,l=l$
  2. $LCP(L,M)<l$ , betyder detta att efter positionen i suffixet följs positionen av en missmatchning med vissa tecken i prefixet , och majoriteten av matchningen med mönstret finns i segmentet - det betyder att det definitivt inte kommer att förekomma mönstret i segmentet. Du måste ändra gränserna enligt följande: . $LCP(L,M)$ $M$ $L$ $L$ $[M,R]$ $L=L,R=M,r=LCP(L,M)$
  3. $LCP(L,M)=l$ Detta betyder att på segmentet sammanfaller de första tecknen i alla suffix , och det är omöjligt att omedelbart avgöra vilket undersegment man ska gå till. För att lösa detta är det nödvändigt att jämföra tecknen efter positionen i suffixet med mönstret . Om det är lexikografiskt mindre än eller lika med och det finns en oöverensstämmelse vid den:e positionen (om det finns en lexikografisk match och, då betraktar vi lika ), så ändrar vi gränserna enligt följande:, ,; annars ( lexikografiskt större): , ,. $[L,M]$ $l$ $P$ $l$ $M$ $M$ $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M$ $R=R$ $l=i-1$ $M$ $R=M$ $L=L$ $r=i-1$
3. $l<r$ . Vi kontrollerar och jämför med som i föregående steg, men ändrar till och till . $LCP(R,M),M={\frac {L+R}{2))$ $r$ $L$ $R$ $l$ $r$
Algoritmen fungerar tills och blir lika . Det betyder att det finns ett segment av tillfälligheter. Om invarianten inte uppfylls finns det inget mönster som en delsträng i texten. $l$ $r$ $|P|$ $L<P<R$

Sådan superacceleration ger tid eftersom iterationer över suffixarrayen utförs. $O(|P|+\log _{2}{|T|})$ $\log _{2}{|T|}$

Relaterade algoritmer

Kasais algoritm för att konstruera en uppsättning av de största vanliga prefixen.

Se även

suffixträd

Länkar

Litteratur

Gasfield D. Strängar, träd och sekvenser i algoritmer: Informatik och beräkningsbiologi / Per. från engelska. I. V. Romanovsky. - 2:a uppl. - St Petersburg. : Nevsky Dialect, 2003. - 654 sid.
Smith B. Metoder och algoritmer för beräkning på strängar = Computing Patterns in Strings. - M. : Williams, 2006. - 496 sid. - ISBN 5-8459-1081-1 , 0-201-39839-7.

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