압축

압축 정보

압축은 Web Risk의 주요 기능입니다. 압축은 특히 휴대 기기와 관련된 대역폭 요구사항을 크게 줄여줍니다. 현재 Web Risk 서버는 Rice 압축을 지원합니다. 향후 더 많은 압축 방법이 추가될 수 있습니다.

압축은 supportedCompressions 필드와 CompressionType을 사용하여 설정됩니다. 클라이언트는 RICE 및 RAW 압축 유형을 사용해야 합니다. 압축 유형이 설정되지 않은 경우 Web Risk에서 COMPRESSION_TYPE_UNSPECIFIED 유형을 사용합니다(RAW 압축이 대체됨).

Web Risk 서버는 선택된 압축 유형에 관계없이 클라이언트가 올바른 HTTP 압축 헤더를 설정하는 한 표준 HTTP 압축을 사용하여 응답을 추가로 압축합니다. 자세한 내용은 HTTP 압축에 대한 위키백과 문서를 참조하세요.

Rice 압축

언급한 바와 같이 현재 Web Risk 서버는 Rice 압축을 지원합니다. 자세한 내용은 위키백과 문서 Golomb 코딩를 참조하세요.

압축/압축 해제

RiceDeltaEncoding 객체는 Rice-Golomb으로 인코딩된 데이터를 나타내며 압축된 삭제 색인 또는 압축된 4바이트 해시 프리픽스를 보내는 데 사용됩니다. 4바이트보다 긴 해시 프리픽스는 압축되지 않으며 대신 원시 형식으로 제공됩니다.

삭제 색인의 경우 색인 목록이 오름차순으로 정렬된 다음 RICE 인코딩을 사용하여 델타 인코딩됩니다. 또한 4바이트 해시 프리픽스는 little-endian uint32로 다시 해석되고 오름차순으로 정렬된 다음 RICE 인코딩을 사용하여 델타 인코딩됩니다. RICE 압축과 RAW의 해시 형식 차이는 원시 해시가 사전 순으로 정렬된 바이트이고 RICE 해시는 압축 해제 후에 오름차순으로 정렬된 uint32입니다.

즉, 정수 [1, 5, 7, 13] 목록은 첫 번째 값 1 및 델타 [4, 2, 6]으로 인코딩됩니다.

첫 번째 값은 firstValue 필드에 저장되고 델타는 Golomb-Rice 인코더를 사용하여 인코딩됩니다. Rice 매개변수 k(아래 참조)는 riceParameter에 저장됩니다. numEntries 필드에는 Rice 인코더로 인코딩된 델타 수가 포함됩니다(위의 예시에서는 4가 아닌 3). encodedData 필드에는 실제 인코딩된 델타가 포함됩니다.

인코더/디코더

Rice 인코더/디코더에서 모든 델타 n은 n = (q<<k) + r(또는 n = q * (2**k) + r)인 q 및 r로 인코딩됩니다. k는 상수이며 Rice 인코더/디코더의 매개변수입니다. q 및 r의 값은 다른 인코딩 스키마를 사용하여 비트 스트림에 인코딩됩니다.

몫 q는 단항 코딩으로 인코딩되고 뒤에 0이 붙습니다. 즉, 3은 1110, 4는 11110, 7은 11111110으로 인코딩됩니다. 몫 q는 먼저 디코딩됩니다.

나머지 r은 잘린 바이너리 인코딩을 사용하여 인코딩됩니다. r의 최하위 k 비트만 비트 스트림에서 쓰여지고 읽혀집니다. 나머지 r은 q가 디코딩된 후 디코딩됩니다.

비트 인코더/디코더

Rice 인코더는 비트 인코더에 단일 비트를 추가할 수 있는 비트 인코더/디코더를 사용합니다. 즉, 길이가 2비트일 수 있는 몫 q를 인코딩합니다.

비트 인코더는 8비트 바이트의 목록입니다. 비트는 첫 번째 바이트의 최하위 비트에서 첫 번째 바이트의 최상위 비트로 설정됩니다. 바이트에 이미 모든 비트가 설정된 경우 0으로 초기화된 새 바이트는 바이트 목록의 끝에 추가됩니다. 마지막 바이트가 완전히 사용되지 않는 경우 최상위 비트는 0으로 설정됩니다. 예:

추가된 비트	비트 추가 후 BitEncoder
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]