Full-Text Index 자료구조들의 비교 분석

Abstract

텍스트 인덱스 자료구조는 주어진 문자열에 대하여 문자열을 가능한 작게 압축하여 저장하는 동시에 패턴 검색과 추출을 처리하는 자료구조를 말한다. 최근 텍스트 데이터의 크기가 나날이 커져감에 따라 대용량 텍스트 데이터의 공간 효율적인 인덱스 자료구조 구축의 중요성이 커지고 있다. 그에 따라 인덱스 자료구조에 대한 다양한 연구들이 진행되었다. 제안된 대표적인 텍스트 인덱스 자료구조로는 FM-Index와 Compressed Suffix Array(CSA), Compressed Suffix Tree(CST), 그리고 Lempel-Ziv 압축 알고리즘을 기반으로 인덱스를 구축하는 LZ-Index등이 있다. 본 논문에서는 첫 번째로 다양한 텍스트 데이터에 대해 인덱스 구축 시간, 인덱스 크기, 메모리 사용량, 패턴 검색 및 추출 시간을 측정하는 실험을 통해 인덱스 자료구조들의 실제 성능을 비교 분석한다. 두 번째로 앞의 분석 결과 압축률이 상대적으로 좋은 FM-Index에 대해 알파벳 사이즈가 작은 경우 압축률을 개선할 수 있는 방법을 알아본다. 실험 결과, 공간 효율적인 인덱스 구축 측면에서 일반 텍스트 데이터는 FM-Index가, 고반복 텍스트 데이터는 LZ-Index가 가장 작은 인덱스를 구축했다.