Variable-length quantity (VLQ)

[xwcoder]

[toc]

定义

Variable-length quantity（VLQ）是一种用于编码可变长度数据的技术，主要用于节省存储空间，同时保持一定的扩展性。

wikipedia

用途

• 数据压缩: VLQ主要用于减少数据在存储或传输中占用的空间，适用于那些列数据中存在大量重复项的情况。
• 序列化格式: 例如，Zipack格式使用VLQ来编码整数，希望让绝对值更小的整数占据更小的空间

工作原理

• 编码过程: VLQ编码通过每个字节的首个bit来表示是否有后续字节。如果首个bit是0，则表示当前字节是数据的最后一个字节；如果是1，则表示还有后续字节。
• 解码过程: 从左至右扫描序列化数据，当扫描到首个bit为0的字节时，表示数据已经完全解码。

优点

• 节省空间：VLQ编码可以显著减少数据的存储占用，特别是在处理大量重复值或连续值时
• 简单高效: VLQ编码算法简单，易于实现，且不需要复杂的计算

缺点

• 更新成本：如果数据集需要支持频繁更新，VLQ编码可能会引入额外的复杂性和开销，因为每次插入或删除值时，可能都需要更新编码

应用场景

• 内存缓存：用于存储和快速访问数据。
• 通信协议：在数据传输中减少数据量，提高传输效率。
• 配置文件：用于存储配置信息，减少文件大小。

编码过程

1. 分组：从最低位开始将整数的二进制表示按7位一组进行分组。不足的用 0 补齐。
2. 设置最高位：除了最后一组外，每组的最左位（MSB）设置为1，表示还有后续字节。最后一组的MSB设置为0，表示这是最后一组。

Example

Example: 137 的二进制表示 10001001

1. 分组：0000001 0001001
2. 设置最高位 10000001 00001001

实现

/**
 * @param {number} value
 * @returns {Uint8Array}
 */
function encode(value) {
  let len = 0
  for (let v = value; v !== 0; v = v >>> 7) {
    len++
  }

  const u = new Uint8Array(len)
  for (let i = len - 1, v = value; v !== 0; i -= 1) {
    u[i] = v & 0b01111111 // 获取最后 7 位
    v = v >>> 7 // 移除最后 7 位

    if (i !== len - 1) { // v[i] 不是最后一组
      u[i] |= 0b10000000 // 首位补 1
    }
  }

  return u
}

/**
 * 解码第一个数字
 * @param {Uint8Array}
 * @returns {number}
 */
function decode(u) {
  let value = 0

  let len = 0
  for (let i = 0; i < u.length; i += 1) {
    len += 1
    if ((u[i] & 0b10000000) === 0) {
      break
    }
  }

  for (let i = 0; i < len; i += 1) {
    // 取 7 位有效位, 并移动到正确位置
    value = value | ((u[i] & 0b01111111) << (7 * (len - 1 - i)));

    if ((u[i] & 0b10000000) === 0) {
      return value;
    }
  }
}

// test
function printEncode(n) {
  const r = []
  encode(n).forEach((v) => {
    r.push(`0x${v.toString(16).padStart(2, 0)}`)
  })

  console.log(n, r)
}

printEncode(8192)
printEncode(16384)
printEncode(128)

console.log(decode(new Uint8Array([129, 9])))
console.log(decode(new Uint8Array([129, 7])))
console.log(decode(new Uint8Array([0xFF, 0x7F])))
console.log(decode(new Uint8Array([0xFF, 0xFF, 0x7F])))
console.log(decode(new Uint8Array([0xC0, 0x80, 0x80, 0x00])))
console.log(decode(new Uint8Array([0xFF, 0xFF, 0xFF, 0x7F])))
console.log(decode(new Uint8Array([0xFF, 0xFF, 0xFF, 0x7F, 0x03])))

VS Code 的实现是从低位开始计数并存储分组，这样更方便解析。仍以 137 举例:

1. 137 的二进制表示 10001001
2. 分组：0000001 0001001
3. 从低位开始计数分组, 那么 0001001 为第一个分组，设置最高位为 1 (10001001);
   0000001 为最后一个分组，设置最高位为 0 (10000001)
4. 存储: new new Uint8Array([0b10001001, 0b10000001])

/**
 * @param {number} value
 * @returns {Uint8Array}
 */
function encode(value) {
  let len = 0
  for (let v = value; v !== 0; v = v >>> 7) {
    len++
  }

  const u = new Uint8Array(len)
  for (let i = 0, v = value; v !== 0; i += 1) {
    u[i] = v & 0b01111111 // 获取最后 7 位
    v = v >>> 7 // 移除最后 7 位

    if (v > 0) { // v[i] 不是最后一组
      u[i] |= 0b10000000 // 首位补 1
    }
  }

  return u
}


/**
 * 解码第一个数字
 * @param {Uint8Array}
 * @returns {number}
 */
function decode(u) {
  let value = 0

  for (let i = 0; i < u.length; i += 1) {
    // 取 7 位有效位, 并移动到正确位置
    const next = (u[i] & 0b01111111) << (7 * i)
    value = value | next

    if ((u[i] & 0b10000000) === 0) {
      return value;
    }
  }
}

function printEncode(n) {
  const r = []
  encode(n).forEach((v) => {
    r.push(`0x${v.toString(16).padStart(2, 0)}`)
  })

  console.log(n, r)
}

console.log(decode(encode(137)))
console.log(decode(new Uint8Array([0x80, 0x80, 0xc4, 0x04])))
console.log(decode(new Uint8Array([0x80, 0x80, 0x9c, 0x03])))

console.log(printEncode(6750208))