在预先存在的数据中对数据进行编码的最佳算法

我怀疑预期容量接近限制的 50%，因为 位数 n → ∞。

我想到的编码算法使用线性代数 有限域 F₂.提前选择 ε > 0 和随机 维数为 （1 − ε） n/2 × n 的矩阵 A。解码向量 x，如果 x 不是 所有 1，则返回矩阵向量乘积 A （1 − x）;否则 失败。要对向量 b 进行编码，请使用高斯消元法求解 A′ （1 − x′） = b 中的非零 x′，其中 A′ 省略对应的列 到预先存在的一位，x′ 省略对应于 预先存在的一位。如果没有解决方案，就打花边 卡。

我没有时间写和验证正式证明，但我的直觉 是，在获取 A 的子矩阵时，我们遇到的概率 线性依赖性随着ε边远离零而迅速降低。

我实现了该算法的更实用版本的模拟 在下面的 C++ 中（可以扩展到编码器/解码器对，而无需 太麻烦了）。它不是全有或全无，而是决定了 它可以控制的最长前缀，并将块用作 6 位长度 其次是该数据量，实现了原始存储的 ≈38%。 长度前缀在这里吃掉了大约 9%（我们控制了 ≈47% 的 bits），但在 large-n 限制中接近 0%。即使使用 64 位 块，你可以通过霍夫曼编码长度来做得更好。

（您可能想知道，如果我们甚至无法控制所有 长度位。我们可以进行设置，以便花边卡解码为 长度 0，这意味着它被跳过，然后打一张花边卡 每当必须发生这种情况时。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#include <optional>
#include <random>
#include <vector>

namespace {

static std::random_device g_dev;

class Vector {
public:
  explicit Vector() = default;
  static Vector Random() {
    return Vector{std::uniform_int_distribution<Bits>{
        0, std::numeric_limits<Bits>::max()}(g_dev)};
  }
  Vector &operator^=(const Vector v) {
    bits_ ^= v.bits_;
    return *this;
  }
  bool operator[](const std::size_t i) const { return bits_ & (Bits{1} << i); }

private:
  using Bits = unsigned long long;
  explicit Vector(const Bits bits) : bits_{bits} {}
  Bits bits_ = 0;
};

class Matrix {
public:
  static Matrix Random(const std::size_t num_rows) {
    Matrix a;
    a.rows_.reserve(num_rows);
    for (std::size_t i = 0; i < num_rows; ++i) {
      a.rows_.push_back(Vector::Random());
    }
    return a;
  }

  Matrix RandomSubsetOfRows(const double p) const {
    Matrix a;
    for (const Vector row : rows_) {
      if (std::bernoulli_distribution{p}(g_dev)) {
        a.rows_.push_back(row);
      }
    }
    return a;
  }

  std::size_t NumControllablePrefixBits() && {
    for (std::size_t j = 0; true; ++j) {
      const auto pivot = [&]() -> std::optional<std::size_t> {
        for (std::size_t i = j; i < rows_.size(); ++i) {
          if (rows_[i][j]) {
            return i;
          }
        }
        return std::nullopt;
      }();
      if (!pivot) {
        return j;
      }
      std::swap(rows_[j], rows_[*pivot]);
      for (std::size_t i = 0; i < rows_.size(); ++i) {
        if (i != j && rows_[i][j]) {
          rows_[i] ^= rows_[j];
        }
      }
    }
  }

private:
  std::vector<Vector> rows_;
};

} // namespace

int main() {
  static constexpr std::size_t kBlocks = 10000;
  static constexpr std::size_t kLogBlockSize = 6;
  static constexpr std::size_t kBlockSize = 1 << kLogBlockSize;
  std::size_t num_usable_bits = 0;
  const Matrix a = Matrix::Random(kBlockSize);
  for (int i = 0; i < kBlocks; ++i) {
    num_usable_bits +=
        a.RandomSubsetOfRows(0.5).NumControllablePrefixBits() - kLogBlockSize;
  }
  std::cout << static_cast<double>(num_usable_bits) / (kBlocks * kBlockSize)
            << "\n";
}

我在 Python 中实现了完整的算法。我用单位矩阵来扩充矩阵，就像矩阵反演算法一样，但将对应于孔的列归零。

import math
import random

log_n = 10
n = log_n + ((1 << log_n) - 1)
matrix = [random.randrange(1 << n) for j in range(n)]


def decode(data):
    text = 0
    for j in range(n):
        if (data & (1 << j)) == 0:
            text ^= matrix[j]
    return text


def invert(existing_data):
    sub = [matrix[j] for j in range(n) if (existing_data & (1 << j)) == 0]
    inverse = [1 << j for j in range(n) if (existing_data & (1 << j)) == 0]
    i = 0
    while True:
        for k in range(i, len(sub)):
            if sub[k] & (1 << i):
                break
        else:
            return inverse[:i]
        sub[i], sub[k] = sub[k], sub[i]
        inverse[i], inverse[k] = inverse[k], inverse[i]
        for k in range(len(sub)):
            if k != i and (sub[k] & (1 << i)):
                sub[k] ^= sub[i]
                inverse[k] ^= inverse[i]
        i += 1


def encode(inverse, text):
    data = ~((~0) << n)
    for i in range(len(inverse)):
        if text & (1 << i):
            data ^= inverse[i]
    return data


def test():
    existing_data = random.randrange(1 << n)
    inverse = invert(existing_data)
    payload_size = max(len(inverse) - log_n, 0)
    payload = random.randrange(1 << payload_size)
    text = payload_size ^ (payload << log_n)
    data = encode(inverse, text)
    assert (existing_data & ~data) == 0

    decoded_text = decode(data)
    decoded_payload_size = decoded_text & (~((~0) << log_n))
    decoded_payload = (decoded_text >> log_n) & (~((~0) << payload_size))
    assert payload_size == decoded_payload_size
    assert payload == decoded_payload
    return payload_size / n


print(sum(test() for i in range(100)))