Изворни код странице LCP низ

{{Neprovereni seminarski}}
{| class="infobox" style="width: 22em"
! colspan="3" style="font-size: 125%; text-align: center;" | LCP низ
|-
! Тип
| colspan="2" | [[низ]]
|-
! Проналазач
{{!}} colspan="2" {{!}}  {{harvnb|Manber|Myers|1990}}
|-
! colspan="3" class="navbox-abovebelow" | [[Временска сложеност|Временска]] и [[просторна сложеност]]<br />у [[велико О]] нотацији
|-
|
| Просечан случај
| Најгори случај
|-
! Простор
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|-
! Време
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|}

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

Пример:

LCP од '''a''' и '''a'''abba је 1.

LCP од '''ab'''aabba и '''ab'''ba је 2.

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

== Историја ==

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

== Дефиниција ==

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

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

== Пример ==

Размотримо стринг <math>S=banana\$</math>:
{| class="wikitable"
|-
!i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
!S[i]
| b || a || n || a || n || a || $
|}
и одговарајући [[суфиксни низ]] <math>A</math> :
{| class="wikitable"
!i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
!A[i]
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|}

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

{| class="wikitable"
!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 низ <math>H</math> конструисан поређењем лексикографски узастопних суфикса да би се утврдио њихов најдужи заједнички префикс:
{| class="wikitable"
|-
!i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
!H[i]
| <math>\bot</math> || 0 || 1 || 3 || 0 || 0 || 2
|}

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

== Разлика између суфиксног низа и 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|Manber|Myers|1993}} ају алгоритам за рачунање LCP низа уз суфиксни низ у <math>O(n \log n)</math> времену. {{harvnb|Kärkkäinen|Sanders|2003}} показују да је могуће модификовати њихово <math>O(n)</math> време алгоритма, а да при том једнако добро израчунава LCP низ. {{harvnb|Kasai|Lee|Arimura|Arikawa|2001}} представљају први алгоритам у <math>O(n)</math> времену, алгоритам (FLAAP), који израчунава LCP низ у односу на текст и суфиксни низ.
Под претпоставком да је сваки текстуални симбол величине једног бајта и сваки улазак у суфиксни или LCP низ траје 4 бајта, главни недостатак њиховог алгоритма је то што је попуњен велики простор <math>13n</math> бајтова, док изворни излаз (текст, суфиксни или LCP низ) заузима само <math>9n</math>
бајтова. Тако да је {{harvnb|Manzini|2004}} аправио бољу верзију алгоритма {{harvnb|Kasai|Lee|Arimura|Arikawa|2001}} (lcp9) и са којим је смањио количину попуњеног простора за <math>9n</math> бајтова. {{harvnb|Kärkkäinen|Manzini|Puglisi|2009}}дају један још бољи Kasai's алгоритам (<math>\Phi</math>-алгоритам) који побољшава потребно време. Уместо стварног LCP низа, овај алгоритам гради пермутовани LCP (PLCP) низ, у којем су вредности које се појављују у тексту у лексикографском поретку. 
{{harvnb|Gog|Ohlebusch|2011}} дају два алгоритма, који иако су спори у теорији (<math>O(n^2)</math>), у пракси су доста бржи. 

Од 2012. године, тренутно најбржи, линеарног времена, алгоритма за конструкцију LCP низа је {{harvnb|Fischer|2011}},
који се темељи на једном од најбржих алгоритама за конструкцију суфиксног низа {{harvnb|Nong|Zhang|Chan|2009}}.

== Апликације ==
Као што је наведено од стране {{harvnb|Abouelhoda|Kurtz|Ohlebusch|2004}} неколико проблема се може решити употребом следећих врста [[обилазак стабла|обилазака стабла]]: 
* одоздо према горе обухватањем целокупног суфиксног стабла 
* одозго према доле обилазак подстабла суфиксног стабла 
* Обилазак суфиксног стабла помоћу суфиксних линкова. 

