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

Question

В дополнении к этому вопросу: Algorithm for determining a file’s identity

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

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

Путь мой алгоритм работы является:

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

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

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

Вопросов:

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

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

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

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

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

The algorithm I implemented

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

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 для Id, для алгоритмов hash требуется более 128 бит.