your programing

평범한 영어로 된 Ukkonen의 접미사 트리 알고리즘

lovepro 2020. 9. 27. 13:30
반응형

평범한 영어로 된 Ukkonen의 접미사 트리 알고리즘

이 시점에서 조금 두껍습니다. 나는 접미사 트리 구조에 대해 머리를 완전히 감싸려고 며칠을 보냈지 만 수학적 배경이 없기 때문에 수학적 기호를 과도하게 사용하기 시작하면서 많은 설명이 나를 피합니다. 내가 찾은 좋은 설명에 가장 가까운 것은 접미사 트리를 사용한 빠른 문자열 검색 이지만 그는 다양한 요점에 대해 설명하고 알고리즘의 일부 측면은 명확하지 않습니다.

여기 Stack Overflow에서이 알고리즘에 대한 단계별 설명은 저 외에 많은 다른 사람들에게 매우 중요 할 것입니다.

참고로 알고리즘에 대한 Ukkonen의 논문은 다음과 같습니다. http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

지금까지 나의 기본적인 이해 :

  • 주어진 문자열 T의 각 접두사 P를 반복해야합니다.
  • 접두사 P의 각 접미사 S를 반복하고 트리에 추가해야합니다.
  • 접미사 S를 트리에 추가하려면 S의 각 문자를 반복해야합니다. 반복은 S의 동일한 문자 집합 C로 시작하는 기존 분기를 걸어 내려 가고 잠재적으로 가장자리를 하위 노드로 분할하는 것으로 구성됩니다. 접미사에서 다른 문자에 도달하거나 걸어 내려갈 일치하는 가장자리가없는 경우. C와 일치하는 가장자리가 발견되지 않으면 C에 대한 새 리프 가장자리가 생성됩니다.

대부분의 설명에서 지적했듯이 기본 알고리즘은 O (n 2 )로 보입니다. 모든 접두사를 단계별로 살펴보고 각 접두사에 대한 각 접미사를 단계별로 살펴 봐야하기 때문입니다. Ukkonen의 알고리즘은 그가 사용하는 접미사 포인터 기술로 인해 분명히 독특하지만 그것이 이해하는 데 어려움이 있다고 생각 합니다 .

또한 다음을 이해하는 데 문제가 있습니다.

  • "활성 포인트"가 할당, 사용 및 변경되는 정확한시기와 방법
  • 알고리즘의 정식화 측면에서 무슨 일이 일어나고 있는지
  • 내가 본 구현이 사용중인 경계 변수를 "수정"해야하는 이유

다음은 완성 된 C # 소스 코드입니다. 올바르게 작동 할뿐만 아니라 자동 캐논 화를 지원하고 출력의 더 멋진 텍스트 그래프를 렌더링합니다. 소스 코드 및 샘플 출력은 다음 위치에 있습니다.

https://gist.github.com/2373868

업데이트 2017-11-04

수년 후 접미사 트리에 대한 새로운 용도를 발견하고 JavaScript로 알고리즘을 구현했습니다 . 요점은 아래와 같습니다. 버그가 없어야합니다. npm install chalk동일한 위치에서 js 파일로 덤프 한 다음 node.js로 실행하여 다채로운 출력을 확인하십시오. 디버깅 코드가없는 동일한 Gist에 제거 된 버전이 있습니다.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

다음은 문자열이 단순 할 때 (즉, 반복되는 문자를 포함하지 않음) 수행하는 작업을 먼저 보여준 다음 전체 알고리즘으로 확장하여 Ukkonen 알고리즘을 설명하려는 시도입니다.

첫째, 몇 가지 예비 진술.

  1. 우리가 만들고있는 것은 기본적으로 검색 시도와 같습니다. 그래서 루트 노드가 있고, 그 밖으로 나가는 에지는 새로운 노드로 이어지고, 그 밖의 에지가 나오는 등입니다.

  2. 그러나 : 검색 트라이와 달리 가장자리 레이블은 단일 문자가 아닙니다. 대신 각 가장자리는 정수 쌍을 사용하여 레이블이 지정됩니다 [from,to]. 이들은 텍스트에 대한 포인터입니다. 이러한 의미에서 각 모서리는 임의 길이의 문자열 레이블을 전달하지만 O (1) 공간 (포인터 2 개) 만 사용합니다.

기초 원리

먼저 반복되는 문자가없는 문자열 인 특히 단순한 문자열의 접미사 트리를 만드는 방법을 보여주고 싶습니다.

abc

알고리즘 은 왼쪽에서 오른쪽으로 단계적으로 작동합니다 . 문자열의 모든 문자에 대해 한 단계 가 있습니다 . 각 단계에는 하나 이상의 개별 작업이 포함될 수 있지만 총 작업 수가 O (n)임을 확인할 수 있습니다 (마지막의 최종 관찰 참조).

