Matrice de sufixe

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 noiembrie 2021; verificările necesită 2 modificări .

Matricea de sufixe este o matrice sortată lexicografic cu toate sufixele șirului . Această structură de date a fost concepută de Eugene Myers și Udy Manber ca o alternativă mai economică la arborele sufix în ceea ce privește cerințele de memorie. Este adesea folosit acolo unde sunt necesare căutări rapide de subșiruri, cum ar fi în Burrows-Wheeler Transform (BWT) și ca structură de date într-un index de căutare .

Exemplu

Luați în considerare șirul „abracadabra” de 11 caractere.

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

Lista sortată a sufixelor sale:

A un sutien abracadabra acadabra adabra sutien bracadabra cadabra dabra ra racadabra

Matricea de sufixe a acestui șir este {11,8,1,4,6,9,2,5,7,10,3}, deoarece sufixul „a” începe cu al 11-lea caracter, sufixul „abra” începe cu caracterul 8. merge, și așa mai departe, până la ultimul sufix „racadabra”, care începe cu al treilea caracter al cuvântului original.

Acum, folosind această matrice, puteți găsi cu ușurință toate subșirurile. De exemplu, dacă trebuie să găsiți subșirul „ab”, este suficient să găsiți toate sufixele care încep cu „ab”. Prin sortarea alfabetică, sunt unul lângă celălalt. Folosind căutarea binară , găsim al 2-lea și al 3-lea sufix „abra” și „abracadabra” care se potrivesc cu al 2-lea și al 3-lea element al matricei de sufixe (8 și 1). Aceasta înseamnă că subșirul căutat „ab” apare pe primul și al optulea caracter din cuvântul original.

Clădire

O matrice de sufixe poate fi construită cu sau fără un arbore de sufixe prin completarea unui șir la o lungime ciclică a unei puteri de doi și aplicând un algoritm specific.

Prin arborele sufixului

Construim un arbore sufix pentru șirul T$. Unde T este text.
În acest arbore de sufixe, rulăm o căutare în profunzime, cu prioritate de a alege marginile minime din punct de vedere lexigrafic.
În timpul căutării, considerăm că $ (santinela) este cel mai mic caracter lexicografic.
Sosirea în foaie atingând un sufix lexicografic cel mai mic încă neconsiderat în acest moment, a cărui valoare în foaie, începând cu indexul în, trebuie să fie scrisă în celula curentă a matricei de sufixe.
Rezultă o matrice de sufixe pentru întregul text.

Complexitatea construcției este , linia include construcția unui arbore de sufix și o căutare pe adâncime. $O(|T|)$

Caută

O căutare într-o matrice de sufixe se poate face printr-o căutare binară. Cel mai prost rating al lui . Dar poți accelera până la . $O(n\log {m})$ $O(n+\log _{2}{m})$

Căutare binară naivă

