가변길이수량

Variable-length quantity
이 글은 바이트의 가변 수인 코드에 관한 것이다.가변 비트 길이 코드의 보다 일반적인 범주에 대해서는 가변 길이 코드를 참조하십시오.

가변 길이 수량(VLQ)은 임의의 큰 정수를 나타내기 위해 임의의 바이너리 8진수(8비트 바이트)를 사용하는 범용 코드다.VLQ는 본질적으로 바이트의 연속성을 표시하기 위해 8번째 비트를 추가하는 부호 없는 정수의 기본-128이다.VLQ는 Endianness를 제외하고 LEB128과 동일하다.아래 예제를 참조하십시오.

응용 프로그램 및 기록

베이스-128 압축은 VB(가변 바이트), VByte, Varint, Vint, EncInt 등 여러 이름으로 알려져 있다.[1]

가변 길이 수량(VLQ)은 자원이 제약된 시스템의 추가 공간을 절약하기 위해 표준 MIDI 파일 형식에[2] 사용하도록 정의되었으며, 이후 XMF(Extensible Music Format)에서도 사용된다.

베이스-128은 ASN.1 BER 인코딩에서도 태그 번호와 객체 식별자를 인코딩하는 데 사용된다.[3]또한 WAP 환경에서도 사용되는데, 여기서 가변 길이 비부호 정수 또는 uintvar라고 한다.DEMP 디버깅 형식은[4] LEB128(또는 서명되지 않은 숫자에 대한 ULEB128)이라는 변종을 정의하는데, 여기서 7비트의 가장 적은 그룹이 첫 번째 바이트로 인코딩되고, 가장 중요한 비트는 마지막 바이트(그래서 효과적으로 VLQ의 리틀엔디안 아날로그)이다.Google 프로토콜 버퍼는 유사한 형식을 사용하여 Oracle POF(Portable Object Format)[6] 및 Microsoft와 같이 정수 값을 콤팩트하게 표현한다.[5]NET Framework는 BinaryReader 및 BinaryWriter 클래스의 "7비트 인코딩 인트"를 참조하십시오.[7]

그것은 또한 지도 크기를 최소한으로 유지하기 위해 정수선과 열 번호 매핑을 많이 포함하는 소스 매핑을 위해 웹 브라우저에서 광범위하게 사용된다.[8]

LLVM의 가변 폭 정수는 유사한 원리를 사용한다.인코딩 청크는 작은 엔디안이며 크기가 8비트일 필요는 없다.LLVM 설명서는 4비트 청크를 사용하는 필드를 설명하며, 각 청크는 1비트 연속성과 3비트 페이로드로 구성된다.[9]

일반구조

인코딩은 일반적으로 부호 비트라고도 알려진 가장 중요한 비트(MSB)가 또 다른 VLQ 옥텟을 따르는지 여부를 나타내기 위해 예약된 옥텟(8비트 바이트)을 가정한다.

VLQ 옥텟
7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20
A Bn

A가 0이면 이것이 정수의 마지막 VLQ 옥텟이다.A가 1이면 다른 VLQ 옥텟이 뒤따른다.

B는 7비트 수[0x00, 0x7F]이며 n은 B가0 가장 덜 중요한 VLQ 옥텟의 위치다.VLQ 8진법은 스트림에서 가장 중요한 첫 번째 배열이다.

변형

일반적인 VLQ 인코딩은 간단하지만 기본 형식에서는 부호 없는 정수(비음성, 양수 또는 0)에 대해서만 정의되며 0x80 옥텟을 미리 입력하는 것은 제로 패딩에 해당하므로 다소 중복적이다.음수를 처리하기 위한 서명된 숫자 표현과 중복성을 제거하는 기법이 다양하게 있다.

그룹 바린트 인코딩

구글은 기존 VLQ 인코딩이 압축 해제 시 많은 CPU 분기를 침범하는 것을 보고 GVE(Group Varint Encoding)를 개발했다.GVE는 4개의 가변 길이 uint32 값에 대한 헤더로 단일 바이트를 사용한다.헤더 바이트는 다음의 4개의 uint32s 각각의 저장 길이를 나타내는 4개의 2비트 숫자를 가지고 있다.이러한 레이아웃을 사용하면 VLQ 연속 비트를 확인하고 제거할 필요가 없다.데이터 바이트는 대상으로 직접 복사할 수 있다.이 레이아웃은 CPU 분기를 줄여 최신 파이프라인 CPU의 VLQ보다 GVE를 더 빠르게 만든다.[10]

