LCP niz

LCP niz
Tip	niz
Pronalazač	Manber & Myers 1990
Vremenska i prostorna složenost u veliko O notaciji
	Prosečan slučaj	Najgori slučaj
Prostor	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$
Vreme	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$

U informatici, najduži zajednički prefiks niz (eng. longest common prefix array) je pomoćna struktura podataka pri sufiksnom nizu. Ona čuva dužine najdužih zajedničkih prefiksa, između parova uzastopnih sufiksa u sortiranom sufiksnom niza. Drugim rečima, to je dužina prefiksa zajednička za dva uzastopna sufiksa u sortiranom nizu sufiksa.

Primer:

LCP od a i aabba je 1.

LCP od abaabba i abba je 2.

Povećavajući sufiksni niz sa LCP nizom omogućava efikasno simuliranje odozgo nadole i odozdo nagore obilazak stabla za sufiksno stablo, obrazac poklapanja kod sufiksnog niza i preduslov je za komprimovano sufiksno stablo.

Istorija

LCP niz su zajedno sa sufiksnim nizom uveli, 1993. godine, Udi Manber i Gene Myers sa ciljem da poboljšaju vremensku složenost alogoritma pretrage niza stringova. Gene Myers je bivši potpredsednik Informatics Research u Celera Genomics, a Udi Manber je bio potpredsednik inženjering u Google.

Definicija

Neka je $A$ sufiksni niz niza stringova $S=s_{1},s_{2},...s_{n}\$$ i neka $\operatorname {lcp} (v,w)$ označava dužinu najdužeg zajedničkog prfiksa između dva stringa $v$ i $w$. Označimo dodatno sa $S[i,j]$ podniz od $S$ u rasponu od $i$ do $j$.

Tada je LCP niz $H[1,n]$ ceo niz dužine$n$, tako da je $H[1]$ nedefinisan i $H[i]=\operatorname {lcp} (S[A[i-1],n],S[A[i],n])$ za svako $1<i\leq n$. Tako da $H[i]$ čuva dužinu najdužeg zajedničkog prefiksa od leksikografski i-tog najmanjeg zajedničkog sufiksa i njegov prethodnik u nizu sufiksa.

Primer

Razmotrimo string $S=banana\$$:

i	1	2	3	4	5	6	7
S[i]	b	a	n	a	n	a	$

i odgovarajući sufiksni niz $A$ :

i	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3

Kompletan sufiksni niz sa samim sufiksom :

i	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3
1	$	a	a	a	b	n	n
2		$	n	n	a	a	a
3			a	a	n	$	n
4			$	n	a		a
5				a	n		$
6				$	a
7					$

Tada je LCP niz $H$ konstruisan poređenjem leksikografski uzastopnih sufiksa da bi se utvrdio njihov najduži zajednički prefiks:

i	1	2	3	4	5	6	7
H[i]	$\bot$	0	1	3	0	0	2

Npr., $H[4]=3$ je dužina najdužeg zajedničkog prefiksa $ana$ podeljena sufiksima $A[3]=S[4,7]=ana\$$ i $A[4]=S[2,7]=anana\$$. Treba imati u vidu da je $H[1]=\bot$, dokle god nema leksikografski manjeg sufiksa.

Razlika između sufiksnog niza i LCP niza

Sufiksni niz: Predstavlja leksikografks rang svakog sufiksa niza.

LCP niz: Sadrži maksimalnu dužina prefiksa koji se poklapa između dva uzastopna sufiksa, nakon što su sortirani leksikografski.

Upotreba LCP niza u pronalaženju broj pojava obrasca

U cilju nalaženja broj pojavljivanja datog string P (dužina m) u tekstu T (dužine N),

• Mora se koristiti binarna pretraga za sufiks dužine T.
• Trebalo bi se ubrzati primenom LCP niza kao pomoćne strukture podataka. Preciznije, trebalo bi napraviti posebnu verziju LCP niza (LCP-LR niz) i koristiti takav niz.

Problem sa korišćenjem standardne binarne pretrage (bez LCP niza) je da se u svakom od O(log N) poređenja koja su potrebna da bi uporedili P važećim ulaznim sufiksom niza, prolazimo m karaktera. Dakle, složenost je O(m*log N).

