증분 인코딩

증분 인코딩은 델타 인코딩 압축 알고리즘의 일종으로, 공통 접두사 또는 접미사와 그 길이가 중복되지 않도록 기록된다.이 알고리즘은 특히 사전의 단어 목록과 같이 정렬된 데이터를 압축하는 데 적합하다.

예를 들면 다음과 같다.

myxa myxophyta myxopod 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발 나발

앞의 단어 'myx' 'myxop' no no common prefix 'nabb' 'nabb' 'nab' 'nab' 'na' 'nac'

0 myxa 3 ophyta 5 od 0 ab 3 bed 4 in 3 it 3 k 3 ob 2 carat 3 ele

공통 접두사 길이 저장에 사용되는 인코딩은 어플리케이션마다 다르다.대표적인 기법으로는 값을 단일 바이트로 저장하는 것, 공통 접두사 길이의 변화만 저장하는 델타 인코딩, 그리고 다양한 범용 코드 등이 있다.나머지 접미사를 압축하기 위해 엔트로피 인코딩 및 사전 코더와 같은 다른 일반적인 무손실 데이터 압축 기법과 결합할 수 있다.

적용들

증분 인코딩은 검색 색인에 사용되는 어휘를 압축하기 위해 정보 검색에 널리 사용된다. 이는 모든 문서에서 발견된 모든 단어와 각 단어마다 위치 목록으로 포인터를 표시한다.전형적으로 이 지수를 ^[1]약 40% 압축한다.

하나의 예로서, 증분 인코딩은 파일 이름 및 디렉토리 색인에서 GNU locate 유틸리티에 의해 시작점으로 사용된다.GNU locate 유틸리티는 널리 사용되는 파일 경로 접두사를 더욱 줄이기 위해 bigram 인코딩을 추가로 사용한다.

참조

이 컴퓨터 데이터 저장 관련 소프트웨어 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t