델타 부호화
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
델타 부호화는 두 데이터 소스의 차이를 델타(차분) 형태로 표현하여 데이터 압축을 수행하는 기법이다. 대칭 델타와 지향 델타 방식으로 정의되며, 증분 부호화는 델타 부호화의 변형이다. 이 기술은 데이터의 변동이 작거나 일정할 때 효과적이며, 통신 채널에서 파일의 변경된 부분만 전송하는 데 사용될 수 있다. 델타 부호화는 HTTP 델타 부호화, 델타 복사, 델타 업데이트 등 다양한 분야에서 활용되며, rsync, VCDIFF, bsdiff, Git과 같은 관련 도구 및 표준이 존재한다.
델타 부호화는 두 데이터 소스 간의 차이점을 델타(또는 차분) 형태로 표현하는 데이터 압축 기법이다. 델타는 대칭 델타와 지향 델타 두 가지 방식으로 정의할 수 있다.
델타 부호화는 데이터의 변동이 작거나 일정할 때 가장 효과적이다. 정렬되지 않은 데이터 집합에서는 압축 효과가 미미할 수 있다.
2. 정의
가장 단순한 예시는 순차적인 값 간의 차이를 저장하는 것이다. 예를 들어 2, 4, 6, 9, 7이라는 값의 열이 있을 때, 2, 2, 2, 3, -2를 저장한다. 순서가 있는 값이 자주 나타나는 데이터에서는 더 압축하기 쉬워진다. IFF 8SVX 음성 파일 포맷은 이러한 부호화를 수행한 다음 압축한다. 단, 양자화 비트 수(비트 심도 (음향 장비)) 8비트의 음성 표본 값에서는 차분 부호화가 항상 효율적인 것은 아니며, 16비트 이상에서는 더욱 효과가 떨어진다. 따라서 압축 알고리즘에서는 차분 부호화에 의해 효율이 향상되는 경우에만 차분 부호화를 선택하는 경우가 많다. 동영상 프레임에 차분 부호화를 적용하면 효과가 크며, 거의 모든 동영상 압축 코덱에 사용되고 있다.
논리적으로 볼 때, 두 데이터의 차분이 있으면 한쪽 데이터에서 다른 쪽 데이터를 얻을 수 있다. 어떤 동치 관계에서 같은 값의 차분은 ''0'' 또는 영원이라고 한다. 좋은 차분은 한쪽 데이터가 없을 때 극소 원이거나 다의적이다.
차분 부호화는 데이터의 변화가 작고 일정한 경우에 가장 효율이 좋다. 정렬되지 않고 흩어져 있는 데이터에서는 압축 효율이 작다.
C 언어를 이용한 간단한 차분 부호화/복호화 예시는 다음과 같다.
void delta_encode(char *buffer, int length)
{
char t = 0;
char original;
int i;
for (i=0; i < length; ++i) {
original = buffer[i];
buffer[i] -= t;
t = original;
}
}
void delta_decode(char *buffer, int length)
{
char t = 0;
int i;
for (i=0; i < length; ++i) {
buffer[i] += t;
t = buffer[i];
}
}
차분 부호화는 HTTP 서버가 업데이트된 웹 페이지를 이전 버전과의 차분 형태로 전송하는 데 사용될 수 있다. 이는 인터넷 트래픽을 줄이는 데 도움이 된다.
2. 1. 대칭 델타
두 버전 v1과 v2 간의 차이는 집합 연산을 통해 표현된다. 이 수식은 다음과 같다.
:
2. 2. 지향 델타
지향 델타는 변경이라고도 하며, 한 버전 에 적용하면 다른 버전 를 생성하는 (기본적인) 변경 연산의 순서이다. 이는 데이터베이스의 트랜잭션 로그와 유사하다. 컴퓨터 구현에서는 일반적으로 'v1에서 데이터 복사'와 '리터럴 데이터 쓰기'라는 두 가지 명령어를 가진 언어의 형태를 띤다.
2. 3. 변형: 증분 부호화
접두사 또는 접미사의 차이를 부호화하는 것을 증분 부호화라고 한다. 이는 사전의 단어 목록과 같이 문자열 간의 차이가 적은 정렬된 목록에 특히 효과적이다. 하지만 한국어 사전에서는 한자가 있기 때문에 반드시 효율적이라고 할 수 없다.
3. 작동 원리
파일의 단일 사본만 사용할 수 있는 네트워크를 통해 델타 부호화를 전송할 때는 이전 버전 이후 파일의 어떤 부분이 변경되었는지 감지하기 위해 특수한 오류 제어 코드가 사용된다. 예를 들어, rsync는 Mark Adler의 adler-32 체크섬을 기반으로 하는 롤링 체크섬 알고리즘을 사용한다.
차분에는 "대칭 차분(symmetric delta)"과 "방향적 차분(directed delta)"이 있다. 대칭 차분은 다음과 같이 표현된다.
: ''v''1과 ''v''2는 두 개의 연속적인 버전을 나타낸다.
방향적 차분은 (기본적인) 변경 연산의 순서이며, 이를 ''v''1에 적용함으로써 ''v''2라는 다음 버전을 얻을 수 있게 되어 있다. 이는 데이터베이스의 트랜잭션 로그와도 비슷하다.
문자열의 접두부나 접미부의 차분을 부호화하는 차분 부호화를 증분 부호화 (Incremental encoding)라고 부른다. 이는 예를 들어 사전에 게재된 단어 목록처럼, 정렬되어 있고 앞뒤 문자열과의 차이가 작은 목록에 적용하면 효과적이다 (한국어 사전에서는 한자가 있기 때문에 반드시 효율적이라고 할 수 없다).
3. 1. 예시: 단순 델타 부호화
델타 부호화의 가장 간단한 예는 연속적인 값 간의 차이(델타)를 저장하는 방식이다. 예를 들어 2, 4, 6, 9, 7이라는 값이 있다면, 2, 2, 2, 3, -2로 저장한다. 이 방식은 이웃한 샘플 간의 상관관계가 높을 때 데이터의 분산 (범위)을 줄여 압축 효율을 높이는 데 기여한다.
IFF 8SVX 사운드 형식은 압축 전에 원시 사운드 데이터에 이 방식을 적용한다. 비디오 압축에서 델타 프레임은 프레임 크기를 줄이는 데 크게 기여하며, 거의 모든 비디오 압축 코덱에서 사용된다.
다음은 단순한 델타 부호화 및 복호화를 수행하는 C 언어 코드 예시다.
```c
void delta_encode(unsigned char *buffer, int length)
{
unsigned char last = 0;
for (int i = 0; i < length; i++)
{
unsigned char current = buffer[i];
buffer[i] = current - last;
last = current;
}
}
void delta_decode(unsigned char *buffer, int length)
{
unsigned char last = 0;
for (int i = 0; i < length; i++)
{
unsigned char delta = buffer[i];
buffer[i] = delta + last;
last = buffer[i];
}
}
3. 2. 샘플 C 코드
c
void delta_encode(unsigned char *buffer, int length)
{
unsigned char last = 0;
for (int i = 0; i < length; i++)
{
unsigned char current = buffer[i];
buffer[i] = current - last;
last = current;
}
}
void delta_decode(unsigned char *buffer, int length)
{
unsigned char last = 0;
for (int i = 0; i < length; i++)
{
unsigned char delta = buffer[i];
buffer[i] = delta + last;
last = buffer[i];
}
}
```
다음은 C 코드로, 문자 시퀀스에 대한 델타 부호화 및 복호화를 수행하는 간단한 형태를 보여준다.
4. 활용 사례
델타 부호화는 데이터의 중복성을 줄여 데이터 전송량과 저장 공간을 절약하는 데 기여한다.
예를 들어, 유닉스 파일 비교 유틸리티인 diff는 변경된 부분("차분" 또는 "델타")을 별도 파일로 기록한다. 이 차분 파일은 원본 파일보다 크기가 작아 여러 버전의 파일을 보관할 때 저장 공간을 절약할 수 있다.
논리적으로 두 데이터의 차분이 있으면 한쪽 데이터에서 다른 쪽 데이터를 얻을 수 있다. 동치 관계에서 같은 값의 차분은 '0' 또는 영원으로 표현된다.
가장 단순한 예로, 순차적인 값의 차이를 저장하는 방식이 있다. 예를 들어 2, 4, 6, 9, 7이라는 값은 2, 2, 2, 3, -2로 저장된다. 이 방식은 정렬된 데이터에서 압축 효율을 높이며, 8SVX 음성 파일 포맷 등에 사용된다. 그러나 양자화 비트 수가 낮은 경우에는 효과가 떨어질 수 있다.
차분에는 "대칭 차분"과 "방향적 차분"이 있다. 대칭 차분은 두 버전의 차이 집합의 합집합으로 표현된다. 방향적 차분은 데이터베이스의 트랜잭션 로그처럼 변경 연산의 순서로 표현된다.
문자열의 앞부분이나 뒷부분의 차이를 부호화하는 것을 증분 부호화라고 하며, 정렬된 문자열 목록에 효과적이다.
네트워크로 연결된 두 시스템에서 파일 변경을 감지하기 위해 델타 부호화와 오류 제어 부호를 함께 사용하기도 한다.
델타 부호화는 데이터 변화가 작고 일정할 때 가장 효율적이다. 정렬되지 않은 데이터에서는 압축 효율이 낮다.
아래는 단순한 델타 부호화 및 복호화 C 언어 코드 예시이다.
```c
void delta_encode(char *buffer, int length)
{
char t = 0;
char original;
int i;
for (i=0; i < length; ++i) {
original = buffer[i];
buffer[i] -= t;
t = original;
}
}
void delta_decode(char *buffer, int length)
{
char t = 0;
int i;
for (i=0; i < length; ++i) {
buffer[i] += t;
t = buffer[i];
}
}
4. 1. HTTP 델타 부호화 (RFC 3229)
https://datatracker.ietf.org/doc/html/rfc3229 RFC 3229 "HTTP에서의 델타 부호화"는 HTTP 서버가 웹 페이지를 업데이트할 때, 이전 버전과의 차이점(델타)만 전송하여 인터넷 트래픽을 줄이는 방법을 제안한다.[1] 이는 대부분의 웹 페이지가 시간이 지남에 따라 조금씩 변경되기 때문에, 전체 페이지를 다시 보내는 것보다 효율적이다.이 문서는 델타 부호화가 HTTP/1.1의 호환 가능한 확장으로 어떻게 지원될 수 있는지 설명한다. 많은 HTTP 요청은 클라이언트가 이미 가지고 있는 리소스의 약간 수정된 버전을 가져오게 한다. 연구에 따르면 이러한 수정은 자주 발생하며, 실제 내용보다 훨씬 작다. 이 경우, HTTP는 전체 새 리소스 대신 변경 사항에 대한 최소한의 설명만 전송하여 네트워크 대역폭을 더 효율적으로 사용할 수 있다.
제안된 rsync 기반 프레임워크는 ''rproxy''라는 HTTP 프록시 쌍 시스템에 구현되었다.[1] 그러나 이 시스템은 기본 vcdiff 기반 구현과 마찬가지로 거의 사용되지 않는다.
4. 2. 델타 복사
델타 복사는 파일의 변경된 부분만 복사하는 방식이다. 주로 백업 및 파일 복사 소프트웨어에서 사용되며, 네트워크를 통해 파일을 복사할 때 대역폭을 절약하는 데 유용하다. 이전 버전의 파일이 대상 위치에 이미 존재하는 경우에 특히 효과적이다.rsync는 델타 복사를 활용하는 대표적인 오픈 소스 도구이다.[2][3][4] 유닉스의 파일 비교 유틸리티인 diff처럼 변경 사항을 "차분" 또는 "델타" 형태로 만들어 별도 파일로 기록한다. 이 차분 파일은 원본 파일보다 크기가 작아 여러 버전의 파일을 보관할 때 저장 공간을 절약할 수 있다.
두 데이터 간의 차분을 통해 한쪽 데이터에서 다른 쪽 데이터를 얻을 수 있다는 것이 델타 복사의 논리적 기반이다. 이때 동일한 값의 차분은 '0' 또는 영원으로 표현된다.
순차적인 값 간의 차이를 이용해 바이트 열을 저장하는 것은 델타 복사의 간단한 예시이다. 예를 들어 2, 4, 6, 9, 7이라는 값이 있다면, 2, 2, 2, 3, -2로 저장한다. 이 방식은 정렬된 데이터에서 압축 효율을 높인다.
3229 "HTTP에서의 델타 부호화"는 HTTP 서버가 업데이트된 웹 페이지를 이전 버전과의 차분 형태로 전송하여 인터넷 트래픽을 줄이는 방법을 제안한다. 이는 웹 페이지가 조금씩 수정되는 경향이 있다는 점에 착안한 것이다.
4. 2. 1. 온라인 백업
많은 온라인 백업 서비스는 사용자가 이전 백업에서 동일한 파일의 이전 버전을 제공하기 위해 델타 부호화 방법을 사용하며, 이를 단순히 "델타"라고 부르는 경우가 많다. 이는 저장해야 하는 데이터의 양뿐만 아니라, 변경된 각 파일 버전 전체를 사용자가 접근할 수 있도록 제공해야 하기 때문에 발생하는 비용을 줄여준다. 또한 업데이트된 각 파일을 업로드(및 때로는 다운로드)하는 비용도 절감해준다(전체 파일 대신 더 작은 델타만 사용해야 하므로).[1]4. 3. 델타 업데이트
대규모 소프트웨어 패키지의 경우 버전 간에 변경되는 데이터가 거의 없는 경우가 많다. 많은 공급업체는 시간과 대역폭을 절약하기 위해 델타 전송을 사용한다. 예를 들어, 유닉스 파일 비교 유틸리티인 diff 등에서 "차분" 또는 "델타"를 생성하여 개별 파일로 기록하는데, 차분은 일반적으로 원본 파일보다 작으므로, 차분 부호화를 통해 데이터의 중복성을 대폭 줄일 수 있다. 일련의 차분 파일은 각 버전의 원본 파일 묶음보다 훨씬 기록 용량을 절약할 수 있다.4. 4. 이진 델타 압축
델타 부호화의 한 종류인 이진 델타 압축은 실행 파일처럼 포인터 주소 변경이 많은 파일에 효과적인 압축 방식이다. 유닉스의 파일 비교 유틸리티인 diff는 "차분" 또는 "델타"를 생성하여 개별 파일로 기록하는데, 이 차분은 일반적으로 원본 파일보다 크기가 작아 데이터 중복성을 줄일 수 있다. 일련의 차분 파일은 각 버전의 원본 파일 묶음보다 훨씬 적은 용량을 차지한다.bsdiff와 같은 도구가 이진 델타 압축 방식을 사용한다.
5. 관련 도구 및 표준
- 차분 및 패치
- VCDIFF
- rsync: 파일 동기화 및 델타 복사를 위한 도구로, VCDIFF와 함께 델타 부호화를 활용하며, xdelta와 함께 널리 사용된다.[1]
- xdelta: VCDIFF의 자유 소프트웨어 구현 중 하나이다.[1]
- Git: 소스 코드 관리 시스템으로, 델타 압축을 사용한다.
- bsdiff: 접미사 배열을 사용하여 이진 차분을 수행하는 프로그램이다.
5. 1. Diff/Patch
Diff는 주로 텍스트 파일에 사용되는 파일 비교 프로그램이다. 기본적으로 되돌릴 수 있는 대칭 델타를 생성한다. 소프트웨어 패치에 사용되는 두 가지 형식인 '컨텍스트'와 '통합'은 줄 번호의 변경을 허용하는 추가적인 컨텍스트 라인을 제공한다.5. 2. VCDIFF (RFC 3284)
VCDIFF는 [https://datatracker.ietf.org/doc/html/rfc3284 RFC 3284]에 설명된 델타 부호화의 일반적인 형식 중 하나이다.[1] 자유 소프트웨어 구현에는 Xdelta 및 open-vcdiff가 있다.[1]5. 3. GDIFF
GDIFF(제네릭 델타 형식)는 또 다른 지향적 델타 부호화 형식이다. 1997년 W3C에 제출되었다.[7] 많은 경우, VCDIFF가 GDIFF보다 압축률이 더 좋다.5. 4. rsync
차분 및 패치와 유사한 기능을 제공하며, 파일 동기화 및 델타 복사를 위한 도구로 사용된다.[1] VCDIFF(The VCDIFF Generic Differencing and Compression Data Format|VCDIFF 일반 차분 및 압축 데이터 형식영어)와 함께 델타 부호화를 활용하는 대표적인 도구이다.[1] xdelta와 함께 널리 사용된다.[1]5. 5. xdelta
VCDIFF는 [https://datatracker.ietf.org/doc/html/rfc3284 RFC 3284]에 설명된 델타 부호화의 일반적인 형식 중 하나이다. Xdelta는 VCDIFF의 자유 소프트웨어 구현 중 하나이다.5. 6. Git
Git 소스 코드 관리 시스템은 "[http://git-scm.com/docs/git-repack git repack]" 작업에서 델타 압축을 사용한다. 아직 델타 압축되지 않은 저장소의 객체("느슨한 객체"(loose objects))는 모든 다른 객체의 휴리스틱하게 선택된 하위 집합과 비교되며, 공통 데이터와 차이점은 "팩 파일"로 연결된 다음 기존 방법으로 압축된다. 소스 또는 데이터 파일이 커밋 간에 점진적으로 변경되는 일반적인 사용 사례에서 이는 상당한 공간 절약을 가져올 수 있다. 리팩 작업은 일반적으로 "git gc"[5] 프로세스의 일부로 수행되며, 느슨한 객체 또는 팩 파일의 수가 구성된 임계값을 초과하면 자동으로 트리거된다.형식은 Git 설명서의 팩 형식 페이지에 문서화되어 있으며, 방향 델타를 구현한다.[6]
5. 7. bsdiff
Bsdiff는 접미사 배열을 사용하여 이진 차분을 수행하는 프로그램이다. 포인터 주소의 변경 사항이 많은 실행 파일의 경우, VCDIFF 유형의 "복사 및 리터럴" 인코딩보다 성능이 더 뛰어나다. 이 프로그램의 목적은 어셈블리 코드를 구문 분석할 필요 없이(구글의 Courgette와 같이) 작은 차분을 생성하는 방법을 찾는 것이다. Bsdiff는 오류가 있는 "복사" 일치를 허용하여 이를 달성하며, 바이트 단위 차이의 추가 "add" 배열을 사용하여 수정한다. 이 배열은 오프셋 변경에 대해 대부분 0 또는 반복 값으로 구성되므로 압축 후 공간을 거의 차지하지 않는다.[8]Bsdiff는 델타 업데이트에 유용하다. 구글은 크롬(Chromium)과 안드로이드(Android)에서 bsdiff를 사용한다. RPM 패키지 관리자의 ''deltarpm'' 기능은 일치를 위해 해시 테이블을 사용할 수 있는, 크게 수정된 bsdiff를 기반으로 한다.[9] FreeBSD 역시 업데이트에 bsdiff를 사용한다.[10]
2005년 bsdiff 4.3 릴리스 이후, 다양한 개선 사항이나 수정 사항이 적용되었다. 구글은 각 제품에 대해 여러 버전의 코드를 유지 관리한다.[11] FreeBSD는 구글의 호환 변경 사항 중 많은 부분을 적용했는데, 주로 취약점 수정과 더 빠른 divsufsort영어 접미사 정렬 루틴으로의 전환이다.[12] 데비안은 프로그램에 일련의 성능 조정을 적용했다.[13]
''ddelta''는 데비안의 델타 업데이트에 사용하기 위해 제안된 bsdiff의 재작성 버전이다. 다른 효율성 개선 사항 중에서도 슬라이딩 윈도우를 사용하여 메모리 및 CPU 비용을 줄인다.[14]
참조
[1]
웹사이트
rproxy: introduction
https://rproxy.samba[...]
[2]
웹사이트
Feature request: Delta copying - 2BrightSparks
https://web.archive.[...]
2016-04-29
[3]
웹사이트
"Bvckup 2 | Forum | How delta copying works"
https://www.bvckup2.[...]
[4]
웹사이트
delta-copying.aspx
http://www.eggheadca[...]
[5]
웹사이트
Git - git-gc Documentation
https://git-scm.com/[...]
2024-11-09
[6]
웹사이트
Git - pack-format Documentation
https://git-scm.com/[...]
2020-01-13
[7]
웹사이트
Generic Diff Format Specification
https://www.w3.org/T[...]
[8]
웹사이트
Binary diff
http://www.daemonolo[...]
2024-11-09
[9]
웹사이트
rpmdelta/delta.c
https://github.com/r[...]
rpm-software-management
2019-07-03
[10]
웹사이트
NON-CRYPTANALYTIC ATTACKS AGAINST FREEBSD UPDATE COMPONENTS
https://gist.github.[...]
2016-05
[11]
웹사이트
xtraeme/bsdiff-chromium: README.chromium
https://github.com/x[...]
2012
[12]
웹사이트
History for freebsd/usr.bin/bsdiff
https://github.com/f[...]
[13]
웹사이트
Package: bsdiff
https://sources.debi[...]
[14]
웹사이트
julian-klode/ddelta
https://github.com/j[...]
2020-01-13
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com