따라서 왼쪽 부터 시작 a하여 루트 노드 (왼쪽)에서 리프까지 가장자리를 만들고 레이블을 지정 하여 단일 문자 만 삽입합니다. [0,#]즉, 가장자리는 위치 0에서 시작하여 끝나는 부분 문자열을 나타냅니다. 에서 현재 끝 . 기호 #를 사용하여 위치 1 (바로 뒤 )에 있는 현재 끝 을 의미 합니다a .

따라서 다음과 같은 초기 트리가 있습니다.

이것이 의미하는 바는 다음과 같습니다.

이제 위치 2 (바로 뒤 b)로 진행합니다 . 각 단계의 목표 는 현재 위치까지 모든 접미사 를 삽입 하는 것 입니다. 우리는 이것을

  • 기존 a가장자리 확장ab
  • 하나의 새 모서리 삽입 b

우리의 표현에서 이것은 다음과 같습니다.

여기에 이미지 설명 입력

그 의미는 다음과 같습니다.

우리는 두 가지를 관찰합니다 .

  • 위한 에지 표현 ab이다 동일한 는 초기 트리 예전 같이 [0,#]. 현재 위치 #를 1에서 2로 업데이트했기 때문에 의미가 자동으로 변경되었습니다 .
  • 각 가장자리는 나타내는 문자 수에 관계없이 텍스트에 대한 두 개의 포인터로만 구성되기 때문에 O (1) 공간을 사용합니다.

다음으로 위치를 다시 늘리고 c모든 기존 가장자리에 a 를 추가 하고 새 접미사에 대해 하나의 새 가장자리를 삽입 하여 트리를 업데이트합니다 c.

우리의 표현에서 이것은 다음과 같습니다.

그 의미는 다음과 같습니다.

우리는 다음을 관찰합니다.

  • 트리는 각 단계 후 현재 위치까지 올바른 접미사 트리입니다.
  • 텍스트에있는 문자만큼 많은 단계가 있습니다.
  • 각 단계의 작업량은 O (1)입니다. 기존의 모든 가장자리가를 증가시켜 자동으로 업데이트 #되고 최종 캐릭터에 대해 하나의 새 가장자리를 삽입하는 것은 O (1) 시간에 수행 될 수 있기 때문입니다. 따라서 길이가 n 인 문자열의 경우 O (n) 시간 만 필요합니다.

첫 번째 확장 : 단순 반복

물론 이것은 우리의 문자열에 반복이 없기 때문에 아주 잘 작동합니다. 이제보다 현실적인 문자열을 살펴 보겠습니다.

abcabxabcd

이것은 시작 abc이전 예에서 다음으로 ab반복되고,이어서 x다음과 abc뒤에 반복된다 d.

1 ~ 3 단계 : 처음 3 단계 후에는 이전 예의 트리가 있습니다.

4 단계 :# 위치 4 로 이동 합니다. 이렇게하면 기존의 모든 가장자리가 다음과 같이 암시 적으로 업데이트됩니다.

a루트에 현재 단계의 마지막 접미사를 삽입해야 합니다.

이 작업을 수행하기 전에 두 개의 변수 (외에 #) 를 추가로 소개합니다. 물론 항상 존재했지만 지금까지 사용하지는 않았습니다.

  • 활성 점 트리플이며(active_node,active_edge,active_length)
  • 는 remainder, 이는 우리가 삽입 할 필요가 얼마나 많은 새로운 접미사를 나타내는 정수

이 두 가지의 정확한 의미는 곧 명확해질 것이지만 지금은 다음과 같이 말하겠습니다.

  • 간단한에서 abc예를 들어, 활성 점은 언제나 (root,'\0x',0)즉 active_node, 루트 노드이었다 active_edge널 문자로 지정 '\0x'하고, active_length제로였다. 그 효과는 우리가 모든 단계에서 삽입 한 하나의 새로운 에지가 새로 생성 된 에지로 루트 노드에 삽입된다는 것입니다. 이 정보를 표현하기 위해 왜 트리플이 필요한지 곧 알게 될 것입니다.
  • 는 remainder항상 각 단계의 시작 부분에 1로 설정했다. 그 의미는 각 단계의 끝에 적극적으로 삽입해야하는 접미사 수가 1 (항상 마지막 문자)이라는 것입니다.

이제 이것은 바뀔 것입니다. a루트에 현재 최종 문자 를 삽입하면 a, 특히 :으로 시작하는 나가는 가장자리가 이미 있음을 알 수 있습니다 abca. 이 경우 우리가하는 일은 다음과 같습니다.

  • 우리는 하지 않는 새로운 에지 삽입 [4,#]루트 노드를. 대신 접미사 a가 이미 트리에 있음을 알 수 있습니다. 그것은 더 긴 가장자리의 중간에서 끝나지만 우리는 그것에 신경 쓰지 않습니다. 우리는 그냥 그대로 둡니다.
  • 우리는 활성 점 설정 에를 (root,'a',1). 즉, 활성 지점은 이제로 시작하는 루트 노드의 나가는 가장자리 중간 a, 특히 해당 가장자리의 위치 1 이후에 있습니다. 가장자리는 단순히 첫 번째 문자로 지정됩니다 a. 특정 문자로 시작하는 가장자리 가 하나만 있을 수 있기 때문에 충분 합니다 (전체 설명을 읽은 후 이것이 사실인지 확인하십시오).
  • 또한 증가 remainder하므로 다음 단계의 시작 부분에서 2가됩니다.

관찰 : 삽입해야하는 최종 접미사가 이미 트리에 존재하는 것으로 확인 되면 트리 자체는 전혀 변경되지 않습니다 (활성 지점 및 만 업데이트 함 remainder). 그러면 트리는 더 이상 현재 위치까지 의 정확한 접미사 트리 표현이 아니지만 모든 접미사를 포함 합니다 (최종 접미사 a가 암시 적 으로 포함 되기 때문 ). 따라서 변수 (모두 고정 길이이므로 O (1))를 업데이트하는 것 외에는 이 단계에서 수행 된 작업 이 없습니다 .

5 단계 : 현재 위치 #를 5로 업데이트합니다. 그러면 트리가 다음과 같이 자동으로 업데이트됩니다.

그리고 있기 때문에 remainder2 , 우리는 현재 위치의 마지막 두 접미사를 삽입해야 ab하고 b. 이것은 기본적으로 다음과 같은 이유 때문입니다.

  • a이전 단계 의 접미사가 제대로 삽입되지 않았습니다. 그래서 그것은 남아 있고, 우리가 한 걸음 나아 갔기 때문에 지금은 a에서 ab.
  • 그리고 새로운 최종 모서리를 삽입해야합니다 b.

실제로 이것은 우리가 활성 지점 ( a현재 abcab가장자리의 뒤를 가리키는 )으로 이동하여 현재 최종 문자를 삽입한다는 것을 의미합니다 b. 그러나 다시 말하지만, 그것은 b이미 같은 가장자리에 존재 한다는 것이 밝혀졌습니다 .

다시 말하지만, 우리는 나무를 바꾸지 않습니다. 우리는 간단히 :

  • 활성 포인트를 (root,'a',2)(이전과 동일한 노드 및 에지로 업데이트 하지만 이제 우리는 뒤를 가리 킵니다 b)
  • 를 증가 remainder우리가 아직 제대로 이전 단계에서 최종 가장자리를 삽입하지 않았기 때문에 3, 우리는 하나 현재 최종 가장자리를 삽입하지 마십시오.

명확하게하려면, 우리는 삽입했다 ab및 b현재 단계에 있지만, 때문에 ab이미 발견 된, 우리는 활성 지점을 업데이트하고도 삽입하지 않았다 b. 왜? ab가 트리에 있으면 모든 접미사 (포함 b)도 트리에 있어야합니다. 아마도 묵시적 일 수도 있지만 지금까지 트리를 구축 한 방식 때문에 거기에 있어야합니다.

를 증가시켜 6 단계로 진행합니다 #. 트리는 다음으로 자동 업데이트됩니다.

때문에 remainder3 , 우리는 삽입해야 abx, bx하고 x. 활성 지점은 ab끝이 어디인지 알려주 므로 여기로 이동 하여 x. 실제로 x아직 존재하지 않으므로 abcabx가장자리를 분할하고 내부 노드를 삽입합니다.

가장자리 표현은 여전히 ​​텍스트에 대한 포인터이므로 내부 노드 분할 및 삽입은 O (1) 시간에 수행 할 수 있습니다.

그래서 우리는 처리하고 2로 abx감소 시켰 remainder습니다. 이제 우리는 다음으로 남은 접미사 인 bx. 하지만 그 전에 활성 지점을 업데이트해야합니다. 이에 대한 규칙은 가장자리를 분할하고 삽입 한 후 아래의 규칙 1 이라고하며 active_node루트가 될 때마다 적용됩니다 (다른 경우에는 규칙 3에 대해 자세히 알아 봅니다). 다음은 규칙 1입니다.

루트에서 삽입 후

  • active_node 뿌리로 남아있다
  • active_edge 삽입해야하는 새 접미사의 첫 번째 문자로 설정됩니다. b
  • active_length 1 감소

따라서 새로운 활성 포인트 트리플 (root,'b',1)은 다음 삽입이 한 bcabx문자 뒤 의 가장자리, 즉 뒤에서 이루어져야 함을 나타냅니다 b. O (1) 시점에서 삽입 지점을 식별하고 x이미 존재 하는지 여부를 확인할 수 있습니다. 존재하는 경우 현재 단계를 종료하고 모든 것을 그대로 둡니다. 그러나 x존재하지 않으므로 가장자리를 분할하여 삽입합니다.

다시, 이것은 O (1) 시간이 걸렸고 우리 는 규칙 1 상태에 따라 1로 업데이트 remainder하고 활성 지점을 업데이트 합니다 (root,'x',0).

하지만 우리가해야 할 일이 하나 더 있습니다. 이것을 규칙 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'를 삽입해야합니다. 그러면 최종 트릭을 이해하는 데 도움이됩니다.

두 번째 확장 : 접미사 링크 사용

항상 그렇듯이 #업데이트는 c리프 가장자리 에 자동으로 추가 되고 활성 지점으로 이동하여 'c'를 삽입 할 수 있는지 확인합니다. 'c'는 이미 해당 가장자리에 존재하므로 활성 지점을로 설정하고 (node1,'c',1)증분 remainder하고 다른 작업은 수행하지 않습니다.

이제 단계 #= 10 , remainder is 4이므로 먼저 활성 지점 abcd에 삽입 하여 삽입해야합니다 (3 단계 이전에 남아 있음) d.

d활성 지점 에 삽입하려고 하면 O (1) 시간에 가장자리 분할이 발생합니다.

active_node분할이 시작된로부터는, 적색, 상기에 표시된다. 다음은 최종 규칙 인 규칙 3입니다.

active_node루트 노드가 아닌 에서 에지를 분리 한 후 해당 노드에서 나가는 접미사 링크 (있는 경우)를 따라 가며 active_node가리키는 노드로 재설정합니다 . 접미사 링크가 없으면 active_node을 루트로 설정합니다 . active_edge및 active_length변경되지 않습니다.

따라서 활성 지점은 이제 (node2,'c',1)이며 node2아래에 빨간색으로 표시됩니다.

삽입 abcd이 완료되었으므로 remainder3으로 감소 하고 현재 단계의 다음 나머지 접미사 인 bcd. 규칙 3은 활성 지점을 오른쪽 노드와 가장자리 bcd로만 설정 했으므로 d활성 지점에 최종 문자 를 삽입하기 만하면 삽입 할 수 있습니다 .

이렇게하면 또 다른 가장자리 분할이 발생하고 규칙 2 때문에 이전에 삽입 된 노드에서 새 노드로 접미사 링크를 만들어야합니다.

우리는 다음을 관찰합니다. 접미사 링크를 사용하면 활성 지점을 재설정 할 수 있으므로 O (1) 노력으로 다음 나머지 삽입 을 할 수 있습니다 . 위의 그래프를보고 실제로 레이블 ab의 노드가 b(접미사)의 노드에 abc연결되어 있고의 노드 가에 연결되어 있는지 확인 bc합니다.

현재 단계가 아직 완료되지 않았습니다. remainder이제 2이고 활성 지점을 다시 재설정하려면 규칙 3을 따라야합니다. 현재 active_node(위의 빨간색)에는 접미사 링크가 없으므로 루트로 재설정합니다. 활성 지점은 이제 (root,'c',1)입니다.

따라서 다음 삽입은 레이블이 c:로 시작하는 루트 노드 cabxabcd의 첫 번째 문자 뒤, 즉 뒤에 있는 하나의 나가는 가장자리에서 발생합니다 c. 이로 인해 또 다른 분할이 발생합니다.

그리고 여기에는 새 내부 노드 생성이 포함되므로 규칙 2를 따르고 이전에 생성 된 내부 노드에서 새 접미사 링크를 설정합니다.

(저는 이 작은 그래프에 Graphviz Dot 을 사용하고 있습니다. 새로운 접미사 링크로 인해 점이 기존 가장자리를 재정렬하게했기 때문에 위에 삽입 된 유일한 것이 새로운 접미사 링크인지주의 깊게 확인하십시오.)

이를 통해을 remainder1로 설정할 수 active_node있으며이 루트이므로 규칙 1을 사용하여 활성 포인트를 (root,'d',0). 이것은 현재 단계의 마지막 삽입이 d루트에 단일을 삽입하는 것임을 의미 합니다.

그것이 마지막 단계 였고 우리는 끝났습니다. 하지만 다음 과 같은 최종 관찰 이 있습니다 .

  • 각 단계에서 우리는 #한 위치 씩 앞으로 이동 합니다. 이렇게하면 O (1) 시간에 모든 리프 노드가 자동으로 업데이트됩니다.

  • 그러나 a) 이전 단계에서 남은 접미사 및 b) 현재 단계의 마지막 문자 하나 는 다루지 않습니다 .

  • remainder얼마나 많은 추가 인서트를 만들어야하는지 알려줍니다. 이러한 삽입은 현재 위치에서 끝나는 문자열의 마지막 접미사에 일대일로 대응합니다 #. 우리는 차례로 고려하고 삽입합니다. 중요 : 활성 지점이 정확히 어디로 가야하는지 알려주기 때문에 각 삽입은 O (1) 시간에 이루어지며 활성 지점에 하나의 문자 만 추가하면됩니다. 왜? 다른 문자가 암시 적 으로 포함 되기 때문입니다 (그렇지 않으면 활성 지점이 현재 위치가 아님).

  • 각 삽입 후에 remainder접미사 링크가있는 경우 감소 하고 따라갑니다. 그렇지 않으면 루트로 이동합니다 (규칙 3). 이미 루트에 있다면 규칙 1을 사용하여 활성 지점을 수정합니다. 어떤 경우에도 O (1) 시간 만 걸립니다.

  • 이러한 삽입 중 하나에서 삽입하려는 문자가 이미있는 것을 발견하면 아무것도하지 않고 현재 단계를 종료합니다 remainder. 그 이유는 남아있는 삽입물이 우리가 방금 시도한 접미사가되기 때문입니다. 따라서 이들은 모두 현재 트리에 내재 되어 있습니다. remainder> 0 이라는 사실은 나중에 나머지 접미사를 처리하도록합니다.

  • 알고리즘의 끝에서 remainder> 0이면 어떨까요? 이것은 텍스트의 끝이 이전 어딘가에서 발생한 부분 문자열 인 경우에 해당됩니다. 이 경우 이전에 발생하지 않은 문자열 끝에 하나의 추가 문자를 추가해야합니다. 문헌에서 일반적으로 달러 기호 $는 그 기호 로 사용됩니다. 그게 왜 중요할까요? -> 나중에 완성 된 접미사 트리를 사용하여 접미사를 검색하는 경우 , 잎으로 끝나는 경우에만 일치를 수락해야합니다 . 그렇지 않으면 기본 문자열의 실제 접미사가 아닌 트리에 암시 적으로 포함 된 많은 문자열 이 있기 때문에 많은 가짜 일치를 얻을 수 있습니다. 강제remainder끝에서 0이되는 것은 본질적으로 모든 접미사가 리프 노드에서 끝나도록하는 방법입니다. 그러나 트리를 사용하여 기본 문자열의 접미사 뿐만 아니라 일반 하위 문자열 을 검색하려는 경우 아래 OP의 주석에서 제안한대로이 마지막 단계는 실제로 필요하지 않습니다.

  • 그렇다면 전체 알고리즘의 복잡성은 무엇입니까? 텍스트 길이가 n 자이면 분명히 n 단계 (또는 달러 기호를 추가하면 n + 1)가 있습니다. 각 단계에서 우리는 아무것도하지 않거나 (변수를 업데이트하는 것 외에) remainder삽입을합니다. 각각 O (1) 시간이 걸립니다. remainder이전 단계에서 아무 작업도 수행하지 않았고 지금 만드는 모든 삽입에 대해 감소하는 횟수를 나타 내기 때문에 우리가 어떤 작업을 수행하는 총 횟수는 정확히 n (또는 n + 1)입니다. 따라서 총 복잡도는 O (n)입니다.

  • 그러나 내가 제대로 설명하지 못한 작은 것이 하나 있습니다. 접미사 링크를 따라 가고 활성 지점을 업데이트 한 다음 해당 active_length구성 요소가 새 active_node. 예를 들어, 다음과 같은 상황을 고려하십시오.

(점선은 트리의 나머지 부분을 나타냅니다. 점선은 접미사 링크입니다.)

이제 활성 지점 을로하여 가장자리 (red,'d',3)뒤의 위치를 ​​가리 킵니다 . 이제 필요한 업데이트를 수행하고 접미사 링크를 따라 규칙 3에 따라 활성 포인트를 업데이트한다고 가정합니다. 새 활성 포인트는 입니다. 그러나 녹색 노드에서 나가는 -edge는 이므로 2 자만 있습니다. 올바른 활성 지점을 찾으려면 해당 가장자리를 따라 파란색 노드로 이동하고로 재설정해야 합니다.fdefg(green,'d',3)dde(blue,'f',1)

특히 나쁜 경우는 active_length한 크게 할 수 remainder없음 한 크게 할 수있다. 그리고 올바른 활성 지점을 찾으려면 하나의 내부 노드를 건너 뛸뿐만 아니라 최악의 경우 최대 n 개까지 점프해야 할 수도 있습니다. 각 단계 에서 일반적으로 O (n)이고 접미사 링크를 따르는 활성 노드에 대한 사후 조정도 O (n)이 될 수 있기 때문에 알고리즘에 숨겨진 O (n 2 ) 복잡성 이 있음을 의미합니까 remainder?

아니요. 그 이유는 실제로 활성 지점을 조정해야하는 경우 (예 : 위와 같이 녹색에서 파란색으로) 자체 접미사 링크가있는 새 노드로 이동하여 active_length축소되기 때문입니다. 접미사 링크 체인을 따라갈 때 나머지 삽입물을 만들고 active_length줄일 수만 있으며 도중에 수행 할 수있는 활성 포인트 조정 횟수는 active_length주어진 시간 보다 클 수 없습니다 . 이후는 active_length보다 클 수 없다 remainder, 그리고 remainder뿐만 아니라 매 단계에서 O (n)은, 그러나 이제까지 만든 단위의 총 합이 remainder전체 프로세스의 과정은 O (N)가 너무 활성 점 조정의 수입니다 또한 O (n)에 의해 제한됩니다.

jogojapan의 답변에 주어진 접근 방식으로 Suffix Tree를 구현하려고 시도했지만 규칙에 사용되는 문구로 인해 일부 경우에는 작동하지 않았습니다. 게다가, 아무도이 접근법을 사용하여 절대적으로 정확한 접미사 트리를 구현하지 못했다고 언급했습니다. 아래에서는 규칙을 수정하여 jogojapan의 답변에 대한 "개요"를 작성합니다. 중요한 접미사 링크 를 만드는 것을 잊은 경우도 설명하겠습니다 .

사용 된 추가 변수

  1. 활성 지점 -새 접미사 삽입을 시작해야하는 위치를 보여주는 트리플 (active_node; active_edge; active_length).
  2. 나머지 - 명시 적으로 추가해야하는 접미사 수를 표시합니다 . 예를 들어 우리의 단어가 'abcaabca'이고 나머지 = 3이면 마지막 접미사 3 개 ( bca , ca 및 a)를 처리해야 함을 의미합니다 .

내부 노드 의 개념을 사용해 보겠습니다 . 루트 와 리프를 제외한 모든 노드 는 내부 노드 입니다.

관찰 1

삽입해야하는 최종 접미사가 이미 트리에 존재하는 것으로 확인되면 트리 자체는 전혀 변경되지 않습니다 ( active point및 만 업데이트 remainder).

관찰 2

어떤 지점에서 active_length현재 가장자리의 길이 ( edge_length) 보다 크거나 같으면가 더 커질 active point때까지 아래로 이동합니다 .edge_lengthactive_length

이제 규칙을 재정의 해 보겠습니다.

규칙 1

활성 노드 에서 삽입 = root 이면 활성 길이 가 0보다 크면 다음과 같습니다.

  1. 활성 노드 는 변경되지 않습니다.
  2. 활성 길이 가 감소합니다.
  3. 활성 가장자리 가 오른쪽으로 이동합니다 (삽입해야하는 다음 접미사의 첫 번째 문자로).

규칙 2

우리는 새로운 만들 경우 내부 노드 또는 에서 삽입 할 내부 노드를 ,이 첫 번째 아니다 그러한 내부 노드 현재 단계에서, 우리는 이전의 링크 와 같은 과 노드를 본 스루 하나의 접미사 링크 .

이 정의는 Rule 2jogojapan '과 다릅니다. 여기에서는 새로 생성 된 내부 노드뿐만 아니라 삽입하는 내부 노드도 고려합니다.

규칙 3

루트 노드 가 아닌 활성 노드 에서 삽입 한 후 접미사 링크를 따라 활성 노드 를 가리키는 노드 로 설정해야합니다 . 접미사 링크가없는 경우 활성 노드 를 루트 노드 로 설정 합니다. 어느 쪽이든 활성 에지 와 활성 길이 는 변경되지 않습니다.

이 정의에서는 Rule 3리프 노드 (분할 노드뿐만 아니라)의 삽입도 고려합니다.

마지막으로 관찰 3 :

트리에 추가하려는 심볼이 이미 가장자리에 Observation 1있을 때에 따라 active point및 에 따라 업데이트 remainder만하고 트리는 변경되지 않은 상태로 둡니다. 그러나 접미사 링크가 필요한 것으로 표시된 내부 노드 가있는 경우 접미사 링크active node 를 통해 해당 노드를 전류와 연결해야합니다 .

이러한 경우 접미사 링크를 추가하고 그렇지 않은 경우 cdddcdc 에 대한 접미사 트리의 예를 살펴 보겠습니다 .

  1. 접미사 링크를 통해 노드를 연결 하지 않는 경우 :

    • 마지막 문자 c 를 추가하기 전에 :

    • 마지막 문자 c를 추가 한 후 :

  2. 우리는 경우 DO 접미사 링크를 통해 노드를 연결 :

    • 마지막 문자 c 를 추가하기 전에 :

    • 마지막 문자 c를 추가 한 후 :

큰 차이가없는 것 같습니다. 두 번째 경우에는 접미사 링크가 두 개 더 있습니다. 그러나 이러한 접미사 링크는 정확 하며 그중 하나 (파란색 노드에서 빨간색 노드까지)는 활성 지점을 사용한 접근에 매우 중요 합니다 . 문제는 여기에 접미사 링크를 넣지 않으면 나중에 트리에 새 문자를 추가 할 때으로 인해 트리에 일부 노드를 추가 Rule 3하지 않을 수 있다는 것입니다. 접미사 링크 active_node를 사용하려면을 루트에 넣어야합니다 .

트리에 마지막 문자를 추가 할 때 파란색 노드에서 삽입하기 전에 빨간색 노드가 이미 존재했습니다 (가장자리 'c' ). 파란색 노드의 삽입물 이 있으므로 접미사 링크가 필요하다고 표시합니다 . 그런 다음 활성 지점 접근 방식 active node에 따라 빨간색 노드로 설정되었습니다. 그러나 문자 'c' 가 이미 가장자리에 있으므로 빨간색 노드에서 삽입하지 않습니다 . 파란색 노드가 접미사 링크없이 남아 있어야 함을 의미합니까? 아니요, 접미사 링크를 통해 파란색 노드와 빨간색 노드를 연결해야합니다. 왜 정확합니까? 액티브 포인트 때문에접근 방식은 올바른 위치, 즉 더 짧은 접미사 의 삽입을 처리해야하는 다음 위치에 도달하도록 보장합니다 .

마지막으로 접미사 트리 구현은 다음과 같습니다.

  1. 자바
  2. C ++

이 "개요"가 jogojapan의 자세한 답변과 결합되어 누군가가 자신의 Suffix Tree를 구현하는 데 도움이되기를 바랍니다.

@jogojapan 의 잘 설명 된 튜토리얼에 감사드립니다 . 저는 알고리즘을 파이썬으로 구현했습니다.

@jogojapan이 언급 한 몇 가지 사소한 문제 는 내가 예상했던 것보다 더 정교 해 졌으므로 매우 신중하게 처리해야합니다. 내 구현을 충분히 견고하게 만드는 데 며칠이 걸렸습니다 . 문제와 해결 방법은 다음과 같습니다.

  1. End withRemainder > 0 이 상황은 전체 알고리즘의 끝이 아닌 전개 단계 에서도 발생할 수 있습니다 . 그럴 때 나머지, actnode, actedge 및 actlength를 변경하지 않고 그대로 두고 현재 전개 단계를 종료하고 원래 문자열의 다음 문자가 현재 경로에 있는지 여부에 따라 계속 접거나 펼쳐서 다른 단계를 시작할 수 있습니다. 아니.

  2. Leap Over Nodes : 접미사 링크를 따라갈 때 활성 지점을 업데이트 한 다음 해당 active_length 구성 요소가 새 active_node에서 제대로 작동하지 않음을 확인합니다. 우리는 분할하거나 잎을 삽입 할 올바른 위치 로 이동 해야합니다 . 이 과정은 수 있습니다 이 간단하지 때문에하여 actlength를 이동하고 다시 이동해야 할 때 actedge 킵은, 모든에게 방법을 변경하는 동안 루트 노드 의 actedge 및 actlength이 될 수 잘못 때문에 그 움직임. 해당 정보를 유지하려면 추가 변수가 필요합니다.

    여기에 이미지 설명 입력

다른 두 가지 문제는 @managonov 가 어떻게 든 지적했습니다.

  1. 분할이 퇴화 될 수 있음 에지를 분할하려고 할 때 분할 작업이 노드에서 올바르게 작동하는 것을 발견 할 수 있습니다. 이 경우 해당 노드에 새 리프를 추가하기 만하면됩니다. 표준 에지 분할 작업으로 간주합니다. 즉, 접미사 링크가 있으면 그에 따라 유지되어야합니다.

  2. 숨겨진 접미사 링크 문제 1 과 문제 2 에 의해 발생하는 또 다른 특별한 경우가 있습니다 . 때때로 우리는 분할을 위해 여러 노드를 올바른 지점으로 이동해야합니다. 나머지 문자열과 경로 레이블을 비교하여 이동하면 올바른 지점을 초과 할 수 있습니다 . 이 경우 접미사 링크가 있어야하는 경우 의도하지 않게 무시됩니다. 이것은 앞으로 나아갈 때 올바른 지점 을 기억 함으로써 피할 수 있습니다 . 분할 노드가 이미 존재하거나 전개 단계 에서 문제 1이 발생하는 경우 접미사 링크를 유지해야합니다 .

마지막으로 Python 에서 구현 한 내용 은 다음과 같습니다.

팁 : 위의 코드에 순진한 트리 인쇄 기능 이 포함되어 있으며 이는 디버깅하는 동안 매우 중요 합니다. 그것은 저에게 많은 시간을 절약하고 특별한 경우를 찾는 데 편리합니다.

@jogojapan 당신은 멋진 설명과 시각화를 가져 왔습니다. 그러나 @makagonov가 언급했듯이 접미사 링크 설정과 관련된 몇 가지 규칙이 없습니다. http://brenden.github.io/ukkonen-animation/ 에서 'aabaaabb'라는 단어를 통해 단계별로 진행할 때 멋지게 보입니다 . 10 단계에서 11 단계로 이동하면 노드 5에서 노드 2 로의 접미사 링크가 없지만 활성 포인트가 갑자기 그곳으로 이동합니다.

@makagonov Java 세계에 살고 있기 때문에 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);
        }
    });
  }
}

