在Jeff的幻灯片中查找有关"组变量编码/解码"的更多详细信息

Question

我在Jeff的幻灯片"构建大规模信息检索系统的挑战"中注意到了这一点,也可以在此处下载:http://research.google.com/people/jeff/WSDM09-keynote.pdf,一种整数压缩方法称为"组varint编码".据说比每字节整数编码多7位(多2倍).我对此非常感兴趣并且正在寻找这个的实现,或者任何可以帮助我自己实现的细节.

我不是专业人士和新手,欢迎任何帮助!

Answer 1

这是指"可变整数编码",其中用于在序列化时存储整数的位数不固定为4个字节.协议缓冲区文档中有一个很好的varint描述.

它用于编码Google的协议缓冲区,您可以浏览协议缓冲区源代码.

该CodedOutputStream包含精确编码功能WriteVarint32FallbackToArrayInline:

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;
  }
}

如果保证这些额外字节的大小,则级联ifs将仅在target数组的末尾添加value额外的字节.该0x80口罩字节写入,以及value向下移.据我所知,0x7f掩码使其表示"编码的最后一个字节".(当进行"或"操作时0x80,最高位将始终为1,则最后一个字节将清除最高位(通过"与" 0x7f).因此,在读取变量时,您将读取,直到获得最高位为零的字节.

我刚才意识到你特意询问了"Group VarInt编码".对不起,该代码是关于基本的VarInt编码(仍然比7位快).基本想法看起来很相似.不幸的是,它不是用于在协议缓冲区中存储64位数字的内容.如果该代码在某处开源,我不会感到惊讶.

使用varint幻灯片中的"Group varint"图表和它们的图表,不应该太难以自己烹饪:)

这是另一个描述Group VarInt压缩的页面,它包含解码代码.不幸的是,它们提到了公开可用的实现,但它们没有提供参考.

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;
  }
}