我注意到在Jeff的幻灯片“构建大规模信息检索系统中的挑战”中，也可以在此处下载:http://research.google.com/people/jeff/WSDM09-keynote.pdf，它是一种整数压缩方法，称为“组varint编码”。据说它比每字节7位整数编码快得多(多了2倍)。我对此很感兴趣，并希望对此实现，或者任何其他可以帮助我自己实现的细节。
我不是专业人士，也不是新手，欢迎任何帮助!
最佳答案
这是指“可变整数编码”，其中序列化时用于存储整数的位数不固定为4个字节。 varint in the protocol buffer documentation有一个很好的描述。
它用于对Google's protocol buffers进行编码，您可以浏览protocol buffer source code。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的大小可以保证这些额外的字节，级联的target只会将额外的字节添加到value数组的末尾。 0x80屏蔽正在写入的字节，并且value下移。据我所知，0x7f掩码使它表示“编码的最后一个字节”。 (当对ORning 0x80进行操作时，最高位始终为1，然后最后一个字节清除最高位(通过AND'ing 0x7f)。因此，在读取varint时，您将读取直到获得最高位为零的字节为止。 。我刚刚意识到您曾专门询问过“Group VarInt编码”。抱歉，该代码是有关基本VarInt编码的(仍比7位还快)。基本想法看起来很相似。不幸的是，它不是用于在 Protocol Buffer 中存储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;
}
}