내 대답이 중복되는 것 같으면 사과하지만 최근에 Ukkonen의 알고리즘을 구현했으며 며칠 동안 어려움을 겪고 있습니다. 알고리즘의 일부 핵심 측면의 이유와 방법을 이해하기 위해 주제에 대한 여러 논문을 읽어야했습니다.

나는 이전 답변의 '규칙'접근 방식이 근본적인 이유 를 이해하는 데 도움이되지 않는다는 것을 알았으므로 실용주의에만 초점을 맞춰 아래에 모든 것을 작성했습니다. 내가 한 것처럼 다른 설명을 따르는 데 어려움을 겪었다면 내 보충 설명이 '클릭'하게 만들 것입니다.

내 C # 구현을 여기에 게시했습니다 : https://github.com/baratgabor/SuffixTree

저는이 주제에 대한 전문가가 아니므로 다음 섹션에 부정확하거나 더 나쁜 내용이 포함될 수 있습니다. 만난다면 자유롭게 편집하십시오.

전제 조건

다음 설명의 시작점에서는 접미사 트리의 내용과 사용, Ukkonen 알고리즘의 특성 (예 : 처음부터 끝까지 문자별로 접미사 트리를 확장하는 방법)에 익숙하다고 가정합니다. 기본적으로 다른 설명을 이미 읽었다 고 가정합니다.

