우코넨 알고리즘

Ukkonen's algorithm

컴퓨터 공학에서 Ukkonen 알고리즘은 접미사 트리를 구성하는 선형 시간 온라인 알고리즘으로,[1] 1995년에 Esko Ukonen이 제안했다.알고리즘은 문자열의 첫 번째 문자를 포함하는 암묵적인 접미사 트리로 시작합니다.그런 다음 스트링을 단계별로 진행하여 트리가 완성될 때까지 연속되는 문자를 추가합니다.이러한 문자 순서의 추가에 의해 Ukkonen 알고리즘의 "온라인" 속성이 부여됩니다.피터 와이너가 제시한 원래의 알고리즘은 마지막 문자에서 가장 짧은 접미사에서 가장 긴 접미사로 거꾸로 진행되었습니다.[2]Edward M. McCreight는 가장 긴 [3]접미사에서 가장 짧은 접미사로 더 간단한 알고리즘을 발견했습니다.

암묵적 접미사 트리

Ukkonen 알고리즘을 사용하여 서픽스 트리를 생성할 때 문자열 S의 문자에 따라 중간 단계에서 암묵적인 서픽스 트리를 볼 수 있습니다.암묵적 접미사 트리에서는 $(또는 다른 종단 문자) 라벨이 있는 에지 및 내부 노드가 존재하지 않으며, 내부 노드가 1개만 외부로 출력되지 않습니다.

Ukkonen 알고리즘 개요 설명

Ukonen의 알고리즘은 S(S는 길이 n의 문자열)의 각 접두사 S[1...i]에 대해 암묵적인 접미사 트리i T를 구축한다.먼저 T를 1자로st, T를2 2자로nd, T를3 3자로, T를rd 3자로, T를n n자로th 작성합니다1.Ukkonen 알고리즘을 사용하는 접미사 트리에서 다음 특성을 찾을 수 있습니다.

  • 암묵적 서픽스트리i+1 T는 암묵적 서픽스트리i T 위에 구축됩니다.
  • Ukkonen 알고리즘은 항상 지금까지 본 문자의 서픽스 트리를 구축하기 때문에 온라인 속성을 가지므로 알고리즘의 실행 시간은 O(n)가 됩니다.
  • Ukonen의 알고리즘은 n개의 위상(길이 n의 문자열의 각 문자에 대해 1개의 위상)으로 나뉩니다.
  • 각 위상 i+1은 S[1...i+1]의 각 i+1 접미사에 대해 각각 하나씩 i+1 확장자로 더욱 분할됩니다.

접미사 확장자는 지금까지 작성된 접미사 트리에 다음 문자를 추가하는 것입니다.위상 i+1의 확장 j에서 알고리즘은 S[j...i](이전 단계 i에 의해 이미 트리 내에 있음)의 끝을 찾아 S[j...i]를 확장하여 접미사 S[j...i+1]가 트리 내에 있음을 확인한다.확장 규칙에는 다음 3가지가 있습니다.

  1. S[j...i]라는 라벨이 붙은 루트로부터의 경로가 리프 엣지에서 끝나는 경우(즉, S[i]는 리프 엣지의 마지막 문자임), 문자 S[i+1]가 해당 리프 엣지의 라벨 끝에 추가됩니다.
  2. S[j...i]라는 라벨이 붙은 루트의 경로가 리프 이외의 에지에서 종료되고(즉, 경로의 S[i] 뒤에 문자가 더 있음) 다음 문자가 S[i+1]가 아닌 경우, 라벨 S[i+1]와 번호 j를 가진 새 리프 에지가 문자 S[i+1]부터 생성됩니다.또한 S[1...i]가 리프 이외의 에지 내부에서 끝나는 경우에도 새 내부 노드가 생성됩니다.
  3. S[j]라는 라벨이 붙은 루트로부터의 패스인 경우.i]는 잎이 아닌 가장자리에서 끝납니다(즉, 경로의 S[i] 뒤에 더 많은 문자가 있습니다). 다음 문자는 s[i+1](이미 트리에 있음). 아무것도 하지 않습니다.