{{harvnb|Kasai|Lee|Arimura|Arikawa|2001}} показују како симулирати одоздо према горе обилазак [[суфиксно стабло|суфиксног стабла]], коришћењем само [[суфиксни низ|суфиксног]] и LCP низа. {{harvnb|Abouelhoda|Kurtz|Ohlebusch|2004}} су побољшали суфиксни низ са LCP низом и додатном структуром података, и описали како се побољшани суфиксни низ може користити за симулацију сва три обиласка суфиксног стабла. {{harvnb|Fischer|Heun|2007}} смањује захтеве за простором од стране побољшаног суфиксног низа са предизрачунатим LCP низом за распон минималних упита . Дакле, сваки проблем који се може режити алгоритмом за суфиксно стабло, може се решити и са побољшаним суфиксним стаблом. {{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}}

Одлучивање, ако је узорак <math>P</math> дужине <math>m</math> подниза стрингова <math>S</math> дужине <math>n</math> траје <math> O(m \log n)</math> времена, ако се користи само суфиксни низ. Додатно коришћењем LCP, ово може бити побољшано на <math>O(m + \log n)</math>.{{sfn|Manber|Myers|1993}} {{harvnb|Abouelhoda|Kurtz|Ohlebusch|2004}} показују како побољшати ово време и даље како би се постигла оптимална сложеност <math>O(m)</math> time. Дакле, помоћу суфиксног низа i LCP низа, одабрани упити може одговарати једнако брзо као и применом [[суфиксно стабло|суфиксног стабла]]. 

LCP низ је битан део компримованих суфиксних стабала који пружа пуну функционалност суфиксним стаблима као суфиксних линкова и најважнијег заједничког претка упита. Осим тога може се користити заједно са суфиксним низом за израчунавање Lempel-Ziv [[LZ77 and LZ78|LZ77]] факторизације у <math>O(n)</math> времену. {{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}}{{sfn|Crochemore|Ilie|2008}}{{sfn|Crochemore|Ilie|Smyth|2008}}{{sfn|Chen|Puglisi|Smyth|2008}}

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

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

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

Нека је <math>ST_{i}</math> делимично суфиксно стабло за <math>0\leq i  \leq n</math>. Нека је <math>d(v)</math> дужина стазе уланчавања свих делова ознака од корена <math>ST_i</math> до чвора <math>v</math>.
 [[Датотека:Constructing the suffix tree of banana based on the suffix array and the LCP array - Case 1.pdf|thumb|400п|Случај 1 (<math>d(v)=H[i+1]</math>): Нека су дати суфикси <math>a\$</math>, <math>ana\$</math>, <math>anana\$</math> и <math>banana\$</math> низа <math>S=banana\$</math> већ додати у [[суфиксно стабло]]. Тада се суфикс <math>na\$</math> додаје као што је приказано на слици. ''Крајњи десни'' пут је означен црвеном бојом.]]
Почнимо од <math>ST_0</math>, стабла које се састоји само од корена. За додавање <math>A[i+1]</math>у <math>ST_i</math>, прошетамо крајње десном путем са почетком у недавно додатом листу <math>A[i]</math> па до корена, све док се не стигне до најдубљег чвора <math>v</math> са <math>d(v) \leq H[i+1]</math> је постигнуто..

