В сфере хранения и передачи данных эффективность является решающим аспектом. Одним из способов оптимизации хранения данных является использование схем кодирования целых чисел переменной длины. Base 128 Varints — это популярный метод кодирования, позволяющий компактно представлять целые числа. В этой статье мы рассмотрим различные методы реализации варинтов Base 128, а также приведем примеры кода, иллюстрирующие их использование.

Метод 1: битовый сдвиг и маскирование
Первый метод включает в себя операции битового сдвига и маскировки для кодирования и декодирования вариинтов по основанию 128. Вот пример на Python:

def encode_varint(value):
    encoded_bytes = []
    while value >= 128:
        encoded_bytes.append((value & 0x7F) | 0x80)
        value >>= 7
    encoded_bytes.append(value)
    return bytes(encoded_bytes)

def decode_varint(encoded_bytes):
    value = 0
    shift = 0
    for byte in encoded_bytes:
        value |= (byte & 0x7F) << shift
        if not byte & 0x80:
            break
        shift += 7
    return value

Метод 2: кодирование переменной длины
Другой подход включает кодирование переменной длины, при котором количество байтов, используемых для кодирования целого числа, варьируется в зависимости от его значения. Вот пример на JavaScript:

function encodeVarint(value) {
  const encodedBytes = [];
  while (value >= 128) {
    encodedBytes.push((value & 0x7F) | 0x80);
    value >>= 7;
  }
  encodedBytes.push(value);
  return encodedBytes;
}
function decodeVarint(encodedBytes) {
  let value = 0;
  let shift = 0;
  for (const byte of encodedBytes) {
    value |= (byte & 0x7F) << shift;
    if (!(byte & 0x80)) {
      break;
    }
    shift += 7;
  }
  return value;
}

Метод 3: буферы протокола
Буферы протокола, широко используемый формат сериализации данных, также поддерживают Base 128 Varints в качестве одного из вариантов кодирования. Вот пример на Java:

import com.google.protobuf.CodedOutputStream;
import com.google.protobuf.CodedInputStream;
public byte[] encodeVarint(int value) throws IOException {
  ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
  CodedOutputStream codedOutputStream = CodedOutputStream.newInstance(outputStream);
  codedOutputStream.writeUInt32(value);
  codedOutputStream.flush();
  return outputStream.toByteArray();
}
public int decodeVarint(byte[] encodedBytes) throws IOException {
  ByteArrayInputStream inputStream = new ByteArrayInputStream(encodedBytes);
  CodedInputStream codedInputStream = CodedInputStream.newInstance(inputStream);
  return codedInputStream.readUInt32();
}

Base 128 Varints обеспечивает эффективную схему кодирования для компактного хранения данных. В этой статье мы исследовали три различных метода реализации Varints по основанию 128: от простого сдвига битов и маскировки до использования существующих библиотек, таких как протокольные буферы. Используя эти методы, разработчики могут оптимизировать хранение и передачу данных, добиваясь более эффективного использования ресурсов.

Не забудьте выбрать наиболее подходящий метод, исходя из ваших конкретных требований и языка программирования. Включение переменных Base 128 в ваши приложения может привести к значительному повышению эффективности хранения данных, особенно при работе с большими наборами данных или ограниченными средами.