(하지만 흐름에 대한 몇 가지 기본 설명을 추가해야했기 때문에 시작 부분이 과도하게 느껴질 수 있습니다.)

가장 흥미로운 부분은 접미사 링크를 사용하는 것과 루트에서 다시 검색하는 것의 차이점에 대한 설명입니다 . 이것이 제 구현에서 많은 버그와 골칫거리를주었습니다.

개방형 리프 노드 및 그 한계

가장 기본적인 '속임수'는 접미사 'open'의 끝을 그대로 둘 수 있다는 것을 이미 알고 계실 것입니다. 즉, 끝을 정적 인 값으로 설정하는 대신 문자열의 현재 길이를 참조하면됩니다. 이렇게하면 추가 문자를 추가 할 때 해당 문자를 모두 방문하여 업데이트 할 필요없이 모든 접미사 레이블에 암시 적으로 추가됩니다.

그러나이 접미사의 열린 끝은 – 명백한 이유로 – 문자열의 끝을 나타내는 노드, 즉 트리 구조의 리프 노드에서만 작동합니다. 트리에서 실행하는 분기 작업 (새 분기 노드 및 리프 노드 추가)은 필요한 모든 곳에서 자동으로 전파되지 않습니다.

반복되는 부분 문자열은 트리에 이미 반복되어 있기 때문에 이미 포함되어 있기 때문에 반복되는 부분 문자열이 트리에 명시 적으로 나타나지 않는다는 것은 아마도 기본적이고 언급 할 필요가 없습니다. 그러나 반복되는 부분 문자열이 반복되지 않는 문자를 만나서 끝나는 경우 해당 지점에서 분기를 나타내는 지점을 생성해야합니다.

