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

Question

Я ищу что-то вроде хэш-функции, но для которой она выводится тем ближе, чем ближе два разных входа?

Что-то вроде:

f(1010101) = 0 #original hash

f(1010111) = 1 #very close to the original hash as they differ by one bit
f(0101010) = 9999 #not very close to the original hash they all bits are different

(пример выходных данных только для демонстрационных целей)

Все входные данные будут одинаковой длины.

Я хочу провести сравнение между файлом по множеству других файлов и иметь возможность определить, какой другой файл имеет наименьшие отличия от него.

Answer 1

Вас может заинтересовать simhashing или shingling .

Если вы пытаетесь обнаружить только сходство между документами, существуют другие методы, которые могут вам подойтилучше (например, TF-IDF .) Вторая ссылка является частью хорошей книги, другие главы которой посвящены общим темам поиска информации, включая эти другие методы.

Answer 2

Вы можете попробовать этот алгоритм. http://en.wikipedia.org/wiki/Levenshtein_distance

Так как это только строка. Вы можете конвертировать все ваши двоичные файлы в строку например: 0 -> «00000000» 1 -> «00000001»

Answer 3

То, что вы ищете, это своего рода отпечаток файла.Для обычного текста что-то вроде Nilsimsa (http://ixazon.dynip.com/~cmeclax/nilsimsa.html) работает достаточно хорошо.

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

Ссылка выше для nilsimsa дает два аналогичныхспам-сообщения и вот примеры выходных данных:

773e2df0a02a319ec34a0b71d54029111da90838cbc20ecd3d2d4e18c25a3025 spam1
47182cf0802a11dec24a3b75d5042d310ca90838c9d20ecc3d610e98560a3645 spam2
 *  * ** *** * ** ** ** **     *  *******  **** **     *    *  *

Спам и sdhash более полезны для произвольных двоичных данных. Также существуют алгоритмы специально для изображений, которые будут работать независимо от того, является ли это jpg или png.изображения в разных форматах не будут замечены, например, spamsum.

Answer 4

Вы можете представить свои данные в виде двоичного вектора объектов и затем использовать уменьшение размерности либо с SVD , либо с случайным индексированием .

Answer 5

Вы можете рассчитать количество XOR для двух файлов, которое в точности равно количеству битов, которые не совпадают между двумя файлами. Так что он делает именно то, что вы просили, без приближений.

Answer 6

Вы не должны использовать хеш для этого.

Вы должны вычислять подписи, содержащие несколько значений характеристик, таких как:

• имя файла
• размер файла
• Является двоичным / Есть только
• дата (если необходимо)

некоторые другие, более сложные, например:

• дисперсия значений байтов
• среднее значение байтов
• средняя длина последовательности битов одинакового значения (в сжатых файлах нет длинных идентичных последовательностей битов)
• ...

Затем вы можете сравнивать подписи.

Но самое главное - знать, какие данные содержатся в этих файлах.Если это изображения, размер и основной цвет являются более важными.Если это звук, вы можете анализировать только некоторые частоты ...

Answer 7

Возможно, вы захотите взглянуть на исходный код для таких утилит Unix, как cmp или FileCmp в Python, и использовать это, чтобы попытаться определить разумный алгоритм.

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

Если у вас есть некоторые ограничения, их определение может быть полезным.Например, если все файлы имеют одинаковую длину, это может упростить ситуацию.Или, если вас интересуют только различия между битами в одной и той же позиции, и вы не интересуетесь вещами, которые похожи, только если вы сравниваете биты в разных позициях (например, два файла идентичны, за исключением того, что в одном все смещено на три бита - еслисчитаться похожим или не похожим?).