尋找關於Jeff的幻燈片

Question

中提出的「組varint編碼/解碼」的更多細節我注意到，在Jeff的幻燈片「構建大規模信息檢索系統的挑戰」中，也可以在這裏下載：http://research.google.com/people/jeff/WSDM09-keynote.pdf，整數方法稱爲「組織varint編碼」的壓縮被提及。據說比每字節整數編碼7位（2倍多）要快得多。我對此非常感興趣，希望能夠實現這一點，或者有更多的細節可以幫助我自己來實現。

我不是一個親和新來的，歡迎任何幫助！

Answer 1

這是指「可變整數編碼」，其中用於存儲整數的位數在串行化時不固定在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掩碼使它表示「編碼的最後一個字節」。 （當OR' 0x80，最高位總是1，那麼最後一個字節會清除最高位（通過AND'ing 0x7f）。因此，在讀取varints時，您必須先閱讀，直到獲得最高位爲零的字節。

我才意識到你問「集團VarInt編碼」特別對不起，該代碼是關於基本VarInt編碼（仍快於7位），其基本思想看起來是相似的，不幸的是，這是不什麼是用來在協議緩衝區中存儲64位數字我不會感到驚訝，如果代碼是開源的地方

使用從varint和「組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

我一直在尋找同樣的東西，發現在Java中，這GitHub的項目： https://github.com/stuhood/gvi/ 看起來有前途的！

Answer 3

而是與位掩碼進行解碼，在C/C++，你可以使用對應於第一個字節的值預定義的結構..使用這個完整的例子：http://www.oschina.net/code/snippet_12_5083

Answer 4

另一個Java實現groupvarint：https://github.com/catenamatteo/groupvarint 但我懷疑非常大的交換機在Java中有一些缺點