델타 부호화

Delta encoding

델타 인코딩은 완전한 파일이 아닌 순차 데이터 간의 차이(델타) 형태로 데이터를 저장하거나 전송하는 방법입니다. 더 일반적으로 이를 데이터 차이 렌싱이라고 합니다.델타 부호화는 델타 압축이라고 불리기도 합니다.특히 변경의 아카이브 이력이 필요한 경우(리비전 제어 소프트웨어 등).

차이는 "deltas" 또는 "diffs"라고 불리는 개별 파일에 기록됩니다.큰 문서에서 몇 개의 단어를 변경하거나 큰 표에서 몇 개의 레코드를 변경하는 등 차이가 작은 상황에서는 델타 인코딩을 통해 데이터의 용장성이 크게 감소합니다.고유한 델타 컬렉션은 인코딩되지 않은 동등한 델타 컬렉션보다 훨씬 공간 효율적입니다.

논리적 관점에서 두 데이터 값의 차이는 다른 값에서 한 값을 얻는 데 필요한 정보입니다. 상대 엔트로피를 참조하십시오.동일한 값 사이의 차이(일부 동등성 이하)를 종종 0 또는 중성 원소라고 합니다.

간단한 예

가장 간단한 예는 바이트 값을 값 자체가 아니라 순차 값 간의 차이(델타)로 저장하는 것입니다.2, 4, 6, 9, 7 대신 2, 2, 3, -2를 저장합니다.이것에 의해, 네이버샘플이 상관하고 있는 경우의 값의 분산(범위)이 감소해, 같은 데이터의 비트 사용율이 낮아집니다.IFF 8SVX 사운드 포맷은 압축을 적용하기 전에 원시 사운드 데이터에 이 인코딩을 적용합니다.안타깝게도 모든 8비트 사운드샘플이 델타 부호화 시 더 잘 압축되는 것은 아니며, 16비트 이상의 샘플에서는 델타 부호화의 사용성이 더 작습니다.따라서 압축 알고리즘은 압축이 없는 것보다 나은 경우에만 델타 인코딩을 선택하는 경우가 많습니다.단, 비디오 압축에서는 델타 프레임은 프레임사이즈를 대폭 줄일 수 있으며 거의 모든 비디오 압축 코덱에서 사용됩니다.

정의.

델타는 대칭델타와 방향델타2가지 방법으로 정의할 수 있습니다.대칭 델타는 다음과 같이 나타낼 수 있다.

두 가지 버전을 나타냅니다.

directed delta(변경이라고도 함)는 (초급) 변경 조작의 시퀀스로, 1개의 1에 적용하면 다른 2가 생성됩니다(데이터베이스의 트랜잭션로그 대응에 주의).컴퓨터 구현에서는 일반적으로 v1에서 데이터복사하고 리터럴 데이터를 쓰는 두 가지 명령을 사용하여 언어 형식을 취합니다.

변종

문자열프레픽스 또는 서픽스의 차이를 부호화하는 델타 부호화의 변형을 증분 부호화라고 부릅니다.사전단어 목록과 같이 문자열 간의 차이가 작은 정렬된 목록에 특히 효과적입니다.

구현 문제

부호화되는 데이터의 성질은 특정 압축 알고리즘의 효율성에 영향을 미칩니다.

델타 인코딩은 데이터의 변동이 작거나 일정한 경우에 가장 잘 작동합니다. 정렬되지 않은 데이터 세트의 경우 이 방법에서는 압축이 거의 또는 전혀 가능하지 않을 수 있습니다.

통신 채널의 양 끝에서 파일의 단일 복사본만 사용할 수 있는 네트워크를 통한 델타 부호화 전송에서는 특수 오류 제어 코드가 파일의 이전 버전 이후 변경된 부분을 검출하기 위해 사용됩니다.를 들어 rsync는 Mark Adler-32 체크섬에 기반한 롤링 체크섬알고리즘을 사용합니다.

샘플 C 코드

다음 C 코드는 일련의 문자에 대해 델타 부호화 및 디코딩의 단순한 형식을 수행합니다.

