LCP 어레이

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2012년 9월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍을 확인)

LCP 어레이
유형	어레이
발명자	Manber & Myers (1990)harvtx 오류: 대상 없음: CITREFManberMyers1990(도움말)
빅 O 표기의 시간 복잡성 및 공간 복잡성
평균 최악의 경우 공간 ${\displaystyle\mathcal {O}}(n)}$ ${\displaystyle\mathcal {O}}(n)}$ 건설 ${\displaystyle\mathcal {O}}(n)}$ ${\displaystyle\mathcal {O}}(n)}$

컴퓨터 과학에서 가장 긴 공통 프리픽스 배열(LCP 배열)은 접미사 배열의 보조 데이터 구조입니다.정렬된 서픽스 배열에서 연속되는 모든 서픽스 쌍 사이의 가장 긴 공통 프리픽스(LCP)의 길이를 저장합니다.

예를 들어, A : =aab [ , , , , ]가 접미사 배열인 경우 A[1] =와 A[2] = 사이의 가장 긴 공통 접두사는 길이가 1이므로 LCP 배열 H에서 H[2] = 1입니다. 마찬가지로 A[2] = 및 A[3] = H3의 LCP는 다음과 같습니다.

서픽스 어레이를 LCP 어레이로 증강하면 서픽스 ^[1][2]트리의 하향식 및 상향식 트래버설을 효율적으로 시뮬레이션하여 서픽스 어레이의^[3] 패턴 매칭을 고속화할 수 있으며 압축 서픽스 ^[4]트리의 전제 조건이 됩니다.

역사

LCP 배열은 1993년 ^[3]Udi Manber와 Gene Myers가 문자열 검색 알고리즘의 실행 시간을 개선하기 위해 접미사 배열과 함께 도입했습니다.

정의.

