압축 데이터 구조

압축 데이터 구조라는 용어는 알고리즘, 데이터 구조, 이론 컴퓨터 과학의 컴퓨터 과학 하위 영역에서 발생한다.그것은 그 문제에 대한 전통적인 데이터 구조의 운영 속도만큼 대략적으로 빠르지만 그 크기가 실질적으로 더 작을 수 있는 데이터 구조를 말한다.압축된 데이터 구조의 크기는 대표되는 데이터의 엔트로피에 따라 일반적으로 크게 좌우된다.

압축된 데이터 구조의 중요한 예로는 압축된 접미사^[1][2] 배열과 FM-색인이 있는데,^[3] 두 가지 모두 패턴 일치를 위한 문자 T의 임의 텍스트를 나타낼 수 있다.입력 패턴 P가 있으면 T에 P가 표시되는지 여부와 위치를 찾는 작업을 지원한다.검색 시간은 텍스트 T 길이의 매우 느리게 성장하는 함수인 패턴 P의 길이와 보고된 일치 수를 합한 것에 비례한다.이들이 차지하는 공간은 부분 일치 또는 gzip에 의한 예측과 같이 엔트로피 압축 형태의 텍스트 T 크기와 대략 같다.더욱이, 두 데이터 구조 모두 임의의 접근 방식으로 텍스트 T를 재구성할 수 있다는 점에서 자체 색인화 되어 있어, 기초 텍스트 T는 폐기될 수 있다.즉, 그들은 동시에 텍스트 T의 압축적이고 검색 가능한 표현을 제공한다.그것들은 T의 크기보다 몇 배 더 많은 공간을 차지하는 기존의 접미사 나무와 접미사 배열보다 상당한 공간 개선을 나타낸다.또한 단어 기반 검색만 지원할 수 있는 반전 인덱스와는 달리 임의 패턴 검색도 지원한다.또한 반전된 인덱스는 자체 인덱스 기능이 없다.

중요한 관련 개념은 간결한 데이터 구조의 개념으로, 정보-이론적 최소값과 거의 동일한 공간을 사용하며, 이는 데이터를 나타내기 위해 필요한 공간에 대한 최악의 개념이다.이와는 대조적으로 압축된 데이터 구조의 크기는 표현되는 특정 데이터에 따라 달라진다.자연어 텍스트의 경우처럼 데이터가 압축 가능한 경우, 압축된 데이터 구조는 정보-이론적 최소치에 매우 가까운 공간을 차지할 수 있으며 대부분의 압축 방식보다 훨씬 적은 공간을 차지할 수 있다.^{[example needed][citation needed]}

참조