접미사 트리

Question

이있는 키워드의 모든 인덱스를 찾는 것은 입력 텍스트 "미시시피"에 대한 접미사 트리의 시각적 인 그래프이다. 이 예에서 검색하고있는 키워드는 "si"입니다. 나는 "시"루트 노드에서 #

• 시작의 첫 번째 인덱스를 얻는 방법을 이해하고 생각하는 첫번째 가장자리는 "S"입니다, 그래서 우리는 노드 2
• 초 가장자리까지 여행 1
• 노드 # 2는 "i"이므로 노드 # 7을 검색하고이 노드는 색인을 텍스트에 저장합니다.

"si"의 두 번째 발생에 대해 ... 다음 하위 항목 # 7을 계속 검색합니까? 정말로 나에게 이해가되지 않는다.

또는 여러 인덱스를 지원하기 위해 트리를 다른 방식으로 조합해야합니까?

Answer 1

문제는 트리에 충분한 정보가 없다는 것입니다. 6 표시된 노드로 연결

경로 일본어 단어 모두 (일반적으로, 모든) 발생을 나타낸다. 알고리즘에서 설명한대로 접두어를 처리 할 때 노드에 색인을 저장하려고합니다. 일반적으로 말하자면 알고리즘은 그러한 정보를 저장하지 않지만이를 쉽게 수정합니다.

노드에 액세스 할 때마다 원래 문자열 내의 위치를 ​​일치 위치 목록에 추가하십시오.

1. (빈 트리)
2. (경로 "시", "6"노드에서 노드 "6"(추가 정보 : 4 ~ 5), 트리의 나머지)
3. 등
4. (경로 "si", 노드 "6"("6"노드의 추가 정보 : 4-5, 7-8), 나머지 트리)
5. 등