원형 문자열을 접미어 트리와 함께 사용할 수 있습니까?

Question

원형 문자열을 접미어 트리와 함께 사용할 수 있습니까? 따라서 마지막 문자 다음에 목록의 첫 번째 문자가옵니다.

그렇다면이 접미어 트리 표현이 일반적인 접미어 트리와 어떻게 다릅니 까?

Answer 1

"사용"의 의미에 따라 다릅니다.

1) 첫째, 가장 직접적인 가능한 방법으로 질문을 해석, 길이 n의 원형 문자열 자체 매 n 문자를 반복 즉 무한 문자열을 고려하십시오. 그러한 객체는 절대로 끝나지 않으므로 접미사가 없기 때문에 접미사를 사용하지 않습니다.

2) 그러나, 확실히 아이디어는 우리가 처음에 마지막 문자에서 링크를 사용하는 원형 문자열의 유한 표현을 가지고있다. 유사한 방식으로, 우리는 순환 문자열의 모든 (무한히 긴) 접미사를 나타내는 순환 접미어 트리에 대한 링크를 사용하여 주어진 접미어 트리를 확장 할 수 있습니다. 이 은 모두 문자열의 접미사가 아니라 순환 문자열의 리프에서 오는 루트가 있기 때문에 각 리프의 링크를 노드의 루트에 삽입하여을 수행 할 수 없습니다. 단 하나의 나가는 가장자리가있을 수 있습니다. 예 : "mississippi $"의 접미사 "ssippi $"를 나타내는 잎은 무한 라벨 "mississippi $ mississippi $ mississippi $ ...."를 가지고 나가는 가장자리가 있어야하고 다른 가장자리는 없어야합니다. 나무의 뿌리에 그것을 연결했다면, 더 많은 잘못된 연속이있을 것입니다.

그래서 두 가지가 필요하다 : (재미있는 개념 결국입니다) 잎에서

• 보내는 가장자리. 각 잎은 하나의 나가는 가장자리를 얻습니다.
• 무한 라벨이있는 가장자리. 이 레이블은 원형 문자열로 표현 될 수 있습니다 (원형 문자열은 잎의 모든 나가는 모서리에 대해 동일합니다).

이렇게하면 원형 문자열의 모든 (무한한) 접미사를 올바르게 나타낼 수 있습니다.

3) 그 표현이 유용 할 지 모르겠다. 접미어 트리를 구성하는 목적이 부분 문자열 검색을 가능하게하는 것이면 원형 문자열의 유한 표현 (링크 포함하지 않음)을 자체에 연결하고이 접미어 트리를 구성하는 일반적인 트릭은 검색하는 하위 문자열을 제외하고는 충분합니다 그 자체가 n 문자보다 길다.

이 접미사 트리의 특정 다른 용도로 더 "무한"개념의 도입을 필요로주의하는 것도 중요하다. 예를 들어, 특정 애플리케이션의 경우, 그 노드에서 트리 노드의 문자 깊이 (즉, 루트로부터 특정 노드까지의 에지 라벨들의 결합 된 길이)를 저장할 필요가있을 수있다. 위에 제안 된 "순환 접미사 트리"에서 잎의 나가는 가장자리는 일종의 특별한 "한계 안에있는 잎"을 이끌어 낼 것이며 원형의 문자열을 레이블로 가지고 간다. 이러한 순환 문자열에 일치하는 쿼리는 깊이 정보를 저장하기 위해 해당 가장자리에 내부 노드가 없기 때문에 일치하는 깊이를 추적하는 특별한 방법이 필요합니다.

4)

주지만 나타내는 (1), (2) 또는 (3), 즉 의미에서 원형 스트링 접미사 트리들 중 적어도 하나 개의 공지 된 애플리케이션이 실제로 존재이 모두 상기 데 접미사 트리를 사용하여 전체 무한한 객체. 오히려, 순환 문자열의 유한 하위 문자열의 접미어 트리가 사전 식으로 최소 회전 인 의 문제를 해결하는 데 사용됩니다. 문제는 Wikipedia에 설명되어 있지만 거기에 나열된 솔루션에는 접미어 트리를 사용하는 솔루션이 포함되어 있지 않습니다. 그러나 Dan Gusfield는 해답을 섹션 7.13의 Algorithms on Strings, Trees and Sequences에 설명합니다.