Ideea căutării este că, dacă modelul apare în text, atunci toate sufixele care încep cu în matricea de sufixe vor fi situate unul lângă celălalt. $P$ $Poz$
Efectuăm o căutare binară pe tabloul de sufixe și găsim cel mai mic index : nu începe cu și cel mai mare index : nu începe cu nici . $P$ $Poz$ $i$ $Pos(i-1)$ $P$ $eu$ $Pos(i'+1)$ $P$
Apoi eșantionul vine în poziții de până la . $Poz(i)$ $Pos(i')$
Dacă există multe prefixe de model, atunci scorul scade la . $O(n\log {m})$

Accelerație simplă

$L$ , — limitele intervalului de căutare. La început , . $R$ $L=1$ $R=m$
Ne amintim lungimea prefixelor , , care coincide cu prefixul . $Poz(L)$ $Poz(R)$ $P:l,r$
$mlr=min(l,r)$ .
La următoarea comparație în poziție, începem procesarea caracterelor nu din prima poziție, ci din . $M={\frac {L+R}{2)}$ $mlr(l,r)+1$
De obicei timp de lucru , dar cel mai prost timp de lucru este încă . $O(n+\log {m})$ $O(n\log {m})$

Accelerație prin LCP

Cel mai mare prefix comun ( ing. Cel mai mare prefix comun ) - pentru două șiruri , - lungimea celui mai mare prefix care se potrivește. $S_{1}$ $S_{2}$ $LCP(S_{1},S_{2})$

În acest algoritm, vom presupune că pentru oricare două sufixe se calculează pentru . Funcția este calculată în etapa de preprocesare la construirea unui arbore. Următoarea afirmație este, de asemenea, adevărată : $LCP$ $O(1)$ $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$

Datorită acestei funcții, puteți optimiza căutarea binară pentru o matrice de sufixe.

Lema : Dacă primele caractere ale sufixului coincid pe granițele din stânga și din dreapta ( , respectiv, indicii matricei de sufixe) , atunci același număr de caractere se va potrivi pentru toate sufixele de pe segment . $L$ $R$ $k$ $[L,R]$

$L=1$ , , , . Următoarele cazuri sunt posibile $R=|T|$ $l=LCP(P,L)$ $r=LCP(P,R)$
1. $l=r$ .
  1. Comparați sufixul în cu modelul în poziție . $M={\frac {L+R}{2)}$ $l+1$
  2. Sufixul este mai mare sau egal din punct de vedere lexicografic și a apărut o nepotrivire la poziția din sufix (dacă există o potrivire lexicografică și , atunci îl considerăm egal cu ), atunci modificăm limitele de căutare: . $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M,R=R,l=i-1$
  3. În caz contrar, modificați marginile astfel: . $L=L,R=M,r=i-1$
2. $l>r$ . Verificăm . $LCP(L,M),M={\frac {L+R}{2)}$
  1. $LCP(L,M)>l$ . În acest caz, după poziția din sufixul de pe poziție , urmează un număr de aceleași caractere ca în , care nu se potrivesc cu modelul (dacă ar fi, ar fi mai multe). Deci, trebuie să modificați limitele după cum urmează: . $l$ $M$ $L$ $l$ $L=M,R=R,l=l$
  2. $LCP(L,M)<l$ , aceasta înseamnă că după poziția din sufix, poziția este urmată de o nepotrivire cu unele caractere ale prefixului , iar cea mai mare parte a potrivirii cu modelul este conținută în segment - înseamnă că cu siguranță nu vor exista apariții de modelul din segment. Trebuie să modificați chenarele după cum urmează: . $LCP(L,M)$ $M$ $L$ $L$ $[M,R]$ $L=L,R=M,r=LCP(L,M)$
  3. $LCP(L,M)=l$ , aceasta înseamnă că pe segment primele caractere din toate sufixele coincid și este imposibil să spuneți imediat la ce subsegment să mergeți. Pentru a rezolva acest lucru, este necesar să comparați cu modelul caracterele care urmează poziției în sufix . Dacă din punct de vedere lexicografic este mai mic sau egal cu și există o nepotrivire la a-a poziție (dacă există o potrivire lexicografică și , atunci considerăm egal ), atunci modificăm limitele după cum urmează:, ,; în caz contrar ( mai mare din punct de vedere lexicografic): , ,. $[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$ . Verificăm și comparăm cu ca în pasul anterior, dar schimbăm la și la . $LCP(R,M),M={\frac {L+R}{2)}$ $r$ $L$ $R$ $l$ $r$
Algoritmul funcționează până când și devine egal . Aceasta înseamnă că există un segment de coincidență. Dacă invariantul nu este îndeplinit , atunci nu există niciun model ca subșir în text. $l$ $r$ $|P|$ $L<P<R$

O astfel de supraaccelerare dă timp , deoarece sunt efectuate iterații peste matricea sufixelor. $O(|P|+\log _{2}{|T|})$ $\log _{2}{|T|}$

Algoritmi înrudiți

Algoritmul lui Kasai pentru construirea unei matrice a celor mai mari prefixe comune.

Vezi și

arbore de sufix

Link -uri

Literatură

Gasfield D. Corzi, arbori și secvențe în algoritmi: Informatică și biologie computațională / Per. din engleza. I. V. Romanovsky. - Ed. a II-a. - Sankt Petersburg. : Dialectul Nevski, 2003. - 654 p.
Smith B. Metode și algoritmi de calcul pe șiruri = Computing Patterns in Strings. - M. : Williams, 2006. - 496 p. - ISBN 5-8459-1081-1 , 0-201-39839-7.

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun