나는 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) 시간 복잡성으로 온라인 접미사 트리를 만들 수 있습니다.
답변
차이점은 매우 간단합니다. 접미사 트리에는 접미사 트리보다 “더미”노드가 적습니다. 이러한 더미 노드는 트리에서 조회 작업을 증가시키는 단일 문자입니다.
답변
Trie의 노드에는 더 짧은 컨텍스트에 대한 링크가 있지만 ‘Tree’에는 링크가 없습니다. Tree의 노드가 더 짧은 컨텍스트에 대한 링크를 얻으면 Trie; o)
답변
