LCP низ

LCP низ
Тип	низ
Проналазач	Manber & Myers 1990
Временска и просторна сложеност у велико О нотацији
	Просечан случај	Најгори случај
Простор	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$
Време	${\mathcal {O}}(n)$	${\mathcal {O}}(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}\$$ и нека $\operatorname {lcp} (v,w)$ означава дужину најдужег заједничког прфикса између два стринга $v$ и $w$. Означимо додатно са $S[i,j]$ подниз од $S$ у распону од $i$ до $j$.

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

Пример

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

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]	$\bot$	0	1	3	0	0	2

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

Разлика између суфиксног низа и 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 вредности.

Manber & Myers 1993 ају алгоритам за рачунање LCP низа уз суфиксни низ у $O(n\log n)$ времену. Kärkkäinen & Sanders 2003 показују да је могуће модификовати њихово $O(n)$ време алгоритма, а да при том једнако добро израчунава LCP низ. Kasai et al. 2001 представљају први алгоритам у $O(n)$ времену, алгоритам (FLAAP), који израчунава LCP низ у односу на текст и суфиксни низ. Под претпоставком да је сваки текстуални симбол величине једног бајта и сваки улазак у суфиксни или LCP низ траје 4 бајта, главни недостатак њиховог алгоритма је то што је попуњен велики простор $13n$ бајтова, док изворни излаз (текст, суфиксни или LCP низ) заузима само $9n$ бајтова. Тако да је Manzini 2004 аправио бољу верзију алгоритма Kasai et al. 2001 (lcp9) и са којим је смањио количину попуњеног простора за $9n$ бајтова. Kärkkäinen, Manzini & Puglisi 2009дају један још бољи Kasai's алгоритам ($\Phi$-алгоритам) који побољшава потребно време. Уместо стварног LCP низа, овај алгоритам гради пермутовани LCP (PLCP) низ, у којем су вредности које се појављују у тексту у лексикографском поретку. Gog & Ohlebusch 2011 дају два алгоритма, који иако су спори у теорији ($O(n^{2})$), у пракси су доста бржи.

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

Апликације

Као што је наведено од стране Abouelhoda, Kurtz & Ohlebusch 2004 неколико проблема се може решити употребом следећих врста обилазака стабла:

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

Kasai et al. 2001 показују како симулирати одоздо према горе обилазак суфиксног стабла, коришћењем само суфиксног и LCP низа. Abouelhoda, Kurtz & Ohlebusch 2004 су побољшали суфиксни низ са LCP низом и додатном структуром података, и описали како се побољшани суфиксни низ може користити за симулацију сва три обиласка суфиксног стабла. Fischer & Heun 2007 смањује захтеве за простором од стране побољшаног суфиксног низа са предизрачунатим LCP низом за распон минималних упита . Дакле, сваки проблем који се може режити алгоритмом за суфиксно стабло, може се решити и са побољшаним суфиксним стаблом.

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

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

Проблем најдуже понављаног подниза за низ $S$ дужине $n$ може бити решен у $\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}\$$ дужине $n+1$, његогво суфиксно стабло $ST$ може се изградити у $O(n)$ времену, на темељу следеће идеје: Почнемо са делимичним суфиксним стаблом за лексикографски најмањи суфикс и затим убацујемо остале суфиксе по редоследу који нам је дат суфиксним низом.

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

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

Почнимо од $ST_{0}$, стабла које се састоји само од корена. За додавање $A[i+1]$у $ST_{i}$, прошетамо крајње десном путем са почетком у недавно додатом листу $A[i]$ па до корена, све док се не стигне до најдубљег чвора $v$ са $d(v)\leq 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.
  На овај начин се гради делимично суфиксно стабло $ST_{i+1}$.

  

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

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

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

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

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

LCP низ $H$ садржи само дужину најдужег заједничког префикса сваког пара суфикса у суфиксном низу $A$. Међутим, уз помоћ инверза суфиксног низа $A^{-1}$ ($A[i]=j\Leftrightarrow 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]$ може се израчунати на следећи начин: $\operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]$.

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

• 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)