예를 들어 문자열 'ABCXABCY' (아래 참조)의 경우 X 및 Y 로의 분기를 ABC , BC 및 C 세 가지 접미사에 추가해야합니다 . 그렇지 않으면 유효한 접미사 트리가 아니며 루트에서 아래쪽으로 문자를 일치시켜 문자열의 모든 하위 문자열을 찾을 수 없습니다.

다시 한 번 강조하기 위해 트리의 접미사에 대해 실행하는 모든 작업은 연속 접미사에도 반영되어야합니다 (예 : ABC> BC> C). 그렇지 않으면 유효한 접미사가 더 이상 없습니다.

접미사에서 반복 분기

그러나 이러한 수동 업데이트를 수행해야한다는 사실을 인정하더라도 업데이트해야하는 접미사 수를 어떻게 알 수 있습니까? 반복되는 문자 A (및 나머지 반복되는 문자)를 추가 할 때 접미사를 두 개의 분기로 분할해야하는시기 / 위치를 아직 알 수 없습니다. 분할의 필요성은 반복되지 않는 첫 번째 문자,이 경우 Y ( 트리에 이미 존재 하는 X 대신)를 만날 때만 확인됩니다 .

우리가 할 수있는 일은 우리가 할 수있는 가장 긴 반복 문자열을 일치시키고 나중에 업데이트해야하는 접미사 수를 세는 것입니다. 이것이 '나머지' 가 의미하는 것입니다.

