Jeff의 슬라이드에 제시된 "Group varint 인코딩/디코딩"에 대한 자세한 내용은

Question

으로 Jeff의 슬라이드 "대규모 정보 검색 시스템 구축에 대한 도전"(여기에서 다운로드 할 수 있음)을 참조하십시오 : http://research.google.com/people/jeff/WSDM09-keynote.pdf, 정수 방법 "group varint encoding"이라고하는 압축이 언급되었습니다. 바이트 정수 인코딩 당 7 비트보다 훨씬 빠릅니다 (2 배 이상). 나는 이것에 매우 흥미가 있으며 이것의 구현, 또는 나 자신에 의해 이것을 구현하는 데 도움이 될 수있는 세부 사항을 찾고있다.

전 프로가 아니며 새로운 것이 아니며 모든 도움을 환영합니다!

Answer 1

"가변 정수 인코딩"을 말합니다. 여기서 직렬화 될 때 정수를 저장하는 데 사용되는 비트 수는 4 바이트로 고정되지 않습니다. varint in the protocol buffer documentation에 대한 설명이 있습니다.

Google's protocol buffers 인코딩에 사용되며 protocol buffer source code을 검색 할 수 있습니다.

CodedOutputStream 정확한 인코딩 기능 WriteVarint32FallbackToArrayInline 포함에만 target 배열의 마지막에 추가 바이트를 추가합니다

inline uint8* CodedOutputStream::WriteVarint32FallbackToArrayInline(
    uint32 value, uint8* target) { 
    target[0] = static_cast<uint8>(value | 0x80); 
    if (value >= (1 << 7)) { 
    target[1] = static_cast<uint8>((value >> 7) | 0x80); 
    if (value >= (1 << 14)) { 
     target[2] = static_cast<uint8>((value >> 14) | 0x80); 
     if (value >= (1 << 21)) { 
     target[3] = static_cast<uint8>((value >> 21) | 0x80); 
     if (value >= (1 << 28)) { 
      target[4] = static_cast<uint8>(value >> 28); 
      return target + 5; 
     } else { 
      target[3] &= 0x7F; 
      return target + 4; 
     } 
     } else { 
     target[2] &= 0x7F; 
     return target + 3; 
     } 
    } else { 
     target[1] &= 0x7F; 
     return target + 2; 
    } 
    } else { 
    target[0] &= 0x7F; 
    return target + 1; 
    } 
} 

계단식 if들 경우 value 보증 그 여분의 바이트 크기. 0x80은 기록중인 바이트를 마스크하고 value은 아래로 이동합니다. 내가 알 수있는 바로는 0x7f 마스크는 "인코딩의 마지막 바이트"를 나타냅니다. (OR'ing 0x80, 가장 높은 비트는 항상 1이고, 마지막 바이트는 가장 높은 비트를 지 웁니다 (0x7f의 AND로). 따라서 varints를 읽을 때 가장 높은 비트에 0이 포함 된 바이트가 나타날 때까지 읽습니다 .

난 그냥 당신이. 기본 개념이 유사한 것으로 보인다. 불행하게도, 그것은 하지의 구체적. 죄송합니다, 그 코드는 기본 VarInt 인코딩 (여전히보다 빠른 7 비트)에 대해이었다 "인코딩 그룹 VarInt"에 대해 질문 실현 프로토콜 버퍼에 64 비트 숫자를 저장하는 데 사용되는 코드입니다. 코드가 오픈 소스로되어 있다면 놀랄 일이 아닙니다.

varint의 아이디어와 "Group varint "를 사용하면 슬라이드를 직접 요리 할 수 ​​없습니다.

다음은 디코딩 코드가 포함 된 Group VarInt compression을 설명하는 또 다른 페이지입니다. 불행히도 공개적으로 사용 가능한 구현을 암시하지만 참조를 제공하지는 않습니다.

void DecodeGroupVarInt(const byte* compressed, int size, uint32_t* uncompressed) { 
    const uint32_t MASK[4] = { 0xFF, 0xFFFF, 0xFFFFFF, 0xFFFFFFFF }; 
    const byte* limit = compressed + size; 
    uint32_t current_value = 0; 
    while (compressed != limit) { 
    const uint32_t selector = *compressed++; 
    const uint32_t selector1 = (selector & 3); 
    current_value += *((uint32_t*)(compressed)) & MASK[selector1]; 
    *uncompressed++ = current_value; 
    compressed += selector1 + 1; 
    const uint32_t selector2 = ((selector >> 2) & 3); 
    current_value += *((uint32_t*)(compressed)) & MASK[selector2]; 
    *uncompressed++ = current_value; 
    compressed += selector2 + 1; 
    const uint32_t selector3 = ((selector >> 4) & 3); 
    current_value += *((uint32_t*)(compressed)) & MASK[selector3]; 
    *uncompressed++ = current_value; 
    compressed += selector3 + 1; 
    const uint32_t selector4 = (selector >> 6); 
    current_value += *((uint32_t*)(compressed)) & MASK[selector4]; 
    *uncompressed++ = current_value; 
    compressed += selector4 + 1; 
    } 
} 

Answer 2

나는 같은 일을 찾고 자바에서이 GitHub의 프로젝트 발견 : https://github.com/stuhood/gvi/ 가 유망한 보이는을! 대신 당신이 첫 번째 바이트의 값에 해당하는 미리 정의 된 구조를 사용할 수 ++의 C/C가, 비트 마스크와 디코딩의

Answer 3

..이 사용하는 전체 예제 : http://www.oschina.net/code/snippet_12_5083이

Answer 4

또 다른 자바 groupvarint에 대한 구현 : https://github.com/catenamatteo/groupvarint 하지만 나는 매우 큰 스위치가 Java에서 몇 가지 단점이 있다고 의심한다.