접미어 트리에서 부분 문자열을 제거하는 방법은 무엇입니까?

Question

많은 문헌을 검토했지만 접미사 트리에 삭제 또는 삽입 하위 문자열에 대한 정보를 찾지 못했습니다. Ukkonen 또는 McCreight의 나무 건축 알고리즘 만 있습니다.
가장 가난한 방법은 부분 문자열을 삭제하거나 삽입 한 후 트리를 다시 작성하는 것입니다. 그러나 나는 그것이 최선의 방법이라고 생각합니다.
예 : (위치는 0에서부터 계산됩니다.)
"abcdef"가있는 접미어 트리가 있으며 1에서 3까지의 기호를 삭제해야합니다. 그런 다음 "aef"가있는 접미어 트리를 갖습니다. 그런 다음 위치 1 문자열에서 'as'를 추가해야합니다. 그리고 이것 후에 나는 "aasef"와 함께 접미사 나무를 가질 것이다. 도와 주시겠습니까?

Answer 1

질문에 두 가지 작업이 혼합되어 있으면 먼저 문자를 검색하고 두 번째 문자를 바꾸십시오. Suffix tree는 첫 번째 부분에서 문자를 검색합니다. 이제 문자를 새 문자로 바꾸는 두 번째 알고리즘이 필요합니다. 문자가 대체되면 원본 접미사 트리가 무효화되므로 트리를 다시 매핑하여 두 번째 대체 작업을 수행해야합니다.

당신이 필요로하는 것은 두 가지입니다. 첫 번째 "접미사 배열"은 문자와 그 위치 검색에 대한 제어력을 제고하고, 두 번째는 "캐시 알고리즘"으로 교체에 도움이 될 것입니다.

Answer 2

난 단지 접미어 트리 작업을 시작 했으므로 틀릴 수도 있지만 삽입이나 삭제로 인해 트리가 상당히 바뀔 수 있습니다. 'A는 처음에 매우 용이하다

abcdef 
├a..$ 
├b..$ 
├c..$ 
├d..$ 
├e..$ 
└f$ 

끝에'g '를 추가 또는 삭제 :

는 "ABCDEF는"정말 사소한 접미사 트리입니다.

그러나 우리가 밀어 말하는 또 다른 'A'중간 :

우리는 돌아가서 우리는이에 따라 노드를 삽입 할 필요가 있는지 확인하기 위해 처음부터 모든 편지를 확인해야

abcadef 
├a 
│├b..$ 
│└d..$ 
├b 
├c 
├... 

. 이제 끝으로 "EF"같은 것을 삽입 한 경우

abafef 
├a 
│├bafef$ 
│└fef$ 
├bafef$ 
├f 
│├ef$ 
│└$ 
└ef$ 

, 당신은 통과하고 사방에 새로운 노드를 추가해야 할 것 : 우리가 끝에서 문자가있는 경우 동일!

문자열을 삽입하면 문자열의 모든 문자 즉 선형 시간을 다시 검사하는 것처럼 보입니다. Ukkonen의 알고리즘은 이미 선형 시간을 필요로하기 때문에 동적 인 삽입 알고리즘을 사용할 가치가 없어야합니다. 매번 처음부터 트리를 재생성해야합니다.

공간에 신경 쓰지 않는다면 트리 생성 알고리즘의 각 단계를 항상 캐싱 할 수 있습니다. 그런 다음 x 점에서 삽입 또는 삭제할 시간이되면 x 점까지 구성된 트리를로드하십시오 .