Есть ли какой-то помехоустойчивый алгоритм, который игнорирует ошибки во входящем буфере, без хранения первоначального состояние?

Question

[Ninazu]

Интересует хеширование, не чувствительное для мелких изменений начальных данных с уровнем мутации до 1%.

Тоесть при любой модификации, с любым прасределением 10 байт из 1024 информации, на выходе всегда был один и тот же буфер из минимум 32 байт. Но при модификации скажем 20 байт, выходной буфер был другим уже.

Comments

[Сергей Соколов]

здесь какое-то противоречие..

1. Ничего не меняли, хэш А.
   
2. Поменяли 10 первых байт, хэш А.
   
3. Поменяли другие 10 байт, хэш все равно А.
   

Варианты 2 и 3 отличаются друг от друга уже 20-ю байтами, но имеют одинаковый хэш! ЧЯДНТ?

[Rsa97]

Добавлю
0. Исходные данные, хэш A.
1. Меняем первые 10 байт. Хэш по прежнему A.
2. Теперь, приняв данные из шага 1 за исходные, меняем вторые 10 байт. Хэш остаётся A.
...
n. Приняв данные из шага n-1 за исходные, меняем последние байты. Хэш остаётся A.
Таким образом мы полностью поменяли все данные, но хэш по прежнему остался A.

[Ninazu]

Сергей Соколов, Логично) Возможно я как-то не так выразился или сам запутался.

Может есть идеи, как для двух разных потоков, которые о существовании друг друга не знают ничего, и немного отличающихся входных данных прийти к консенсусу, и выдать один и тот же идентификатор

[Владимир Олохтонов]

Ninazu, это зависит от природы данных, нужно больше подробностей.

[Ninazu]

Владимир Олохтонов, Природа данных не должна играть какой либо роли. Воспринимаем последовательность как случайную.

[Сергей Соколов]

Ninazu, можно. Но зависит )
Например, на вход валятся точки (x, y) которые обозначают какую-то линейную зависимость в реальном физическом эксперименте, и поэтому все отличаются от идеальной прямой, но лежат где-то около.
И таких набора данных два. И оба «имеют в виду» одну и ту же y = Ax + B
Для таких двух наборов можно посчитать для каждого свои A и B, и потом сравнив две пары (A, B) сделать вывод, что они, в общем-то очень близки (насколько?).

[Владимир Олохтонов]

Ninazu,
Такого рода задачами занимается теория информации (это чтобы было куда копать).

Вы, для своей задачи, можете применять например выравнивание над битовыми представлениями данных, или то же расстояние Левенштейна.

Если две последовательности отличаются не слишком сильно, то они ложатся в один бакет, поиск происходит путём сравнения новой последовательности со всеми имеющимися, такая кластеризация для бедных.

Если ваши данные всё-таки не совсем случайные, то можно придумать более хорошее решение.

[АртемЪ]

Может есть идеи, как для двух разных потоков, которые о существовании друг друга не знают ничего, и немного отличающихся входных данных прийти к консенсусу, и выдать один и тот же идентификатор

Не совсем понятно.
Возможно вам нужно фильтровать шумы, и случайные всплески?
Два разных потока в норме должны нести одну и ту же информацию? Или как?

[Ninazu]

АртемЪ, интересен алгоритм подобный тому который используется для распознавании лиц. С одной оговоркой что что система должна наполнятся сама и не хранить исходники. Тоесть допустим база пуста, я загружаю свою фотографию, из нее формируется идентификатор, но сама моя фотография из которой он получился не хранится. И если я завтра изменю имидж то новая запись не создастся, так как система опознает меня, а вот мой брат который хоть на меня и похожий но всё же добавится в систему, так как его набор контрольных точек отличается.

[d'Ivan]

Ninazu, тогда это не хэш, а набор весов.

Answer 1

[Lander]

Код Хэмминга подойдёт?

Comments

[Ninazu]

Наверное что нет. Код Хэмминга может исправить 1 ошибку, а не процент ошибок, и как понимаю ошибка исправляется в транслирующем буфере а не изменении начального