지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학위논문
- 저자정보
- 발행연도
- 2018
- 저작권
- 서울대학교 논문은 저작권에 의해 보호받습니다.
이용수0
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
텍스트 인덱스 자료구조는 주어진 문자열에 대하여 문자열을 가능한 작게 압축하여 저장하는 동시에 패턴 검색과 추출을 처리하는 자료구조를 말한다. 최근 텍스트 데이터의 크기가 나날이 커져감에 따라 대용량 텍스트 데이터의 공간 효율적인 인덱스 자료구조 구축의 중요성이 커지고 있다. 그에 따라 인덱스 자료구조에 대한 다양한 연구들이 진행되었다. 제안된 대표적인 텍스트 인덱스 자료구조로는 FM-Index와 Compressed Suffix Array(CSA), Compressed Suffix Tree(CST), 그리고 Lempel-Ziv 압축 알고리즘을 기반으로 인덱스를 구축하는 LZ-Index등이 있다.
본 논문에서는 첫 번째로 다양한 텍스트 데이터에 대해 인덱스 구축 시간, 인덱스 크기, 메모리 사용량, 패턴 검색 및 추출 시간을 측정하는 실험을 통해 인덱스 자료구조들의 실제 성능을 비교 분석한다. 두 번째로 앞의 분석 결과 압축률이 상대적으로 좋은 FM-Index에 대해 알파벳 사이즈가 작은 경우 압축률을 개선할 수 있는 방법을 알아본다. 실험 결과, 공간 효율적인 인덱스 구축 측면에서 일반 텍스트 데이터는 FM-Index가, 고반복 텍스트 데이터는 LZ-Index가 가장 작은 인덱스를 구축했다.
본 논문에서는 첫 번째로 다양한 텍스트 데이터에 대해 인덱스 구축 시간, 인덱스 크기, 메모리 사용량, 패턴 검색 및 추출 시간을 측정하는 실험을 통해 인덱스 자료구조들의 실제 성능을 비교 분석한다. 두 번째로 앞의 분석 결과 압축률이 상대적으로 좋은 FM-Index에 대해 알파벳 사이즈가 작은 경우 압축률을 개선할 수 있는 방법을 알아본다. 실험 결과, 공간 효율적인 인덱스 구축 측면에서 일반 텍스트 데이터는 FM-Index가, 고반복 텍스트 데이터는 LZ-Index가 가장 작은 인덱스를 구축했다.
목차
1. 서론 12. 사전지식 및 실험 데이터 42.1 실험 데이터 42.2 버로우즈-휠러 변환 52.3 Rank/Select 질의 72.4 웨이블릿 트리 83. 대표적인 Full-Text Index 자료구조 113.1 FM-Index 113.2 Compressed Suffix Array 133.3 Compressed Suffix Tree 153.4 Lempel-Ziv 압축 알고리즘을 이용한 Index 자료구조 163.4.1 Lempel-Ziv 압축 알고리즘 163.4.2 LZ-Index 184. 실험 결과 및 분석 204.1 인덱스 구축 시간 비교 204.2 인덱스 크기 비교 224.3 메모리 사용량 비교 244.4 패턴 검색 시간 비교 254.5 문자열 추출 시간 비교 284.6 실험 결과 분석 295. 알파벳 사이즈가 작은 경우 FM-Index 압축률 향상법 306. 결론 35참고문헌 36Abstract 39
최근 본 자료
댓글(0)
0