본 문서는 시퀀싱 문자열 자료 처리를 위해 이용되어져 왔던 접미사 트리의 생성을 효율적으로 하기위한 알고리즘 중 하나인 Ukkonen 씨의 알고리즘에 대해 설명한다.
본 문서는 http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english의 번역이다. 이 내용은 http://stackoverflow.com/users/63550/peter-mortensen 씨의 질문에 대한 http://stackoverflow.com/users/777186/jogojapan 씨의 답변이다.
나는 현재 약간 답답함을 느낀다. 나는 며칠간을 머리를 싸매고 접미사 트리 생성을 완전히 이해하려고 노력해왔다. 그러나 내게 충분한 수학 지식이 없기 때문에, 수 많은 설명들은 화려한 수식의 향연을 만들면서 내 이해를 방해했다. 내가 발견한 내용 중 가장 좋은 답변에 근접한 것은 접미사 트리를 이용한 빠른 문자열 검색(http://marknelson.us/1996/08/01/suffix-trees/)이다. 하지만, 그는 여러가지 관점들을 둘러대고 알고리즘의 몇몇 관점들은 여전히 불분명하게 남아 있다.
StackOverflow 포럼에서 이 알고리즘에 대한 단계별 설명은 나 뿐만 아니라 다른 많은 사람들에게 귀중한 자산이 될 것이라 나는 확신한다.
참고를 위해서, 여기에 알고리즘에 대한 Ukkonen 씨의 논문을 연결한다. http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
지금까지의 내 기본적인 이해는 다음과 같다:
- 나는 주어진 문자열 T의 각 접두사 P를 순회해야 한다
- 나는 접두사 P에 있는 각 접미사 S를 순회하고 그것을 트리에 추가한다
- 접미사 S를 트리에 추가하기 위해서, 나는 S에 있는 각 문자를 순회해야 한다. 순회는 S 안의 같은 문자 집합 C로 시작하는 존재하는 브랜치를 통해 내려가는 방향으로 진행하고 접미사 안의 다른 문자를 발견했을 때는 잠재적으로 에지를 하위 노드들로 분해하거나 또는 만약 거기에 일치하는 에지가 없을 때 분해한다. C를 순회를 위한 일치되는 에지가 없을 경우, 새로운 리프 에지가 C를 위해서 생성된다.
기본적인 알고리즘은 많은 설명들에서 언급되었듯이, 
- 정확히 언제 그리고 어떻게 "액티브 포인트(active point)"가 할당되는지, 사용되는지, 변경되는지
- 알고리즘의 종결점 찍기(canonization)에 대한 관점이 무엇인지
- 왜 내가 보아온 구현체들은 그들이 사용한 경계 변수(bounding variable)를 "수정" 해야만 하는지
수정(2012년 4월 13일)
여기에 아래에 jogojapan 씨의 답변에 기반하여 내가 작성한 완전한 소스코드와 출력 결과가 있다. 이 코드는 트리를 생성해 나가는 과정 대해서 자세한 설명과 함께 텍스트 기반의 다이어그램을 출력한다. 이것은 초기 버전이고 아마도 성능 향상을 한다 던지 등등을 해야 하겠지만, 아무튼 동작한다. 이 점이 주요하다.
[수정된 URL, 아래의 수정된 링크 참고]
수정(2012년 4월 15일)
이 소스 코드는 완전히 처음부터 재 작성되었고, 이제 제대로 동작할 뿐 아니라 자동적인 종결점 찍기를 지원하고, 나은 텍스트 기반 그래프를 출력한다. 소스 코드와 예제 출력은 여기에 있다.
https://gist.github.com/2373868
아래는 첫째로는 문자열이 간단할 때(예를 들어 아무런 반복되는 문자열을 가지고 있지 않을 때), Ukkonen 알고리즘이 어떻게 동작하는 지 보이고 다음으로 그것을 전체 알고리즘으로 확장함으로써 그 알고리즘을 설명하려는 시도이다.
첫째, 약간의 기본적인 설명들.
- 우리가 생성하려고 하는 것은, 기본적으로 하나의 검색 트라이(search trie)와 같다. 그러므로 거기에는 루트 노드와 거기에서 나와서 새로운 노드들로 뻗쳐나가는 에지들 그리고 그 노드들로 부터 나오는 에지들 등등이다..
- 하지만 검색 트라이(search trie)와 다르게, 에지 표지(label)들은 단일 문자열이 아니다. 대신, 각 에지들은 한 쌍의 정수[시작,끝]를 사용하여 표지(label)된다. 이 것들은 주어진 텍스트를 향한 포인터이다. 이와 동일한 느낌으로, 각 에지는 다양한 길이의 문자열 표지를 전달할 수 있으며, 비록 길이는 다름에도 오직
의 공간만 소모한다(두 포인터).
기본 원리
나는 먼저 매우 간단한 문자열(아무런 반복도 없은 문자열)의 접미사 트리를 어떻게 생성하는지 보이려고 한다.
abc
이 알고리즘은 단계별로 왼쪽에서 오른쪽으로 진행된다. 문자열의 모든 문자 별로 각각 하나의 단계가 있다. 각 단계는 하나 이상의 별개의 연산을 포함하기도 하지만, 우리는 결국 전체 연산의 수가 
그러므로, 우리는 왼쪽에서부터 시작하고, 첫째로 루트노드에서(왼쪽에 있는) 리프노드로 에지를 하나 생성하므로써 오직 단일 문자 a를 입력하고, 그것을 [0, #]이라고 표기한다. 이것은 에지가 0의 지점에서 시작하여 현재의 종결지점에서 끝남을 표현한다. 나는 현재의 종결지점을 표현하기 위해서 기호 #을 이용하고, 지금은 a의 바로 다음 위치인 1의 값을 가지고 있다.
그러므로 우리는 다음과 같이 보이는 초기의 트리를 가지게 되었다.
그리고 이것이 의미하는 바는 다음과 같다.
이제 우리는 b의 바로 다음인 위치 2로 진행한다. 각 단계에서 우리의 목적은 현재의 위치까지 있는 모든 접미사를 입력하는 것이다. 우리는 다음 과정을 통해서 수행한다.
- 존재하는 a-에지를 ab-에지로 확장한다
- b를 위해 새로운 에지를 추가한다.
우리의 표기 방식에서 이것은 다음과 같이 보인다.
그리고 이것이 의미하는 바는 다음과 같다.
우리는 두가지 내용을 관찰했다.
- ab를 위한 에지 표기 방식은 초기 트리 [0, #]에서 사용되어진 것과 동일하다. 그것의 의미는 실제로 트리를 조작하지 않고, 자동적으로 변경되었다. 왜냐하면 우리는 현재의 위치인 #의 값을 1에서 2로 변경했기 때문이다.
- 각 에지는
다음으로 우리는 위치를 다시 증가시키고 모든 존재하는 에지들에 하나의 c를 추가하고 새로운 접미사인 c를 위해 하나의 새로운 노드를 추가함으로써 트리를 갱신한다.
우리의 표기 방식에서 이것은 다음과 같이 보인다.
그리고 이것이 의미하는 바는 다음과 같다.
우리는 관찰했다.
- 트리는 각 단계 후에 현재의 위치까지 정확한 접미사 트리이다.
- 텍스트에 있는 문자열의 갯수 만큼 단계들이 있다.
- 각 단계 별로 요구되는 작업의 양은
첫번째 확장: 단순 반복들
물론 이것은 매우 멋지게 동작한다. 왜냐하면 우리의 문자열은 아무런 반복도 포함하고 있지 않기 때문이다. 우리는 이제 좀더 현실적인 문자열을 보도록 하자.
abcabxabcd
이 문자열은 이전 예제에서의 abc로 시작하며, ab가 반복되고 x가 따라온 뒤 abc가 나오고 d가 나온다.
단계 1부터 3까지: 이전의 예제에서 초기의 3 단계 후에 우리는 다음의 트리를 가진다:
단계 4: 우리는 #을 위치 4로 옮긴다. 이것은 암시적으로 모든 존재하는 에지를 이렇게 갱신한다.
그리고 우리는 루트 노드에서 현재 단계의 최종 접미사인 a를 추가할 필요가 있다.
이렇게 하기 전에 #을 추가했던 것처럼 변수를 두 개 더 소개하고자 한다. 사실 이 변수들은 이미 존재했지만, 우리들은 아직까지 사용하지 않았었다.
- 액티브 포인트(active point)는 세 가지 값의 쌍(액티브 노드, 액티브 에지, 액티브 길이)이다.
- 나머지(remainder)는 얼마나 많은 새로운 접미사들이 추가되어야 하는지 나타내는 정수
위 두 변수의 정확한 의미에 대해서는 차차 명확해 질 것이다. 그러니 지금은 그냥 이렇게 말하도록 하겠다.
- 단순한 abc 예제에서, 액티브 포인트(active point)는 항상 (루트, '\0', 0) 이었다. 예를 들어, 액티브 노드는 루트 노드, 액티브 에지는 널 문자('\0'), 그리고 액티브 길이는 0이었다. 이것은 각 단계 마다 새롭게 에지를 추가할 때마다 이 에지가 루트 노드에서 새롭게 생성된 에지를 추가하는 것과 같은 효과를 나타낸다. 우리는 곧 왜 이 세 가지 값의 쌍이 이 정보를 표현하는데 필요한 지 알게 될 것이다.
- 나머지(remainder)는 각 단계의 시작에서 항상 1로 설정되었었다. 이것의 의미는 우리가 각 단계의 끝에서 열심히 추가해야 했었던 접미사의 갯수가 1임을 나타낸다.(이것의 다른 의미는 언제나 마지막 문자가 추가됨을 나타낸다.)
이제 이 방법은 약간 변경될 것이다. 우리가 현재의 마지막 문자인 a를 루트에서 추가하려고 할 때, 우리는 이미 거기에 a로 시작하며 바깥쪽으로 향하는 에지가 있음을 알아차릴 수 있다. 바로, abca-에지를 말한다. 여기에 이런 경우 우리가 어떻게 하는지 설명하고자 한다.
- 우리는 루트 노드에서 새로운 에지를 추가하지 않는다.
- 대신에 우리는 우리의 트리에 이미 접미사 a가 있음을 알아차릴 수 있다. 그것은 결국 하나의 더 긴 에지의 중간에서 끝난다. 하지만, 우리는 그것을 신경 쓰지 않아도 된다. 우리는 그들이 있는 모양 그대로 그냥 둘 것이다.
- 우리는 액티브 포인트(active point)를 (루트, 'a', 1)로 설정한다. 이것의 의미는 액티브 포인트가 이제 a로 시작하는 루트 노드의 바깥으로 나가는 어느 한 에지의 중간 어디엔가에 있다는 것을 나타낸다. 그리고 특별히 지금의 경우엔 에지의 1번 위치 뒤에 있음을 나타낸다. 우리는 에지가 단순히 그것의 첫 문자인 a에 의해서 명시되어짐을 알 수 있다. 이 정도의 정보만으로도 충분한데, 이것은 왜냐하면 특별한 문자로 시작하는 에지가 오직 하나만 존재할 수 있기 때문이다.(전체 알고리즘의 설명을 읽고 난 후에 이 내용이 사실임을 확신할 수 있을 것이다.)
- 우리는 또한 나머지를 증가시킨다. 그래서 다음 단계의 나머지 값은 2가 될 것이다.
관찰: 우리가 입력하려는 최종 접미사가 트리에 이미 존재할 때, 트리 자체는 전혀 변화되지 않는다.(우리는 단지 액티브 포인트와 나머지만 갱신한다.) 그런 까닭에 현재의 위치까지의 접미사 트리의 표현은 더 이상 정확한 표현 방식이 아니다. 그러나 그것은 모든 접미사들을 포함한다.(왜냐하면 최종 접미사 a는 암시적으로 포함되어지기 때문이다.) 그런 까닭에, 변수들을 갱신하는 것을 제외하고(이것은 항상 고정 길이이며, 그래서 이것은
단계 5: 우리는 현재의 위치 #을 5로 갱신한다. 이것은 자동적으로 트리를 다음과 같이 갱신한다.
그리고 나머지가 2이기 때문에, 우리는 현재의 위치에서 두 개의 최종 접미사 ab와 b들 입력할 필요가 있다. 이것은 기본적으로 다음과 같은 이유를 가진다.
- 이전 단계에서부터 있었던 a 접미사는 아직까지 한번도 제대로 입력되지 않았다. 그것이 여전히 남아있고, 우리가 한 단계 진행했기 때문에, 이 접미사는 이제 a에서 ab로 성장했다.
- 그리고 우리는 새로운 최종 b-에지를 추가할 필요가 있다.
실제로 이것은 우리가 액티브 포인트(a의 뒤를 가리키고 현재 abcab 에지에 있는)로 가서 현재의 최종 문자 b를 추가함을 의미한다. 하지만, 또 다시 b가 이미 같은 에지에 있음을 알 수 있다.
그러므로 또 다시, 우리는 트리를 변경할 필요가 없다. 우리는 단순히 다음을 수행한다.
- 액티브 포인트를 (루트,'a',2)로 갱신한다(이전과 같은 노드와 에지이지만, b의 뒤를 가리킨다)
- 나머지를 3으로 증가시킨다. 왜냐하면 이전 단계에서 부터 우리는 아직 제대로 최종 에지를 입력하지 않았고, 게다가 현재의 최종 에지조차도 입력하지 않았기 때문이다.
좀더 명확히 말하자면, 우리는 ab와 b를 이번 단계에서 입력했었어야만 했다. 그러나 ab는 이미 발견되었기 때문에, 우리는 액티브 포인트만을 다시 갱신하고 b를 입력하려고 시도조차 하지 않았다. 왜 그럴까? 왜냐하면 만약 ab가 트리에 있다면, ab의 모든 접미사(b를 포함하여) 또한 반드시 트리에 있어야 하기 때문이다. 아마도 반드시 거기에 존재하여야 한다고 하더라도 우리는 지금까지 트리를 오직 암시적으로만 생성하였기 때문일 것이다.
우리는 #을 증가시킴으로써 단계 6으로 진행한다. 트리는 자동적으로 다음과 같이 갱신된다.
나머지가 3이기 때문에 우리는 abx, bx, 그리고 x를 입력해야만 한다. 액티브 포인트는 ab가 어디에서 끝나는지 말해준다. 그러므로 우리는 단지 엑티브 노드가 가리키는 노드로 가서 x를 추가하면 된다. 사실, x는 아직 트리에 없다, 그래서 우리는 abcabx 에지를 쪼개고 하나의 내부 노드를 추가한다.
에지 표현 방법은 여전히 주어진 문자열에 대한 포인터들일 뿐이므로, 에지를 쪼개고 새로운 내부 노드를 추가하는 동작은
마침내 우리는 abx를 처리했고, 나머지를 2로 감소시킨다. 이제 우리는 다음의 남아 있는 접미사 bx를 입력할 필요가 있다. 하지만 그것을 하기 전에 우리는 액티브 포인트를 갱신할 필요가 있다. 앞으로는 이것을 위한 규칙, 즉, 에지를 쪼개고 난 후 하나의 에지를 추가하는 과정에 적용되는 규칙을 규칙 1이라고 부르겠다. 그리고 이것은 액티브 노드가 루트 노드 일 때 적용된다(우리는 다른 경우를 위한 규칙 3에 대해서 나중에 배우게 될 것이다.). 이것은 규칙 1이다.액티브 노드는 루트이다.
- 액티브 노드는 루트이다.
- 액티브 에지는 우리가 입력할 새로운 접미사의 첫 문자로 설정된다. 여기에서는, b
- 엑티브 길이는 1만큼 감소한다.
시간 안에 발견할 수 있고, x가 입력 지점에 이미 존재하는지 여부를 검사할 수 있다. 만약 그것이 존재하면, 우리는 현재의 단계를 종료하고, 모든 것을 있는 그대로 둘 것이다. 하지만, x는 현재 입력 지점에 존재하지 않는다. 그러므로 우리는 에지를 쪼갬으로써 그것을 입력할 것이다.
다시 이것은
하지만, 이것에 더해서 우리는 한가지 더 수행해야할 일이 있다. 우리는 앞으로 이것을 규칙 2라 부르겠다.
만약 하나의 에지를 쪼개고, 하나의 새로운 노드를 추가하고, 만약 그 노드가 현재 단계 동안 생성된 첫째 노드가 아니라면, 우리는 이전에 입력된 노드와 새로운 노드를 특별한 포인터인 접미사 링크(suffix link)를 통해 연결한다. 우리는 나중에 이것이 왜 유용한지 보게될 것이다. 아래에 새롭게 도입한 개념인, 접미사 링크가 점선 에지로 표현되어 있다.
우리는 여전히 현재 단계의 마지막 접미사인 x를 입력해야 한다. 다만, 액티브 노드의 액티브 길이 값이 0이 되었기 때문에, 최종 입력은 루트 노드에서 직접적으로 수행된다. 루트 노드에는 x로 시작하는 바깥으로 나가는 에지가 없기 때문에, 우리는 새로운 에지를 추가한다.
우리가 볼 수 있듯이, 현재 단계의 남아 있는 모든 입력이 완료되었다.
우리는 #을 7로 설정함으로써 단계 7로 진행한다. 이것은 항상 그랬듯이 자동으로 다음 문자인 a를 모든 리프 에지들에 추가한다. 다음으로 우리는 액티브 노드(루트 노드)에 최종 문자를 입력하고 이미 이 값이 액티브 노드에 있는지 알게 된다. 그러므로 우리는 다른 아무 것도 입력하지 않고 액티브 포인트를 (루트,'a',1)로 갱신함으로써 현재 단계를 종료한다.
단계 8에서, #은 8이며, b를 추가한다. 이미 여러차례 봐왔듯이 이미 b가 액티브 노드에 있기 때문에 단지 액티브 포인트만을 (루트.'b',2)로 갱신하고 나머지를 증가시키는 것만으로 이것은 완료된다. 하지만, 우리는 (
다음으로 #=9인 단계에서, 우리는 'c'를 입력해야 하고 이것은 마지막 기술을 이해하는데 도움을 줄 것이다.
두번째 확장: 접미사 링크 이용하기
언제나처럼, #을 갱신하는 것은 c를 자동적으로 리프 노드들에 덧붙이게 되고, 다음으로 액티브 포인트로 가서 우리가 'c'를 입력할 수 있는지 보게 된다. 사실 'c'는 이미 그 에지에 존재하기 때문에, 우리는 액티브 포인트를 (노드1,'c',1)로 설정하고 나머지를 증가시킨 후 다른 아무 것도 하지 않는다.
이제 #=10인 단계에서, 나머지는 4이고, 그래서 우리는 먼저 액티브 포인트에 d를 입력함으로써 abcd(3 단계 이전에 부터 남아 있었던)를 입력해야 한다.
d를 입력하려고 하는 것은 에지가
쪼개짐이 시작되었던 액티브 노드는 위 그림에서 빨간색으로 표시되었다. 여기에 마지막 규칙인 규칙 3이 있다.
루트 노드가 아닌 액티브 노드에서 하나의 에지를 쪼갠 후에 우리는 그 노드에서 만약 거기에 바깥으로 나가는 접미사 링크가 있다면 그것을 따라가서 원래의 노드가 가리키던 노드로 액티브 노드를 재설정한다. 만약 접미사 링크가 없다면, 우리는 액티브 노드를 루트 노드로 설정하고 액티브 길이는 그대로 둔다.
그러므로 액티브 포인트는 이제 (노드2,'c',1)이고 노드2는 아래에 빨간색으로 표시되었다.
이제 abcd의 입력이 완료되었기 때문에, 우리는 나머지를 3으로 감소시키고 지금 단계의 다음의 남은 접미사인 bcd를 고려한다.규칙3은 액티브 포인트를 바로 오른쪽 노드와 에지로 설정하기 때문에 bcd를 입력하는 것은 단지 그것의 최종 문자인 d를 액티브 포인트에 입력함으로써 수행된다.
이렇게 하는 것은 다른 에지가 쪼개지게 한다. 그리고 규칙 2 때문에, 우리는 이전에 입력된 노드에서 새롭게 생성된 노드로의 접미사 링크를 생성해야 한다.
우리는 관찰한다. 접미사 링크들은 액티브 포인트를 재설정하게 해주기 때문에 우리는 다음의 남아 있는 입력을
지금의 단계는 아직 끝나지 않았다. 나머지는 이제 2이고, 우리는 액티브 포인트를 재설정하기 위해서 규칙 3을 따라야 한다. 현재의 액티브 노드(위에서 빨간 부분)은 아무런 접미사 링크를 가지고 있지 않기 때문에, 이것을 루트 노드로 재설정한다. 액티브 노드는 이제 (루트,'c',1)이다.
다음의 입력은 루트 노드의 하나의 바깥으로 나가는 에지인 c로 시작되고(cabxabcd) 첫째 문자 뒤(예를 들어 c의 뒤)에서 일어난다. 이것은 다른 쪼개짐을 야기한다.
그리고 이것은 하나의 새로운 내부 노드의 생성을 포함하기 때문에, 우리는 규칙 2를 따르게 되고, 이전에 생성된 내부 노드로부터 새로운 접미사 링크를 설정하게 된다.
(나는 이 작은 그래프들을 위해서 http://www.graphviz.org/을 이용한다. 새로운 접미사 링크는 존재하는 에지들을 재설정하기 위해서 점선을 만든다. 그러므로 자세히 살펴 보면 위에서 입력된 것은 하나의 새로운 접미사 링크 밖에 없음을 알 수 있다.) 이 결과와 함께, 나머지는 1로 설정될 수 있고, 액티브 노드는 루트 노드이기 때문에, 우리는 규칙 1을 이용하여 액티브 포인트를 (루트,'d',0)으로 갱신한다. 이것은 지금 단계의 최종 입력이 루트 노드에서 단일 문자 d를 입력하는 것임을 나타낸다.
이것이 마지막 단계이고, 우리는 마침내 접미사 트리를 만들었다. 여기에 여러 최종 관찰들이 있다.
- 각 단계마다, 우리는 #을 1 위치 만큼씩 증가시켰다. 이것은 자동적으로 모든 리프 노드들을
- 하지만, 이런 갱신은 a) 이전 단계에서 남아 있는 접미사들과 b) 지금 단계의 하나의 마지막 문자를 처리하지 않는다.
- 나머지는 얼마나 많은 추가적인 입력이 요구되는지를 말해준다. 이 입력들은 현재 위치인 #에서 끝나는 문자열의 최종 접미사로 1:1로 대응된다. 우리는 한 노드 다음에 다음 노드를 고려하고 입력을 수행한다. 중요한 것은 각 입력이
- 각각의 그러한 입력 후에, 우리는 나머지를 감소시키고, 만약 접미사 링크가 있다면, 이를 따라간다. 만약 접미사 링크가 없다면, 우리는 루트 노드로 간다(규칙 3). 우리가 이미 루트 노드에 있다면, 우리는 규칙 1을 이용해서 액티브 포인트를 수정한다. 어떤 경우든지, 그것은 오직
- 만약, 이 입력들을 진행하는 동안 입력하고자 하는 문자가 이미 트리에 존재할 때, 심지어 나머지 >0인 경우라도 우리는 아무것도 하지 않고 현재 단계를 종료한다. 이것에 대한 이유는 어떠한 입력이든지 남아 있는 경우에는 우리가 생성하려고하는 노드의 접미사일 뿐이기 때문이다. 그래서 그들은 모두 현재의 트리에서 암시적으로 존재할 뿐이다. 나머지 > 0이라는 사실은 우리가 남아 있는 접미사를 차후에 처리할 것임을 나타낸다.
- 알고리즘을 모두 수행했는데도 나머지 > 0이면 어떻게 할 것인가? 이것은 주어진 문자열의 마지막 부분이 이전 어디에선가 이미 처리된 전체 문자열의 일부분 문자열과 일치하는 경우이다. 이 경우에 우리는 이전 문자열에서 나타나지 않았던 하나의 추가적인 문자를 문자열의 끝 부분에 추가해야만 한다. 여러 문헌들에서는 $ 기호가 이런 용도로 사용되어져 왔다. 그래서 왜 이것이 문제인가? --> 차후에 우리가 완성된 접미사 트리를 이용하여 접미사들을 검색하려고할 때, 우리는 오직 리프 노드에서 끝나는 접미사들만 검색하게 된다. 그렇지 않으면 우리는 많은 양의 이상한 검색 결과들까지 얻게 된다. 왜냐하면 접미사 트리에는 주어진 문자열의 실제적인 접미사 뿐만 아니라 암시적으로 포함된 수많은 문자열들이 존재하기 때문이다. 나머지 값을 0으로 강제적으로 맞추는 것은 기본적으로 모든 접미사들이 리프 노드에서 종결되도록 보장해주는 방법이다. 하지만, 만약 우리가 접미사 트리를 단지 주어진 문자열에 대한 접미사들을 검색하는데만 사용하는 것이 아니라 일반적인 부분 문자열을 검색하는데 사용하고자 한다면, 원래 질문(Original Post, OP)의 아래쪽의 답글에서 제시하듯이 이 최종 단계는 필요하지 않다.
- 그래서 전체 알고리즘의 복잡도는 무엇인가? 만약 문자열이 n개의 문자로 이뤄져 있다면, 거기에는 명백히 n개의 단계가 요구된다(또는 만약 $ 기호를 추가한다면, n+1개의 단계). 각 단계마다 우리는 아무것도 하지 않거나(변수들을 갱신하는 것 이상의 작업), 혹은 각 연산이
- 하지만 여전히 제대로 설명하지 않은 것이 하나 있다. 이것은 우리가 접미사 링크를 따라가서 액티브 포인트를 갱신한 후에 발생한다. 그것은 바로 새로운 액티브 노드가 그것의 액티브 길이 값과 잘 동작하지 않는 것이다. 예를 들어, 다음과 같은 상황을 생각해 보자.
(긴 점선으로 표현된 선은 나머지 접미사 트리를 나타낸다. 점선은 접미사 링크를 나타낸다.)
이제 액티브 포인트가 (빨강,'d',3)이라고 하자. 그래서 액티브 포인트는 defg-에지에서 f의 뒤의 지점을 가리킨다. 이제 우리는 필요한 갱신들을 모두 수행했고, 규칙 3에 의해서 접미사 링크를 따라가서 액티브 포인트를 갱신했다고 하자. 이제 새로운 액티브 포인트는 (녹,'d',3)이다. 하지만, 녹색 에지에서 바깥으로 나가는 d-에지는 de이고, 이는 오직 두 개의 문자들만 가지고 있다. 정확한 액티브 포인트를 발견하기 위해서, 우리는 우리는 파랑 노드로 가는 에지를 따라가야하고 액티브 노드를 (파랑.'f',1)로 재설정 해야만 한다.
이런 특별히 안 좋은 경우에, 액티브 길이는 n만큼 커질 수 있는 나머지만큼 커질 수 있다. 이것의 문제점은 정확한 액티브 포인트를 발견하기 위해서, 우리는 오직 한번의 내부 노드로 점프하는 것이 아니라 아마도 여러번, 최악의 경우 n 번까지 점프를 해야할 수도 있다. 그래서 이 알고리즘은 숨겨진
아니다. 만약 실제로 우리가 액티브 포인트를 조정해야한다면(예를 들어, 위의 그림에서는 녹색에서 파랑 노드), 이것은 자기 자신의 접미사 링크를 가진 새로운 노드를 생성하고, 액티브 길이는 감소할 것이다. 남아있는 입력들을 수행하기 위해서 연결되어 있는 접미사 연결을 따라 내려가다 보면, 액티브 길이는 오직 감소할 수 밖에 없고, 액티브 포인트의 재설정 횟수는 주어진 시간에 액티브 길이 보다 클 수가 없다. 액티브 길이가 나머지 보다 클 수가 없고 나머지는 모든 단일 단계에서
댓글