접미사 트리 및 시도.

접미사 트리 및 시도. 차이점은 무엇입니까?

---

나는 Tries일반적으로 접두사 트리 및 Suffix Trees.
내가 코드를 발견하지만 Trie난에 대한 예를 찾을 수 없습니다 Suffix Tree. 또한 a를 빌드하는 코드가 a의 코드 Trie와 동일 Suffix Tree하지만 전자의 경우 접두사를 저장하지만 후자의 접미사에 유일한 차이점이 있다는 느낌을받습니다 .
이것이 사실입니까? 누구든지 내 머릿속에서 이것을 정리할 수 있습니까? 예제 코드가 큰 도움이 될 것입니다!

---

접미사 트리는 문자열 자체를 trie에 추가하는 대신 해당 문자열의 가능한 모든 접미사를 추가하는 trie 위에 구축 된 데이터 구조로 볼 수 있습니다. 예를 들어 접미사 트리에서 banana 문자열을 인덱싱 하려면 다음 문자열로 trie를 빌드합니다.

banana
anana
nana
ana
na
a

이 작업이 완료되면 n-gram을 검색하여 색인화 된 문자열에 있는지 확인할 수 있습니다. 즉, n-gram 검색은 문자열의 가능한 모든 접미사에 대한 접두사 검색입니다.

이것은 접미사 트리를 만드는 가장 간단하고 느린 방법입니다. 이 데이터 구조에는 공간과 빌드 시간 중 하나 또는 둘 모두를 향상시키는 더 멋진 변형이 많이 있습니다. 나는이 분야에 대한 개요를 제공하기에 충분히 정통하지 않지만 접미사 배열 이 나이 클래스의 고급 데이터 구조 (강의 16 및 18) 를 살펴 보는 것으로 시작할 수 있습니다 .

이 답변 은 또한이 데이터 구조의 변형을 설명하는 훌륭한 작업을 수행합니다.

---

어떤 단어의 접미사를 넣는 Trie를 상상한다면 문자열의 하위 문자열을 매우 쉽게 쿼리 할 수 ​​있습니다. 이것이 접미사 트리의 기본 아이디어이며 기본적으로 "접미사 트리"입니다.

그러나이 순진한 접근 방식을 사용하면 크기 n의 문자열에 대해이 트리를 구성하면 O (n ^ 2)가되고 많은 메모리가 사용됩니다.

이 트리의 모든 항목은 동일한 문자열의 접미사이므로 많은 정보를 공유하므로보다 효율적으로 생성 할 수있는 최적화 된 알고리즘이 있습니다. 예를 들어 Ukkonen의 알고리즘을 사용하면 O (n) 시간 복잡성으로 온라인 접미사 트리를 만들 수 있습니다.

---

차이점은 매우 간단합니다. 접미사 트리는 접미사 트리보다 "더미"노드가 적습니다. 이러한 더미 노드는 트리에서 조회 작업을 증가시키는 단일 문자입니다.

참고 URL : https://stackoverflow.com/questions/13893950/suffix-tree-and-tries-what-is-the-difference