LCP низ

LCP низ
Тип	низ
Проналазач	Шаблон:Harvnb
Временска и просторна сложеност у велико О нотацији
	Просечан случај	Најгори случај
Простор	$𝒪(n)$	$𝒪(n)$
Време	$𝒪(n)$	$𝒪(n)$

У информатици, најдужи заједнички префикс низ (енг. longest common prefix array) је помоћна структура података при суфиксном низу. Она чува дужине најдужих заједничких префикса, између парова узастопних суфикса у сортираном суфиксном низа. Другим речима, то је дужина префикса заједничка за два узастопна суфикса у сортираном низу суфикса.

Пример:

LCP од a и aabba је 1.

LCP од abaabba и abba је 2.

Повећавајући суфиксни низ са LCP низом омогућава ефикасно симулирање одозго надоле и одоздо нагоре обилазак стабла за суфиксно стабло, образац поклапања код суфиксног низа и предуслов је за компримовано суфиксно стабло.

Историја

LCP низ су заједно са суфиксним низом увели, 1993. године, Udi Manber и Gene Myers са циљем да побољшају временску сложеност алогоритма претраге низа стрингова. Gene Myers је бивши потпредседник Informatics Research у Celera Genomics, а Udi Manber је био потпредседник инжењеринг у Google.

Дефиниција

Нека је $A$ суфиксни низ низа стрингова $S=s_1,s_2,...s_n\mathrm{\$}$ и нека $\mathrm{lcp}(v,w)$ означава дужину најдужег заједничког прфикса између два стринга $v$ и $w$. Означимо додатно са $S[i,j]$ подниз од $S$ у распону од $i$ до $j$.

Тада је LCP низ $H[1,n]$ цео низ дужине$n$, тако да је $H[1]$ недефинисан и $H[i]=\mathrm{lcp}(S[A[i-1],n],S[A[i],n])$ за свако $1<i\le n$. Тако да $H[i]$ чува дужину најдужег заједничког префикса од лексикографски и-тог најмањег заједничког суфикса и његов претходник у низу суфикса.

Пример

Размотримо стринг $S=banana\mathrm{\$}$:

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

и одговарајући суфиксни низ $A$ :

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

Комплетан суфиксни низ са самим суфиксом :

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					$

Тада је LCP низ $H$ конструисан поређењем лексикографски узастопних суфикса да би се утврдио њихов најдужи заједнички префикс:

i	1	2	3	4	5	6	7
H[i]	$\mathrm{\perp }$	0	1	3	0	0	2

Нпр., $H[4]=3$ је дужина најдужег заједничког префикса $ana$ подељена суфиксима $A[3]=S[4,7]=ana\mathrm{\$}$ и $A[4]=S[2,7]=anana\mathrm{\$}$. Треба имати у виду да је $H[1]=\mathrm{\perp }$, докле год нема лексикографски мањег суфикса.

Разлика између суфиксног низа и LCP низа

Суфиксни низ: Представља лексикографкс ранг сваког суфикса низа.

LCP низ: Садржи максималну дужина префикса који се поклапа између два узастопна суфикса, након што су сортирани лексикографски.

Употреба LCP низа у проналажењу број појава обрасца

У циљу налажења број појављивања датог стринг P (дужина m) у тексту Т (дужине N),

• Мора се користити бинарна претрага за суфикс дужине Т.
• Требало би се убрзати применом LCP низа као помоћне структуре података. Прецизније, требало би направити посебну верзију LCP низа (LCP-LR низ) и користити такав низ.

Проблем са коришћењем стандардне бинарне претраге (без LCP низа) је да се у сваком од O(log N) поређења која су потребна да би упоредили P важећим улазним суфиксом низа, пролазимо м карактера. Дакле, сложеност је O(m*log N).

LCP-LR низ побољшава сложеност до O(m+log N), на следећи начин:

У било ком тренутку током бинарне претраге, ви сматрате, као и обично, низ (L,...,R)суфиксом низа и његова централна тачка М, одлучите да ли наставити претрагу у левом поднизу (L,...,M) или у десном поднизу (M,...,R). Да би донели одлуку, упоредите P са стрингом у М. Ако је P идентичан М, готово, али ако није, имаћете у односу на првих K карактера P а затим одлучити да ли је P лексикографски мање или већа од М. Претпоставимо исход је да је P већи од М. Дакле, у следећем кораку, ви сматрате (M,...,R) и нова централна тачка M' у средини:

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

Трик је у томе да је LCP-LR унапред одређено као што О(1) -указује на најдужи заједнички префикс М и M', lcp(M,M').