A$(\displaystyle$ A$)$를 문자열$$$S{\displaystyle }$ ${\displaystyle =}$ ${\displaystyle {}_{}{}_{}{1\mathrm{}}_{}}$, s${\displaystyle {}_{}{2\mathrm{}}_{}}$, ${\displaystyle ...s_{}}$ n$$-${\displaystyle {}_{}\mathrm{}{1}_{}}$$(\$displaystyle$ S$=s_{1}, s_{2},\ldots$s_{$n-1$$\}\backslash \$)$의 접미사 배열로 $합니다{\displaystyle }$. 여기서$$$(\$displaystyle \$)$는 고유하고 사전학적으로 작은 문자입니다.$S{\displaystyle }$[${\displaystyle i}$ , $]{$ $display$S [$i$ , $j$]{ display S }는$,$ i { $style$i$$ } $~j$ { display $style$j$\}$ 의 서브스트링을 $나타냅니다.$따라서 S${\displaystyle }$[${\displaystyle A}$ [ ${\displaystyle i]}$ , $]{$ $displaystyle$S [$A$ [ i$$] , $n$}는 S$${ $displaystyle$$$S$\}$의$i번째$ $최소 접미사$입니다.

${\displaystyle \mathrm{lcp}}$ ${\displaystyle (}$ (${\displaystyle v}$ ,${\displaystyle w}$) { $displaystyle$ $\operatorname {lcp$} ($v$ , $w$) denote$$ 、 2 $string{\displaystyle }$v [ $style$ $v$$$]와 w$${ $display$ w$\}$ 사이의$$ 가장 긴 공통 프레픽스의 길이를 나타냅니다.그러면 LCP $배열$H [$n$$]$는 $다음$과 같은 $크기$의 $정수{\displaystyle }$ 배열입니다$.$$Tyle$ H$[1]}$는 정의되지 $않았으며{\displaystyle }$ H${\displaystyle }$[$=$ lcp ${\displaystyle \mathrm{cp}}$(${\displaystyle }$S [${\displaystyle A}$ [${\displaystyle i}$- ${\displaystyle 1]}$ , ${\displaystyle n]}$ , S [ ${\displaystyle i}$ , ${\displaystyle n}$ ){ $display style$H [ i ]= \$operatorname {lcp$} ( S [$A$ [ i - 1 ] , $n$] ) ,$[ A$ [ $i ]$ , n$$ ]、 < in \ $displaystyle 1$ < i \ $leq$ n 。$따라서{\displaystyle }$H [ $]$ \ $displaystyle$$$H [$$i$]$는 사전 편찬상$가장{\displaystyle }$ 작은 접미사의 가장 긴 공통 접두사 $길이$와 접미사 배열의 이전 접미사를 저장합니다.

LCP 배열과 접미사 배열의 차이:

• 접미사 배열: 배열의 각 접미사의 사전 순위를 나타냅니다.
• LCP 어레이:사전 편집에 따라 정렬된 후 연속된 두 접미사 간의 최대 길이 접두사 일치가 포함됩니다.

예

${\displaystyle \text{문자열}}$ S ${\displaystyle =}$banana$$(\$ S$=snatextrm {display$

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

및 대응하는 정렬된 접미사 $배열{\displaystyle }$ A$(\style$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
S[A[i], n][1]	$	a	a	a	b	n	n
S[A[i], n][2]		$	n	n	a	a	a
S[A[i], n][3]			a	a	n	$	n
S[A[i], n][4]			$	n	a		a
S[A[i], n][5]				a	n		$
S[A[i], n][6]				$	a
S[A[i], n][7]					$

다음으로 LCP $배열{\displaystyle }$H(\$displaystyle$ H$)$를 사전 편집적으로 연속되는 서픽스를 비교하여 가장 긴 공통 프레픽스를 결정합니다.

i	1	2	3	4	5	6	7
H[i]	정의되어 있지 않다	0	1	3	0	0	2

$예$를 들어${\displaystyle ,}$ ${\displaystyle \mathrm{H}}$ [${\displaystyle }$4 ]$=$3 { $displaystyle H$ [ 4 $]=$ 3 { $displaystyle$ H [ 4$$]=${\displaystyle \mathrm{S}}$ [${\displaystyle 4}$, 7 ]=${\displaystyle \text{ana}}$ $$$ { $displaystyle A$ [$3 ]=$S [${\displaystyle }$4 , 7 ]= ana $$$ ${\displaystyle =}$ $4$. $textrmana$${\displaystyle ]}$의 ${\displaystyle \text{길이}}$가 됩니다.사전 편집상 작은 서픽스가 없기 때문에${\displaystyle }$H [ $]$ { $style$H [ $1$}는 $정의$되어 있지 않습니다.

효율적인 구축 알고리즘

LCP 배열 구축 알고리즘은 접미사 배열의 부산물로 LCP 배열을 계산하는 알고리즘과 LCP 값을 계산하기 위해 이미 구성된 접미사 배열을 사용하는 알고리즘의 두 가지 범주로 나눌 수 있습니다.

Manber & Myers(1993)는 서픽스 배열과 함께 LCP 배열을 O${\displaystyle (n}$ log${\displaystyle n}$n $)\style$ O$(n\log$ n$)$ 시간으로$$ $계산$하는 알고리즘을 제공합니다.Kérkaiinen & Sanders(2003)는 LCP 어레이도 계산하도록 $)\display style$ O$(n)$ 시간$$ 알고리즘을 변경할 수 있음을 보여준다.카사이 등 (2001)는 텍스트와 서픽스 배열에 따라 LCP 배열을 계산하는 첫 $번째{\displaystyle }$O${\displaystyle }$( n$$) \ $displaystyle$O ($n$ ) Time$$ Algorithm (FLaAP )를 $제시$합니다.

각 텍스트 기호가 1바이트이고 서픽스 또는 LCP 배열의 각 엔트리가 4바이트라고 가정할 때 알고리즘의 주요 단점은 $(텍스트$, 서픽스 배열, LCP 배열)의 $용량$이 $(표시$ $스타일$ $9n)$바이트에 불과하다는 것입니다.따라서 Manzini(2004)는 Kasai 등의 알고리즘을 개량한 버전을 만들었다. (2001) (lcp9) 및 공간 점유율을 $(\displaystyle 9n)$ $바이트$로 줄였습니다.Kérkkaiinen, Manzini 및 Puglisi(2009)는 Kasai 알고리즘$(δ$\displaystyle $\Phi }$ - algorithm$$)을 개선하여 실행 시간을 향상시킵니다.이 알고리즘은 실제 LCP 배열이 아닌 permated LCP(PLCP; 치환 LCP) 배열을 구축합니다.이 배열에서는 값이 사전 순서가 아닌 텍스트 순서로 표시됩니다.

Gog & Ohlebusch(2011)는 이론적으로는 느리지만(${\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$2$)\display style$ O$(n^{2$ 실제로는 위의 알고리즘보다 빠르다는 두 가지 알고리즘을 제공한다.

2012년 현재^[update] 가장 빠른 선형 시간 LCP 어레이 구축 알고리즘은 Fischer(2011년)에 의한 것이며, 이는 Nang, Zhang & Chan(2009)의 가장 빠른 서픽스 배열 구축 알고리즘(SA-IS) 중 하나에 기초하고 있습니다.유타 모리의 DivSufSort를 기반으로 한 Fischer & Kurpicz(2017)는 더욱 빠르다.

적용들

Abouelhoda, Kurtz & Ohlebusch(2004)가 지적한 바와 같이 다음과 같은 종류의 트리 트래버설을 통해 몇 가지 문자열 처리 문제를 해결할 수 있습니다.

• 완전한 서픽스 트리의 상향식 트래버설
• 서픽스 트리의 서브트리의 톱다운 트래버설
• 서픽스 링크를 사용하여 서픽스 트리를 트래버설합니다.

카사이 등 (2001)에서는 서픽스 배열과 LCP 배열만을 사용하여 서픽스 트리의 상향식 트래버설을 시뮬레이트하는 방법을 보여 줍니다.Abouelhoda, Kurtz 및 Ohlebusch(2004)는 LCP 배열 및 추가 데이터 구조를 사용하여 서픽스 배열을 확장하여 이 확장 서픽스 배열을 사용하여 3종류의 서픽스 트리 트래버설을 모두 시뮬레이트하는 방법을 설명합니다.Fischer & Heun(2007)은 범위 최소 쿼리에 대해 LCP 어레이를 전처리함으로써 확장 접미사 어레이의 공간 요건을 줄입니다.따라서 확장 접미사 ^[2]배열로 서픽스 트리 알고리즘으로 해결할 수 있는 모든 문제도 해결할 수 있습니다.

$m$의 $패턴{\displaystyle }$ P$(\$$displaystyle$ P$)$가 $n$의 $문자열{\displaystyle }$ S$(\$$displaystyle$$$S$)$의 서브스트링인지 판단하려면 서픽스 배열만 사용하는 경우 $(m$$$log ${\displaystyle }$ $)$ 시간이 $걸립니다$.또한 LCP 정보를 사용함으로써 이 바인드를 O${\displaystyle (}$^[3]${\displaystyle m}$ ${\displaystyle +}$ log ${\displaystyle n}$n$display style$ O$(m+\log$ n$)$ 시간으로$$ $개선$할 수 있습니다.Abouelhoda, Kurtz & Ohlebusch(2004)는 최적의 $)\displaystyle$ O$(m)$ 시간을$$ 달성하기 위해 이 실행 시간을 더욱 향상시키는 방법을 보여줍니다.따라서 서픽스 배열 및 LCP 배열 정보를 사용하면 서픽스 트리를 사용하는 것처럼 신속하게 결정 쿼리에 응답할 수 있습니다.

LCP 배열은 압축된 접미사 트리의 필수적인 부분이기도 합니다.접미사 트리 기능은 접미사 링크 및 가장 낮은 공통 상위 ^[5][6]쿼리와 같은 완전한 접미사 트리 기능을 제공합니다.또한 접미사 배열과 함께 사용하여 O${\displaystyle }$(${\displaystyle n}$) \ $displaystyle$O ($n$ )$시간$으로 ^[2][7][8][9]Lempel-Ziv LZ77 인수분해를 계산할 수 있습니다.

$길이{\displaystyle }$$n$(\$displaystyle$ n)의$$문자열 S$(\$displaystyle S$)$에 대해 가장 오래 반복되는 서브스트링 문제는 $접미사{\displaystyle }$ 배열$$A(\$displaystyle$A$$)와 LCP 배열 모두를 $사용$하여 ${\displaystyle \delta (}$n$)\displaystyle\Theta(n)$로 해결할 수 있습니다.LCP 어레이의 최대값 v ${\displaystyle m_{}}$ a ${\displaystyle x_{}}$ ${\$ 및$$ v ${\displaystyle m_{}}$ ${\displaystyle x_{}}${\$displaystyle v_{max}$가 저장되어 있는 대응하는 $인덱스{\displaystyle }$i {\$display$ i$}$를 찾으려면 LCP 어레이를 통해 선형 스캔하면 됩니다.최소 2회 발생하는 가장 긴 서브스트링은 $S{\displaystyle }$[${\displaystyle A}$ [${\displaystyle i}$ ${\displaystyle ]}$ ,${\displaystyle A}$ [ ${\displaystyle i]}$ + ${\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\displaystyle a_{}}$x - $]{$ $display style$ S [ $A$[ $i$],$A$[$i$] +$v$ _ {$max }$ - 1$$。

이 섹션의 나머지 부분에서는 LCP 어레이의 다음 두 가지 애플리케이션에 대해 자세히 설명합니다.문자열의 서픽스 배열과 LCP 배열을 사용하여 대응하는 서픽스 트리를 구축하는 방법 및 LCP 배열의 범위 최소 쿼리를 사용하여 임의의 서픽스에 대한 LCP 쿼리에 응답하는 방법.

패턴 발생 횟수 찾기

이 문서는 Wikipedia의 품질 기준을 충족하기 위해 청소가 필요할 수 있습니다.구체적인 문제는 이 섹션은 StackOverflow 응답의 스트레이트 카피이므로 질문에 대한 응답 형식으로 되어 있다는 것입니다. 가능하다면 이 문서의 개선에 협조해 주십시오.(2016년 6월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

$텍스트{\displaystyle }$ T$($$길이{\displaystyle }$ N$)(길이$ N(\$displaystyle$ N$)$^[3]에서 특정 $문자열{\displaystyle }$ P$($$길이{\displaystyle }$ m$\displaystyle$ P$)(\$$displaystyle$ m$)$의 발생 횟수를 찾으려면 ,

• T$${\$displaystyle$ T$}$의 접미사 배열에 대해 이진 검색을 사용하여 모든 P$${\$displaystyle$ P$\}$의 $시작{\displaystyle }$ 및 끝 위치를 찾습니다.
• 검색 속도를 높이기 위해 LCP 어레이, 특히 LCP 어레이의 특수 버전(아래 LCP-LR)을 사용합니다.

표준 바이너리 검색(LCP 정보 없음)을 사용할 때의 문제는 실행해야 $하는{\displaystyle }$ 각 O${\displaystyle (\log n}$N$)\displaystyle$ O$(\log$ N$)$ 비교에서$$ P를 서픽스 배열의 현재 엔트리와 비교한다는 것입니다.즉, 최대 m자의 문자열 전체를 비교합니다.복잡도는 $O{\displaystyle }$ (${\displaystyle m}$ ${\displaystyle \log }$ ${\displaystyle n}$N )$${ $displaystyle$O ($m$ \ $log$ N$$)$$} 입니다.

LCP-LR 어레이는 다음과 같은 방법으로${\displaystyle O(m}$ + log${\displaystyle n}$N${\displaystyle }$)\$displaystyle O(m$+\$log$ N$)$로 개선합니다.

바이너리 검색 알고리즘의 어느 시점에서도, 종래와 같이 접미사 배열의 범위$L, …,$ $)$와 그 $중심점{\displaystyle }$ M$(\$$displaystyle$ M$)$을 고려하여 왼쪽 서브 범위$L,$ ${\displaystyle \dots ,}$ $,$ $오른쪽)$에서 검색을 계속할지를 결정합니다.${\displaystyle }$, ${\displaystyle ...}$ , ${\displaystyle R}$)$${$displaystyle (M,\dots,R)$。판정을 위해 P$(\displaystyle$ P$)$를$$M(\$displaystyle$ M$)$의 문자열과 $비교$합니다.P$(\displaystyle$ P$)$가 M$(\displaystyle$ M$)$과 동일한 경우 $검색$이 완료됩니다${\displaystyle .}$그러나 그렇지 않은 경우$P$의 첫 $k자$({$displaystyle$P$})$를 비교한 후$$P({$displaystyle$ P$$$}$가 사전 편찬적으로$$M({$displaystyle$M$\})$보다 작은지 $큰지{\displaystyle }$ $판단$하였습니다$.$다음 단계에서는 (${\displaystyle M,\dots ,}$ $)$ {$displaystyle(M,\dots,R)}$과(와) 새로운 $중심점{\displaystyle {}^{}}$ M ${\${$displaystyle$ M'}을$($를) 고려합니다$.{\displaystyle }$

M ........ M' ....알고 있는 R: lcp(P,M)==k

여기서 문제는 O${\displaystyle (}$1$)\displaystyle$O($1)-$lookup이$$ $M{\displaystyle }$$(\displaystyle$ M$$$)$ 및 $(\$ M$\text{'}\},$ ${\displaystyle \mathrm{c}}$ ${\displaystyle \mathrm{p}({}^{,}}$ M$)\displaystyle \mathrm {lcp}(M, M,$ M)의 가장 긴 공통 프레픽스를 나타내도록 LCP-LR이 미리 계산된다는 것입니다$.$

$($이전 $단계$에서) M {\$displaystyle$ M$}$ 자체의$$ 접두사가$$$P{\displaystyle }${{$displaystyle$$$P$\}$ : ${\displaystyle \mathrm{l}}$ c${\displaystyle \mathrm{p}}$ (${\displaystyle P}$ ,${\displaystyle M}$ ) $k$ { $displaystyle$\$mathrm${$lcp$} ($P$, M ) $=$k $\}$ 의 $3{\displaystyle }$ 개의$$ 문자가 $있습니다{\displaystyle }$.

• 사례 1:k<>l cp(M, M′){\displaystyle k<, \mathrm{lcp}(M,M의)}, 즉 P{P\displaystyle}. 이 M의(k+1)-th 성격'을 의미하는 그 M의, 그리고 이후 P사전 편찬 상. M보다 크면, 그 사전 편찬 상.보다 더 커야만 한다 같은 상식에서 M으로 적은 접두사 문자보다 MM'와 공통점만 가지고 있다.M'too. 오른쪽 절반(M', ...R)으로 계속 진행합니다.
• 사례 2:k>l cp(M, M′){\displaystyle k>, \mathrm{lcp}(M,M의)}, 즉 P{P\displaystyle}공통적으로 M{M\displaystyle}과 더 많은 접두사 문자보다 M{M\displaystyle}공통적으로 M′{\displaystyle M의}과 맺고 있다. M.에 결과적으로, 만약 우리가 비교할 P{P\displaystyle}′ $(\displaystyle$ M$\text{'}),$ 공통 접두사는 k$(\displaystyle$ k$)$보다 $작고{\displaystyle {}^{}}$ M$(\$ M$\text{'})$은 사전 편찬상$$P(\$displaystyle$ P$)$보다 크므로 실제로 비교하지 않고 왼쪽 절반$,$ ${\displaystyle \dots ,}$ $)으로 계속 진행합니다.$
• 케이스 3: $k{\displaystyle }$ ${\displaystyle =}$ ${\displaystyle l\mathrm{}}$ ${\displaystyle \mathrm{c}\mathrm{p}}$ (${\displaystyle M}$ , ${\displaystyle {}^{}}$ ${\displaystyle \prime }$) { $displaystyle$ k = \ $mathrm${$lcp$} ($M$ , $M$' )$$} 。따라서 M과 M'은 모두 첫 $번째{\displaystyle }$k { $displaystyle$ k$}$자의$$P { $displaystyle$ P$}$와 동일합니다.왼쪽 절반으로 계속할지 오른쪽 절반으로 계속할지 결정하려면 (${\displaystyle k}$ ${\displaystyle +}$1)$(k+1)$번째$$${\displaystyle }$문자부터 $시작$하여 P$(\displaystyle$ P$)$와 M$(\$ M$')$을 $비교$하면 됩니다.
• 우리는 반복적으로 계속한다.

전체적인 효과는 P$(\displaystyle$ P$)$의 문자가 텍스트의 어떤 문자와도 두 번 이상 비교되지 않는다는 것입니다.문자 비교의 총수는 m$${\$displaystyle$ m$\}$으로 제한되어 있기 때문에 총 복잡도는 $실제로{\displaystyle }$ O${\displaystyle (m}$ + ${\displaystyle l}$ ${\displaystyle g}$ N$)$ {\$displaystyle$ O$(m+logN$ 입니다.

서픽스 배열의 임의의 2개의 엔트리 사이의 lcp를${\displaystyle }$O($)\displaystyle$O(1)의$$ $시간$으로 알 수 있도록 LCP-LR을 미리 계산해야 합니다.표준 LCP 배열에서는 연속되는 엔트리의 ${\displaystyle \mathrm{lcp}}$만 얻을 수 있습니다.${\displaystyle \mathrm{즉}}$, i\$displaystyle$ i${\displaystyle \backslash }$$display$$\mathrm {lcp}(i-1,i)$는 $임의$의$i$\displaystyle i$\}$에 대해 사용할 수 있습니다.다만, 상기의 설명에 기재된 M$\$$displaystyle$M과 $M$은$$반드시 연속되는 것은 아닙니다.

여기서 중요한 것은 바이너리 검색 중에 특정 범위$({\displaystyle L}$ ${\displaystyle ,}$ ${\displaystyle ...}$ ,$)(\displaystyle$ (L$,\dots,$R$$))만 발생한다는 것을 인식하는 것입니다.항상 ($,$ $N)$으로${\displaystyle }$시작하고 중앙에서 분할한 후 왼쪽 또는 $오른쪽$으로 반복하여 절반씩 분할합니다.다른 관점에서 보면: 서픽스 배열의 모든 엔트리는 바이너리 검색 중 정확히 하나의 가능한 범위의 중앙점으로 발생합니다.따라서 바이너리 검색 중에 역할을 할 수 있는 N개의 고유 범위$({\displaystyle L}$ …${\displaystyle M}$ …${\displaystyle R}$)(\$displaystyle (L\dots$ M$\dots$ R$))$가 있습니다.이러한 범위에서는 ${\displaystyle \mathrm{l}}$p ${\displaystyle (L,}$ M$)$와 l ${\displaystyle \mathrm{p}}$(\displaystyle \$mathrm$${lcp}$ ($L$$,$ $)$를 사전에 $계산$할 수 있습니다${\displaystyle .}$레인지즉, $({displaystyle 2N})$의 값이 미리 계산된 $것$이므로 LCP-LR의 $크기$는 O$)\displaystyle$ O$(N)$입니다.

또한 표준 LCP 어레이에서 LCP-LR의 $2N(\$$displaystyle$ 2N$)$ $값$을 O$(N$$)$ 시간 $단위$로 계산하는 간단한 재귀 알고리즘이 있습니다.

정리하면:

• LCP-LR은 LCP에서${\displaystyle }$O ($)$ {\$displaystyle$O ($N)}$ 시간$$ 및${\displaystyle }O{\displaystyle }$ (${\displaystyle \mathrm{2N})}$ $=$ ($)$ {\$displaystyle$O ($2N$)=$O (N)}$ 공간으로$$ $계산$할 수 있습니다.
• 바이너리 검색 중에 LCP-LR을 사용하면 검색 절차를 O$M$ log${\displaystyle n}$N$$${\displaystyle )(\{\mathrm{displaystyle}}$ O$(M\log$ N$)}$에서 O${\displaystyle (M}$ + ${\displaystyle l}$ g $)({displaystyle$ O$(M+log$ N$)\})$로 가속화할 수 있습니다.
• 2개의 바이너리 검색을 사용하여 P$\backslash$$displaystyle$P의 $일치{\displaystyle }$ 범위의 왼쪽 끝과 오른쪽 끝을 판별할 수 있습니다.일치 범위의 길이는 P의 발생 횟수에 대응합니다.

접미사 트리 구성

$문자열{\displaystyle }$ S $=$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}{}_{}{2\mathrm{}}_{}}$,${\displaystyle s_{}\mathrm{}}$n$$$ { $displaystyle S_{1}, s_{2},$$$\$ldots s_{n$$}\$$의 접미사 $배열{\displaystyle }$A(\$displaystyle$ A$)$와 LCP $배열{\displaystyle }$H(\$displaystyle$ H$)$를 지정하면${\displaystyle }$해당 접미사 $트리{\displaystyle }$ $(\displaystyle$$$S)가 될 수 있습니다.다음 아이디어를 기반으로 합니다.사전 편집상 가장 작은 접미사에 대한 부분 접미사 트리에서 시작하여 접미사 배열에서 지정된 순서대로 다른 접미사를 반복해서 삽입합니다.

${\displaystyle {}_{}}$ $(\$$displaystyle$ $ST_{i})$를 0${\displaystyle i}$ i${\displaystyle }$n$(\displaystyle$ 0$\leq$ i$\leq$ n$)$의 부분 서픽스 트리로 합니다.$또한{\displaystyle }$ d$(v)$는 S $(\$$\}$ $노드$의 루트에서$vstyle$로의 모든 경로 라벨 연결 길이입니다.

루트만으로 ${\displaystyle {구성}_{}}$된 트리인 S ${\displaystyle {}_{}}$ 0$(\$ ST_${0$부터 시작합니다.${\displaystyle A_{}}$${\displaystyle }$[${\displaystyle i}$ + $]{$ $display$ A$$[$i$ + $1$]{ $display$ style $ST$_ {$i$${\displaystyle <img\; alt="ST\_\{i\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/67895a931fd5224590fb79d606c4758536e29112"\; style="vertical-align:\; -0.671ex;\; width:3.656ex;\; height:2.509ex;">}$} } $s$ 、 최근 삽입된 $리프{\displaystyle }$A [ ${\displaystyle i}$$]$에서 시작하여 루트까지 오른쪽 끝에 있는 $경로{\displaystyle }$($display style$ v$)$가 d$v$ ${\displaystyle \le }$ ${\displaystyle H[}$ $display$1 ( \ $display style$ d$)$로 이동합니다.

다음 두 가지 경우를 구분할 필요가 있습니다.

• $]{$$H [ i$ + $1$ : 루트$$투 ${\displaystyle }$ \ $display style$ v$$equals$$ equals equals equals equals equals equals onatenatenatenatenatenatenatenA ${\displaystyle [}$i $]{$ $display style$A [ ${\displaystyle i}$ $]및$${\displaystyle }$A [${\displaystyle i}$ + $]{$ $display style$A [$i$ + $1$의 가장 긴 공통 프레픽스입니다.
  이 경우${\displaystyle }$A$$[ i + 1$$$]{$ $displaystyle$ A $[ i$+ $1$]{ $displaystyle$ v$$}의 새로운 $리프{\displaystyle }$ x { $displaystyle$ x$$}로서$$$$$$ $삽입$하고 가장자리 $({\displaystyle }$${\displaystyle v}$ ${\displaystyle ,x}$ $){$ $displaystyle (v , x$ ){$displaystyle$(v , x )}에 S [${\displaystyle }$i${\displaystyle }$+$1$$],$n의 $라벨$을 $붙입니다.$$H[i+1],n$ 따라서 엣지 라벨은 루트 ${\displaystyle }$v$경로$의 라벨 연결로 표현되지 않은 $접미사{\displaystyle }$A [${\displaystyle i}$+ $]$ {{$displaystyle$ A$[i+1]}$의 나머지 문자로 구성됩니다.
  그러면 부분 $서픽스{\displaystyle }$ ${\displaystyle {}_{}}$가${\displaystyle S_{}}$ ${\displaystyle {\mathrm{Ti}}_{}}$+ 1(\$displaystyle ST_{i+$1$\})$로 생성됩니다.
  

  케이스 2 ( () < [ + $]{$ $displaystyle$d ($v$ ) <$H{\displaystyle }$$[ i$ + $1$] } : ${\displaystyle \mathrm{접미사n}}$ a$$$ a \ $displaystyle$ na \$$$ 를 추가하려면 이전에 삽입한 ${\displaystyle \mathrm{접미사n}}$ a$$$ \ $displaystyle$ na \ $$$ 에지를$$ 분할해야 $합니다$.새로운 내부 노드에 대한 새로운 엣지에는 ${\displaystyle \mathrm{접미사n}}$ a$$\displaystyle$ na$\$$ 및$$ ${\displaystyle \mathrm{nn}}$ a $$\displaystyle$ na$\backslash \$$ 중 가장 긴 공통 프레픽스로 라벨이 부착되어 있습니다.두 leaf를 연결하는 엣지에는 프레픽스의 일부가 아닌 나머지 서픽스 문자가 라벨이 부착되어 있습니다.
• $]{$$v$$H [i+1]$: 루트 투$$v {$display$ $}$ 경로의$$$$ 라벨이 연결된 경우 $접미사{\displaystyle }$A [$i ]$ 및 $A{\displaystyle }$[${\displaystyle i}$+ $1 ]$의 $가장{\displaystyle }$ 긴 공통 접두사보다 적은 문자가 표시되며 누락된 문자가 $vstyle$ v$$엣지에 포함되어 있음을 의미합니다$.$오른쪽 끝따라서 이 에지를 다음과 같이 분할해야 합니다.
  ${\displaystyle {}_{}}$$\displaystyle$w를$$ S $\$의 가장 오른쪽 경로에 $있는{\displaystyle }$ v$\displaystyle$v의$$ $자식$이라고 $합니다{\displaystyle }$.

1. 가장자리$({\displaystyle }$ ${\displaystyle v}$,${\displaystyle w}$) {$display ( v$ ,$w$ ) $\}$ 를 삭제합니다.
2. $라벨{\displaystyle }$S [${\displaystyle A}$ [ ${\displaystyle i]}$ +${\displaystyle d}$ (${\displaystyle v}$) ${\displaystyle 、}$ A${\displaystyle }$[ ${\displaystyle \mathrm{i}}$] +${\displaystyle }$D ( ${\displaystyle v}$ ) 、 ${\displaystyle A}$ [ i + 1$]$ -${\displaystyle 1}$ { $display style$S [$A$ [ $i$]+$d$ ($$$v$$$)의 새로운 내부 $y$와$$ 새로운${\displaystyle }$엣지 (${\displaystyle }$v $,$ $y )$를 추가합니다.$A[i]+H[i+1]-1$새 라벨은 A${\displaystyle }$[ $]$ { $displaystyle$A [ $i$] $a$ a${\displaystyle }$aA [ i${\displaystyle }$] a a ${\displaystyle \mathrm{aA}}$ [ $i$+ 1$$]{ $displaystyle A$[ i + 1$$]}$$$a{\displaystyle }$ the the the ofersersersersersersersersersersersersersersersersersersersersersers of of of of of of of of of of따라서 루트 투$\displaystyle$ y$$ 경로의 라벨을 연결하면 A${\displaystyle }$[ $]$ \$displaystyle$A [ i$$]$및$ A${\displaystyle }$[${\displaystyle i}$ + $]$ \$displaystyle$A [$i$ + $1$의 가장 긴 공통 프레픽스가 표시됩니다.
3. $새로$ 생성된 내부 $y$에 S${\displaystyle }$[ ${\displaystyle A}$[ ${\displaystyle i]}$ + ${\displaystyle H}$[${\displaystyle i}$ + ${\displaystyle 1],}$ ${\displaystyle A}$[${\displaystyle i}$$$${\displaystyle ]}$ +${\displaystyle d}$ (${\displaystyle w}$) - 1 { $displaystyle$$$S $[$$A$ [ i ]+ 1$]$로$$w {$displaystyle$$$w$$}를 $연결$합니다.$H[i+1], A[i]+d(w)-1$새 라벨은 삭제된 에지$({\displaystyle }$ v ,${\displaystyle }$w$$)의 나머지 문자(${\displaystyle v}$${\displaystyle }$, w ) \$displaystyle ( v$ , w ) \displaystyle ($$v , w$$) \$displaystyle$ (${\displaystyle }$v , y ) \display$$ ( v ,$y$ )$$} )로 구성됩니다.
4. $A{\displaystyle }$[${\displaystyle i}$ + $]{$ $style$A [$i$ + $1$]{ $display$ $style$ x$$}{ $display style$$y$}의$$$$$$ 새로운 $내부{\displaystyle }$ $노드$에 S${\displaystyle }$[ $A$[${\displaystyle i}$ + $1$ ${\displaystyle H}$[$i$ + 1$$$],$${\displaystyle }$엣지 ($y$ , x$)$로 연결합니다$.$$H[i+1],n$ 따라서 엣지 라벨은 루트 ${\displaystyle }$v$경로$의 라벨 연결로 표현되지 않은 $접미사{\displaystyle }$A [${\displaystyle i}$+ $]$ {{$displaystyle$ A$[i+1]}$의 나머지 문자로 구성됩니다.
5. 그러면 부분 $서픽스{\displaystyle }$ ${\displaystyle {}_{}}$가${\displaystyle S_{}}$ ${\displaystyle {\mathrm{Ti}}_{}}$+ 1(\$displaystyle ST_{i+$1$\})$로 생성됩니다.

단순한 상각 인수는 이 알고리즘의 실행 시간이 O${\displaystyle }$(${\displaystyle n}$ $)\displaystyle$O ($n$ )로$$$제한됨$을 나타냅니다.

$i$에서 (마지막 $노드{\displaystyle }$v(\$displaystyle$ v$)$를 ${\displaystyle {}_{}}$하고) S$$의 $오른쪽{\displaystyle }$ 끝에 있는 $경로$를 걸어 올라가 횡단한 노드는 A${\displaystyle }$[${\displaystyle i}$+${\displaystyle 1}$$](\$$displaystyle$ A$[i+1])$가 트리에 새 리프로 추가되면 $오른쪽{\displaystyle }$ 경로에서 삭제됩니다.이러한 노드는 이후의 모든 > \ $displaystyle$ j $> i$ 에서는 다시 통과하지 않습니다.따라서 $최대{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{2n개}}$의$노드$가 모두 통과합니다.

임의 접미사에 대한 LCP 쿼리

LCP $배열{\displaystyle }$H {\$style$ H$}$에는 $접미사{\displaystyle }$ 배열$$A {\$displaystyle$ A$\}$의 모든 연속된 접미사 쌍 중 가장 긴 공통 접두사 길이만 $포함$됩니다. 단, 역접미사${\displaystyle {}^{}}배열{\displaystyle {}^{}}$ A$$- ${\displaystyle 1^{}}$ {\$displaystyle$${\displaystyle {}^{}}$A $-$${\displaystyle 1{}^{}}$} $$(${\displaystyle A}$[${\displaystyle }$] ${\displaystyle =}$ $= Istyledisplay$$ow$ A$^{-1}[j]=i$ 즉$S$의 $위치{\displaystyle }$$$j({$displaystyle$$$S})에서$$ 시작하는 $접미사{\displaystyle }$S [$j$ S$[$$j,n])$는$$최소 디스플레이$$스타일의 쿼리에서 $A{\displaystyle {}^{}}$-${\displaystyle {}^{}{1}^{}}$ [$]({displaystyle$ A$^{-1}[j$$][$j$])$ 위치에 $저장$됩니다.e: 임의 접미사의 가장 긴 공통 접두사 길이를${\displaystyle }$O ($)(\displaystyle$O(1) 시간으로$$ $결정$합니다.

접미사 배열의 사전적 순서에 $따라{\displaystyle }$ 접미사${\displaystyle }$S [${\displaystyle i}$, n$$] { $displaystyle S$[ i , n$$} 및${\displaystyle }S$ [${\displaystyle j}$ , $]$ { $displaystyle$S [$j$ , n ]{ $displaystyle$ S$$[ j , n$$]의 모든 접미사 $배열{\displaystyle {}^{}}$ A${\displaystyle {}^{}}$-${\displaystyle {}^{}{1}^{}}$[ $]$의 위치 사이의 $공통{\displaystyle }$ 접두사여야 합니다$.$${\displaystyle }$접미사 $배열{\displaystyle {}^{}}$A - ${\displaystyle 1^{}}$[ $]{$ $displaystyle$ A^ { - $1$}[ $j$ { displaystyle j$\}$의 위치$.$따라서 이들 서픽스가 공유하는 최장 프리픽스의 길이는 H${\displaystyle }$[${\displaystyle {}^{}}$ ${\displaystyle {-}^{}{1}^{}}$ [ ${\displaystyle i]}$ +${\displaystyle {}^{}}$,${\displaystyle {}^{}}$A -${\displaystyle {}^{}{1}^{}}$ [${\displaystyle j}$ $]{$ $displaystyle$H [ A$$^ { - $1$} [ $i$]+$1, A^$ { - 1 ][ $j$]}$$의 $최소값$입니다.이 값은 범위 최소 쿼리에 대해$$H(\$displaystyle$ H$)$가 사전 처리되는 $경우{\displaystyle }$ 일정 시간 내에 찾을 수 있습니다.

$따라서{\displaystyle }$ $문자열{\displaystyle }$$S{\displaystyle }$$(\displaystyle$ n)와$$문자열$$S$$$$(\$displaystyle$ i,$j)$의$$2개의$$$$ 의 위치 i${\displaystyle (\backslash \mathrm{displaystyle}}$ S)가 A - [A - [ j$])$로 $지정$됩니다.\$displaystyle A^$ { - 1 [ i]<$A^{-1$$j],$ $접미사{\displaystyle }$S[$]({displaystyle$ S$[i,$ n$])$ 및$$ $]({displaystyle$ S$[j, n$])의$$ 가장 긴 공통 프리픽스의 길이는 다음과 같이 계산할 수 있습니다. ${\displaystyle \mathrm{LCP}}$δ(${\displaystyle {}^{},j}$) ${\displaystyle =H}$ [${\displaystyle \mathrm{RMQ}}$ ${\displaystyle {}_{}}$1 -${\displaystyle {}^{}\mathrm{n}]}$$H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,$ $A^{-1}[j$

메모들

레퍼런스

• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). "Replacing suffix trees with enhanced suffix arrays". Journal of Discrete Algorithms. 2: 53–86. doi:10.1016/S1570-8667(03)00065-0.
• Manber, Udi; Myers, Gene (1993). "Suffix Arrays: A New Method for On-Line String Searches". SIAM Journal on Computing. 22 (5): 935. CiteSeerX 10.1.1.105.6571. doi:10.1137/0222058. S2CID 5074629.
• Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science. Vol. 2089. pp. 181–192. doi:10.1007/3-540-48194-X_17. ISBN 978-3-540-42271-6.
• Ohlebusch, Enno; Fischer, Johannes; Gog, Simon (2010). CST++. String Processing and Information Retrieval. Lecture Notes in Computer Science. Vol. 6393. p. 322. doi:10.1007/978-3-642-16321-0_34. ISBN 978-3-642-16320-3.
• Kärkkäinen, Juha; Sanders, Peter (2003). Simple linear work suffix array construction. Proceedings of the 30th international conference on Automata, languages and programming. pp. 943–955. Retrieved 2012-08-28.
• Fischer, Johannes (2011). Inducing the LCP-Array. Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 6844. pp. 374–385. arXiv:1101.3448. doi:10.1007/978-3-642-22300-6_32. ISBN 978-3-642-22299-3.
• Manzini, Giovanni (2004). Two Space Saving Tricks for Linear Time LCP Array Computation. Algorithm Theory - SWAT 2004. Lecture Notes in Computer Science. Vol. 3111. p. 372. doi:10.1007/978-3-540-27810-8_32. ISBN 978-3-540-22339-9.
• Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J. (2009). Permuted Longest-Common-Prefix Array. Combinatorial Pattern Matching. Lecture Notes in Computer Science. Vol. 5577. p. 181. doi:10.1007/978-3-642-02441-2_17. ISBN 978-3-642-02440-5.
• Puglisi, Simon J.; Turpin, Andrew (2008). Space-Time Tradeoffs for Longest-Common-Prefix Array Computation. Algorithms and Computation. Lecture Notes in Computer Science. Vol. 5369. p. 124. doi:10.1007/978-3-540-92182-0_14. ISBN 978-3-540-92181-3.
• Gog, Simon; Ohlebusch, Enno (2011). Fast and Lightweight LCP-Array Construction Algorithms (PDF). Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2011. pp. 25–34. Retrieved 2012-08-28.
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linear Suffix Array Construction by Almost Pure Induced-Sorting. 2009 Data Compression Conference. p. 193. doi:10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0.
• Fischer, Johannes; Heun, Volker (2007). A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Lecture Notes in Computer Science. Vol. 4614. p. 459. doi:10.1007/978-3-540-74450-4_41. ISBN 978-3-540-74449-8.
• Chen, G.; Puglisi, S. J.; Smyth, W. F. (2008). "Lempel–Ziv Factorization Using Less Time & Space". Mathematics in Computer Science. 1 (4): 605. doi:10.1007/s11786-007-0024-4. S2CID 1721891.
• Crochemore, M.; Ilie, L. (2008). "Computing Longest Previous Factor in linear time and applications". Information Processing Letters. 106 (2): 75. CiteSeerX 10.1.1.70.5720. doi:10.1016/j.ipl.2007.10.006.
• Crochemore, M.; Ilie, L.; Smyth, W. F. (2008). A Simple Algorithm for Computing the Lempel Ziv Factorization. Data Compression Conference (dcc 2008). p. 482. doi:10.1109/DCC.2008.36. hdl:20.500.11937/5907. ISBN 978-0-7695-3121-2.
• Sadakane, K. (2007). "Compressed Suffix Trees with Full Functionality". Theory of Computing Systems. 41 (4): 589–607. CiteSeerX 10.1.1.224.4152. doi:10.1007/s00224-006-1198-x. S2CID 263130.
• Fischer, Johannes; Mäkinen, Veli; Navarro, Gonzalo (2009). "Faster entropy-bounded compressed suffix trees". Theoretical Computer Science. 410 (51): 5354. doi:10.1016/j.tcs.2009.09.012.
• Fischer, Johannes; Kurpicz, Florian (5 October 2017). "Dismantling DivSufSort". Proceedings of the Prague Stringology Conference 2017. arXiv:1710.01896.

외부 링크

• Fischer(2011)에 기술된 코드의 임시 구현 거울
• SDSL: 간결한 데이터 구조 라이브러리 - 다양한 LCP 어레이 구현, Range Minimum Query(RMQ) 지원 구조 및 많은 간결한 데이터 구조를 제공합니다.
• 서픽스 배열 및 LCP 배열(Java)을 사용하여 에뮬레이트된 상향 서픽스 트리 트래버설
• 텍스트 색인화 프로젝트(접미사 트리, 접미사 배열, LCP 배열 및 버로우스의 선형 시간 구성)휠러 변환)