'나머지'및 '재검색'의 개념

변수 remainder는 분기없이 암시 적으로 추가 한 반복 문자 수를 알려줍니다. 즉, 일치 할 수없는 첫 번째 문자를 찾은 후 분기 작업을 반복하기 위해 방문해야하는 접미사 수입니다. 이것은 본질적으로 우리가 뿌리에서 트리에있는 '깊이'문자 수와 같습니다.

따라서 ABCXABCY 문자열의 이전 예를 유지하면서 반복 된 ABC 부분을 ​​'암시 적으로' 일치시켜 매번 증가 remainder하여 나머지 3이됩니다. 그런 다음 반복되지 않는 문자 'Y' 가 발생합니다 . 여기에서 이전에 추가 된 ABCX 를 ABC- > X 및 ABC- > Y 로 분할합니다 . 그런 다음 ABC 분기를 remainder이미 처리했기 때문에 3에서 2로 감소 합니다. 이제 우리 는 루트에서 분할해야하는 지점까지 마지막 2 개 문자 인 BC 를 일치시켜 작업을 반복하고 BCX 도 BC 로 분할합니다.-> X 및 BC -> Y . 다시 remainder1로 감소 하고 작업을 반복합니다. (가) 될 때까지 remainder마지막으로 0입니다, 우리는 (현재의 문자를 추가 할 필요가 Y를 루트뿐만 아니라 자체를).

이 작업은 루트에서 연속 접미사를 따라 단순히 작업을 수행해야하는 지점에 도달하기 위해 Ukkonen의 알고리즘에서 '재검색' 이라고 부르는 작업 이며 일반적으로 알고리즘에서 가장 비용이 많이 드는 부분입니다. 수십 개의 노드에서 긴 부분 문자열을 '재검색'해야하는 긴 문자열이 잠재적으로 수천 번이라고 상상해보십시오.

해결책으로 우리는 '접미사 링크' 라고 부르는 것을 소개합니다 .

'접미사 링크'의 개념

접미사 링크는 기본적으로 우리가 일반적으로 '재 스캔' 해야하는 위치를 가리 키 므로 값 비싼 재 스캔 작업 대신 단순히 링크 된 위치로 이동하여 작업을 수행하고 다음 링크 된 위치로 이동 한 다음 반복 할 수 있습니다. 더 이상 업데이트 할 위치가 없습니다.

