- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我注意到 Jeff 的幻灯片“构建大规模信息检索系统的挑战”,也可以在这里下载:http://research.google.com/people/jeff/WSDM09-keynote.pdf ,提到了一种称为“group varint encoding”的整数压缩方法。据说比每字节 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
掩码使它表示“编码的最后一个字节”。 (当 OR'ing 0x80
时,最高位将始终为 1
,然后最后一个字节清除最高位(通过 AND'ing 0x7f
)。因此,在读取 varint 时,您会一直读取到最高位为零的字节。
我刚刚意识到您专门询问了“Group VarInt encoding”。抱歉,该代码是关于基本 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;
}
}
关于algorithm - 在 Jeff 的幻灯片中查找有关 "Group varint encoding/decoding"的更多详细信息,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2982957/
我使用术语“词法编码”是因为我没有更好的编码。 与字母相反,单词可以说是交流的基本单位。 Unicode 尝试为所有已知字母表的每个字母分配一个数值。对一种语言来说是字母,对另一种语言来说是字形。 U
我在UTF-8中有csv文件,我想将其保存在西里尔字母(Windows 1251)中...在中,我仅找到Atom -重新打开,并使用ctrl+shift+u编码 在 Sublime Text 3 中,
在lua 5.3引用手册中,我们可以看到: Lua is also encoding-agnostic; it makes no assumptions about the contents of a
看完后how gzip compression works它让我思考。如果源和代理服务器 (CDN) 都支持 gzip,则添加 Vary: Accept-Encoding头需要吗? 最佳答案 Vary
我正在向我的项目添加一项功能,我们将生成指向我们网站内部内容的链接,并且我们希望这些链接尽可能短,因此我们将制作自己的“URL 缩短器”。 我想知道生成的短网址的最佳编码/字母表是什么。这很大程度上是
我构建了一个用于压缩 HTTP 输出的模块。阅读spec ,我在以下几件事上没有发现明显的区别: 接受编码: 是否应将其视为与 Accept-Encoding: * 相同,还是视为不存在 header
在下面的代码中: package main import ( "bytes" "encoding/json" "fmt" ) type Student struct {
这个问题在这里已经有了答案: Why does encode delete the argument? (1 个回答) 6年前关闭。 Encode::encode 的文档说: encode $octe
在Android4.1中,实时编码应用中经常会请求关键帧。但是如何使用 MediaCodec 对象呢?当前的 Android4.2 SDK 似乎不支持它。 最佳答案 您可以 通过在排队输入缓冲区时指定
我有 CSV 格式的数据,这些数据在字符编码方面被严重打乱,可能在不同的软件应用程序(LibreOffice Calc、Microsoft、Excel、Google Refine、自定义 PHP/My
您可能知道,在 Perl 中,“utf8”意味着 Perl 对 UTF-8 的宽松理解,它允许使用技术上不是 UTF-8 中有效代码点的字符。相比之下,“UTF-8”(或“utf-8”)是 Perl
本文整理了Java中org.geotools.ysld.encode.YsldEncoder.encode()方法的一些代码示例,展示了YsldEncoder.encode()的具体用法。这些代码示例
现在还没有任何关于红色的书,因为它太新了。因此,我正在尝试遵循一本旧的 Rebol 书,并从中挽救我能得到的东西。 我发现一些命令,例如 read,由于文件编码的原因,我无法执行代码。 save %
错误:无法映射用于编码 UTF-8 的字符。由于版权特征,我收到此错误。我使用的是 Netbeans 7.2。 /** * � 2006 * * This class was generate
现在还没有任何关于红色的书,因为它太新了。因此,我正在尝试遵循一本旧的 Rebol 书,并从中挽救我能得到的东西。 我发现一些命令,例如 read,由于文件编码的原因,我无法执行代码。 save %
错误:无法映射用于编码 UTF-8 的字符。由于版权特征,我收到此错误。我使用的是 Netbeans 7.2。 /** * � 2006 * * This class was generate
我正在尝试使用客户端提供的值在 PHP 中测试 Soap Security header 。 他们提供的值(value)如... wTAmCL9tmg6KNpeAQOYubw== ...并说这是一个
这个问题已经有答案了: ClassNotFoundException/NoClassDefFoundError in my Java web application (3 个回答) 已关闭 8 年前。
世界!我正在使用 .Net Framework 4 System.Net.Sockets.TcpClient 编写简单的 HTML 服务器。 我在 StringBuilder html 中有 HTML
我正在尝试使用 Yii 来提供网络服务。自动生成的 wsdl 如下。我可以从命令行成功使用 Web 服务,但是通过 Web 浏览器,我得到了 SOAP-ERROR: Encoding: Violati
我是一名优秀的程序员,十分优秀!