쉬운 영어로 된 우코넨의 접미사 트리 알고리즘
이쯤 되면 좀 답답한 느낌이 들어요.저는 접미사 트리 구조에 대해 머리를 싸매려고 며칠을 보냈습니다만, 수학적인 배경이 없기 때문에, 많은 설명들이 수학적인 기호를 과도하게 사용하기 시작하면서 이해가 가지 않습니다.내가 발견한 가장 좋은 설명은 '서픽스 트리로 빠른 문자열 검색'이지만, 그는 여러 점을 얼버무리고 알고리즘의 일부 측면은 불분명하다.
Stack Overflow에 대한 이 알고리즘에 대한 단계별 설명은 저 이외의 많은 사람들에게 매우 유용할 것입니다.
참고로 알고리즘에 관한 Ukkonen의 논문은 다음과 같습니다.http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
지금까지의 저의 기본 지식:
- 특정 문자열 T의 각 프리픽스 P를 반복해야 합니다.
- 접두사 P의 각 접미사 S를 반복하여 트리에 추가해야 합니다.
- 트리에 서픽스 S를 추가하려면 S의 각 문자를 반복해야 합니다.반복하는 것은 S의 동일한 문자 세트 C로 시작하는 기존 분기를 내려가고 서픽스 내의 다른 문자가 도달했을 때 에지를 하위 노드로 분할하는 것입니다.또는 걸어 내려갈 수 있는 일치하는 가장자리가 없다면.C에 대해 워크다운할 일치하는 가장자리가 발견되지 않으면 C에 대해 새 리프 가장자리가 생성됩니다.
기본 알고리즘은 대부분의 설명에서 설명한 바와 같이 O(n2)인 것으로 보입니다.모든 프레픽스를 순서대로 처리해야 하기 때문에 각 프레픽스에 대해 각 서픽스를 순서대로 처리해야 합니다.Ukkonen의 알고리즘은 서픽스 포인터 테크닉을 사용하고 있기 때문에 매우 독특하다고 생각합니다만, 저는 그것을 이해하기 어렵다고 생각합니다.
저도 잘 모르겠습니다.
- '액티브 포인트'가 정확히 언제 어떻게 할당, 사용 및 변경되는가
- 알고리즘의 성화 측면에서는 무슨 일이 일어나고 있는가?
- 지금까지 본 구현에서 사용하고 있는 경계 변수를 '수정'해야 하는 이유
이것이 완성된 C# 소스 코드입니다.올바르게 동작할 뿐만 아니라, 자동 캐논라이제이션도 서포트해, 출력의 텍스트 그래프를 보다 아름답게 표현합니다.소스 코드 및 샘플 출력은 다음과 같습니다.
2017-11-04 업데이트
몇 년 후 접미사 트리의 새로운 용도를 발견하여 자바스크립트에 알고리즘을 구현했습니다.Gist는 다음과 같습니다.버그가 없어야 합니다.js 파일로 덤프합니다.npm install chalk"node.display" "node.display" "node.display" "node.display" 입니다.디버깅 코드 없이 동일한 Gist에 제거된 버전이 있습니다.
https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6
다음은 문자열이 단순할 때(즉, 반복된 문자가 포함되지 않을 때) 실행되는 동작을 먼저 보여주고 나서 완전한 알고리즘으로 확장함으로써 Ukkonen 알고리즘을 설명하려는 시도입니다.
먼저, 몇 가지 예비 진술이 있습니다.
우리가 만들고 있는 것은 기본적으로 수색 트라이와 같습니다.루트 노드가 있고, 거기서 나오는 가장자리가 새로운 노드로 이어지고, 거기서 나오는 가장자리 등이 있습니다.
단, 검색 트라이와 달리 엣지 라벨은 단일 문자가 아닙니다.대신, 각 모서리에는 정수 쌍을 사용하여 레이블이 지정됩니다.
[from,to]이치노이러한 의미에서 각 에지는 임의의 길이의 문자열 라벨을 전송하지만 O(1) 공간(2개의 포인터)만 사용합니다.
기본원칙
먼저 간단한 문자열의 접미사 트리를 만드는 방법에 대해 설명하겠습니다.문자 반복이 없는 문자열입니다.
abc
알고리즘은 왼쪽에서 오른쪽으로 스텝으로 동작합니다.문자열의 모든 문자에는 하나의 단계가 있습니다.각 단계에는 둘 이상의 개별 작업이 수반될 수 있지만, 총 작업 수는 O(n)임을 알 수 있습니다(마지막에 있는 최종 관측치 참조).
그래서 왼쪽부터 시작해서 먼저 한 글자만 넣어요.a하고, 을 「 노드(왼쪽)」라고 하는 라벨로 .[0,#]즉, 에지는 위치 0에서 시작하여 현재 끝에서 끝나는 서브스트링을 나타냅니다.나는 심볼을 사용한다.#위치 1(직후)에 있는 현재 끝을 의미한다.a를 참조해 주세요.
첫 번째 트리는 다음과 같습니다.
그 의미는 다음과 같습니다.
, 그럼 이제 2번에 2번)으로.b각 단계에서 목표는 현재 위치까지 모든 접미사를 삽입하는 것입니다.이 작업을 수행할 때
- " " " 확장
a- 부터 -ab -
b
우리의 표현으로 이것은 다음과 같이 보인다.
그 의미는 다음과 같습니다.
다음 두 가지를 관찰합니다.
- " " 의
ab초기 트리와 동일합니다.[0,#]했기#에서 21까지입니다. - 각 에지는 텍스트에 대한 포인터 2개만으로 구성되므로 O(1) 공간을 사용합니다.
고칩니다.c 서픽스 「New 」를 합니다.c.
우리의 표현으로 이것은 다음과 같이 보인다.
그 의미는 다음과 같습니다.
델은 다음과 같이 관찰합니다.
- 이 트리는 각 단계 후 현재 위치까지 올바른 접미사 트리입니다.
- 텍스트의 글자 수만큼 단계가 있습니다.
- (1)입니다.는 O(1)를 입니다. 모든 기존 가장자리가 증가하여 자동으로 업데이트되기 때문입니다.
#마지막 문자의 새로운 엣지를 1개 삽입하면 O(1)시간 내에 완료할 수 있습니다.따라서 길이가 n인 문자열에는 O(n) 시간만 필요합니다.
첫 번째 내선번호:단순 반복
물론 이것은 우리의 문자열에 반복이 포함되어 있지 않기 때문에 매우 잘 작동합니다.이제 좀 더 현실적인 문자열을 살펴보겠습니다.
abcabxabcd
, 먼저 with터시 it it이다로 시작합니다.abc 「」를 참조해 주세요.ab '아까불까불까불까불까불까불까불까불까불까불까불까불까불까'가 나옵니다.x , , 을 누릅니다.abc 반복이 됩니다.d.
스텝 1 ~ 3: 첫 번째 3단계 뒤에 이전 예제의 트리가 있습니다.
4단계: 이동#4번입니다.이렇게 하면 모든 기존 에지가 암묵적으로 업데이트됩니다.
인 '아까면 안 될 것 같다'를 넣어야 합니다.a
이 작업을 수행하기 전에 두 가지 변수를 더 소개합니다.#물론 항상 사용했지만 지금까지 사용하지 않았습니다.
- 액티브 포인트는 트리플입니다.
(active_node,active_edge,active_length) remainder를 몇 개
이 두 개의 정확한 의미는 곧 밝혀지겠지만, 일단은 다음과 같이 말해 두자.
- 말하면
abc를 들어, 「」입니다.(root,'\0x',0)discriptions.active_node노드입니다.active_edge문자로 되었습니다.'\0x', , , , 입니다.active_length0이었다이었습니다.그 결과 모든 단계에서 삽입한 하나의 새로운 에지가 루트 노드에 새로 생성된 에지로 삽입되었습니다.우리는 왜 이 정보를 나타내기 위해 트리플이 필요한지 곧 알게 될 것이다. remainder각 스텝의 선두에서는 항상 1로 설정되어 있습니다.그 의미는 각 스텝의 마지막에 적극적으로 삽입해야 하는 접미사의 수가 1(항상 마지막 문자만)이라는 것입니다.
이제 이 상황은 바뀔 것이다. 글자를 할 때a 「는 이미 「 에지는」, 「출발 에지는 「출발 에지는 「출발 에지」로 .a구체적으로는 다음과 같습니다.abca때 과 같습니다.
- 새로운 엣지는 삽입하지 않습니다.
[4,#]루트 노드에 있습니다. 서픽스 「」가 붙어 을 알 수 있습니다.a이미 우리 트리 안에 있어요더 긴 가장자리의 중간에서 끝나지만 우리는 그것에 대해 신경 쓰지 않는다.그냥 이대로 놔두면 돼 - 액티브 포인트를 다음과 같이 설정합니다.
(root,'a',1), 는 루트 노드의 에지는 starts, 티, 음, 음, 음 등으로 시작됩니다.a1번, 1번, 1번, 1번, 1번.첫된다는 것을 알 수 있습니다.a특정 문자로 시작하는 엣지는 1개뿐이므로 이 정도면 충분합니다(설명 전체를 읽어본 후 이것이 사실임을 확인). - 아, 아, 아, 아, 아, 하다를 늘립니다.
remainder2번으로 하다
관찰:삽입해야 할 최종 접미사가 트리에 이미 존재하는 경우 트리 자체는 변경되지 않습니다(액티브포인트와 업데이트만 합니다).remainder그러면 트리는 현재 위치까지 접미사 트리의 정확한 표현은 아니지만 모든 접미사가 포함됩니다(최종 접미사가 있기 때문입니다).a암묵적으로 포함되어 있습니다).따라서 변수(모두 고정 길이이므로 O(1))를 업데이트하는 것 외에 이 단계에서는 작업이 수행되지 않았다.
5단계: 현재 위치를 업데이트합니다.#으로 이트리로 그러면 트리가 다음 트리가 자동적으로 갱신됩니다.
그리고 2이므로 현재 위치의 마지막 접미사를 두 개 삽입해야 합니다.ab ★★★★★★★★★★★★★★★★★」b다음과 같습니다.
a이전 단계의 접미사가 제대로 삽입되지 않았습니다.그래서 그것은 남아 있었고, 우리가 한 단계 발전한 이후, 그것은 이제 에서 성장해 왔다.a로로 합니다.ab.- 모서리를 새로 요.
b.
는 '액티브 을 의미합니다.a에 있어서abcab엣지 글자를 합니다.b하지만 다시 한 번 말씀드리지만b같은 엣지에도 이미 존재합니다.
다시 말씀드리지만 트리는 변경하지 않습니다.델의 심플한 점은 다음과 같습니다.
- 를 「」로 갱신합니다.
(root,'a',2)입니다만, 는 (노드나 등)b) - 「」를 인크리먼트 .
remainder이전 단계에서 최종 에지를 제대로 삽입하지 않았고 현재 최종 에지도 삽입하지 않았기 때문에 3으로 이동합니다.
명확히 하자면:우리는 삽입해야 했다.ab ★★★★★★★★★★★★★★★★★」b, 「」의 이유로, 「」는 「」가 됩니다.ab.또, 「접근처」나 「접근처」를 않았습니다.b??ab모든 접미사가 트리 안에 있습니다(등).b)도 트리에 있어야 합니다.암묵적으로만 그럴 수도 있지만, 우리가 지금까지 트리를 만든 방법 때문에 반드시 거기에 있을 거야.
스텝 6으로 넘어갑니다.#리음
왜냐하면 3이니까 삽입을 해야 돼요.abx,bx ★★★★★★★★★★★★★★★★★」x는 어디에 있는지 줍니다.ab요.x이지, . . . . . . . . . . . . . 。x하지 않았기 에, 「」을 합니다.abcabx이치
에지 표현은 여전히 텍스트에 대한 포인터이므로 내부 노드를 분할하고 삽입하는 작업은 O(1) 시간 내에 수행할 수 있습니다.
까지 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★abx 디크리먼트 andremainder접미사인 '먹다'를 요.bx그러나 그 전에 액티브포인트를 갱신할 필요가 있습니다.엣지를 분할하여 삽입한 후 이 규칙을 아래 규칙 1이라고 부릅니다.이 규칙은 항상 적용됩니다.active_node는 root 입니다(아래에 있는 다른 경우에 대해서는 규칙 3에 대해 학습합니다).1번 룰이 있어요.
루트 삽입 후
active_node(루트)인 채로 .active_edge할 의 첫 되어 있습니다.bactive_length† 감소
트리플은(root,'b',1), 하다, 하다, 하다, 하다, 하다, 에서 해야 합니다.bcabx즉 '뒤', '1글자 '뒤'b 내에 하고 O(1)가 삽입되었는지 여부를 할 수 x이미 존재하는지 여부를 확인합니다.만약 그것이 존재한다면, 우리는 현재의 단계를 끝내고 모든 것을 그대로 둘 것이다. ★★★★★★★★★★★★★★★★★.x하지 않기 합니다.
이(1) , 는 O(1)입니다.remainder를 1로 합니다.(root,'x',0)1번으로 하다
하지만 우리가 해야 할 일이 하나 더 있어.이 룰 2라고 부릅니다.
가장자리를 분할하여 새 노드를 삽입하고 현재 단계에서 작성된 첫 번째 노드가 아닌 경우 이전에 삽입된 노드와 새 노드를 특수 포인터인 접미사 링크를 통해 연결합니다.우리는 그것이 왜 유용한지 나중에 알게 될 것이다.접미사 링크는 점으로 둘러싸인 가장자리로 표시됩니다.
현재 단계의 마지막 접미사를 삽입해야 합니다.x. 그 이후로active_length액티브 노드의 컴포넌트가 0으로 떨어지면 루트에서 직접 최종 삽입이 이루어집니다. 에는 「」로 에,x 모서리를요.
보시는 바와 같이, 현재 단계에서는 나머지 모든 삽입이 이루어졌습니다.
설정에 의해 스텝7로 넘어갑니다.#=7, 으면 되다, 하다, 하다, 하다를 a모든 리프 엣지(항상 그렇듯이)에 대응합니다.그런 다음 활성 지점(루트)에 새 최종 문자를 삽입하려고 시도하면 해당 문자가 이미 존재하는 것을 알 수 있습니다. 아무것도 하지 않고 현재 .(root,'a',1).
스텝 8에서#=8개 추가b와 같이 를 갱신하는 것을 (root,'a',2) 「」remainder도 안 요.왜냐하면요.왜냐하면b는 이미 존재합니다.단, 액티브포인트가 에지의 끝에 있는 것을 알 수 있습니다(O(1)시간).이것을 다음과 같이 재설정하여 반영합니다.(node1,'\0x',0)기,, 는는을 사용합니다node1 ab엣지 끝은 다음과 같습니다.
그런 다음 =9단계에서 'c'를 삽입하면 최종 요령을 이해하는 데 도움이 됩니다.
두 번째 내선번호:서픽스 링크 사용
그렇듯이, 「」는# appends " " " "c자동으로 리프 가장자리로 이동하고 활성 지점으로 이동하여 'c'를 삽입할 수 있는지 확인합니다.에 'c을 'c'로 합니다. 그래서 우리는 활성 지점을(node1,'c',1) , "discrement"remainder른른른른른른 른른른른른
이제 스텝 =10에서remainder를 먼저 요. 을 사용법abcd 전)을하여 (3단계 전을 남깁니다.d액티브 포인트에서
" " " 삽입 d활성 지점에서 에지가 O(1) 시간 내에 분할됩니다.
active_node스플릿이 시작된 시점은 위의 빨간색으로 표시되어 있습니다.마지막 규칙 3은 다음과 같습니다.
후
active_node경우 " 노드"를 리셋합니다.그 노드로부터 나가는 서픽스 링크를 따라가, 그 링크가 있는 경우는 리셋 합니다.active_node이 노드가 가리키는 노드입니다.링크가 는, 「」를 합니다.active_node뿌리까지.active_edge★★★★★★★★★★★★★★★★★」active_length함이이없없
에서 액티브포인트는 'Active 가 됩니다(node2,'c',1) , , , , 입니다.node2이치노
「 」가 abcd decrement 、 감 isremainder 해서 3단계에서 해서 3단계에서 3단계는 3단계는 3단계는 3단계는 3단계는 3단계는 3단계는 3단계는 3단계입니다.bcd 「3」을 삽입합니다.bcd 글자를 만으로 할 수 d액티브 포인트에서
이렇게 하면 또 다른 엣지가 분할됩니다.규칙 2에 따라 이전에 삽입한 노드에서 새로운 노드로 서픽스링크를 작성해야 합니다.
서픽스 링크를 사용하면 액티브 포인트를 리셋할 수 있기 때문에, O(1)에 의한 다음 삽입을 실시할 수 있습니다.위의 그래프를 보고 레이블에 노드가 있는지 확인하십시오.ab는 노드로 .b및 (서픽스)의 :abc 연결되어 있습니다.bc.
이치노 remainder2번입니다.규칙 3에 따라 액티브포인트를 다시 리셋해야 합니다.의 「 」active_node(위의 빨간색)에는 접미사 링크가 없습니다.루트로 리셋 됩니다.액티브 포인트는 지금입니다.(root,'c',1).
다음 이 "하다"로 의 한쪽 합니다.ccabxabcd문자 즉 에, " "는 ", "는 ", "는 ", "는c이로 인해 다른 스플릿이 발생합니다.
여기에는 새로운 내부 노드의 생성이 포함되므로 규칙 2에 따라 이전에 작성한 내부 노드에서 새로운 서픽스링크를 설정합니다.
(이 작은 그래프에는 Graphviz Dot을 사용하고 있습니다.새로운 서픽스 링크로 인해 도트가 기존 에지를 재배치하였으므로 위에 삽입된 것이 새로운 서픽스 링크뿐인지 주의하여 확인하십시오.)
이렇게하면요.remainder할 수 할 수 있습니다.active_noderoot를 root 다입 root로 합니다.규칙 1을 사용하여 액티브포인트를 갱신합니다.(root,'d',0), 이 은 1개의 삽입, 1개의 d★★★★
그것이 마지막 단계였고 우리는 끝났다.그러나 다음과 같은 몇 가지 최종 관측치가 있습니다.
에서 이동한다.
#1월 1일그러면 O(1) 시간 내에 모든 리프 노드가 자동으로 업데이트됩니다.그러나 a) 이전 단계에서 남아 있는 접미사 및 b) 현재 단계의 마지막 문자 하나와 관련된 접미사는 다루지 않습니다.
remainder에 추가 삽입 수를 나타냅니다.은 현재 로 대응합니다.#하나하나 검토하여 인서트를 만듭니다.중요:각 삽입은 O(1)시간 내에 완료됩니다.액티브 포인트는 위치를 정확하게 알려주고 액티브포인트에 1글자만 추가하면 되기 때문입니다.왜일까요?다른 문자는 암묵적으로 포함되어 있기 때문에(그렇지 않으면 액티브포인트는 현재 위치에 없습니다).삽입을 할 , 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다, 줄인다.
remainder서픽스 링크가 있는 경우는, 그 링크를 클릭해 주세요.3번으로 나누다이미 루트에 있는 경우 규칙 1을 사용하여 활성 지점을 수정합니다.O(1)라고 합니다.하고 싶은 가 이미 있는 현재 합니다.
remainder>0. 그 이유는 나머지 삽입물은 방금 만든 삽입물의 접미사가 되기 때문입니다.따라서 모두 현재 트리에 암묵적으로 포함되어 있습니다.이 사실은remainder> 0 에서는, 나머지 서픽스에 대해서는 나중에 확실히 취급합니다.remainder0?의 끝부분이 일 때 이것은 텍스트의 끝이 이전에 발생한 서브스트링일 때 발생합니다.이 경우 이전에는 발생하지 않았던1개의 문자를 문자열 끝에 추가해야 합니다.문헌에서, 보통 달러 기호는$그 상징으로 쓰입니다.이것이 중요한 이유는 무엇입니까? --> 나중에 완성된 서픽스 트리를 사용하여 서픽스를 검색할 경우 리프에서 끝나는 경우에만 일치를 허용해야 합니다.그렇지 않으면 많은 가짜 일치가 발생합니다.메인 문자열의 실제 서픽스가 아닌 문자열이 트리에 암묵적으로 포함되어 있기 때문입니다.강제remainder기본적으로 모든 접미사가 리프 노드에서 끝나도록 하기 위한 방법입니다.단, 메인 문자열의 서픽스뿐만 아니라 일반적인 서브스트링을 검색하기 위해 트리를 사용하는 경우에는 아래 OP의 코멘트에서 제시된 바와 같이 이 마지막 단계는 필요하지 않습니다.그러면 알고리즘 전체의 복잡성은 어느 정도일까요?텍스트 길이가 n자일 경우 스텝이 n개(달러 기호를 추가하는 경우 n+1)로 나타납니다.도 하지 (변수 갱신 이외에는)를 만듭니다.
remainderO(1)라고 합니다.★★remainder는 이전 단계에서 아무것도 하지 않은 횟수로, 현재 삽입할 때마다 감소하는 횟수를 나타냅니다.nnnnnn(n+1)O(n)하다하지만 제가 제대로 설명하지 못한 작은 것이 하나 있습니다.링크에 , 그 링크가 액티브 포인트인 을 알 수.
active_length컴포넌트에서는 .active_node예를 들어 다음과 같은 상황을 생각해 봅시다.
(파선은 트리의 나머지 부분을 나타냅니다.점선은 서픽스 링크입니다).
를 'Active point'로 (red,'d',3) 있습니다.f defg엣지. 이제 필요한 업데이트를 하고 서픽스 링크를 따라 규칙 3에 따라 활성 지점을 업데이트한다고 가정합니다.는 '''입니다.(green,'d',3) 단,입니다.★★★★★★★★★★★★★★★★★ 。d- 는 - "입니다.de2번포인트를 , 그해, 「」로 할 .(blue,'f',1).
" " "는active_length와 같은 크기일 수 있다remainder(n까지 가능합니다).또, 적절한 액티브 포인트를 찾기 위해서, 1개의 내부 노드(최악의 경우 n개까지)를 점프할 필요가 있는 경우도 있습니다.즉, 알고리즘에는 O(n2)의 복잡성이 숨겨져 있는 것입니까?각 단계에서remainder는 일반적으로 O(n)이며, 서픽스 링크에 이어 액티브노드로의 사후 조정도 O(n)가 될 수 있습니다.
아니요.그위와 를해야 할 입니다. 그 이유는 액티브포인트(예를 들어 위와 같이 녹색에서 파란색으로)를 조정해야 할 경우 자체 접미사 링크가 있는 새로운 노드로 이동하기 때문입니다.active_length 인 '접미사 연결 고리'를 요.active_length 수가 줄어들 밖에 없고, 할 수 횟수는 그 수 .active_length언제든지 할 수 있습니다.★★active_length 더 클 수 remainder , , , , 입니다.remainder만 아니라 까지 O(n)로 증가된 도 O(n)로 되어 있습니다.remainder전체 공정의 과정에서도 O(n)가 되며 활성 점 조정 횟수도 O(n)로 제한됩니다.
JOGOJAPAN의 답변에 따라 서픽스 트리를 구현하려고 했지만 규칙에 사용된 표현으로 인해 작동하지 않는 경우가 있었습니다.게다가, 이 어프로치를 사용해 완전히 올바른 서픽스 트리를 실장하는 사람은 아무도 없다고 언급했습니다.이하에, 조고 재팬의 회답의 「개요」를 몇개의 룰을 수정해 적습니다.또, 중요한 서픽스 링크를 작성하는 것을 잊은 경우도 기술합니다.
추가 변수 사용
- active point - 새로운 서픽스를 삽입할 필요가 있는 위치에서 나타내는 트리플(active_node; active_edge; active_length).
- rember - 명시적으로 추가해야 하는 접미사 수를 표시합니다.예를 들어, 우리의 단어가 'abcaabca'이고 나머지가 = 3이면, 우리는 bca, ca, a라는 세 개의 마지막 접미사를 처리해야 한다는 것을 의미한다.
내부 노드의 개념을 사용합니다.루트와 리프(leaf)가 내부 노드인 것을 제외한 모든 노드가 내부 노드입니다.
관찰 1
해야 할 이미 는 트리를 입니다).active point ★★★★★★★★★★★★★★★★★」remainder를 참조해 주세요.
관찰 2
active_length에지의 (즉, 현재 에지의 길이)edge_length） 、 델 、 델 、 。active point★★★★★★★★★★★★★★★★★★까지edge_length 엄히 than than보다 크다active_length.
이제 규칙을 다시 정의하겠습니다.
규칙 1
활성 노드 = root에서 삽입한 후 활성 길이가 0보다 큰 경우:
- 활성 노드가 변경되지 않음
- 활성 길이가 감소함
- 활성 가장자리가 오른쪽으로 이동됨(다음 접미사의 첫 번째 문자로 삽입해야 함)
규칙 2
새로운 내부 노드를 작성하거나 내부 노드에서 inserter를 만들 때 현재 단계에서 첫 번째 SUC 내부 노드가 아닌 경우 접미사 링크를 통해 이전 SUC 노드를 THIS 노드와 링크합니다.
의 이 입니다.Rule 2jogojapan'과는 다릅니다.새로 생성된 내부 노드뿐만 아니라 삽입을 하는 내부 노드도 고려합니다.
규칙 3
루트 노드가 아닌 액티브노드에서 삽입 후 서픽스링크를 따라 액티브노드를 포인트노드로 설정해야 합니다.접미사 링크가 없는 경우 활성 노드를 루트 노드로 설정합니다.어느 쪽이든 활성 에지와 활성 길이는 변경되지 않습니다.
의 이 Rule 3리프 노드의 삽입도 고려하고 있습니다(스플릿 노드뿐만 아니라).
마지막으로, 관찰 3:
때, 그 심볼에 , 그 심볼에 붙이고 싶은 심볼이렇게.Observation 1 only , " " " " "active point ★★★★★★★★★★★★★★★★★」remainder트리를 변경하지 않고 그대로 둡니다.그러나 접미사 링크가 필요하다고 표시된 내부 노드가 있는 경우 해당 노드를 현재 노드에 연결해야 합니다.active node서픽스 링크를 통해
cddcdc의 서픽스트리의 예를 보겠습니다.이 경우 서픽스링크를 추가하고 추가하지 않으면 다음과 같습니다.
접미사 링크를 통해 노드를 연결하지 않는 경우:
- 마지막 문자 c를 추가하기 전에:
- 마지막 문자 c를 추가한 후:
접미사 링크를 통해 노드를 연결하는 경우:
- 마지막 문자 c를 추가하기 전에:
- 마지막 문자 c를 추가한 후:
큰 차이는 없는 것 같습니다.두 번째 예에서는 2개의 서픽스 링크가 더 있습니다.그러나 이러한 접미사 링크는 정확하며, 그 중 하나(파란색 노드부터 빨간색 노드까지)는 액티브포인트에 대한 접근법에 매우 중요합니다.문제는 여기에 서픽스링크를 붙이지 않으면 나중에 트리에 새 문자를 추가할 때 트리에 노드 추가를 생략할 수 있다는 점입니다.Rule 3에 따르면, 서픽스 링크가 없는 경우, 이 링크는active_node뿌리까지.
트리에 마지막 문자를 추가할 때 빨간색 노드는 파란색 노드(가장자리에 'c' 라벨이 붙어 있음)에서 삽입하기 전에 이미 존재했습니다.파란색 노드에서 삽입이 있었기 때문에 서픽스 링크가 필요하다고 표시했습니다.그리고 액티브 포인트 어프로치에 의존하여active node빨간색 노드로 설정되었습니다.단, 빨간색 노드에서 삽입은 하지 않습니다.문자 'c'가 이미 가장자리에 있기 때문입니다.파란 노드는 서픽스 링크 없이 남겨야 한다는 뜻인가요?아니요, 파란색 노드와 빨간색 노드를 접미사 링크를 통해 연결해야 합니다.왜 맞을까요?액티브 포인트 어프로치는, 적절한 장소, 즉, 보다 짧은 접미사를 삽입할 필요가 있는 다음 장소에의 액세스를 보증하기 때문입니다.
마지막으로 서픽스 트리의 실장은 다음과 같습니다.
이 「개요」와 조고 재팬의 상세한 회답이 조합되어 누군가가 자신의 서픽스 트리를 실장하는 데 도움이 되었으면 한다.
만약 제 답변이 불필요한 것 같다면 죄송합니다.최근에 Ukkonen의 알고리즘을 실장했습니다만, 며칠간 이 알고리즘에 대해 고민하고 있었습니다.알고리즘의 주요 측면의 이유와 방법을 이해하기 위해서, 그 주제에 관한 복수의 논문을 읽어낼 필요가 있었습니다.
이전 답변의 '규칙' 접근법은 근본적인 이유를 이해하는 데 도움이 되지 않는다는 것을 알았기 때문에, 아래에 있는 모든 것을 오로지 프래그매틱스에 초점을 맞춰 작성했습니다.만약 당신이 저처럼 다른 설명을 따르는데 어려움을 겪고 있다면, 아마도 제 보충 설명이 당신을 '찰칵'하게 만들 것입니다.
C#의 실장은, https://github.com/baratgabor/SuffixTree 에서 공개했습니다.
저는 이 주제에 대해 전문가가 아니기 때문에 다음 섹션에는 부정확한 내용이 포함될 수 있습니다.어떤 것이라도 발견되면, 자유롭게 편집해 주세요.
전제 조건
다음 설명의 시작점은 사용자가 접미사 트리의 내용 및 사용법, Ukkonen 알고리즘의 특징(예를 들어 문자별로 접미사 트리를 어떻게 확장하는지)에 대해 잘 알고 있다고 가정합니다.기본적으로, 다른 설명은 이미 읽어보셨을 겁니다.
(단, 흐름의 기본적인 설명을 추가해야 하기 때문에 처음에 장황하게 느껴질 수 있습니다.)
가장 흥미로운 부분은 서픽스 링크를 사용하는 것과 루트에서 다시 스캔하는 것의 차이에 대한 설명입니다.이것이, 실장중에 많은 버그와 골칫거리가 되었습니다.
오픈 엔드 리프 노드 및 그 제한
가장 기본적인 '꼼수'는 접미사의 끝을 고정값으로 설정하는 대신 문자열의 현재 길이를 참조하는 '열린' 상태로 두면 된다는 것을 이미 알고 있습니다.이렇게 하면 문자를 추가할 때 모든 서픽스 라벨에 해당 문자가 암묵적으로 추가되므로 모든 서픽스 라벨에 액세스하여 갱신할 필요가 없습니다.
단, 이 서픽스의 오픈엔딩은 명백한 이유로 스트링의 끝을 나타내는 노드, 즉 트리 구조의 리프노드에 대해서만 기능합니다.트리에서 실행하는 분기 작업(새로운 분기 노드 및 리프 노드 추가)은 필요한 모든 곳에 자동으로 전파되지 않습니다.
반복된 서브스트링이 트리에 명시적으로 나타나지 않는 것은 아마도 기초적이고 언급할 필요가 없을 것입니다. 왜냐하면 트리는 이미 반복적인 서브스트링을 포함하기 때문입니다.단, 반복적인 서브스트링이 비반복적인 문자와 조우함으로써 종료되었을 때,그 시점부터의 차이를 나타내기 위해 그 지점에 분기를 만들 필요가 있습니다.
예를 들어 'ABCX' 문자열의 경우ABCY' (아래 참조)는 X와 Y로 분기하는 것을 ABC, BC, C의 세 가지 다른 접미사에 추가해야 합니다.그렇지 않으면 유효한 접미사 트리가 되지 않기 때문에 루트부터 아래까지 문자를 일치시켜 문자열의 모든 하위 문자열을 찾을 수 없습니다.
다시 한 번 강조합니다.트리의 서픽스에 대해서 실행하는 조작은, 연속하는 서픽스(예를 들면, ABC > BC > C)에 의해서도 반영할 필요가 있습니다.그렇지 않으면, 그것들은 유효한 서픽스가 되지 않게 됩니다.
그러나 이러한 수동 갱신을 해야 한다고 해도 갱신해야 하는 서픽스의 수를 어떻게 알 수 있을까요?반복문자 A(및 나머지 반복문자 연속)를 추가할 때 접미사를 언제 어디서 2개의 분기로 분할해야 하는지 알 수 없기 때문입니다.분할의 필요성이 확인되는 것은 첫 번째 비반복 문자(이 경우 트리에 이미 존재하는 X가 아닌 Y)가 발생한 경우뿐입니다.
가능한 한 길게 반복되는 문자열을 대조하여 나중에 업데이트해야 하는 서픽스 수를 세는 것이 가능합니다.이것이 'remainer'의 약자이다.
'remainer'와 'rescanning'의 개념
변수remainder는 분기하지 않고 암묵적으로 추가한 반복 문자 수, 즉 일치하지 않는 첫 번째 문자가 발견된 후 분기 조작을 반복하기 위해 방문해야 하는 서픽스 수를 나타냅니다.이는 본질적으로 트리의 뿌리에서부터 얼마나 많은 문자가 '깊이' 있는지와 같습니다.
따라서 ABCX 문자열의 이전 예를 그대로 사용합니다.ABCY, 우리는 반복된 ABC 부분을 '암묵적으로' 일치시키고, 증가시킨다.remainder그 결과 3이 남습니다.그러면 반복되지 않는 문자 'Y'를 만나게 됩니다.여기에서는 이전에 추가한 ABCX를 ABC->X와 ABC->Y로 분할합니다.그러면 우리는 감소한다.remainder3시부터 2시까지 ABC 지사를 이미 처리했기 때문입니다.여기서 루트부터 마지막 2개의 문자(BC)를 대조하여 분할할 필요가 있는 포인트에 도달하고 BCX를 BC->X와 BC->Y로 분할하여 작업을 반복합니다.다시, 우리는 감소한다.remainder한다.remainder는 0 입니다.마지막으로 현재 문자(Y) 자체를 루트에 추가해야 합니다.
루트에서 연속된 서픽스를 따라 단순히 연산을 수행해야 하는 지점에 도달하는 이 연산을 Ukkonen 알고리즘에서는 '재스캐닝'이라고 부릅니다.일반적으로 이것은 알고리즘에서 가장 비용이 많이 드는 부분입니다.수십 개의 노드에 걸쳐 긴 서브스트링을 수천 번 '리스캔'해야 하는 긴 스트링을 상상해 보십시오(나중에 설명하겠습니다).
해결책으로 이른바 'suffix links'를 소개합니다.
suffix links의 개념
서픽스 링크는 기본적으로 우리가 일반적으로 '재할 수 있는' 위치를 가리키기 때문에 비용이 많이 드는 재스캔 작업 대신 링크된 위치로 이동하여 작업을 수행하고 다음 링크된 위치로 이동하여 업데이트할 위치가 없어질 때까지 반복할 수 있습니다.
물론 이러한 링크를 추가하는 방법은 매우 중요합니다.기존의 답은 새로운 분기 노드를 삽입할 때 링크를 추가할 수 있다는 것입니다.트리의 각 확장에서 분기 노드는 서로 링크해야 하는 정확한 순서로 자연스럽게 하나씩 생성됩니다.단, 마지막으로 작성한 브랜치노드(가장 긴 서픽스)에서 이전에 작성한 브랜치노드(가장 긴 서픽스)로 링크해야 합니다.따라서 마지막으로 작성한 노드를 캐시하고 다음으로 작성한 노드에 링크하여 새로 작성한 노드를 캐시해야 합니다.
그 결과 특정 분기 노드가 방금 생성되었기 때문에 실제로 서픽스 링크가 없는 경우가 많습니다.이러한 경우, 우리는 여전히 앞서 언급한 '재개'로 근본부터 돌아가야 합니다.따라서 삽입 후 접미사 링크를 사용하거나 루트로 이동하라는 메시지가 나타납니다.
(혹은 부모 포인터를 노드에 저장하는 경우 부모 포인터를 팔로우하여 링크가 있는지 확인하고 사용할 수 있습니다.이것은 거의 언급되지 않지만, 서픽스 링크의 용법은 돌에 설정되어 있지 않습니다.여러 가지 접근법이 있습니다.기본적인 메커니즘을 이해하면 요구에 가장 적합한 방법을 구현할 수 있습니다.)
'액티브 포인트'의 개념
지금까지 트리를 구축하기 위한 여러 효율적인 툴에 대해 논의했으며, 여러 에지 및 노드를 통과하는 것에 대해 모호하게 언급했지만, 이에 따른 결과 및 복잡성에 대해서는 아직 검토하지 않았습니다.
앞서 설명한 'remainer' 개념은 트리의 위치를 추적하는 데 유용하지만 충분한 정보를 저장하지 않는다는 것을 깨달아야 합니다.
첫째, 항상 노드의 특정 엣지에 존재하기 때문에 엣지 정보를 저장해야 합니다.이것을 「액티브 에지」라고 부릅니다.
둘째, 엣지 정보를 추가한 후에도 루트 노드에 직접 연결되지 않고 트리에서 더 아래쪽에 있는 위치를 식별할 수 없습니다.따라서 노드도 저장해야 합니다.이것을 「액티브 노드」라고 부릅니다.
마지막으로, "remainer"는 루트 전체의 길이이기 때문에 루트에 직접 연결되어 있지 않은 엣지 상의 위치를 식별하기에 불충분하다는 것을 알 수 있습니다.또한 이전 엣지의 길이를 기억하고 뺄 필요가 없을 수도 있습니다.따라서 우리는 기본적으로 현재 가장자리의 나머지가 되는 표현이 필요합니다.이것을 '활성 길이'라고 합니다.
이를 통해 이른바 '액티브 포인트'가 생성됩니다.이 세 가지 변수에는 트리에서 당사의 위치에 대해 유지해야 하는 모든 정보가 포함되어 있습니다.
Active Point = (Active Node, Active Edge, Active Length)
다음 이미지에서 ABCABD의 일치 경로가 엣지 AB(루트에서)에 2자, 엣지 CABDABCABD(노드 4에서)에 4자로 구성되어 6자의 '잔량'이 되는 것을 확인할 수 있습니다.따라서 현재 위치는 Active Node 4, Active Edge C, Active Length 4로 식별할 수 있습니다.
'액티브 포인트'의 또 다른 중요한 역할은 알고리즘에 추상화 레이어를 제공한다는 것입니다. 즉, 액티브 포인트가 루트에 있는지 여부에 관계없이 알고리즘의 일부가 '액티브 포인트'에서 작업을 수행할 수 있다는 것을 의미합니다.이것에 의해, 서픽스 링크의 사용을 알기 쉽고 알기 쉬운 방법으로 실장할 수 있습니다.
다시 검색과 접미사 링크 사용의 차이점
제 경험상 어려운 점은 서픽스 링크 케이스와 재스캔 케이스의 처리의 차이입니다.이것은, 서픽스 링크 케이스의 처리와 재스캔 케이스의 차이입니다.
'AAAB' 문자열의 다음 예를 고려하십시오.AAABAAC':
위의 'remainer'가 루트의 총 문자 합계에 해당하는 반면, 'active length'가 4인 경우 활성 노드의 활성 가장자리에서 일치된 문자 합계에 해당하는 방식을 관찰할 수 있습니다.
액티브 포인트에서 분기 조작을 실행한 후 액티브노드에 서픽스링크가 포함될 수도 있고 포함되지 않을 수도 있습니다.
서픽스 링크가 존재하는 경우:'활성 길이' 부분만 처리하면 됩니다.접미사 링크를 통해 점프하는 노드가 이미 암시적으로 올바른 'remainer'를 인코딩하고 있기 때문에 'remainer'는 관련이 없습니다. 단순히 해당 노드가 있는 트리에 있기 때문입니다.
서픽스 링크가 존재하지 않는 경우:0/root부터 다시 시작해야 합니다. 즉, 처음부터 전체 접미사를 처리해야 합니다.이를 위해 전체 '남은 것'을 다시 검색의 기본으로 사용해야 합니다.
접미사 링크가 있는 경우와 없는 경우의 처리 비교 예제
위 예의 다음 단계에서 어떤 일이 일어나는지 생각해 보십시오.같은 결과를 얻는 방법, 즉 처리할 다음 서픽스로 이동하는 방법을 비교합니다.서픽스 링크가 있는 경우와 없는 경우입니다.
'suffix link' 사용
서픽스 링크를 사용하면, 자동적으로 「적절한 장소에 있다」라고 하는 점에 주의해 주세요.이는 종종 '활성 길이'가 새로운 위치와 '호환성 없음'이 될 수 있기 때문에 엄밀하게는 사실이 아닙니다.
위의 경우 '활성 길이'가 4이므로 접미사 'AB'로 작업합니다.AA'는 링크된 노드 4에서 시작합니다.그러나 접미사('A')의 첫 번째 문자에 해당하는 가장자리를 찾은 후 이 가장자리에 '활성 길이'가 3자 오버플로우하는 것을 알 수 있습니다.따라서 다음 노드로 점프하여 점프에 사용한 문자만큼 '활성 길이'를 줄입니다.
그런 다음 감소된 접미사 'BAA'에 해당하는 다음 에지 'B'를 찾은 후, 에지 길이가 나머지 '활성 길이'인 3보다 크다는 것을 마지막으로 알게 되었습니다. 즉, 올바른 위치를 찾은 것입니다.
이 작업은 보통 '재스캐닝'이라고 부르지는 않지만, 길이가 짧아지고 루트가 아닌 시작점이 있는 것만으로 재스캐닝과 직결되는 것처럼 보입니다.
rescan 사용
기존의 'rescan' 연산(여기에서는 서픽스 링크가 없는 것처럼 가정)을 사용하는 경우 트리의 맨 위 루트부터 시작하여 현재 서픽스의 전체 길이를 따라 올바른 위치로 다시 이동해야 합니다.
이 접미사의 길이는 앞에서 설명한 '남은'입니다.우리는 이 나머지를 0이 될 때까지 다 소비해야 한다.여기에는 여러 노드를 통과하여 점프하는 것이 포함될 수 있습니다(그리고 종종 해당). 각 점프에서는 나머지 부분이 점프하는 가장자리 길이만큼 감소합니다.마지막으로 남은 '잔량'보다 긴 에지에 도달합니다. 여기서 활성 에지를 지정된 에지로 설정하고 '활성 길이'를 남은 '잔량'으로 설정하면 완료됩니다.
다만, 실제의 「잔여」변수는 보존할 필요가 있어, 각 노드를 삽입한 후에만 감소하는 것에 주의해 주세요.위에서 설명한 내용은 'remainer'로 초기화된 별도의 변수를 사용하는 것으로 가정합니다.
서픽스 링크 및 재검색에 관한 주의사항
1) 두 방법 모두 동일한 결과를 가져온다는 점에 유의한다.그러나 대부분의 경우 접미사 링크 점핑이 훨씬 더 빠릅니다. 이것이 접미사 링크의 이면에 있는 전체적인 이유입니다.
2) 실제 알고리즘 구현은 다를 필요가 없습니다.앞에서 설명한 바와 같이 서픽스 링크를 사용하는 경우에도 '액티브 길이'가 링크된 위치와 호환되지 않는 경우가 많습니다. 이는 트리의 분기점에 추가 분기가 포함될 수 있기 때문입니다.따라서 기본적으로 'remainer' 대신 'active length'를 사용하여 남은 접미사 길이보다 짧은 가장자리를 찾을 때까지 동일한 재스캔 로직을 실행해야 합니다.
3) 퍼포먼스에 관한 중요한 주의사항 중 하나는 재스캔 시 일일이 문자를 확인할 필요가 없다는 것입니다.유효한 접미사 트리가 구축되어 있기 때문에 문자가 일치한다고 추측할 수 있습니다.즉, 주로 길이를 세는 것입니다.단, 에지는 첫 번째 문자에 의해 식별되기 때문에 새로운 에지로 이동할 때에만 문자 등가성 체크가 필요합니다(특정 노드의 컨텍스트에서는 항상 고유합니다).즉, '재스캐닝' 논리는 전체 문자열 매칭 논리(즉, 트리에서 하위 문자열 검색)와 다릅니다.
4) 여기서 설명하는 원래의 서픽스 링크는 가능한 접근법 중 하나에 불과합니다.예를 들어 NJ Larsson 등은 이 접근 방식을 노드 지향 하향식이라고 명명하고 노드 지향 상향식 및 두 가지 에지 지향식 변종과 비교합니다.다른 접근방식은 일반적인 경우와 최악의 경우 성능, 요건, 제한사항 등을 가지고 있지만, 일반적으로 에지 지향 접근방식은 원래의 접근방식에 비해 전반적으로 개선된 것으로 보입니다.
@capanojapan 당신은 멋진 설명과 시각화를 가지고 왔습니다.그러나 @makagonov가 언급했듯이 서픽스 링크 설정에 관한 몇 가지 규칙이 누락되어 있습니다.http://brenden.github.io/ukkonen-animation/에서 'aabaaabb'라는 단어를 통해 한 단계씩 진행하면 보기 좋습니다.스텝 10에서 스텝 11로 넘어가면 노드5에서 노드2로의 서픽스 링크는 없지만 액티브포인트가 갑자기 이동합니다
@makagonov는 Java world에 살고 있기 때문에 ST빌딩의 워크플로우를 파악하기 위해 귀사의 구현을 따르려고 했지만 다음과 같은 이유로 어려웠습니다.
- 모서리를 노드와 결합
- 참조 대신 인덱스 포인터 사용
- 스테이트먼트를 깨다
- 스테이트먼트를 속행한다.
그래서 저는 Java에서 이러한 구현을 하게 되었습니다.이 구현은 모든 단계를 보다 명확하게 반영하여 다른 Java 사용자의 학습 시간을 단축할 수 있기를 바랍니다.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class ST {
public class Node {
private final int id;
private final Map<Character, Edge> edges;
private Node slink;
public Node(final int id) {
this.id = id;
this.edges = new HashMap<>();
}
public void setSlink(final Node slink) {
this.slink = slink;
}
public Map<Character, Edge> getEdges() {
return this.edges;
}
public Node getSlink() {
return this.slink;
}
public String toString(final String word) {
return new StringBuilder()
.append("{")
.append("\"id\"")
.append(":")
.append(this.id)
.append(",")
.append("\"slink\"")
.append(":")
.append(this.slink != null ? this.slink.id : null)
.append(",")
.append("\"edges\"")
.append(":")
.append(edgesToString(word))
.append("}")
.toString();
}
private StringBuilder edgesToString(final String word) {
final StringBuilder edgesStringBuilder = new StringBuilder();
edgesStringBuilder.append("{");
for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
edgesStringBuilder.append("\"")
.append(entry.getKey())
.append("\"")
.append(":")
.append(entry.getValue().toString(word))
.append(",");
}
if(!this.edges.isEmpty()) {
edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
}
edgesStringBuilder.append("}");
return edgesStringBuilder;
}
public boolean contains(final String word, final String suffix) {
return !suffix.isEmpty()
&& this.edges.containsKey(suffix.charAt(0))
&& this.edges.get(suffix.charAt(0)).contains(word, suffix);
}
}
public class Edge {
private final int from;
private final int to;
private final Node next;
public Edge(final int from, final int to, final Node next) {
this.from = from;
this.to = to;
this.next = next;
}
public int getFrom() {
return this.from;
}
public int getTo() {
return this.to;
}
public Node getNext() {
return this.next;
}
public int getLength() {
return this.to - this.from;
}
public String toString(final String word) {
return new StringBuilder()
.append("{")
.append("\"content\"")
.append(":")
.append("\"")
.append(word.substring(this.from, this.to))
.append("\"")
.append(",")
.append("\"next\"")
.append(":")
.append(this.next != null ? this.next.toString(word) : null)
.append("}")
.toString();
}
public boolean contains(final String word, final String suffix) {
if(this.next == null) {
return word.substring(this.from, this.to).equals(suffix);
}
return suffix.startsWith(word.substring(this.from,
this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
}
}
public class ActivePoint {
private final Node activeNode;
private final Character activeEdgeFirstCharacter;
private final int activeLength;
public ActivePoint(final Node activeNode,
final Character activeEdgeFirstCharacter,
final int activeLength) {
this.activeNode = activeNode;
this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
this.activeLength = activeLength;
}
private Edge getActiveEdge() {
return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
}
public boolean pointsToActiveNode() {
return this.activeLength == 0;
}
public boolean activeNodeIs(final Node node) {
return this.activeNode == node;
}
public boolean activeNodeHasEdgeStartingWith(final char character) {
return this.activeNode.getEdges().containsKey(character);
}
public boolean activeNodeHasSlink() {
return this.activeNode.getSlink() != null;
}
public boolean pointsToOnActiveEdge(final String word, final char character) {
return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
}
public boolean pointsToTheEndOfActiveEdge() {
return this.getActiveEdge().getLength() == this.activeLength;
}
public boolean pointsAfterTheEndOfActiveEdge() {
return this.getActiveEdge().getLength() < this.activeLength;
}
public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
return new ActivePoint(this.activeNode, character, 1);
}
public ActivePoint moveToNextNodeOfActiveEdge() {
return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
}
public ActivePoint moveToSlink() {
return new ActivePoint(this.activeNode.getSlink(),
this.activeEdgeFirstCharacter,
this.activeLength);
}
public ActivePoint moveTo(final Node node) {
return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
}
public ActivePoint moveByOneCharacter() {
return new ActivePoint(this.activeNode,
this.activeEdgeFirstCharacter,
this.activeLength + 1);
}
public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
final char character) {
return new ActivePoint(node, character, this.activeLength - 1);
}
public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
return new ActivePoint(this.getActiveEdge().getNext(),
word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
this.activeLength - this.getActiveEdge().getLength());
}
public void addEdgeToActiveNode(final char character, final Edge edge) {
this.activeNode.getEdges().put(character, edge);
}
public void splitActiveEdge(final String word,
final Node nodeToAdd,
final int index,
final char character) {
final Edge activeEdgeToSplit = this.getActiveEdge();
final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
activeEdgeToSplit.getFrom() + this.activeLength,
nodeToAdd);
nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
activeEdgeToSplit.getTo(),
activeEdgeToSplit.getNext()));
nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
}
public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
final Node node) {
if(previouslyAddedNodeOrAddedEdgeNode != null) {
previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
}
return node;
}
public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
}
}
private static int idGenerator;
private final String word;
private final Node root;
private ActivePoint activePoint;
private int remainder;
public ST(final String word) {
this.word = word;
this.root = new Node(idGenerator++);
this.activePoint = new ActivePoint(this.root, null, 0);
this.remainder = 0;
build();
}
private void build() {
for(int i = 0; i < this.word.length(); i++) {
add(i, this.word.charAt(i));
}
}
private void add(final int index, final char character) {
this.remainder++;
boolean characterFoundInTheTree = false;
Node previouslyAddedNodeOrAddedEdgeNode = null;
while(!characterFoundInTheTree && this.remainder > 0) {
if(this.activePoint.pointsToActiveNode()) {
if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
characterFoundInTheTree = true;
}
else {
if(this.activePoint.activeNodeIs(this.root)) {
rootNodeHasNotEdgeStartingWithCharacter(index, character);
}
else {
previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
character, previouslyAddedNodeOrAddedEdgeNode);
}
}
}
else {
if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
activeEdgeHasCharacter();
characterFoundInTheTree = true;
}
else {
if(this.activePoint.activeNodeIs(this.root)) {
previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
character,
previouslyAddedNodeOrAddedEdgeNode);
}
else {
previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
character,
previouslyAddedNodeOrAddedEdgeNode);
}
}
}
}
}
private void activeNodeHasEdgeStartingWithCharacter(final char character,
final Node previouslyAddedNodeOrAddedEdgeNode) {
this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
if(this.activePoint.pointsToTheEndOfActiveEdge()) {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
}
}
private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
this.activePoint = this.activePoint.moveTo(this.root);
this.remainder--;
assert this.remainder == 0;
}
private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
final char character,
Node previouslyAddedNodeOrAddedEdgeNode) {
this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
if(this.activePoint.activeNodeHasSlink()) {
this.activePoint = this.activePoint.moveToSlink();
}
else {
this.activePoint = this.activePoint.moveTo(this.root);
}
this.remainder--;
return previouslyAddedNodeOrAddedEdgeNode;
}
private void activeEdgeHasCharacter() {
this.activePoint = this.activePoint.moveByOneCharacter();
if(this.activePoint.pointsToTheEndOfActiveEdge()) {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
}
}
private Node edgeFromRootNodeHasNotCharacter(final int index,
final char character,
Node previouslyAddedNodeOrAddedEdgeNode) {
final Node newNode = new Node(idGenerator++);
this.activePoint.splitActiveEdge(this.word, newNode, index, character);
previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
this.word.charAt(index - this.remainder + 2));
this.activePoint = walkDown(index);
this.remainder--;
return previouslyAddedNodeOrAddedEdgeNode;
}
private Node edgeFromInternalNodeHasNotCharacter(final int index,
final char character,
Node previouslyAddedNodeOrAddedEdgeNode) {
final Node newNode = new Node(idGenerator++);
this.activePoint.splitActiveEdge(this.word, newNode, index, character);
previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
if(this.activePoint.activeNodeHasSlink()) {
this.activePoint = this.activePoint.moveToSlink();
}
else {
this.activePoint = this.activePoint.moveTo(this.root);
}
this.activePoint = walkDown(index);
this.remainder--;
return previouslyAddedNodeOrAddedEdgeNode;
}
private ActivePoint walkDown(final int index) {
while(!this.activePoint.pointsToActiveNode()
&& (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
}
else {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
}
}
return this.activePoint;
}
public String toString(final String word) {
return this.root.toString(word);
}
public boolean contains(final String suffix) {
return this.root.contains(this.word, suffix);
}
public static void main(final String[] args) {
final String[] words = {
"abcabcabc$",
"abc$",
"abcabxabcd$",
"abcabxabda$",
"abcabxad$",
"aabaaabb$",
"aababcabcd$",
"ababcabcd$",
"abccba$",
"mississipi$",
"abacabadabacabae$",
"abcabcd$",
"00132220$"
};
Arrays.stream(words).forEach(word -> {
System.out.println("Building suffix tree for word: " + word);
final ST suffixTree = new ST(word);
System.out.println("Suffix tree: " + suffixTree.toString(word));
for(int i = 0; i < word.length() - 1; i++) {
assert suffixTree.contains(word.substring(i)) : word.substring(i);
}
});
}
}
@jogojapan의 튜토리얼에 대해 잘 설명해 주셔서 Python에 알고리즘을 실장했습니다.
@jogo japan에서 언급한 몇 가지 사소한 문제는 생각보다 세심하고 신중하게 다루어져야 합니다.확실히 실장하는 데 며칠이 걸렸습니다(아마도).문제 및 해결 방법은 다음과 같습니다.
종료: 이 상황은 알고리즘 전체의 종료뿐만 아니라 전개 단계에서도 발생할 수 있습니다.이 경우 나머지 actnode, actge 및 actlength를 변경하지 않고 현재 전개 단계를 종료하고 원래 문자열의 다음 문자가 현재 경로 상에 있는지 여부에 따라 계속 접거나 전개하여 다음 단계를 시작할 수 있습니다.
[루프오버 노드(Leap Over Nodes)]:서픽스 링크를 따라가면 액티브포인트를 갱신하고 그 active_length 컴포넌트가 새로운 active_node와 올바르게 동작하지 않는 것을 알 수 있습니다.갈라지려면 적당한 곳으로 가거나 잎을 넣어야 해이 프로세스는 간단하지 않을 수 있습니다.액티브 길이와 액티언트 길이가 이동하는 동안 루트 노드로 돌아가야 할 경우 액티언트 길이와 액티언트 길이가 잘못될 수 있기 때문입니다.우리는 그 정보를 유지하기 위해 추가 변수가 필요하다.
다른 두 가지 문제는 @managonov에 의해 지적되었습니다.
분할이 변질될 수 있음 에지를 분할하려고 하면 분할 작업이 노드에서 올바르게 수행된다는 것을 알게 될 수 있습니다.이 경우 해당 노드에 새 리프만 추가하면 됩니다. 표준 에지 분할 작업으로 간주합니다. 즉, 접미사 링크가 있는 경우 그에 따라 유지되어야 합니다.
숨겨진 서픽스 링크 문제 1과 문제 2에 의해 발생한 또 다른 특별한 경우가 있습니다.분할을 위해 여러 노드를 건너뛸 필요가 있는 경우가 있습니다.나머지 문자열과 패스라벨을 비교하여 이동하면 적절한 포인트를 초과할 수 있습니다.이 경우 서픽스 링크가 있을 경우 의도하지 않게 무시됩니다.이것은 앞으로 나아갈 때 올바른 점을 기억함으로써 피할 수 있었다.스플릿 노드가 이미 존재하는 경우 또는 전개 단계 중에 문제 1이 발생한 경우 서픽스링크를 유지해야 합니다.
마지막으로 Python에서의 실장은 다음과 같습니다.
힌트: 위의 코드에 간단한 트리 인쇄 기능이 포함되어 있습니다.이것은 디버깅 중에 매우 중요합니다.시간이 많이 절약되었고 특별한 사례를 찾는 데 편리합니다.
제 직감은 다음과 같습니다.
메인 루프를 k회 반복하면 첫 번째 k자로 시작하는 전체 문자열의 모든 접미사가 포함된 접미사 트리가 생성되었습니다.
처음에 이것은 접미사 트리에 문자열 전체를 나타내는 단일 루트 노드가 포함되어 있음을 의미합니다(0으로 시작하는 유일한 접미사).
len(string)을 반복하면 모든 접미사가 포함된 접미사 트리가 나타납니다.
루프 중에는 키가 액티브포인트가 됩니다이것은 접미사 트리에서 문자열의 첫 번째 k 문자의 적절한 접미사에 대응하는 가장 깊은 점을 나타내는 것 같습니다(적절한 것은 접미사가 문자열 전체가 될 수 없다는 것을 의미합니다).
예를 들어, 'abcabc'라는 문자를 봤다고 가정합니다.활성 점은 접미사 'abc'에 해당하는 트리의 점을 나타냅니다.
액티브 포인트는 (origin, first, last)로 표시됩니다.즉, 노드 원점부터 시작하여 문자열의 문자를 입력함으로써 현재 트리 내에서 도달하는 지점에 도달했음을 의미합니다.
새 문자를 추가하면 활성 지점이 여전히 기존 트리에 있는지 확인합니다.만약 그렇다면 당신은 끝이다.그렇지 않으면 활성 지점의 접미사 트리에 새 노드를 추가하고 다음으로 짧은 일치 항목으로 폴백한 후 다시 확인해야 합니다.
주 1: 접미사 포인터는 각 노드의 다음 최단 일치에 대한 링크를 제공합니다.
주 2: 새 노드를 추가하고 폴백을 할 때는 새 노드의 새 접미사 포인터를 추가합니다.이 접미사 포인터의 대상은 단축된 활성 지점의 노드가 됩니다.이 노드는 이미 존재하거나 이 폴백루프의 다음 반복 시 생성됩니다.
주 3: 캐논라이제이션부는 액티브 포인트를 체크하는 시간을 절약할 수 있습니다.예를 들어, 항상 원점=0을 사용하고 처음과 마지막으로 변경했다고 가정합니다.활성 지점을 확인하려면 모든 중간 노드를 따라 매번 접미사 트리를 따라야 합니다.마지막 노드로부터의 거리만 기록함으로써 이 경로를 따른 결과를 캐시하는 것이 좋습니다.
"수정" 경계 변수가 의미하는 코드 예를 들어주시겠습니까?
건강 경고: 이 알고리즘도 특히 이해하기 어려웠기 때문에 이 직관은 모든 중요한 세부 사항에서 부정확할 수 있습니다.
안녕하세요, 저는 위에서 설명한 구현을 루비로 구현하려고 했습니다만, 확인해 주십시오.잘 작동하는 것 같아요.
구현의 유일한 차이점은 심볼을 사용하는 대신 엣지 오브젝트를 사용하려고 노력했다는 것입니다.
https://gist.github.com/suchitpuri/9304856에도 게재되어 있습니다.
require 'pry'
class Edge
attr_accessor :data , :edges , :suffix_link
def initialize data
@data = data
@edges = []
@suffix_link = nil
end
def find_edge element
self.edges.each do |edge|
return edge if edge.data.start_with? element
end
return nil
end
end
class SuffixTrees
attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder
def initialize
@root = Edge.new nil
@active_point = { active_node: @root , active_edge: nil , active_length: 0}
@remainder = 0
@pending_prefixes = []
@last_split_edge = nil
@remainder = 1
end
def build string
string.split("").each_with_index do |element , index|
add_to_edges @root , element
update_pending_prefix element
add_pending_elements_to_tree element
active_length = @active_point[:active_length]
# if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
# @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
# @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
# end
if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length] )
@active_point[:active_node] = @active_point[:active_edge]
@active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
@active_point[:active_length] = 0
end
end
end
def add_pending_elements_to_tree element
to_be_deleted = []
update_active_length = false
# binding.pry
if( @active_point[:active_node].find_edge(element[0]) != nil)
@active_point[:active_length] = @active_point[:active_length] + 1
@active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
@remainder = @remainder + 1
return
end
@pending_prefixes.each_with_index do |pending_prefix , index|
# binding.pry
if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil
@active_point[:active_node].edges << Edge.new(element)
else
@active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil
data = @active_point[:active_edge].data
data = data.split("")
location = @active_point[:active_length]
# binding.pry
if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )
else #tree split
split_edge data , index , element
end
end
end
end
def update_pending_prefix element
if @active_point[:active_edge] == nil
@pending_prefixes = [element]
return
end
@pending_prefixes = []
length = @active_point[:active_edge].data.length
data = @active_point[:active_edge].data
@remainder.times do |ctr|
@pending_prefixes << data[-(ctr+1)..data.length-1]
end
@pending_prefixes.reverse!
end
def split_edge data , index , element
location = @active_point[:active_length]
old_edges = []
internal_node = (@active_point[:active_edge].edges != nil)
if (internal_node)
old_edges = @active_point[:active_edge].edges
@active_point[:active_edge].edges = []
end
@active_point[:active_edge].data = data[0..location-1].join
@active_point[:active_edge].edges << Edge.new(data[location..data.size].join)
if internal_node
@active_point[:active_edge].edges << Edge.new(element)
else
@active_point[:active_edge].edges << Edge.new(data.last)
end
if internal_node
@active_point[:active_edge].edges[0].edges = old_edges
end
#setup the suffix link
if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data
@last_split_edge.suffix_link = @active_point[:active_edge]
end
@last_split_edge = @active_point[:active_edge]
update_active_point index
end
def update_active_point index
if(@active_point[:active_node] == @root)
@active_point[:active_length] = @active_point[:active_length] - 1
@remainder = @remainder - 1
@active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
else
if @active_point[:active_node].suffix_link != nil
@active_point[:active_node] = @active_point[:active_node].suffix_link
else
@active_point[:active_node] = @root
end
@active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
@remainder = @remainder - 1
end
end
def add_to_edges root , element
return if root == nil
root.data = root.data + element if(root.data and root.edges.size == 0)
root.edges.each do |edge|
add_to_edges edge , element
end
end
end
suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry
언급URL : https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english
'programing' 카테고리의 다른 글
| ORA-01461: LONG 열에 삽입하는 경우에만 LONG 값을 바인딩할 수 있습니다. 쿼리 시 발생합니다. (0) | 2023.04.19 |
|---|---|
| UITextView 플레이스 홀더 (0) | 2023.04.19 |
| curl 명령으로 특정 폴더에 파일 저장 (0) | 2023.04.19 |
| SQL Server에서 구체화된 뷰를 작성하는 방법 (0) | 2023.04.19 |
| 의 의미.셀(.Rows).카운트 "A").End(xlUp).행 (0) | 2023.04.19 |