물론 한 가지 큰 질문은 이러한 링크를 추가하는 방법입니다. 기존의 대답은 우리가 새로운 분기 노드를 삽입 할 때 링크를 추가 할 수 있다는 것입니다. 트리의 각 확장에서 분기 노드는 서로 연결하는 데 필요한 정확한 순서대로 자연스럽게 하나씩 생성된다는 사실을 활용하여 . 하지만 마지막으로 생성 된 분기 노드 (가장 긴 접미사)에서 이전에 생성 된 노드로 연결해야하므로 마지막으로 생성 한 노드를 캐시하고 다음 생성 한 노드에 연결하고 새로 생성 된 노드를 캐시해야합니다.

한 가지 결과는 주어진 분기 노드가 방금 생성 되었기 때문에 실제로 따라갈 접미사 링크가없는 경우가 많습니다. 이 경우에도 루트에서 앞서 언급 한 '재검색'으로 돌아 가야 합니다. 이것이 삽입 후 접미사 링크를 사용하거나 루트로 이동하라는 지시를받는 이유입니다.

(또는 노드에 부모 포인터를 저장하는 경우 부모를 따라 가서 링크가 있는지 확인하여 사용할 수 있습니다. 이것은 거의 언급되지 않지만 접미사 링크 사용은 그렇지 않습니다. 돌에서 설정합니다. 이 여러 가능한 방법이 있고, 당신은 기본 메커니즘을 이해한다면 당신은 당신의 요구에 가장 적합한 하나를 구현할 수 있습니다.)

'액티브 포인트'의 개념

지금까지 우리는 트리를 구축하기위한 여러 가지 효율적인 도구에 대해 논의했고 여러 에지와 노드를 가로 지르는 것에 대해 모호하게 언급했지만 해당 결과와 복잡성을 아직 탐구하지 않았습니다.

앞서 설명한 '나머지' 개념은 우리가 트리에서 어디에 있는지 추적하는 데 유용하지만 충분한 정보를 저장하지 않는다는 것을 깨달아야합니다.

첫째, 우리는 항상 노드의 특정 에지에 상주하므로 에지 정보를 저장해야합니다. 이것을 '액티브 에지'라고 부를 것 입니다.

둘째, 에지 정보를 추가 한 후에도 루트 노드에 직접 연결되지 않고 트리에서 더 아래에있는 위치를 식별 할 수있는 방법이 없습니다 . 따라서 노드도 저장해야합니다. 이것을 '액티브 노드' 라고합시다 .

마지막으로, 우리는 것을 알 수 있습니다 '나머지' 때문에, 직접 루트에 연결되지 않은 가장자리에 위치를 식별하는 데 부적절하다 ', 나머지는' 전체 경로의 길이가; 그리고 우리는 아마도 이전 가장자리의 길이를 기억하고 빼는 것을 귀찮게하고 싶지 않을 것입니다. 그래서 우리는 본질적으로 현재 가장자리 의 나머지 인 표현이 필요합니다 . 이것이 우리가 '활성 길이' 라고 부르는 것 입니다.

이것은 우리가 트리에서 우리의 위치에 대해 유지하는 데 필요한 모든 정보를 포함하는 3 개의 변수 패키지 인 '활성 포인트'로 이어집니다 .

Active Point = (Active Node, Active Edge, Active Length)

다음 이미지에서 ABCABD 의 일치하는 경로가 에지 AB ( root에서 ) 에있는 2 개의 문자와 CABDABCABD (노드 4에서) 에있는 4 개의 문자 로 구성되는 방식을 관찰 할 수 있습니다. 결과적 으로 6 자의 '나머지' 가 생성됩니다 . 따라서 현재 위치는 Active Node 4, Active Edge C, Active Length 4 로 식별 할 수 있습니다 .

나머지 및 활성 포인트

'활성 지점' 의 또 다른 중요한 역할은 알고리즘에 대한 추상화 계층을 제공한다는 것입니다. 즉, 알고리즘의 일부가 해당 활성 지점이 루트에 있든 다른 곳에 있든 관계없이 '활성 지점' 에서 작업을 수행 할 수 있습니다. . 이를 통해 우리 알고리즘의 접미사 링크 사용을 깔끔하고 직관적 인 방식으로 쉽게 구현할 수 있습니다.

재검색과 접미사 링크 사용의 차이점

제 경험상 많은 버그와 골칫거리를 유발할 수 있고 대부분의 소스에서 잘 설명되지 않는 까다로운 부분은 접미사 링크 케이스 처리와 재검색 케이스 처리의 차이입니다.

'AAAABAAAABAAC' 문자열의 다음 예를 고려하십시오 .

여러 모서리에 걸친 나머지

7 의 '나머지' 가 루트의 총 문자 합계에 해당하는 반면 '활성 길이' 4는 활성 노드의 활성 에지에서 일치하는 문자의 합계에 해당하는 방식을 위에서 볼 수 있습니다 .

이제 활성 지점에서 분기 작업을 실행 한 후 활성 노드에 접미사 링크가 포함되거나 포함되지 않을 수 있습니다.

접미사 링크가있는 경우 : '활성 길이' 부분 만 처리하면 됩니다. '나머지' 때문에 무관하다 우리는 접미사 링크를 통해 이동할 노드가 이미 암시 적으로 올바른 '나머지'를 인코딩 단순히이 트리에있는 덕분에,.

접미사 링크가없는 경우 : 0 / 루트에서 '재검색' 해야합니다. 즉, 처음부터 전체 접미사를 처리해야합니다. 이를 위해 우리는 전체 '나머지' 를 재검색의 기초로 사용해야합니다 .

접미사 링크가 있거나없는 처리 비교 예

위 예의 다음 단계에서 어떤 일이 발생하는지 고려하십시오. 접미사 링크를 사용하거나 사용하지 않고 동일한 결과를 얻는 방법 (예 : 처리 할 다음 접미사로 이동)을 비교해 보겠습니다.

사용 '접미사 링크를'

접미사 링크를 통해 연속 접미사에 도달

접미사 링크를 사용하면 자동으로 '올바른 위치'에 있습니다. '활성 길이' 가 새 위치와 '호환되지 않을'수 있기 때문에 엄격하게 사실이 아닌 경우가 많습니다 .

위의 경우 '활성 길이' 가 4이므로 연결된 Node 4에서 시작 하여 접미사 ' ABAA'로 작업합니다 .하지만 접미사 ( 'A') 의 첫 번째 문자에 해당하는 가장자리를 찾은 후 ), 우리는 우리의 '활성 길이' 가이 가장자리를 3 자로 넘친다 는 것을 알 수 있습니다. 그래서 우리는 전체 가장자리에서 다음 노드로 점프하고 점프로 소비 한 캐릭터에 의해 '활성 길이' 를 줄입니다.