Већ из претходног корака знамо lcp(P,M)=k.да и сам М има префикс заједничких ликова са P. Сада постоје три могућности:

• Случај 1: k < lcp(M,M'), тј. Р има мање префиксних карактера заједничких са М него што има М са М'. Ово значи (k+1)-ви карактер M' је исти као код М, а пошто P лексикографски већа од М, онда мора бити лексикографски веће и од М'. Тако смо и даље у десној половини (M',...,R).
• Случај 2: k > lcp(M,M'), тј. P има више префиксних карактера заједничких са М него М са М'. Према томе, ако смо за поређење P на М', заједничких префикса, мање од К и М' биће лексикографски већа од p, тако, без упоређења, настављамо у левој половини (M,...,M').
• Случај 3: k == lcp(M,M'). Тако ако су М и М' оба идентични са P у првих к карактера. Да би се одлучило да ли ћемо наставити са леве или десне стране, довољно је упоредити P на М', почевши од (k+1)-ог карактера.
• Наставити рекурзивно.

Свеукупни учинак је да се ниједан карактер p не пореди са било којим карактером из текста више од једног пута. Укупан број поређења карактера је ограничен м, тако да је укупна сложеност заиста О(m+log n).

Очигледно, преостало је још кључно питање како смо одредили LCP-LR тако да нам сложеност LCP-a између било која два уписа у суфиксном низу буде О(1)? Као што је речено, стандардни LCP низ говори нам само да имамо LCP узастопних улазака, односно LCP (x-1, x) за било које x. Ма да, M i M' у опису изнад нису кључно узастопни улази, па како смо онда то учинили?

Кључно за то је да схватимо да се одређени распони (L,...,R) никада неће појавити током бинарне претраге: она увек почиње са (0,...,n) и дели на средини, а затим даље било лево или десно и онда опет подели ту половину. Ако размишљамо о томе: сваки улазак суфиксом низ настаје као централна тачка тачно једног могућег распона током бинарне претраге. Дакле, постоји тачно n различитих распона (L...M...R) који евентуално могу играти улогу у бинарном претраживању, а довољно је одредити lcp(L,M) и lcp(M,R) за оних N могућих распона. Тако да имамо 2*N различитих, унапред израчунатих вредности, па је LCP-LR сложености O(N).

Осим тога, ту је једноставан алгоритам за одређивање 2xN вредности LCP-LR у времену O(N) за стандардне LCP низове.

Да сумирамо:

• Могуће је израчунати LCP-LR у времену O(N) и O(2*N)=O(N) простору за LCP.
• Коришћење LCP-LR током бинарне претраге убрзава поступак са O(M*log N) to O(M+log N).
• Могу се користити две бинарне претраге да би се одредио леви и десни крај опсега за подударање P, а даљи опсег подударања одговара броју појављивања за P.

Ефикасна конструкција алгоритма

Алгоритми за конструкцију LCP низа могу се поделити на две категорије: алгоритми који израчунавају LCP низ као нуспродукт у суфиксном низу и алгоритми који користе већ изграђени суфиксни низ како би израчунали LCP вредности.

Шаблон:Harvnb ају алгоритам за рачунање LCP низа уз суфиксни низ у $O(n\log n)$ времену. Шаблон:Harvnb показују да је могуће модификовати њихово $O(n)$ време алгоритма, а да при том једнако добро израчунава LCP низ. Шаблон:Harvnb представљају први алгоритам у $O(n)$ времену, алгоритам (FLAAP), који израчунава LCP низ у односу на текст и суфиксни низ. Под претпоставком да је сваки текстуални симбол величине једног бајта и сваки улазак у суфиксни или LCP низ траје 4 бајта, главни недостатак њиховог алгоритма је то што је попуњен велики простор $13n$ бајтова, док изворни излаз (текст, суфиксни или LCP низ) заузима само $9n$ бајтова. Тако да је Шаблон:Harvnb аправио бољу верзију алгоритма Шаблон:Harvnb (lcp9) и са којим је смањио количину попуњеног простора за $9n$ бајтова. Шаблон:Harvnbдају један још бољи Kasai's алгоритам ($\mathrm{\Phi }$-алгоритам) који побољшава потребно време. Уместо стварног LCP низа, овај алгоритам гради пермутовани LCP (PLCP) низ, у којем су вредности које се појављују у тексту у лексикографском поретку. Шаблон:Harvnb дају два алгоритма, који иако су спори у теорији ($O(n^2)$), у пракси су доста бржи.

Од 2012. године, тренутно најбржи, линеарног времена, алгоритма за конструкцију LCP низа је Шаблон:Harvnb, који се темељи на једном од најбржих алгоритама за конструкцију суфиксног низа Шаблон:Harvnb.

Апликације

Као што је наведено од стране Шаблон:Harvnb неколико проблема се може решити употребом следећих врста обилазака стабла:

• одоздо према горе обухватањем целокупног суфиксног стабла
• одозго према доле обилазак подстабла суфиксног стабла
• Обилазак суфиксног стабла помоћу суфиксних линкова.

Шаблон:Harvnb показују како симулирати одоздо према горе обилазак суфиксног стабла, коришћењем само суфиксног и LCP низа. Шаблон:Harvnb су побољшали суфиксни низ са LCP низом и додатном структуром података, и описали како се побољшани суфиксни низ може користити за симулацију сва три обиласка суфиксног стабла. Шаблон:Harvnb смањује захтеве за простором од стране побољшаног суфиксног низа са предизрачунатим LCP низом за распон минималних упита . Дакле, сваки проблем који се може режити алгоритмом за суфиксно стабло, може се решити и са побољшаним суфиксним стаблом. Шаблон:Sfn

Одлучивање, ако је узорак $P$ дужине $m$ подниза стрингова $S$ дужине $n$ траје $O(m\log n)$ времена, ако се користи само суфиксни низ. Додатно коришћењем LCP, ово може бити побољшано на $O(m+\log n)$.Шаблон:Sfn Шаблон:Harvnb показују како побољшати ово време и даље како би се постигла оптимална сложеност $O(m)$ time. Дакле, помоћу суфиксног низа i LCP низа, одабрани упити може одговарати једнако брзо као и применом суфиксног стабла.

LCP низ је битан део компримованих суфиксних стабала који пружа пуну функционалност суфиксним стаблима као суфиксних линкова и најважнијег заједничког претка упита. Осим тога може се користити заједно са суфиксним низом за израчунавање Lempel-Ziv LZ77 факторизације у $O(n)$ времену. Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn

Проблем најдуже понављаног подниза за низ $S$ дужине $n$ може бити решен у $\mathrm{\Theta }(n)$ времену, коришћењем и суфиксног низа $A$ и LCP низа. То је довољно за обављане линеарне претраге LCP како би се пронашла максимална вредност $v_{max}$ акао и одговарајући индекс $i$ на коме се налази $v_{max}$. Најдужи подниз који се јавља најмање два пута је дат са $S[A[i],A[i]+v_{max}-1]$.

У наставку су објашњене две апликације LCP низа: Како се суфиксни низ и LCP низ могу користити за изградњу одговарајућег суфиксног стабла и како је могуће одговорити LCP упите за произвољне суфиксе који користе минимални распон упита LCP низа.

Конструкција суфиксног стабла

Дат нам је суфиксни низ $A$ и LCP низ $H$ од стрингова $S=s_1,s_2,...s_n\mathrm{\$}$ дужине $n+1$, његогво суфиксно стабло $ST$ може се изградити у $O(n)$ времену, на темељу следеће идеје: Почнемо са делимичним суфиксним стаблом за лексикографски најмањи суфикс и затим убацујемо остале суфиксе по редоследу који нам је дат суфиксним низом.

Нека је $S{T}_i$ делимично суфиксно стабло за $0\le i\le n$. Нека је $d(v)$ дужина стазе уланчавања свих делова ознака од корена $S{T}_i$ до чвора $v$.

Случај 1 ($d(v)=H[i+1]$): Нека су дати суфикси $a\mathrm{\$}$, $ana\mathrm{\$}$, $anana\mathrm{\$}$ и $banana\mathrm{\$}$ низа $S=banana\mathrm{\$}$ већ додати у суфиксно стабло. Тада се суфикс $na\mathrm{\$}$ додаје као што је приказано на слици. Крајњи десни пут је означен црвеном бојом.

Почнимо од $S{T}_0$, стабла које се састоји само од корена. За додавање $A[i+1]$у $S{T}_i$, прошетамо крајње десном путем са почетком у недавно додатом листу $A[i]$ па до корена, све док се не стигне до најдубљег чвора $v$ са $d(v)\le H[i+1]$ је постигнуто..

Морамо да размотримо следећа два сличаја:

• $d(v)=H[i+1]$: То значи да уланчавање ознака на путу од корена до чвора $v$, је једнака најдужем заједничком префиксу суфикса $A[i]$ и $A[i+1]$.
  У том случају, додати $A[i+1]$ као нови лист $x$ чвора $v$ и означити руб $(v,x)$ са $S[A[i+1]+H[i+1],n]$. Тако се ознака руба састоји од преосталих карактера суфикса $A[i+1]$ који нису већ заступљени у уланчавању ознака пута од корена до чвора $v$ path.
  На овај начин се гради делимично суфиксно стабло $S{T}_{i+1}$.

  

  Случај 2 ($d(v)<H[i+1]$): Да би додали суфикс $nana\mathrm{\$}$, на руб претходно убаченог суфикс $na\mathrm{\$}$ треба да се раздвоји. Нови руб интерног чвора је означен са најдужим заједничким префиксом суфикса $na\mathrm{\$}$ и $nana\mathrm{\$}$. Руб повезује два листа са преосталим суфиксним карактерима који нису део префикса.

• $d(v)<H[i+1]$: То значи да уланчавање ознака на путу од корена до чвора $v$ приказује мање карактера него најдужи заједнички префикс суфикса $A[i]$ и $A[i+1]$ и изгубљени карактери су садржани у рубној ознаци од $v$-тог најдеснијег руба. Тако да морамо раздвојити тај руб на следећи начинs:
  Нека је $w$ потомак од $v$ у $S{T}_i$ најдеснијем путу.

1. Брисање руба $(v,w)$.
2. 2. Додавање новог интерног чвора $y$ и новог руба $(v,y)$ са ознаком $S[A[i]+d(v),A[i]+H[i+1]-1]$. Нова ознака састоји се од несталих карактера најдужег заједничког префикса од $A[i]$ и $A[i+1]$. Дакле, уланчавање ознака пута од корена до чвора $y$ сада показује најдужи заједнички префикс од $A[i]$ и $A[i+1]$.
3. Спојити $w$ на новонастали интерни чвор $y$ од стране руба $(y,w)$ који је означен са $S[A[i]+H[i+1],A[i]+d(w)-1]$. Нова ознака састоји се од преосталих знакова брисаног руба $(v,w)$ који нису коришћени као ознака руба $(v,y)$.
4. Додати $A[i+1]$ као нови лист $x$ и повезати га са новим интерним чвором $y$ од стране руба $(y,x)$ који је означен са $S[A[i+1]+H[i+1],n]$. Тако се ознака руба састоји од преосталих карактера суфикса $A[i+1]$ који нису већ заступљени у уланчавању ознака пута од корена до чвора $v$.
5. Тако добијамо делимично суфиксно стабло $S{T}_{i+1}$.

Једноставна амортизација аргумената показује да је време рада овог алгоритма ограничено са $O(n)$:

Чворови који су прелазили у кораку $i$ прошавши најдеснијим путем $S{T}_i$ (осим последњег чвора $v$) се уклањају из најдеснијег пута када је $A[i+1]$ додан у стабло као нови лист. Овим чворовима се никада више неће проћи за све наредне кораке $j>i$. Тако да ће се готово увек проћи кроз $2n$ чворова, укупно.

LCP упити за произвољне суфиксе

LCP низ $H$ садржи само дужину најдужег заједничког префикса сваког пара суфикса у суфиксном низу $A$. Међутим, уз помоћ инверза суфиксног низа $A^{-1}$ ($A[i]=j\iff A^{-1}[j]=i$, тј. суфикса $S[j,n]$ који почиње на позицији $j$ у $S$ је похрањен на положају $A^{-1}[j]$ у $A$) и константо време распона минималног упита на $H$, могуће је одредити дужину најдужег заједничког префикса произвољних суфикса у времену $O(1)$.

Због лексикографског редоследа суфиксног низа, сваки заједнички префикс од суфикса $S[i,n]$ и $S[j,n]$мора бити заједнички префикс свих суфикса између $i$-те позиције у суфиксном низу $A^{-1}[i]$ и $j$-те позиције у суфиксном низу $A^{-1}[j]$. Тако да, дужина најдужег заједничког префикса који дели све ове суфиксе је минимална вредност у интервалу $H[A^{-1}[i]+1,A^{-1}[j]]$. Ова вредност може се наћи у константном времену, ако је $H$ предобрађен за распон минималних упита.

Према томе добијен низ $S$ дужине $n$ и две произвољне позиције $i,j$ у стрингу $S$ са $A^{-1}[i]<A^{-1}[j]$, дужина најдужег заједничког префикса од суфикса $S[i,n]$ и $S[j,n]$ може се израчунати на следећи начин: $\mathrm{LCP}(i,j)=H[{\mathrm{RMQ}}_H(A^{-1}[i]+1,A^{-1}[j])]$.

Спољашње везе

• Mirror of the ad-hoc-implementation of the code described in Шаблон:Harvnb
• 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)