무효 delta_delta_delta(서명되어 있지 않다  *완충 장치, 인트 길이) {     서명되어 있지 않다  지난 = 0;     위해서 (인트 i = 0; i < > 길이; i++)     {         서명되어 있지 않다  현재의 = 완충 장치[i];         완충 장치[i] = 현재의 - 지난;         지난 = 현재의;     } }  무효 delta_delta_delta(서명되어 있지 않다  *완충 장치, 인트 길이) {     서명되어 있지 않다  지난 = 0;     위해서 (인트 i = 0; i < > 길이; i++)     {         서명되어 있지 않다  델타 = 완충 장치[i];         완충 장치[i] = 델타 + 지난;         지난 = 완충 장치[i];     } } 

HTTP에서의 델타 부호화

델타 인코딩의 또 다른 사용 로는 RFC 3229의 "Delta encoding in HTTP"가 있습니다.이것에 의해, HTTP 서버는 갱신된 Web 페이지를 버전(델타)간의 차이의 형태로 송신할 수 있게 됩니다.이것은, 대부분의 페이지가 완전하게 고쳐 쓰는 것이 아니라, 시간이 지남에 따라 서서히 변화하기 때문에, 인터넷트래픽을 줄일 수 있습니다.

이 문서에서는 델타 인코딩을 HTTP/1.1과의 호환 확장으로 지원하는 방법에 대해 설명합니다.

많은 HTTP(Hypertext Transport Protocol) 요청으로 인해 클라이언트에 캐시 항목이 이미 있는 리소스의 약간 수정된 인스턴스가 검색됩니다.연구에 따르면 이러한 수정 업데이트는 빈번히 이루어지며 수정은 일반적으로 실제 개체보다 훨씬 작은 것으로 나타났다.이러한 경우 HTTP는 자원의 새로운 인스턴스 전체가 아닌 변경에 대한 최소한의 설명을 전송할 수 있다면 네트워크 대역폭을 보다 효율적으로 사용할 수 있습니다.

[...] 이 문서의 뒷부분에서 설명하는 '인스턴스 조작' 프레임워크를 사용하여 rsync를 지원할 수 있다고 생각합니다만, 자세한 내용은 설명되지 않았습니다.

권장되는 rsync 기반 프레임워크는 HTTP 프록시 [1]쌍으로 rproxy 시스템에 구현되었습니다.기본적인 vCDiff 기반 구현과 마찬가지로 두 시스템 모두 거의 사용되지 않습니다.

델타 복사

델타 복사는 이전 버전이 대상 위치에 있는 경우 부분적으로 변경된 파일을 빠르게 복사하는 방법입니다.델타 복사에서는 파일의 변경된 부분만 복사됩니다.일반적으로 백업 또는 파일 복사 소프트웨어에서 사용되며 개인 네트워크나 인터넷을 통해 컴퓨터 간에 복사할 때 대역폭을 절약하기 위해 사용됩니다.주목할 만한 오픈소스의 로는 [2][3][4]rsync가 있습니다.

온라인 백업

대부분의 온라인 백업 서비스는 사용자에게 이전 백업에서 동일한 파일의 이전 버전을 제공하기 위해 이 방법론(델타라고도 함)을 채택하고 있습니다.이것에 의해, 다른 버전으로 보존할 필요가 있는 데이터량 뿐만이 아니라(각 변경 버전의 파일 전체를 유저가 액세스 할 수 있도록 제공할 필요가 있기 때문에), 갱신된 각 파일의 업로드(및 경우에 따라서는 다운로드)에 드는 코스트도 삭감됩니다.er 전체 파일보다 커집니다).

델타 업데이트

대규모 소프트웨어 패키지의 경우 버전 간에 변경된 데이터는 거의 없습니다.많은 벤더가 시간과 대역폭을 절약하기 위해 델타 전송을 사용하고 있습니다.

차이

Diff는 주로 텍스트 파일에 사용되는 파일 비교 프로그램입니다.기본적으로는 되돌릴 수 있는 대칭 델타가 생성됩니다.소프트웨어 패치에 사용되는 두 가지 형식(콘텍스트와 통합)은 행 번호의 이동을 허용하는 추가 컨텍스트 행을 제공합니다.

Git