그런 다음 감소 된 접미사 'BAA '에 해당하는 다음 가장자리 'B'를 찾은 후 마지막으로 가장자리 길이가 나머지 '활성 길이' 3 보다 큽니다. 즉, 올바른 위치를 찾았 음을 의미합니다.

이 작업은 길이가 짧고 루트가 아닌 시작점을 사용하는 재검색과 직접적으로 동일 해 보이지만 일반적으로 '재검색'이라고 부르지 않는 것 같습니다.

사용 '다시 검색'

재검색을 통해 연속 접미사에 도달

기존의 '재검색'작업 (여기서는 접미사 링크가없는 척)을 사용하는 경우 트리 맨 위, 루트에서 시작하여 올바른 위치로 다시 내려 가야합니다. 현재 접미사의 전체 길이를 따라갑니다.

이 접미사의 길이는 이전에 논의한 '나머지' 입니다. 0에 도달 할 때까지 나머지 전체를 소비해야합니다. 여기에는 여러 노드를 통한 점프가 포함될 수 있으며 각 점프에서 우리가 통과 한 가장자리의 길이만큼 나머지가 감소합니다. 마지막으로 남은 '나머지' 보다 더 긴 가장자리에 도달합니다 . 여기에서 활성 에지를 주어진 에지로 설정하고 '활성 길이' 를 나머지 '나머지 '로 설정하면 완료됩니다.

그러나 실제 '나머지' 변수는 보존되어야하며 각 노드 삽입 후에 만 ​​감소해야합니다. 그래서 위에서 설명한 것은 'remainder'로 초기화 된 별도의 변수를 사용한다고 가정했습니다 .

접미사 링크 및 재검색에 대한 참고 사항

1) 두 방법 모두 동일한 결과를 가져옵니다. 그러나 접미사 링크 점프는 대부분의 경우 훨씬 더 빠릅니다. 이것이 접미사 링크의 전체적인 근거입니다.

2) 실제 알고리즘 구현은 다를 필요가 없습니다. 위에서 언급했듯이 접미사 링크를 사용하는 경우에도 '활성 길이' 는 트리의 분기에 추가 분기가 포함될 수 있으므로 링크 된 위치와 호환되지 않는 경우가 많습니다. 따라서 기본적 으로 'remainder ' 대신 'active length' 를 사용 하고 나머지 접미사 길이보다 짧은 가장자리를 찾을 때까지 동일한 재검색 논리를 실행해야합니다.

3) 성능과 관련하여 한 가지 중요한 점은 다시 스캔하는 동안 모든 문자를 확인할 필요가 없다는 것입니다. 유효한 접미사 트리가 구축되는 방식으로 인해 문자가 일치한다고 안전하게 가정 할 수 있습니다. 그래서 당신은 대부분 길이를 세고 있고, 우리가 새로운 엣지로 점프 할 때 캐릭터 동등성 검사에 대한 유일한 필요성이 발생합니다. 엣지는 그들의 첫 번째 캐릭터 (주어진 노드의 맥락에서 항상 고유함)로 식별되기 때문입니다. 즉, '재검색'논리는 전체 문자열 일치 논리 (예 : 트리에서 하위 문자열 검색)와 다릅니다.

4) 여기에 설명 된 원래 접미사 연결 은 가능한 접근 방식 중 하나 일뿐 입니다. 예를 들어 NJ Larsson et al. 이 접근 방식을 Node-Oriented Top-Down 으로 명명 하고 Node-Oriented Bottom-Up 및 두 개의 Edge-Oriented 품종 과 비교합니다 . 다른 접근 방식은 일반적인 및 최악의 경우 성능, 요구 사항, 제한 사항 등이 다르지만 일반적으로 Edge-Oriented 접근 방식은 원본에 대한 전반적인 개선 인 것 같습니다 .

내 직감은 다음과 같습니다.

메인 루프를 k 번 반복 한 후 처음 k 개 문자로 시작하는 전체 문자열의 모든 접미사를 포함하는 접미사 트리를 구성했습니다.

처음에는 접미사 트리에 전체 문자열을 나타내는 단일 루트 노드가 포함되어 있음을 의미합니다 (이는 0에서 시작하는 유일한 접미사입니다).

len (string) 반복 후에는 모든 접미사를 포함하는 접미사 트리가 있습니다.

루프 중에 키는 활성 지점입니다. 내 생각에 이것은 문자열의 처음 k 문자의 적절한 접미사에 해당하는 접미사 트리에서 가장 깊은 지점을 나타냅니다. (올바른 것은 접미사가 전체 문자열이 될 수 없다는 것을 의미한다고 생각합니다.)

예를 들어 'abcabc'문자를 본 적이 있다고 가정합니다. 활성 포인트는 접미사 'abc'에 해당하는 트리의 포인트를 나타냅니다.

활성 포인트는 (원점, 첫 번째, 마지막)으로 표시됩니다. 이것은 현재 노드 원점에서 시작하여 string [first : last]의 문자를 입력하여 도달하는 트리의 지점에 있음을 의미합니다.

새 캐릭터를 추가 할 때 활성 포인트가 여전히 기존 트리에 있는지 확인합니다. 그렇다면 완료된 것입니다. 그렇지 않으면 활성 지점의 접미사 트리에 새 노드를 추가하고 다음 가장 짧은 일치 항목으로 대체 한 다음 다시 확인해야합니다.

참고 1 : 접미사 포인터는 각 노드에 대해 다음으로 가장 짧은 일치 항목에 대한 링크를 제공합니다.

참고 2 : 새 노드를 추가하고 대체 할 때 새 노드에 대한 새 접미사 포인터를 추가합니다. 이 접미사 포인터의 대상은 단축 된 활성 지점의 노드가됩니다. 이 노드는 이미 존재하거나이 폴백 루프의 다음 반복에서 생성됩니다.

참고 3 : 정규화 부분은 단순히 활성 지점을 확인하는 시간을 절약합니다. 예를 들어 항상 origin = 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

반응형

'your programing' 카테고리의 다른 글

지정된 이름의 열을 포함하는 모든 테이블 찾기-MS SQL Server  (0) 2020.09.27
Vim에서 줄에 주석을 달거나 주석을 제거하는 빠른 방법은 무엇입니까?  (0) 2020.09.27
iOS 6의 Safari가 $ .ajax 결과를 캐싱합니까?  (0) 2020.09.27
두 목록을 사전으로 변환  (0) 2020.09.27
Visual Studio에서 솔루션 빌드, 솔루션 다시 빌드 및 솔루션 정리의 차이점은 무엇입니까?  (0) 2020.09.27

'your programing'의 다른글

  • 현재글평범한 영어로 된 Ukkonen의 접미사 트리 알고리즘

관련글

댓글

티스토리툴바