PrefixVarint는 설계는 유사하지만 uint64 최대값이다.그것은 "비엔이 독립적으로 여러 번 발명했다"[11]고 한다.무한히 많은 연속이 있는 사슬형 버전으로 바꾸는 것이 가능하다.

서명된 번호

사인 비트

음수는 첫 번째 옥텟에만 있으면 되는 부호 비트를 사용하여 처리할 수 있다.

언리얼 엔진에서 사용하는 언리얼 패키지의 데이터 형식에서는 컴팩트 인덱스라는[12] 가변 길이 수량 체계가 사용된다.이 인코딩에서 유일한 차이점은 첫 번째 VLQ가 인코딩된 정수가 양수인지 음수인지를 나타내기 위해 6번째 비트를 예약했다는 것이다.모든 연속 VLQ 옥텟은 일반 구조를 따른다.

언리얼 서명 VLQ
첫 번째 VLQ 옥텟 기타 VLQ 8진수
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 27 26 25 24 23 22 21 20
A B C0 B Cn (n > 0)

A가 0이면 VLQ는 양의 정수를 나타낸다.A가 1이면 VLQ는 음수를 나타낸다.

B가 0이면 정수의 마지막 VLQ 옥텟이다.B가 1이면 다른 VLQ 옥텟이 뒤따른다.

C는 인코딩되는 숫자 청크로, n은 C가0 가장 덜 중요한 VLQ 옥텟의 위치다.VLQ 8진법은 스트림에서 가장 먼저 중요도가 낮다.

지그재그 부호화

음수를 인코딩하는 다른 방법은 부호를 위해 가장 유의하지 않은 비트를 사용하는 것이다.이는 구글 프로토콜 버퍼에 특히 적용되며, 서명된 정수의 지그재그 인코딩으로 알려져 있다.[13]인코딩된 0이 0, 1 ~ -1, 10 ~ 1, 11 ~ -2, 100 ~ 2 등에 해당하도록 숫자를 인코딩할 수 있다. 즉, 각 단계가 0에서 시작하는 비트와 음(각 단계마다 중요도가 가장 낮은 비트가 변경되므로 부호가 변경됨), "지그재그 인코딩" 등의 명칭이 번갈아 계산된다.구체적으로는 정수를 다음과 같이 변환한다.(n << 1) ^ (n >> k - 1)고정 k-비트 정수의 경우

2의 보어

LEB128은 서명된 숫자를 나타내기 위해 두 개의 보어를 사용한다.이 표현 방식에서 n비트는 -2n ~ 2n - 1의 범위를 인코딩하며, 모든 음수는 가장 중요한 비트의 1로 시작한다.서명된 LEB128에서는 입력이 사인 확장되어 길이가 7비트의 배수가 된다.거기서부터 인코딩은 평상시와 같이 진행된다.[14]

LEB128에서는 가장 먼저 스트림이 배열된다.[14]

중복 제거 중

위에서 설명한 VLQ 인코딩으로, 단순히 0x80 옥텟을 제로 패딩으로 추가하기 전에 N 옥텟으로 인코딩할 수 있는 숫자도 N 옥텟 이상으로 인코딩할 수 있다.예를 들어 소수점 358을 2옥텟 VLQ 0x8266으로 인코딩하거나, 숫자 0358을 3옥텟 VLQ 0x808266으로 인코딩하거나, 00358을 4옥텟 VLQ 0x808266 등으로 인코딩할 수 있다.

그러나 Git에서[15] 사용되는 VLQ 형식은 이러한 선행 중복성을 제거하고 그러한 (N + 1) 옥텟의 VLQ에 대해 가능한 최저 값이 N-Octet VLQ의 최대값보다 정확히 1이 되도록 2개 이상의 옥텟에 오프셋을 추가하여 VLQ의 표현 가능한 범위를 확장한다.특히 1옥텟 VLQ는 최대값 127을 저장할 수 있으므로 최소 2옥텟 VLQ(0x8000)는 0이 아닌 128이 할당된다.반대로, 그러한 2옥텟 VLQ(0xFF7F)의 최대값은 16383이 아니라 16511이다.마찬가지로 최소 3옥텟 VLQ(0x808000)의 값은 0이 아닌 16512로, 즉 최대 3옥텟 VLQ(0xFFF7F)는 2097151이 아닌 2113663이다.

이런 식으로 각 정수의 인코딩은 하나뿐이며, 이것은 염기-128 생체적 숫자(basebase-128 bijective number)가 된다.

예

