간단한 예제가있는 C++ 접미사 트리 라이브러리 사용 방법

Question

접미어 트리 라이브러리 (선형 시간 구성이 있음)를 찾고 있는데 찾은 것이 모두 PATL이지만 PATL에는 설명서가 없으므로 알아낼 수 없습니다. 어떤 예든지. 괜찮은 설명서가있는 C++ 용 접미어 트리 라이브러리가 있습니까?

PATL 홈 : http://code.google.com/p/patl/

편집 :
동기 부여 : 나는 문자열의 많은 양을 처리하고 자주 일반적인 문자열을 찾고, 어떤 문자열 이상 n 개의 발생이 t 초 이내에 발생한 경우보고해야합니다. 나는 트리를 구현했다. (노드에 카운터가있다. 실제로는 카운터가 아니지만 시간이 필요하다고 말한 이후의 방문 시간 벡터이다.)하지만 매우 느리다. 그래서 (문자열 사이에 무작위로 연결하여 문자열이 하나 이상의 문자열에 걸쳐 있지 않도록하기 위해) 특정 양의 메시지 (30 초의 가치가있는 데이터)를 작성한 다음 그 위에 접미어 트리를 작성한다고 생각했습니다. 끈.

Answer 1

Pizza&Chili project에 대한 구현을 살펴볼 수 있습니다. 접미어 트리가 없지만 접미어 배열과 다양한 압축 된 인덱스가 있습니다. 일반 (압축되지 않은) 접미어 배열은 접미어 트리가 아니어도 용도에 적합해야합니다.

는 (당신은 "인덱스 컬렉션"링크에서 다운로드 할 수있는 코드를 찾을 수 있습니다.)

Answer 2

는 문서와 다양한 검색 알고리즘과 데이터 구조의 고성능 구현을 제공 SeqAn 라이브러리를 살펴 보자.

예를 들어, suffix array 클래스는 접미어 트리의 드롭 인 대체품으로 사용할 수 있습니다.

그 외에도 문제는 본질적으로 복잡해 보입니다. 속도를 얼마나 높일 수 있는지 잘 모르겠습니다. 일반적인 문구에서는 다중 배열 NP 어려운 문제입니다. 정확한 서브 미션에만 관심이 있기 때문에 좀 더 다루기 쉬운 것으로 변환 할 수는 있지만 여전히 복잡합니다.