Git 소스 코드 제어 시스템은 보조 "깃 리팩" 작업에서 델타 압축을 사용합니다.저장소 내의 델타 압축되지 않은 개체("느슨한 개체")를 경험적으로 선택한 다른 모든 개체의 하위 집합과 비교하고 공통 데이터와 차이를 "팩 파일"로 연결한 다음 기존 방법을 사용하여 압축합니다.커밋 간에 소스 또는 데이터 파일이 점진적으로 변경되는 일반적인 사용 사례에서는 공간을 크게 절약할 수 있습니다.리패킹 조작은 보통 "git gc" 프로세스의 일부로 실행됩니다.이 프로세스는 느슨한 오브젝트 또는 팩파일 수가 설정된 임계값을 초과할 때 자동으로 트리거됩니다.

포맷은 Git 문서의 pack-format 페이지에 기재되어 있습니다.다이렉트 [5]델타를 실장합니다.

비디오

다이렉트 델타 부호화의 일반적인 포맷은 RFC 3284에 기재되어 있는 VCDIFF입니다.무료 소프트웨어 구현에는 Xdelta 및 open-vcdiff가 포함됩니다.

GDIFF

Generic Diff Format(GDIFF)은 다른 다이렉트 델타 부호화 형식입니다.그것은 1997년에 [6]W3C에 제출되었다.대부분의 경우 VCDIFF는 GDIFF보다 압축률이 우수합니다.

BSDiff

Bsdiff는 서픽스 정렬을 사용하는 바이너리 diff 프로그램입니다.포인터 주소가 많이 변경된 실행 파일의 경우 VCDIFF 유형의 "복사 및 리터럴" 인코딩보다 성능이 우수합니다.목적은 (구글의 Courgette처럼) 어셈블리 코드를 해석하지 않고 작은 차이를 생성하는 방법을 찾는 것이다.Bsdiff는 에러와 일치하는 "복사"를 허용하여 이를 실현하고 바이트 단위 차이의 "추가" 배열을 사용하여 오류를 수정합니다.이 배열은 대부분 오프셋 변경에 대한 0 또는 반복 값이기 때문에 압축 [7]후 공간을 거의 차지하지 않습니다.

Bsdiff는 델타 업데이트에 유용합니다.구글은 크롬과 안드로이드에서 bsdiff를 사용한다.RPM Package Managerdeltarpm 기능은 해시 테이블을 사용하여 [8]대조할 수 있는 대폭 수정된 bsdiff에 기초하고 있습니다.FreeBSD는 업데이트에도 [9]bsdiff를 사용합니다.

2005년 4.3 bsdiff 출시 이후 다양한 개선사항 또는 수정사항이 제공되었습니다.Google은 각 [10]제품에 대해 여러 버전의 코드를 유지합니다.FreeBSD는 주로 취약성 수정과 고속 전환 등 구글과 호환되는 많은 변경 사항을 취합니다.divsufsort 접미사를 붙이는 [11]루틴데비안은 그 프로그램에 [12]대해 일련의 퍼포먼스를 조정했다.

ddelta는 Debian의 델타 업데이트에서 사용하기 위해 제안된 bsdiff의 개서입니다.효율성 향상 중에서도 슬라이딩 윈도우를 사용하여 메모리와 CPU [13]비용을 절감합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "rproxy: introduction". rproxy.samba.org.
  2. ^ "Archived copy". Archived from the original on 2016-03-13. Retrieved 2016-04-29.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  3. ^ "Bvckup 2 Forum How delta copying works".
  4. ^ http://www.eggheadcafe.com/software/aspnet/33678264/delta-copying.aspx[영구 데드링크]
  5. ^ "Git - pack-format Documentation". Git documentation. Retrieved 13 January 2020.
  6. ^ 범용 Diff 포맷 사양
  7. ^ Colin Percival, Naigent differences of executive code, http://www.daemonology.net/bsdiff/, 2003.
  8. ^ "rpmdelta/delta.c". rpm-software-management. 3 July 2019. Retrieved 13 January 2020.
  9. ^ Anonymous (May 2016). "NON-CRYPTANALYTIC ATTACKS AGAINST FREEBSD UPDATE COMPONENTS". GitHub Gist.
  10. ^ "xtraeme/bsdiff-chromium: README.chromium". GitHub. 2012.;;
  11. ^ "History for freebsd/usr.bin/bsdiff". GitHub.
  12. ^ "Package: bsdiff". Debian Patch Tracker.
  13. ^ Klode, Julian. "julian-klode/ddelta". GitHub. Retrieved 13 January 2020.

외부 링크

  • RFC 3229 - HTTP에서의 델타 부호화