스트링 B-트리

우리는 전통적인 외부 메모리 데이터 구조와 문자열 매칭 데이터 구조 사이의 연결로 볼 수 있는 새로운 텍스트 인덱싱 데이터 구조, 스트링 B-트리를 소개합니다. 간단히 말해, 이는 B-트리와 패트리샤 트리를 결합하여 더 효율적인 검색 및 업데이트 작업을 위해 추가 포인터를 추가함으로써 만들어진 내부 노드 인덱스입니다. 결과적으로, 스트링 B-트리는 역파일, B-트리, 접두사 B-트리, 접미사 배열, 압축된 트라이 및 접미사 트리의 이론적 한계를 극복합니다. 스트링 B-트리는 B-트리와 동일한 최악의 성능을 가지지만, 무한 길이의 문자열을 처리하고 접미사 트리가 지원하는 것과 같은 훨씬 더 강력한 검색 작업을 수행합니다. 스트링 B-트리는 또한 주 메모리(RAM 모델)에서도 효과적이며, 동적 문자열 집합에서 온라인 접미사 트리 검색을 개선합니다. 데이터베이스 인덱싱 및 소프트웨어 중복 제거에도 성공적으로 적용될 수 있습니다.