LCP-LR niz poboljšava složenost do O(m+log N), na sledeći način:

U bilo kom trenutku tokom binarne pretrage, vi smatrate, kao i obično, niz (L,...,R)sufiksom niza i njegova centralna tačka M, odlučite da li nastaviti pretragu u levom podnizu (L,...,M) ili u desnom podnizu (M,...,R). Da bi doneli odluku, uporedite P sa stringom u M. Ako je P identičan M, gotovo, ali ako nije, imaćete u odnosu na prvih K karaktera P a zatim odlučiti da li je P leksikografski manje ili veća od M. Pretpostavimo ishod je da je P veći od M. Dakle, u sledećem koraku, vi smatrate (M,...,R) i nova centralna tačka M' u sredini:

             M ...... M' ...... R
             |
      знамо:
         lcp(P,M)==k

Trik je u tome da je LCP-LR unapred određeno kao što O(1) -ukazuje na najduži zajednički prefiks M i M', lcp(M,M').

Već iz prethodnog koraka znamo lcp(P,M)=k.da i sam M ima prefiks zajedničkih likova sa P. Sada postoje tri mogućnosti:

• Slučaj 1: k < lcp(M,M'), tj. R ima manje prefiksnih karaktera zajedničkih sa M nego što ima M sa M'. Ovo znači (k+1)-vi karakter M' je isti kao kod M, a pošto P leksikografski veća od M, onda mora biti leksikografski veće i od M'. Tako smo i dalje u desnoj polovini (M',...,R).
• Slučaj 2: k > lcp(M,M'), tj. P ima više prefiksnih karaktera zajedničkih sa M nego M sa M'. Prema tome, ako smo za poređenje P na M', zajedničkih prefiksa, manje od K i M' biće leksikografski veća od p, tako, bez upoređenja, nastavljamo u levoj polovini (M,...,M').
• Slučaj 3: k == lcp(M,M'). Tako ako su M i M' oba identični sa P u prvih k karaktera. Da bi se odlučilo da li ćemo nastaviti sa leve ili desne strane, dovoljno je uporediti P na M', počevši od (k+1)-og karaktera.
• Nastaviti rekurzivno.

Sveukupni učinak je da se nijedan karakter p ne poredi sa bilo kojim karakterom iz teksta više od jednog puta. Ukupan broj poređenja karaktera je ograničen m, tako da je ukupna složenost zaista O(m+log n).

Očigledno, preostalo je još ključno pitanje kako smo odredili LCP-LR tako da nam složenost LCP-a između bilo koja dva upisa u sufiksnom nizu bude O(1)? Kao što je rečeno, standardni LCP niz govori nam samo da imamo LCP uzastopnih ulazaka, odnosno LCP (x-1, x) za bilo koje x. Ma da, M i M' u opisu iznad nisu ključno uzastopni ulazi, pa kako smo onda to učinili?

Ključno za to je da shvatimo da se određeni rasponi (L,...,R) nikada neće pojaviti tokom binarne pretrage: ona uvek počinje sa (0,...,n) i deli na sredini, a zatim dalje bilo levo ili desno i onda opet podeli tu polovinu. Ako razmišljamo o tome: svaki ulazak sufiksom niz nastaje kao centralna tačka tačno jednog mogućeg raspona tokom binarne pretrage. Dakle, postoji tačno n različitih raspona (L...M...R) koji eventualno mogu igrati ulogu u binarnom pretraživanju, a dovoljno je odrediti lcp(L,M) i lcp(M,R) za onih N mogućih raspona. Tako da imamo 2*N različitih, unapred izračunatih vrednosti, pa je LCP-LR složenosti O(N).

Osim toga, tu je jednostavan algoritam za određivanje 2xN vrednosti LCP-LR u vremenu O(N) za standardne LCP nizove.

Da sumiramo:

• Moguće je izračunati LCP-LR u vremenu O(N) i O(2*N)=O(N) prostoru za LCP.
• Korišćenje LCP-LR tokom binarne pretrage ubrzava postupak sa O(M*log N) to O(M+log N).
• Mogu se koristiti dve binarne pretrage da bi se odredio levi i desni kraj opsega za podudaranje P, a dalji opseg podudaranja odgovara broju pojavljivanja za P.

Efikasna konstrukcija algoritma

Algoritmi za konstrukciju LCP niza mogu se podeliti na dve kategorije: algoritmi koji izračunavaju LCP niz kao nusprodukt u sufiksnom nizu i algoritmi koji koriste već izgrađeni sufiksni niz kako bi izračunali LCP vrednosti.

Manber & Myers 1993 aju algoritam za računanje LCP niza uz sufiksni niz u $O(n\log n)$ vremenu. Kärkkäinen & Sanders 2003 pokazuju da je moguće modifikovati njihovo $O(n)$ vreme algoritma, a da pri tom jednako dobro izračunava LCP niz. Kasai et al. 2001 predstavljaju prvi algoritam u $O(n)$ vremenu, algoritam (FLAAP), koji izračunava LCP niz u odnosu na tekst i sufiksni niz. Pod pretpostavkom da je svaki tekstualni simbol veličine jednog bajta i svaki ulazak u sufiksni ili LCP niz traje 4 bajta, glavni nedostatak njihovog algoritma je to što je popunjen veliki prostor $13n$ bajtova, dok izvorni izlaz (tekst, sufiksni ili LCP niz) zauzima samo $9n$ bajtova. Tako da je Manzini 2004 apravio bolju verziju algoritma Kasai et al. 2001 (lcp9) i sa kojim je smanjio količinu popunjenog prostora za $9n$ bajtova. Kärkkäinen, Manzini & Puglisi 2009daju jedan još bolji Kasai's algoritam ($\Phi$-algoritam) koji poboljšava potrebno vreme. Umesto stvarnog LCP niza, ovaj algoritam gradi permutovani LCP (PLCP) niz, u kojem su vrednosti koje se pojavljuju u tekstu u leksikografskom poretku. Gog & Ohlebusch 2011 daju dva algoritma, koji iako su spori u teoriji ($O(n^{2})$), u praksi su dosta brži.

Od 2012. godine, trenutno najbrži, linearnog vremena, algoritma za konstrukciju LCP niza je Fischer 2011, koji se temelji na jednom od najbržih algoritama za konstrukciju sufiksnog niza Nong, Zhang & Chan 2009.

Aplikacije

Kao što je navedeno od strane Abouelhoda, Kurtz & Ohlebusch 2004 nekoliko problema se može rešiti upotrebom sledećih vrsta obilazaka stabla:

• odozdo prema gore obuhvatanjem celokupnog sufiksnog stabla
• odozgo prema dole obilazak podstabla sufiksnog stabla
• Obilazak sufiksnog stabla pomoću sufiksnih linkova.

Kasai et al. 2001 pokazuju kako simulirati odozdo prema gore obilazak sufiksnog stabla, korišćenjem samo sufiksnog i LCP niza. Abouelhoda, Kurtz & Ohlebusch 2004 su poboljšali sufiksni niz sa LCP nizom i dodatnom strukturom podataka, i opisali kako se poboljšani sufiksni niz može koristiti za simulaciju sva tri obilaska sufiksnog stabla. Fischer & Heun 2007 smanjuje zahteve za prostorom od strane poboljšanog sufiksnog niza sa predizračunatim LCP nizom za raspon minimalnih upita . Dakle, svaki problem koji se može režiti algoritmom za sufiksno stablo, može se rešiti i sa poboljšanim sufiksnim stablom.

Odlučivanje, ako je uzorak $P$ dužine $m$ podniza stringova $S$ dužine $n$ traje $O(m\log n)$ vremena, ako se koristi samo sufiksni niz. Dodatno korišćenjem LCP, ovo može biti poboljšano na $O(m+\log n)$. Abouelhoda, Kurtz & Ohlebusch 2004 pokazuju kako poboljšati ovo vreme i dalje kako bi se postigla optimalna složenost $O(m)$ time. Dakle, pomoću sufiksnog niza i LCP niza, odabrani upiti može odgovarati jednako brzo kao i primenom sufiksnog stabla.

LCP niz je bitan deo komprimovanih sufiksnih stabala koji pruža punu funkcionalnost sufiksnim stablima kao sufiksnih linkova i najvažnijeg zajedničkog pretka upita. Osim toga može se koristiti zajedno sa sufiksnim nizom za izračunavanje Lempel-Ziv LZ77 faktorizacije u $O(n)$ vremenu.

Problem najduže ponavljanog podniza za niz $S$ dužine $n$ može biti rešen u $\Theta (n)$ vremenu, korišćenjem i sufiksnog niza $A$ i LCP niza. To je dovoljno za obavljane linearne pretrage LCP kako bi se pronašla maksimalna vrednost $v_{max}$ akao i odgovarajući indeks $i$ na kome se nalazi $v_{max}$. Najduži podniz koji se javlja najmanje dva puta je dat sa $S[A[i],A[i]+v_{max}-1]$.

U nastavku su objašnjene dve aplikacije LCP niza: Kako se sufiksni niz i LCP niz mogu koristiti za izgradnju odgovarajućeg sufiksnog stabla i kako je moguće odgovoriti LCP upite za proizvoljne sufikse koji koriste minimalni raspon upita LCP niza.

Konstrukcija sufiksnog stabla

Dat nam je sufiksni niz $A$ i LCP niz $H$ od stringova $S=s_{1},s_{2},...s_{n}\$$ dužine $n+1$, njegogvo sufiksno stablo $ST$ može se izgraditi u $O(n)$ vremenu, na temelju sledeće ideje: Počnemo sa delimičnim sufiksnim stablom za leksikografski najmanji sufiks i zatim ubacujemo ostale sufikse po redosledu koji nam je dat sufiksnim nizom.

Neka je $ST_{i}$ delimično sufiksno stablo za $0\leq i\leq n$. Neka je $d(v)$ dužina staze ulančavanja svih delova oznaka od korena $ST_{i}$ do čvora $v$.

Slučaj 1 ($d(v)=H[i+1]$): Neka su dati sufiksi $a\$$, $ana\$$, $anana\$$ i $banana\$$ niza $S=banana\$$ već dodati u sufiksno stablo. Tada se sufiks $na\$$ dodaje kao što je prikazano na slici. Krajnji desni put je označen crvenom bojom.

Počnimo od $ST_{0}$, stabla koje se sastoji samo od korena. Za dodavanje $A[i+1]$u $ST_{i}$, prošetamo krajnje desnom putem sa početkom u nedavno dodatom listu $A[i]$ pa do korena, sve dok se ne stigne do najdubljeg čvora $v$ sa $d(v)\leq H[i+1]$ je postignuto..

Moramo da razmotrimo sledeća dva sličaja:

• $d(v)=H[i+1]$: To znači da ulančavanje oznaka na putu od korena do čvora $v$, je jednaka najdužem zajedničkom prefiksu sufiksa $A[i]$ i $A[i+1]$.
  U tom slučaju, dodati $A[i+1]$ kao novi list $x$ čvora $v$ i označiti rub $(v,x)$ sa $S[A[i+1]+H[i+1],n]$. Tako se oznaka ruba sastoji od preostalih karaktera sufiksa $A[i+1]$ koji nisu već zastupljeni u ulančavanju oznaka puta od korena do čvora $v$ path.
  Na ovaj način se gradi delimično sufiksno stablo $ST_{i+1}$.

  

  Slučaj 2 ($d(v)<H[i+1]$): Da bi dodali sufiks $nana\$$, na rub prethodno ubačenog sufiks $na\$$ treba da se razdvoji. Novi rub internog čvora je označen sa najdužim zajedničkim prefiksom sufiksa $na\$$ i $nana\$$. Rub povezuje dva lista sa preostalim sufiksnim karakterima koji nisu deo prefiksa.

• $d(v)<H[i+1]$: To znači da ulančavanje oznaka na putu od korena do čvora $v$ prikazuje manje karaktera nego najduži zajednički prefiks sufiksa $A[i]$ i $A[i+1]$ i izgubljeni karakteri su sadržani u rubnoj oznaci od $v$-tog najdesnijeg ruba. Tako da moramo razdvojiti taj rub na sledeći načins:
  Neka je $w$ potomak od $v$ u $ST_{i}$ najdesnijem putu.

1. Brisanje ruba $(v,w)$.
2. 2. Dodavanje novog internog čvora $y$ i novog ruba $(v,y)$ sa oznakom $S[A[i]+d(v),A[i]+H[i+1]-1]$. Nova oznaka sastoji se od nestalih karaktera najdužeg zajedničkog prefiksa od $A[i]$ i $A[i+1]$. Dakle, ulančavanje oznaka puta od korena do čvora $y$ sada pokazuje najduži zajednički prefiks od $A[i]$ i $A[i+1]$.
3. Spojiti $w$ na novonastali interni čvor $y$ od strane ruba $(y,w)$ koji je označen sa $S[A[i]+H[i+1],A[i]+d(w)-1]$. Nova oznaka sastoji se od preostalih znakova brisanog ruba $(v,w)$ koji nisu korišćeni kao oznaka ruba $(v,y)$.
4. Dodati $A[i+1]$ kao novi list $x$ i povezati ga sa novim internim čvorom $y$ od strane ruba $(y,x)$ koji je označen sa $S[A[i+1]+H[i+1],n]$. Tako se oznaka ruba sastoji od preostalih karaktera sufiksa $A[i+1]$ koji nisu već zastupljeni u ulančavanju oznaka puta od korena do čvora $v$.
5. Tako dobijamo delimično sufiksno stablo $ST_{i+1}$.

Jednostavna amortizacija argumenata pokazuje da je vreme rada ovog algoritma ograničeno sa $O(n)$:

Čvorovi koji su prelazili u koraku $i$ prošavši najdesnijim putem $ST_{i}$ (osim poslednjeg čvora $v$) se uklanjaju iz najdesnijeg puta kada je $A[i+1]$ dodan u stablo kao novi list. Ovim čvorovima se nikada više neće proći za sve naredne korake $j>i$. Tako da će se gotovo uvek proći kroz $2n$ čvorova, ukupno.

LCP upiti za proizvoljne sufikse

LCP niz $H$ sadrži samo dužinu najdužeg zajedničkog prefiksa svakog para sufiksa u sufiksnom nizu $A$. Međutim, uz pomoć inverza sufiksnog niza $A^{-1}$ ($A[i]=j\Leftrightarrow A^{-1}[j]=i$, tj. sufiksa $S[j,n]$ koji počinje na poziciji $j$ u $S$ je pohranjen na položaju $A^{-1}[j]$ u $A$) i konstanto vreme raspona minimalnog upita na $H$, moguće je odrediti dužinu najdužeg zajedničkog prefiksa proizvoljnih sufiksa u vremenu $O(1)$.

Zbog leksikografskog redosleda sufiksnog niza, svaki zajednički prefiks od sufiksa $S[i,n]$ i $S[j,n]$mora biti zajednički prefiks svih sufiksa između $i$-te pozicije u sufiksnom nizu $A^{-1}[i]$ i $j$-te pozicije u sufiksnom nizu $A^{-1}[j]$. Tako da, dužina najdužeg zajedničkog prefiksa koji deli sve ove sufikse je minimalna vrednost u intervalu $H[A^{-1}[i]+1,A^{-1}[j]]$. Ova vrednost može se naći u konstantnom vremenu, ako je $H$ predobrađen za raspon minimalnih upita.

Prema tome dobijen niz $S$ dužine $n$ i dve proizvoljne pozicije $i,j$ u stringu $S$ sa $A^{-1}[i]<A^{-1}[j]$, dužina najdužeg zajedničkog prefiksa od sufiksa $S[i,n]$ i $S[j,n]$ može se izračunati na sledeći način: $\operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]$.

Spoljašnje veze

• Mirror of the ad-hoc-implementation of the code described in Fischer 2011
• SDSL: Succinct Data Structure Library - Provides various LCP array implementations, Range Minimum Query (RMQ) support structures and many more succinct data structures
• Bottom-up suffix tree traversal emulated using suffix array and LCP array (Java)
• Text-Indexing project (linear-time construction of suffix trees, suffix arrays, LCP array and Burrows-Wheeler Transform)