Есть такая задачка — например есть две строки

1) красный, оранжевый, зелёный, голубой.
2) красный, оранжевый, зелёный, фиолетовый.

Если смотреть по значениям, то отличие двух строк равно 25%.

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

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

Спасибо.

Здравствуйте, barmaleische, Вы писали:

B>Есть такая задачка — например есть две строки

B>1) красный, оранжевый, зелёный, голубой.
B>2) красный, оранжевый, зелёный, фиолетовый.

B>Если смотреть по значениям, то отличие двух строк равно 25%.

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

B>Одно уточнение — сам список возможных значений заранее определить невозможно, так что вариант с присвоением каждому значению уникального номера не подойдёт.

B>Спасибо.

хэшируй значения отдельно(можно даже какой-нить туфтой типа CRC16 ), потом склеивай результаты

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, barmaleische, Вы писали:

B>>Есть такая задачка — например есть две строки

B>>1) красный, оранжевый, зелёный, голубой.
B>>2) красный, оранжевый, зелёный, фиолетовый.

B>>Если смотреть по значениям, то отличие двух строк равно 25%.

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

B>>Одно уточнение — сам список возможных значений заранее определить невозможно, так что вариант с присвоением каждому значению уникального номера не подойдёт.

B>>Спасибо.

А>хэшируй значения отдельно(можно даже какой-нить туфтой типа CRC16 ), потом склеивай результаты

Не это не совсем то что нужнго, а если структура содержит 100 значений и больше?

Здравствуйте, barmaleische, Вы писали:

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

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

Здравствуйте, barmaleische, Вы писали:

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

Читай про шинглы

Они решают родственную задачу поиска цитат (или похожих текстов). Т.е. цифру тебе никто не даст, но может она и не нужна?

Хотя вру. Есть такой хэш — сама строка. Сравнивая 2 строки с помощью функции Левенштейна можно получить некое число, которое будет характеризовать близость строк. Но нахождение близких таким образом весьма медленно.

Здравствуйте, mihoshi, Вы писали:

M>Здравствуйте, barmaleische, Вы писали:

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

M>Насколько приблизительно?

На данном этапе, пытаюсь понять возможно ли это в принципе.

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

Какого рода будет корреляция? Каую полезную информацию я смогу получить исходя из неё?

Здравствуйте, Kaa, Вы писали:

Kaa>Здравствуйте, barmaleische, Вы писали:

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

Kaa>Читай про шинглы

Kaa>Они решают родственную задачу поиска цитат (или похожих текстов). Т.е. цифру тебе никто не даст, но может она и не нужна?

Kaa>Хотя вру. Есть такой хэш — сама строка. Сравнивая 2 строки с помощью функции Левенштейна можно получить некое число, которое будет характеризовать близость строк. Но нахождение близких таким образом весьма медленно.

Дело в том что имеет смысл сравнение только уже хэшированных значений, которые должны каким то образом сохранять качественную информацию об оригинале. Таким образом можно сравнить два хэш значения и сделать выводу о близости оригиналов. Это возможно в принципе?

Здравствуйте, barmaleische, Вы писали:

B>Это возможно в принципе?

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

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

Здравствуйте, Kaa, Вы писали:

Kaa>Здравствуйте, barmaleische, Вы писали:

B>>Это возможно в принципе?

Kaa>Я о хэшах, коррелирующих между собой пропорционально корреляции исходных текстов — не слышал.

Вот и я не слышал, поэтому и спрашиваю.

Kaa>Кэш, который задает совпадение с заданной точностью — составить можно. Таким образом делается поиск похожих документов в больших поисковиках. Но этот метод поиска не пользуется популярностью, т.к. его результаты работы прии большой базе никто кроме запрограммировавшего их программиста объяснить не может

А есть дополнительная информация об этом?

Здравствуйте, barmaleische, Вы писали:

B>А есть дополнительная информация об этом?

Под рукой нет. Надо искать описания алгоритмов поиска похожих документов. Для этого используется некая сигнатура документа. Весь сыр-бор — вокруг ее способа построения. Однако, действенных широко распространенных методов поиска похожих нет.

Здравствуйте, Kaa, Вы писали:

Kaa>Здравствуйте, barmaleische, Вы писали:

B>>А есть дополнительная информация об этом?

Kaa>Под рукой нет. Надо искать описания алгоритмов поиска похожих документов. Для этого используется некая сигнатура документа. Весь сыр-бор — вокруг ее способа построения. Однако, действенных широко распространенных методов поиска похожих нет.

Ок, спасибо за помощь Алексей.

B>Есть такая задачка — например есть две строки
B>1) красный, оранжевый, зелёный, голубой.
B>2) красный, оранжевый, зелёный, фиолетовый.

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

Попробуй параметрическую корреляцию.
реализацию можешь найти у меня,
n64dev.narod.ru/softcmp.rar

Здравствуйте, mihoshi, Вы писали:


M>Насколько приблизительно?
M>Можешь просто складывать хэши-значения. Тогда матожидание разности сумм для двух сочетаний будет коррелировать с уоличеством различий.

Почему это оно будет коррелировать?

Здравствуйте, Andy77, Вы писали:

A>Здравствуйте, mihoshi, Вы писали:


M>>Насколько приблизительно?
M>>Можешь просто складывать хэши-значения. Тогда матожидание разности сумм для двух сочетаний будет коррелировать с уоличеством различий.

A>Почему это оно будет коррелировать?

Вот и я стараюсь понять почему.

M>>Насколько приблизительно?
M>>Можешь просто складывать хэши-значения. Тогда матожидание разности сумм для двух сочетаний будет коррелировать с уоличеством различий.

A>Почему это оно будет коррелировать?

кросскорреляция например коррелирует сама по себе.
в буквальном, самом прямом смысле этого слова.