Алгоритм определения личности файла (Оптимизация)

Question

В дополнение к этому вопросу: Алгоритм определения личности файла

Резюме : Я ищу дешевый алгоритм для определения идентичности файлов, который работает подавляющее большинство времени.

Я реализовал алгоритм, который дает мне " довольно уникальный " хэш для файла.

Мой алгоритм работает так:

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

• Для файлов, превышающих пороговое значение, я беру случайные N выборок размера X.

• Я включаю размер файла в хэшированные данные. (то есть все файлы с разными размерами приводят к разным хэшам)

Вопросы:

• Какие значения я должен выбрать для N и X (сколько случайных выборок мне взять, какого размера?) Я выбрал 4 выборки по 8 КБ каждая и не могу поставить алгоритм в тупик. Я обнаружил, что увеличение количества выборок быстро снижает скорость работы алгоритма (потому что поиск довольно дорогой)

• Математика первая: насколько неизменными должны быть мои файлы, чтобы этот алгоритм взорвался. (2 разных файла одинаковой длины имеют одинаковый хэш)

• Оптимизация: есть ли способы, которыми я могу оптимизировать свою конкретную реализацию для повышения пропускной способности (мне кажется, я могу делать около 100 файлов в секунду в моей системе).

• Эта реализация выглядит вменяемой? Можете ли вы привести примеры из реальной жизни, где это не получится. (Я сосредоточен на медиа-файлах)

Соответствующая информация:

Алгоритм, который я реализовал

Спасибо за вашу помощь!

Answer 1

• Всегда включайте 1-й и последний блок файла в хеш.

Это потому, что они, скорее всего, будут отличаться от файла к файлу. Если вы рассматриваете BMP, он может иметь довольно стандартный заголовок (например, изображение 800x600, 24 бита, нулевой остаток), поэтому вы можете захотеть немного перескочить заголовок, чтобы получить дифференцирующие данные. Проблема в том, что заголовки сильно различаются по размеру.

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

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

Даже тогда, если вам не повезет, вы ошибочно определите некоторые файлы как одинаковые (например, файл базы данных SQL Server и его резервная копия 1: 1 после нескольких вставок; за исключением того, что SS действительно записывает метку времени ..)

Answer 2

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

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

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

Несколько мыслей о спектакле. Для небольших файлов шансы одинаковой длины файла довольно высоки - не так много разных небольших длин файлов. Но хэшировать небольшие файлы не дорого.

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

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

UPDATE

Для фильмов я бы посчитал, что длина файла практически уникальна, но файлы, перекодированные для размещения на данном носителе, вероятно, лишают эту идею смысла - (S) Все фильмы VCD будут иметь небольшой диапазон длин файлов примерно на CD-ROM. .

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

Answer 3

1. Не ищите назад и не открывайте файл с помощью FILE_FLAG_SEQUENTIAL_SCAN (в Windows).
   (Выберите X случайных чисел, затем отсортируйте их).
2. Чтобы искать далеко, обычно есть некоторые данные в кэше с опережающим чтением.
3. Если у вас большие файлы, отформатируйте раздел так, чтобы он имел большой размер сектора.
4. Вы возвращаете Guid для идентификатора, алгоритмам хэша Must нужно более 128 бит.