Алгоритм определения личности файла (Оптимизация)
В дополнение к этому вопросу: Алгоритм определения личности файла
Напомним: я ищу дешевый алгоритм определения идентичности файлов, который работает в большинстве случаев.
Я пошел дальше и реализовал алгоритм, который дает мне "довольно уникальный" хэш для каждого файла.
Мой алгоритм работает так:
Для файлов меньше определенного порога я использую полный контент файлов для хеша идентификации.
Для файлов, превышающих порог, я беру случайные N выборок размера X.
Я включаю размер файла в хэшированные данные. (то есть все файлы с разными размерами приводят к разным хэшам)
Вопросы:
Какие значения я должен выбрать для N и X (сколько случайных выборок я должен взять с каким размером?) Я выбрал 4 выборки по 8 КБ каждая и не могу поставить алгоритм в тупик. Я обнаружил, что увеличение количества выборок быстро снижает скорость работы алгоритма (потому что поиск довольно дорогой)
Математика первая: насколько неизменными должны быть мои файлы, чтобы этот алгоритм взорвался. (2 разных файла одинаковой длины имеют одинаковый хэш)
Оптимизация одна: есть ли способы, которыми я могу оптимизировать свою конкретную реализацию для повышения пропускной способности (кажется, я могу делать около 100 файлов в секунду в моей системе).
Эта реализация выглядит вменяемой? Можете ли вы вспомнить какие-либо примеры из реальной жизни, где это не получится. (Мой фокус на медиа-файлах)
Релевантная информация:
Алгоритм, который я реализовал
Спасибо за вашу помощь!
3 ответа
- Всегда включайте 1-й и последний блок файла в хеш.
Это потому, что они, скорее всего, будут отличаться от файла к файлу. Если вы рассматриваете BMP, он может иметь довольно стандартный заголовок (например, изображение 800x600, 24 бита, нулевой остаток), поэтому вы можете захотеть немного перескочить заголовок, чтобы добраться до дифференцирующих данных. Проблема в том, что заголовки сильно различаются по размеру.
Последний блок предназначен для форматов файлов, которые добавляют данные к оригиналу.
- Читайте в блоках размера, который является родным для файловой системы, которую вы используете, или, по крайней мере, делится на 512.
- Всегда считывайте блоки со смещением, которое делится на размер блока.
- Если вы получаете то же самое для файла того же размера, сделайте его глубокое сканирование (хэшируйте все данные) и запомните путь к файлу, чтобы не сканировать его снова.
Даже тогда, если вам не повезет, вы ошибочно определите некоторые файлы как одинаковые (например, файл базы данных SQL Server и его резервная копия 1:1 после нескольких вставок; за исключением того, что SS действительно записывает метку времени...)
Я бы избежал такого решения. Я практикую, может быть, почти невозможно, чтобы два медиа-файла имели одинаковый размер и одинаковые данные в основных положениях для сжатых форматов. Но если вам приходится иметь дело с несжатыми изображениями или волновыми файлами, вероятность того, что небольшие локальные изменения не будут обнаружены, возрастет.
Поэтому я думаю, что вы должны действительно хэшировать весь файл. Хотя это кажется дорогим, это может быть не так, если у вас есть доступ ко всем файлам - например, если вы создаете файловый сервер или что-то в этом роде. Вы можете создавать хэш постепенно.
Если вы видите новый файл с уникальной длиной, просто сохраните длину файла. Если добавляется другой файл с такой же длиной, вычисляйте хэши обоих файлов по блокам, пока они не будут различаться. Сохраните длину файла, хеш и сколько блоков файла включены в хеш. Всякий раз, когда вы обнаруживаете совпадающие длины файла и хэши, и вы еще не хэшировали весь файл, вы расширяете хеш, добавляя больше блоков.
Несколько мыслей о спектакле. Для небольших файлов шансы одинаковой длины файла довольно высоки - не так много разных небольших длин файлов. Но это не дорого, чтобы хэшировать небольшие файлы.
Для больших файлов шансы столкновения длины файла уменьшаются, поскольку появляется все больше и больше возможных длин файлов. Для разных медиа-файлов очень велики шансы, что они отличаются непосредственно за заголовком, поэтому вам нужно будет хэшировать только короткую часть начала файла.
Наконец, вы обязательно обнаружите разные файлы (за исключением коллизий хешей), потому что при необходимости вы будете хешировать весь файл.
ОБНОВИТЬ
Для фильмов я бы посчитал, что длина файла практически уникальна, но файлы, перекодированные для размещения на данном носителе, вероятно, лишают эту идею смысла - (S) фильмы VCD будут иметь небольшой диапазон длин файлов примерно на CD-ROM.
Но для файлов фильмов в целом, я бы просто хэшировал один блок (возможно, 512 байт) от середины файла. Два разных фильма с одинаковым изображением и звуком в одной позиции? Практически невозможно, кроме того, что вы манипулируете файлами, чтобы не пройти этот тест. Но вы можете легко сгенерировать файлы, чтобы потерпеть неудачу во всех стратегиях детерминированной выборки, поэтому это не должно иметь большого значения
- Не ищите в обратном направлении и откройте файл с помощью FILE_FLAG_SEQUENTIAL_SCAN (в Windows).
(Выберите X случайных чисел, затем сортируйте их). - Чтобы искать далеко, обычно есть некоторые данные в кеше чтения.
- Если у вас большие файлы, отформатируйте ваш раздел, чтобы иметь большой размер сектора.
- Вы возвращаете Guid для Id, алгоритмы хеширования Must должны иметь более 128 бит.