Минимальный двоичный diff для аналогичных 1000-байтовых блоков со статическим шумом?

Мне нужна минимальная разница для похожих блоков по 1000 байт. Эти блоки будут отличаться не более чем на 20% битов. Перевернутые биты будут похожи на радиопомехи — случайным образом перевернутые биты с равномерным распределением по всему блоку. Вот мой псевдокод, использующий сжатие XOR и lzo:

minimal_diff=lzo(XOR(block1,block2))

Поскольку блоки небольшие, я использую сжатие lzo в надежде, что этот формат сжатия имеет минимальный шаблон.

Я рассмотрел такие алгоритмы, как xdelta и bsdiff, но они не будут работать для случайного статического шума, подобного этому. Они больше ориентированы на поиск смещенных последовательностей байтов.

Могут ли здесь работать коды исправления ошибок для создания минимальной разницы? Как именно?

Точные алгоритмы были бы хороши. Если это просто теория исследовательской работы, а не реализованная, то меня это не интересует.

ПРИМЕЧАНИЕ. Одинаковые биты в каждом блоке выстраиваются в линию. Сдвига нет. Есть только случайные перестановки битов шума, которые различают блоки.


python algorithm diff
person user213060    schedule 24.11.2009    source источник

Ответы (2)


arrow_upward
3
arrow_downward

если это действительно случайный шум, то он действительно не сжимается. Это означает, что если у вас есть 8000 бит (1000 байт x 8 бит/байт) и каждый отдельный бит имеет 1/5 (20%) вероятность переворачивания, то вы не сможете закодировать измененные биты менее чем за 8000 x (-4). /5 x ln2 4/5 + -1/5 x ln2 1/5) = 8000 x (-4/5 x -0,322 + -1/5 x -2,322) = 8000 x (0,2576 + 0,4644) = 5776 бит, т.е. 722 байта. Это основано на теории информации Шеннона.

Поскольку тривиальный способ представления измененных битов занимает 1000 байт (просто закодируйте XOR двух блоков), вы можете сэкономить не более 30% пространства за счет сжатия. Если вы постоянно достигаете большего, то биты не распределяются случайным образом или вероятность переворота битов составляет менее 20%.

Стандартные алгоритмы, такие как Lempel-Ziv, предназначены для структурированных данных (то есть данных, которые не являются случайным шумом). Случайный шум, подобный этому, лучше всего кодируется простым кодированием Хаффмана и подобными вещами. Но вы можете сэкономить не более 30%, так что вопрос в том, стоит ли это затраченных усилий.

person Antti Huima    schedule 25.11.2009
comment
В своем сообщении вы сказали, что будет отличаться не более 20% битов, а не 20% байтов. - person Jason Orendorff; 26.11.2009
comment
С 20% различий битов я получаю в среднем 821 байт с zlib. 996 с bz2, который должен быть байт-ориентированным. - person Jason Orendorff; 26.11.2009
comment
Да, случайное ИЗМЕНЕНИЕ 20% БАЙТОВ сильно отличается от ИЗМЕНЕНИЯ 20% битов. - person Antti Huima; 26.11.2009
comment
Продолжая это, обратите внимание, что если вы измените 20% байтов на случайные байты, вы фактически перевернете только 10% битов (потому что изменение бита на случайный бит перевернет его только с 50% вероятностью). Кроме того, перевороты битов коррелированы. Это значительно снижает количество энтропии. - person Antti Huima; 26.11.2009

arrow_upward
0
arrow_downward

Вы уже пробовали стандартные алгоритмы сжатия? Какой спектакль вы видите? Вы должны получить довольно хорошие коэффициенты сжатия при xor старых и новых блоков из-за высокого смещения в сторону 0.

Помимо стандартных опций, одна из альтернатив, которая приходит на ум, заключается в кодировании каждого diff в виде списка целых чисел переменной длины, определяющих расстояние между перевернутыми битами. Например, используя 5-битные целые числа переменной длины, вы можете описать промежутки до 16 бит в 5 битах, промежутки от 17 до 1024 бит в 10 битах и ​​так далее. Если в интервалах между перевернутыми битами есть какая-то закономерность, вы можете использовать обычный компрессор для этой кодировки для дополнительной экономии.

person Nick Johnson    schedule 25.11.2009