접미어 트리에서 센티넬 문자가 필요한 이유는 무엇입니까?

Question

suffix tree을 구현할 때 왜 원래 문자열에 "$"를 추가해야합니까?

Answer 1

특정 건설 ​​알고리즘 접미사 나무의 경우 – 모두를 사용하는 경우 문자열의 마지막에 (더 이상) 특수 문자 하나를 추가하기위한 특별한 이유가있을 수 있습니다 접미사 배열. 가장자리 라벨은 즉

1. 접미사 나무 가장자리는 달리, PATRICIA 나무됩니다

   그러나 접미사 나무의 경우 가장 기본적인 근본적인 이유는 접미사 나무의 두 가지 속성의 조합이다 시도의 라벨 만 분기점

이에서 문자열

내부 노드가 존재 하나 이상의 문자로 구성된

생각이 여기에 즉 접미사는 여기서 끝, 오른쪽에 검은 색 노드가 잎 노드 점이다 : 당신은 잠재적으로 하나 개의 에지 라벨이 다른 접두사 인 상황을 가질 수 있습니다 의미합니다. 그러나 텍스트의 접미어가 aa 인 경우 단일 문자 a도 접미사 여야합니다. 그러나 aa이 트리의 하나의 연속 가장자리를 형성하기 때문에 (위의 속성 1) 접미사가 첫 번째 a 다음에 끝나는 정보를 저장할 방법이 없습니다. 우리는 다음과 같이, 우리는 정보를 저장할 수있는 중간 노드를 도입해야 할 것 :

하지만이 때문에 재산이 불법이 될 것입니다 : 분기점이 존재하지 않는 한 내부 노드는 존재하지 않는해야합니다.

텍스트의 마지막 문자가 전체 문자열에서 다른 곳에서 발생하지 않는 문자임을 보장 할 수 있으면 문제가 해결됩니다. 달러 기호는 일반적으로 그 기호로 사용됩니다.

분명히 마지막 문자가 다른 곳에서 발생하지 않으면 문자열 끝에 아무런 반복 (예 : aa 또는 심지어 더 복잡한 문자 abcabc)이 가능할 수 없으므로 비 분기 문제 내부 노드가 발생하지 않습니다.위의 예에서, 문자열의 끝에서 $ 퍼팅의 효과는 다음과 같습니다

이제 세 접미사가 있습니다 aa$, a$ 및 $, 그러나 아무도는 다른 사람의 접두어입니다. 분명히 이것은 내부 노드를 결국 도입 할 필요가 있음을 의미하며 현재 총 3 개의 잎이 있습니다. 따라서, 이점은 이 아니며이 아니므로 공간을 절약하거나 더 효율적으로 사용할 수 있습니다. 위의 두 가지 속성을 보장하는 방법 일뿐입니다. 이러한 속성은 내부 노드 수가 문자열 길이에서 선형이라는 사실을 포함하여 접미어 트리의 유용한 특성을 증명할 때 중요합니다 (비 분기 내부 노드가 허용되는 경우 prove this 수 없음).

실제로의 을 의미하므로 다른 접미사의 접두어 인 접미사와 비 분기 내부 노드를 처리하는 다른 방법을 사용할 수 있습니다. 예를 들어 잘 알려진 Ukkonen 알고리즘을 사용하여 트리를 구성하면 끝 부분에 고유 한 문자를 추가하지 않고도이를 수행 할 수 있습니다. 마지막 반복이 끝나면 비 - 분기 내부 노드를 모든 암시 적 접미사 (즉, 가장자리의 끝에서 끝나는 모든 접미어)의 끝에 넣어야합니다.

는 다시 더있을 수 있고, 접미사 트리 나 배열을 구성하기 전에 텍스트 끝에 $를 착용하는 아주 특별한 이유. 예를 들어, DC (차폐 커버) 원리를 기반으로하는 접미어 배열의 생성 알고리즘에서 두 개의 $ 기호를 문자열 끝에 붙여 넣어 문자열의 마지막 문자조차도 완전한 문자 trigram의 일부인지 확인해야합니다 이 알고리즘은 trigram 정렬을 기반으로합니다. 또한 고유 한 $ 문자를 특수한 방식으로 해석해야하는 특정 상황이 있습니다. Ukkonen 생성 알고리즘의 경우 $은 고유해야합니다. DC 접미사 배열 알고리즘의 경우 유일성 외에도 $이 사전 식으로 모든 다른 문자보다 작아야하고 접미어 트리 기반 원형 문자열 커팅 알고리즘 (최근 언급 된 here)에서는 실제로 $을 다음과 같이 해석해야합니다. 사전 식으로 최대 문자.

Answer 2

나는 횡단 목적으로 생각합니다. 뭔가를 생성 할 때 접미어 트리에서을 알아야합니다. 문자열이 끝나는 노드에 있는지 알아야합니다. 그렇지 않으면 계속해야한다는 것을 알게됩니다. 접미어 트리가 선형 시간 솔루션을 제공하는 longest common substring을 보면 $ 센티널이 있어야 문자열이 끝나는 노드에 도달했는지 확인할 수 있습니다. A-NA 이후에 완료 할 수 없습니다. 위키 백과

에서