Оптимальный алгоритм кодирования данных в уже существующих данных
Скажем, у нас есть некоторые существующие случайные данные, равномерно распределенные, которые были записаны на какой-то носитель. Допустим также, что запись 1 битов является деструктивным действием, а для 0 битов — неразрушающим. Это может быть аналогично пробиванию отверстий в перфокарте или сжиганию предохранителя в цепи, чтобы жестко закодировать 1. После того, как эта первоначальная запись уже была выполнена, скажем, теперь мы хотим записать дополнительные данные на этот носитель с некоторой специальной кодировкой, которая позволит нам извлекать эти новые данные в будущем, без специальных знаний о ранее существовавших данных, которые были уже деструктивно записано на носитель. Сами ранее существовавшие данные не обязательно должны оставаться доступными — только новые данные.
Также предположим, что новые данные сами по себе случайны или, по крайней мере, уже сжаты, чтобы быть эффективно случайными.
Очевидно, что мы не можем ожидать, что превысим ~50% емкости исходного хранилища, поскольку только примерно половина будет доступна для записи. Проблема в том, чтобы максимально приблизить эффективность к этому пределу.
У меня есть две довольно простые кодировки с, казалось бы, разумной эффективностью, однако они не кажутся оптимальными. Для простоты объяснения я буду предполагать, что носитель представляет собой бумажную ленту с отверстиями (обозначающими 1) или промежутками (обозначающими 0) через равные промежутки времени.
Кодировка А
Кодируйте 1 биты с помощью gap с четным смещением вдоль ленты и 0 битов с gap с нечетным смещением.
Offset: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Tape: G G H H H H H G H H H G H H H H G H H H
| | | | |
New Data: 1 0 0 0 1
Кодировка Б
Закодируйте 1 битов с помощью gap, за которым следует еще один gap, и 0 битов с помощью gap, за которым следует hole.
Offset: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Tape: H G G H H H H G H H H G G H H H G H G H
/ / / / /
New Data: 1 0 1 0 0
Оба они, в среднем, могут кодировать 25% данных исходной емкости хранилища. Это кажется довольно разумным, по крайней мере, для меня - только половина ленты изначально была gap, и любые hole, которые мы записываем, теряют информацию (поскольку мы не можем знать, существовали ли они ранее или нет, когда позже попытаемся декодировать), так четверть- 25%. Сначала кажется, что это может быть оптимальным.
Однако меня беспокоит то, что кажется, что на самом деле это не так. У меня есть несколько более сложная кодировка, которая постоянно нарушает этот порог.
Кодировка С
По сути, мы кодируем 1 биты как серии hole нечетной длины, а 0 биты как серии hole четной длины. Таким образом, HHG будет представлять 0, а HG или HHHG будет представлять 1.
Однако этого самого по себе недостаточно, чтобы преодолеть порог в 25%, поэтому мы добавляем одну оптимизацию. Когда мы видим два последовательных gaps после выполнения holes и его завершение gap, мы рассматриваем эти gaps как 0. Логика этого заключается в том, что если бы мы хотели закодировать 1, мы могли бы просто удалить первый из двух пробелов, создав HG, закодировав 1. Поскольку мы этого не сделали, мы можем предположить, что вместо этого нам нужно было закодировать 0.
С этой оптимизацией кодирование C достигает стабильной эффективности хранения 26,666 +/- 0,005, что постоянно превышает теоретические 25%. У меня также есть несколько действительно хитрых оптимизаций глазка, которые я могу добавить к этой кодировке, что, как я подозреваю, повысит ее эффективность до 28-30%, но мне кажется, что я уже слишком много думаю об этом.
Кодировка D?
На самом деле это не кодировка, а последняя моя мысль, которая может улучшить любую из вышеперечисленных кодировок. Рассмотрим кодировку E(x) и некоторое детерминированное + обратимое преобразование T(x), которое произвольно изменяет данные. Скажем, мы добавляем бит 0 к нашим данным, которые нужно закодировать, и кодируем их- E('0' + DATA). Скажем, мы также мутируем наши данные, добавляем бит 1, а затем кодируем его- E('1' + T(DATA)). Затем мы могли бы сравнить их, посмотреть, какой из них кодирует больше данных (более высокая эффективность), и выбрать его. Улучшение в целом будет небольшим, зависящим от статистической изменчивости, и мы немного пожертвовали в качестве индикатора, но пока данные достаточно велики, средняя экономия будет перевешивать потерю одного бита. Это можно было бы обобщить — разбить данные на несколько разделов и выбрать между двумя или более кодировками, в зависимости от того, что лучше всего подходит случайным образом, но это не относится к делу. В целом, улучшение будет небольшим, но оно все же должно быть прямым улучшением, указывающим на то, что базовое кодирование E(x) не является оптимальным.
Подводя итог, я ищу наиболее эффективное (в среднем случае) кодирование без потерь для записи данных на носитель, который уже был полудеструктивно (только 1) записан с чистыми случайными данными. Я действительно считаю, что оптимальным решением является эффективность где-то между 30-50%, но я борюсь. Я надеюсь, что кто-то может либо поделиться оптимальным кодированием, либо пролить свет на соответствующую литературу/теорию по этой теме.
Примечание: пытаясь лучше понять эту проблему, я попытался создать менее эффективный алгоритм, ограничивающий эффективность кодирования в наихудшем случае где-то выше 0%, но потерпел неудачу. Похоже, какое бы кодирование я ни пробовал, даже если бы половина хранилища была гарантированно доступна для записи, в астрономически маловероятном случае: порядок ранее существовавших данных может гарантировать, что мы не сможем закодировать даже один бит новые данные. На самом деле это не касается фактической постановки задачи, поскольку меня интересует эффективность в среднем случае, но это беспокоило.
@ Дэмиен, я посмотрю на Теорию Шеннона, спасибо за предложение
@Damien У нас нет доступа к первым данным при декодировании вторых
Тестируя метод А, я получаю результат 28,57% ± 0,05%, что кажется значительно выше ваших результатов. Как вы тестировали?
@trincot Очевидно, из-за нехватки данных - с некоторыми математическими вычислениями я получил ожидаемый результат 25%, а затем провел (слишком) небольшой тест для каждого, который дал 25%.
@trincot Теперь я провел гораздо более полный тест на A и B (сравнимый с тестом для кодирования C по размеру / точности), для хранения 20 миллионов бит, и получил тот же результат, что и вы для кодирования A, и получил 22,22% ± 0,05% для кодирования B.
Ответы 2
Я подозреваю, что ожидаемая емкость приближается к 50% в пределе, поскольку число битов n → ∞.
Алгоритм кодирования, который я имею в виду, использует линейную алгебру над конечное поле F2. Заранее выберите ε > 0 и случайный матрица A размерности (1 − ε) n/2 × n. Чтобы декодировать вектор x, если x не все единицы, затем вернуть матрично-векторное произведение A (1 − x); в противном случае, неудача. Чтобы закодировать вектор b, используйте исключение Гаусса, чтобы решить для ненулевой x′ в A′ (1 − x′) = b, где A′ опускает столбцы, соответствующие к существовавшему ранее одному биту, а x 'пропускает строки, соответствующие ранее существовавший один бит. Если нет решения, пробейте шнурок карта .
У меня нет времени писать и проверять формальное доказательство, но моя интуиция состоит в том, что при выборе подматриц матрицы A вероятность того, что мы встретимся линейная зависимость убывает очень быстро по мере удаления ε от нуля.
Я реализовал симуляцию более практичной версии этого алгоритма. в C++ ниже (который может быть расширен до пары кодировщик/декодер без слишком много проблем). Вместо того, чтобы быть всем или ничем, он определяет самый длинный префикс, которым он может управлять, и использует блок как 6-битную длину за которым следует этот объем данных, реализующий ≈38% исходного хранилища. Префикс длины съедает здесь около 9% (мы контролировали ≈47% бит), но приближается к 0% в пределе больших n. Даже с 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";
}
Я буду рад попробовать закодировать это решение, когда у меня будет шанс сегодня. На данный момент у меня есть проблема: не должны ли кодер и декодер заранее согласовать заранее подготовленную матрицу A и значение эпсилон? A на самом деле не должно быть проблемой - это может быть детерминировано сгенерировано из заранее подготовленного начального числа PRNG. Эпсилон, однако, кажется, что это создаст проблему. Как декодер узнает эпсилон, выбранный декодером?
@DillonDavis теоретически эпсилон будет выбран заранее вместе с A, например, поставьте цель в 49% от исходной емкости, и для достаточно большого n кодирование будет успешным с высокой вероятностью. На практике может быть лучше отказаться более изящно, особенно если вы используете блочный вариант для скорости. Я подумаю, как лучше это сделать.
@DillonDavis Я добавил несколько заметок о практической реализации и моделировании C++.
@DillonDavis С удовольствием подумаю о разработке алгоритмов, если вы расскажете мне о своих ограничениях реализации.
Я просто хотел, чтобы вы знали - это не пропало с моего радара, у меня просто появились некоторые вещи за последние пару дней. Я рассмотрю ваш ответ и этот код C++ более подробно, как только смогу; Я хочу быть в состоянии понять и реализовать это
Я попытался закодировать общий алгоритм на Python, но потерпел неудачу — он выдает неправильный результат. Я думаю, что у меня может быть какое-то фундаментальное непонимание вашего алгоритма. Я знаю, что могу столкнуться с проблемами, выполняя GE над целыми числами, а затем уменьшая их до GF2, но сейчас это не основная проблема — у меня много случаев, когда строки A' линейно независимы в GF2, и это все еще дает неправильные выход. Вы случайно не сможете посмотреть? pastebin.com/MUMu4t9J
Если я смогу заставить его работать, я поделюсь кодом здесь, на SO, но пока он кажется неподходящим в качестве дополнительного ответа, поскольку он не работает.
@DillonDavis Я опубликовал рабочий Python, теперь с правильной обработкой префикса длины во всех случаях на случай, если вы видели исходное уведомление об ответе.
Сначала я действительно был сбит с толку новым постом, но последние правки имеют гораздо больше смысла. Я собираюсь принять этот ответ, так как он объясняет основной алгоритм, но я проголосовал за оба. Спасибо за подробное объяснение и за предоставление кода для устранения путаницы
Я реализовал полный алгоритм на 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)))
Теория Шеннона (энтропия) может дать верхнюю границу. Важный момент: при декодировании вторых данных у нас есть доступ к первым данным, то есть к позициям 1?