길이 n의 문자열 S의 사전 식 최소 회전 집합을 원형 문자열의 첫 번째 길이 -n 하위 문자열 집합과 동일하게 생각하는 것이 좋습니다. 문제는 사전 편집 상 최소한의 컷오프 지점을 찾는 것과 같습니다. Gusfield는 문자열 SS $의 접미어 트리를 구성하여이를 해결하고 각 노드에서 사전 식으로 가장 작은 가장자리를 취하여 사전 식으로 가장 작은 컷오프 지점에 해당하는 노드에서 끝내서이 트리를 가로 지릅니다. (4) 보여줍니다으로 그 관심있는 사용의 종류 인 경우

그래서,이 원형 문자열의 맥락에서 접미사 나무의 특정 실제 "사용"은,하지만 난 확신입니다.

Answer 2

예 문자열의 길이가 유한 한 경우 원형 문자열을 저장할 수 있습니다.

단어 banban을 고려하자.

는 자바 프로그래밍 언어를 사용하여 접미사 나무의 깔끔한 구현을 찾을 수

다음

는

root -> b -> a -> n -> b -> a -> n -> $ 

        -> $ 

root -> a -> n -> b -> a -> n -> $ 

       -> $ 

root -> n -> b -> a -> n -> $ 

      -> $ 

달러 기호는 접미사의 종료가

편집 것을 나타내는 구조 here

편집 : 댓글 섹션에서 묻는 질문 :

"mississippi 문자열이 있는데 'pim'을 검색하려고하면 어떻게됩니까?"

pim은 mississippi의 접미사가 아니므로 검색이 실패합니다.

편집 : 그러나 PIM은 원형 문자열에 내가, 별도의 단어로 꼼꼼한 취급에 트라이에 추가해야합니다 너무

이 작업을 수행하기 위해서는 트라이에 추가 할 글로벌 확장 접미사 트라이를 형성합니다.

원래 단어 banban의 순환 문자열에 anb가 있다고 생각하십시오.

그래서 글로벌 증강 접미사 트라이은 다음과 같습니다

root -> b -> a -> n -> b -> a -> n -> $ (original word) 

      -> a -> n -> $ (original word) 

      -> $ (from anb) 

root -> a -> n -> b -> a -> n -> $ (original word) 

       -> $ (original word) 

       -> b -> $ (from anb) 

root -> n -> b -> a -> n -> $ (original word) 

       -> $ (from anb) 

      -> $ (original word) 

Answer 3

나는 당신이 염두에두고 다음과 같은 해결 방법으로,이 원하는 일에 대해 생각

: 당신은 원형의 접미사 배열을 가지고 있다면

문자열 인 경우, 이는 주로 문자열 내부의 오프셋 목록이므로 각 오프셋에서 시작된 시퀀스는 정렬 된 순서가됩니다.

이제는 ABCD를 래핑하여 만든 원형 문자열이 있다고 가정합니다. ABCDABC에 자체의 문자 중 하나를 제외한 모든 문자를 추가하여 형성된 문자열을 고려하십시오.이 문자열에서 접미어 배열을 작성하면 어떻게됩니까? 순환 문자열 (ABCD BCDA CDAB DABC)의 모든 시퀀스는 ABCDABC 내부에 나타나므로 접미어 배열을 작성할 때 순환 문자 열에서 작성한 것과 같은 접미사 배열을 얻습니다. 일부 시퀀스에는 문자가 붙어 있습니다. 끝 (ABCD 대신 ABCDABC)과 너무 짧은 일부 추가 시퀀스 (ABC). 서브 시퀀스의 길이를 보거나 ABCDABC 내의 시작 위치를 보아도이 두 경우를 모두 인식 할 수 있습니다.

확실히, 당신은 mississippississipp 내의 pim을 찾을 수 있습니다.