106903을 10진수에서 uintvar로 변환하는 방법을 보여주는 다이어그램

다음은 소수점 137에 대한 연습된 예시 입니다.

  • 이항 표기법으로 값 표시(예: 137 as 10001001)
  • 최하위 유의 비트(예: 137 as 000000001 0001001)부터 시작하여 7비트 그룹으로 나뉜다.이것은 염기서열 128로 숫자를 나타내는 것과 같다.
  • 최하위 7비트를 취하면 최하위 바이트(0000 1001)가 된다.이 바이트는 꼴찌다.
  • 7비트의 다른 모든 그룹(예: 0001)에 대해 MSB를 1로 설정하십시오(예: 1000 0001 제공).따라서 137은 1000 0001 0000 1001이 되고, 여기서 굵은 글씨체의 비트는 우리가 추가한 것이다.이 추가된 비트는 따를 다른 바이트가 있는지 여부를 나타낸다.따라서 정의에 따르면 가변 길이 정수의 마지막 바이트는 MSB로 0을 갖는다.

이것을 살펴보는 또 다른 방법은 base-128의 값을 표시한 다음 마지막 base-128 숫자를 제외한 모든 숫자의 MSB를 1로 설정하는 것이다.

표준 MIDI 파일 형식 사양은 다음과 같은 더 많은 예를 제공한다.[2][16]

정수(십진수) 정수(헥사데시멀) 정수(이진수) 가변 길이 수량(헥사데시멀) 가변 길이 수량(이진수)
0 0x00000000 
00000000 00000000 00000000 00000000
 0x00 
                           00000000
127 0x0000007F 
00000000 00000000 00000000 01111111
 0x7F 
                           01111111
128 0x00000080 
00000000 00000000 00000000 10000000
 0x81 0x00 
10000001 00000000
8192 0x00002000 
00000000 00000000 00100000 00000000
 0xC0 0x00 
11000000 00000000
16383 0x00003FFF 
00000000 00000000 00111111 11111111
 0xFF 0x7F 
11111111 01111111
16384 0x00004000 
00000000 00000000 01000000 00000000
 0x81 0x80 0x00 
10000001 10000000 00000000
2097151 0x001FFFFF 
00000000 00011111 11111111 11111111
 0xFF 0xFF 0x7F 
11111111 11111111 01111111
2097152 0x00200000 
00000000 00100000 00000000 00000000
 0x81 0x80 0x80 0x00 
10000001 10000000 10000000 00000000
134217728 0x08000000 
00001000 00000000 00000000 00000000
 0xC0 0x80 0x80 0x00 
11000000 10000000 10000000 00000000
268435455 0x0FFFFFFF 
00001111 11111111 11111111 11111111
 0xFF 0xFF 0xFF 0x7F 
11111111 11111111 11111111 01111111

참조

  1. ^ 장궈왕, 천빈린, 야니스 파파콘스탄티누, 스티븐 스완슨."비트맵 압축 vs에 대한 실험적 연구 반전 목록 압축" 2017. doi:10.1145/3035918.3064007.
  2. ^ a b MIDI 파일 형식: 가변 수량.
  3. ^ "ITU-T Recommendation X.690" (PDF). International Telecommunication Union. 2002.
  4. ^ 왜소 표준.
  5. ^ Google 프로토콜 버퍼.
  6. ^ Oracle POF(Portable Object Format)
  7. ^ 시스템.IO.바이너리 작성기.Write7BitEncodedInt(int) 방법 및 시스템.IO.BinaryReader.Read7BitEncodedInt() 메서드.
  8. ^ 자바스크립트 소스 맵 소개
  9. ^ "LLVM 비트코드 파일 형식", 섹션 "가변 폭 정수".2019-10-01 접속.
  10. ^ Jeff Dean. "Challenges in Building Large-Scale Information Retrieval Systems" (PDF). p. 58. Retrieved 2020-05-30.
  11. ^ Olesen, Jakob Stoklund (31 May 2020). "stoklund/varint".
  12. ^ "Unreal Packages". 1999-07-21. Archived from the original on 2010-08-20. Retrieved 2021-08-29.
  13. ^ 프로토콜 버퍼: 인코딩: 서명된 정수.
  14. ^ a b Free Standards Group (December 2005). "DWARF Debugging Information Format Specification Version 3.0" (PDF). p. 70. Retrieved 2009-07-19.
  15. ^ "Git – fast, scalable, distributed revision control system". 28 October 2021.
  16. ^ 표준 MIDI-파일 형식 규격 1.1.

외부 링크