寻找有关“Group varint 编码/解码”的更多详细信息在杰夫的幻灯片中呈现

Question

我注意到 Jeff 的幻灯片“构建大规模信息检索系统的挑战”，也可以在此处下载：http://research.google.com/people/jeff/WSDM09-keynote.pdf，提到了一种称为“group varint编码”的整数压缩方法。据说比每字节 7 位整数编码快得多（快 2 倍）。我对此非常感兴趣，并正在寻找它的实现，或者任何可以帮助我自己实现它的更多细节。

我不是专业人士，也不是新手，欢迎任何帮助！

Answer 1

这指的是“可变整数编码”，其中序列化时用于存储整数的位数不固定为 4 个字节。 protocol buffer 文档中对 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;
  }
}

级联 if<如果 value 的大小保证了这些额外的字节， /code>s 只会在 target 数组的末尾添加额外的字节。 0x80 屏蔽正在写入的字节，并且值 向下移动。据我所知，0x7f 掩码使其表示“编码的最后一个字节”。 （当对 0x80 进行 OR 运算时，最高位将始终为 1，然后最后一个字节清除最高位（通过对 0x7f 进行 AND 运算）因此，在读取 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;
  }
}

Answer 2

我一直在寻找同样的东西，并发现了这个 Java 的 GitHub 项目：
https://github.com/stuhood/gvi/
看起来很有前途！

Answer 3

在 c/c++ 中，您可以使用与第一个字节中的值相对应的预定义结构，而不是使用位掩码进行解码。使用此结构的完整示例： http://www.oschina.net/code/snippet_12_5083

Answer 4

groupvarint 的另一个 Java 实现： https://github.com/catenamatteo/groupvarint
但我怀疑 Java 中非常大的 switch 有一些缺点