Морамо да размотримо следећа два сличаја:
* <math>d(v)=H[i+1]</math>: То значи да уланчавање ознака на путу од корена до чвора <math>v</math>, је једнака најдужем заједничком префиксу суфикса <math>A[i]</math> и <math>A[i+1]</math>. <br /> У том случају, додати <math>A[i+1]</math> као нови лист <math>x</math> чвора <math>v</math> и означити руб <math>(v,x)</math> са <math>S[A[i+1]+H[i+1],n]</math>. Тако се ознака руба састоји од преосталих карактера суфикса <math>A[i+1]</math> који нису већ заступљени у уланчавању ознака пута од корена до чвора <math>v</math> path. <br />На овај начин се гради делимично суфиксно стабло <math>ST_{i+1}</math>. [[Датотека:Constructing the suffix tree of banana based on the suffix array and the LCP array - Case 2.pdf|thumb|400п|Случај 2 (<math>d(v) < H[i+1]</math>): Да би додали суфикс <math>nana\$</math>, на руб претходно убаченог суфикс <math>na\$</math> треба да се раздвоји. Нови руб интерног чвора је означен са најдужим заједничким префиксом суфикса <math>na\$</math> и <math>nana\$</math>. Руб повезује два листа са ''преосталим'' суфиксним карактерима који нису део префикса.]]
* <math>d(v) < H[i+1]</math>: То значи да уланчавање ознака на путу од корена до чвора <math>v</math> приказује мање карактера него најдужи заједнички префикс суфикса <math>A[i]</math> и <math>A[i+1]</math> и ''изгубљени'' карактери су садржани у рубној ознаци од <math>v</math>-тог ''најдеснијег'' руба. Тако да морамо ''раздвојити'' тај руб на следећи начинs: <br />Нека је <math>w</math> потомак од <math>v</math> у <math>ST_i</math> најдеснијем путу.
# Брисање руба <math>(v,w)</math>.
# 2. Додавање новог интерног чвора <math>y</math> и новог руба <math>(v,y)</math> са ознаком <math>S[A[i]+d(v),A[i]+H[i+1]-1]</math>. Нова ознака састоји се од ''несталих'' карактера најдужег заједничког префикса од <math>A[i]</math> и <math>A[i+1]</math>. Дакле, уланчавање ознака пута од корена до чвора <math>y</math> сада показује најдужи заједнички префикс од <math>A[i]</math> и <math>A[i+1]</math>.
# Спојити <math>w</math> на новонастали интерни чвор <math>y</math> од стране руба <math>(y,w)</math> који је означен са <math>S[A[i]+H[i+1],A[i]+d(w)-1]</math>. Нова ознака састоји се од ''преосталих'' знакова брисаног руба <math>(v,w)</math> који нису коришћени као ознака руба <math>(v,y)</math>.
# Додати <math>A[i+1]</math> као нови лист <math>x</math> и повезати га са новим интерним чвором <math>y</math> од стране руба <math>(y,x)</math> који је означен са <math>S[A[i+1]+H[i+1],n]</math>. Тако се ознака руба састоји од преосталих карактера суфикса <math>A[i+1]</math> који нису већ заступљени у уланчавању ознака пута од корена до чвора <math>v</math>.
# Тако добијамо делимично суфиксно стабло <math>ST_{i+1}</math>.

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

Чворови који су прелазили у кораку <math>i</math> прошавши ''најдеснијим'' путем <math>ST_i</math> (осим последњег чвора <math>v</math>) се уклањају из ''најдеснијег'' пута када је <math>A[i+1]</math> додан у стабло као нови лист. Овим чворовима се никада више неће проћи за све наредне кораке <math>j>i</math>. Тако да ће се готово увек проћи кроз <math>2n</math> чворова, укупно. 

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

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

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

== Референце ==
{{reflist|30em}}

== Спољашње везе ==
* [https://github.com/elventear/sais-lite-lcp Mirror of the ad-hoc-implementation of the code described in {{harvnb|Fischer|2011}}]
* [https://github.com/simongog/sdsl/ SDSL: Succinct Data Structure Library - Provides various LCP array implementations, Range Minimum Query (RMQ) support structures and many more succinct data structures ]
* [https://github.com/carrotsearch/jsuffixarrays/blob/master/src/main/java/org/jsuffixarrays/Traversals.java Bottom-up suffix tree traversal emulated using suffix array and LCP array (Java)]
* [http://code.google.com/p/text-indexing/ Text-Indexing project] (linear-time construction of suffix trees, suffix arrays, LCP array and [[Burrows-Wheeler Transform]])
{{Commonscat|LCP array}}

{{нормативна контрола}}

[[Категорија:Стабла (структуре података)]]
[[Категорија:Алгоритми]]