encoding - 可变字节编码说明

Question

我对字节编码的世界很陌生，所以如果我以错误的方式使用/表达简单的概念，请原谅我(无论如何，请纠正我)。

我正在尝试了解可变字节编码。我已阅读维基百科文章 ( http://en.wikipedia.org/wiki/Variable-width_encoding ) 以及 book chapter来自信息检索教科书。我想我明白如何编码一个十进制整数。例如，如果我想为整数 60 提供可变字节编码，我将得到以下结果:

1 0 1 1 1 1 0 0

(如果上述内容不正确，请告诉我)。如果我理解这个方案，那么我就不能完全确定信息是如何压缩的。是不是因为通常我们会用32位来表示一个整数，所以表示60会导致 1 1 1 1 0 0前面有 26 个零，从而浪费了那个空间而不是只用 8 位来表示它？

预先感谢您的澄清。

Answer 1

你这样做的方法是保留一个位来表示“我没有完成这个值”。通常，这是最重要的位。

当您读取一个字节时，您会处理低 7 位。如果最高有效位为 1，则您知道还有一个字节要读取，然后重复该过程，将接下来的 7 位添加到当前的 7 位。

MIDI 格式使用该精确编码来表示 MIDI 事件的长度，如下所示:

预期值 = 0

byte=ReadFromFile

ExpectedValue = ExpectedValue + (byte AND 0x7f)

如果字节 > 127 那么

预期值 = 预期值 SHL 7

转到 2

完成

例如，值 0x80 将使用字节 0x81 0x00 表示。您可以尝试在这两个字节上运行算法，您会看到您将获得正确的值。

UTF-8 的工作原理类似，但它使用稍微复杂的方案来告诉您应该期望多少字节。这允许进行一些错误更正，因为您可以轻松判断您获得的字节是否与声明的长度匹配。 Wikipedia describes their structure很好。