주의할 점은 특정 노드(루트 또는 내부)에서 1개의 문자로 시작하는 엣지는 1개뿐이라는 것입니다.같은 문자로 시작하는 노드에서는 둘 이상의 에지가 출력되지 않습니다.

실행 시간

앞으로 서픽스 트리를 생성하기 위한 간단한 구현에서는 O(n2) 또는 O(n3) 시간의 복잡성이 빅 O 표기법(n은 문자열 길이)으로 요구됩니다.다수의 알고리즘 기술을 이용함으로써 Ukkonen은 이것을 O(n)(선형) 시간, 그리고 일반적으로 O(n log n)로 줄여 앞의 두 알고리즘의 런타임 성능과 일치시켰다.

우코넨 알고리즘 예시

Ukkonen 알고리즘을 사용한 최종 접미사 T스크린(예)

Ukkonen 알고리즘을 사용한 서픽스트리의 구성 방법을 알기 쉽게 설명하기 위해 다음 예를 사용할 수 있습니다.

S=xabxac

  1. 빈 루트 노드부터 시작합니다.
  2. 문자열의 첫 번째 문자를 추가하여 S[1]용 T를 구성합니다1.규칙 2가 적용되어 새로운 리프 노드가 생성됩니다.
  3. xa(xa 및 a)의 접미사를 추가하여 S[1...2]에 T를 구성합니다2.규칙 1이 적용되어 기존 리프 가장자리의 경로 라벨이 확장됩니다.규칙 2가 적용되어 새로운 리프 노드가 생성됩니다.
  4. xab(xab, ab, b)의 접미사를 추가하여 S[1...3]의 T를 구한다3.규칙 1이 적용되어 기존 리프 가장자리의 경로 라벨이 확장됩니다.규칙 2가 적용되어 새로운 리프 노드가 생성됩니다.
  5. xabx(xabx, abx, bx 및 x)의 접미사를 추가하여 S[1...4]의 T를 구성합니다4.규칙 1이 적용되어 기존 리프 가장자리의 경로 라벨이 확장됩니다.규칙 3이 적용되면 아무것도 하지 마세요.
  6. xabxa(xabxa, abxa, bxa, xa 및 x)의 접미사를 추가하여 S[1...5]의 T를 구성합니다5.규칙 1이 적용되어 기존 리프 가장자리의 경로 라벨이 확장됩니다.규칙 3이 적용되면 아무것도 하지 마세요.
  7. xabxac(xabxac, abxac, bxac, xac, ac 및 c)의 접미사를 추가하여 S[1...6]용 T를 구성합니다6.규칙 1이 적용되어 기존 리프 가장자리의 경로 라벨이 확장됩니다.규칙 2가 적용되어 새로운 리프 노드가 생성됩니다(이 경우 새로운 리드 엣지 3개와 새로운 내부 노드 2개가 생성됩니다).

레퍼런스

  1. ^ Ukkonen, E. (1995). "On-line construction of suffix trees" (PDF). Algorithmica. 14 (3): 249–260. CiteSeerX 10.1.1.10.751. doi:10.1007/BF01206331. S2CID 6027556.
  2. ^ Weiner, Peter (1973). "Linear pattern matching algorithms" (PDF). 14th Annual Symposium on Switching and Automata Theory (SWAT 1973). pp. 1–11. CiteSeerX 10.1.1.474.9582. doi:10.1109/SWAT.1973.13.
  3. ^ McCreight, Edward Meyers (1976). "A Space-Economical Suffix Tree Construction Algorithm". Journal of the ACM. 23 (2): 262–272. CiteSeerX 10.1.1.130.8022. doi:10.1145/321941.321946. S2CID 9250303.

외부 링크


Stub icon

이 알고리즘 또는 데이터 구조 관련 문서는 stub입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.