protobuf를 찾아보던 와중 protobuf의 int형 encode방식을 알게 되었다.
흥미가 생겨 찾아보았고, VLQ라는 것을 알았다. 이에 대하여 적어보려 한다.

VLQ

Variable-length quantity의 약자로 가변적인 길이로 수량을 나타내는 방법을 뜻 한다.

장점

압축성

값이 작을 수록 작은 byte로 표현이 가능하다.
byte의 낭비가 적다.

유연성

값의 따라 길이가 달라지기에 값의 제한이 없다.

단점

성능

가변적인 성질때문에 고정길이보다 처리가 많다.

vs Fixed-length

Fixed-length란 가변적이지 않은 고정 길이를 뜻한다.

	VL	FL
압축성	높음	낮음
유연성	높음	낮음
성능	낮음	높음

동작

VLQ는 Byte단위로 구성되며
연속을 확인하는 bit와 값을 저장하는 bit로 나누어진다.

byte

0	1	2	3	4	5	6	7
A	B	B	B	B	B	B	B

• A : byte의 가장 앞에 위치하며
  1이면 뒤 연속적으로 값이 존재하는 것 이고,
  0이면 이 값이 마지막이라는 것 이다.
• B : 값을 저장하는 공간이다.

예시

encoding

300을 2진수로 표현
00000001 00101100

7bit 단위로 나누기
A0000010 A0101100

연속되면 1, 마지막이면 0 채우기
10000010 00101100

decoding

값 받기
10000010 00101100

첫 bit 제거
A0000010 00101100

합치기
00000001 00101100

10진수 변환
300

첨언

• least significant group first(최하위 그룹 우선)을 적용하여 encoding과 decoding의 효율성을 더할 수 있다.
• ZigZagEncoding 방식을 활용하여 음수를 표현 할 수 있다.

참조

https://en.wikipedia.org/wiki/Variable-length_quantity