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

Question

Для проекта с открытым исходным кодом я пишу слой абстракции поверх файловой системы.

Этот слой позволяет мне прикреплять метаданные и отношения к каждому файлу.

Я бы хотел, чтобы слой корректно обрабатывал переименования файлов и поддерживал метаданные, если файл переименовывается / перемещается или копируется.

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

Итак, я думал об алгоритме, который, хотя и не на 100% правильный, будет прав в подавляющем большинстве случаев и дешев.

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

Какие байты выбрать для образца? Как сделать расчет дешевым и достаточно точным? Я понимаю, что здесь есть компромисс, но производительность критична. И пользователь сможет обрабатывать ситуации, когда система допускает ошибки.

Мне нужен этот алгоритм для работы с очень большими файлами (1 ГБ + и маленькими файлами 5 КБ)

РЕДАКТИРОВАТЬ

Мне нужен этот алгоритм для работы с NTFS и всеми общими папками SMB (на основе linux или windows), я хотел бы, чтобы он поддерживал ситуации, когда файл копируется из одного места в другое (существует 2 физических копии, которые рассматриваются как одна личность) , Я могу даже подумать о том, чтобы это работало в ситуациях, когда MP3-файлы повторно помечены (физический файл изменен, поэтому у меня может быть поставщик удостоверений для каждого типа файла).

РЕДАКТИРОВАТЬ 2

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

Answer 1

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

Первый уровень индексации - это только длина файла.

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

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

Answer 2

Делайте первые 128 КБ, еще 128 КБ на отметке 1 МБ, еще 128 КБ на отметке 10 МБ, еще 128 КБ на отметке 100 МБ, еще 128 КБ на отметке 1000 МБ и т. Д. По мере увеличения размеров файлов это становится более вероятным что вы сможете различать два файла, основываясь только на их размере, вы хешируете все меньшую и меньшую часть данных. Все под 128 КБ позаботится полностью.

Answer 3

Если вы можете отказаться от требований к общим ресурсам Linux и ограничиться NTFS, то альтернативные потоки данных NTFS станут идеальным решением, которое:

• не требует никакого хеширования;
• переживает переименования; и
• выдерживает ходы (даже между различными томами NTFS).

Подробнее об этом можно прочитать здесь . По сути, вы просто добавляете двоеточие и имя для своего потока (например, «: мета») и пишете в него все, что вам нравится. Поэтому, если у вас есть каталог «D: \ Movies \ Terminator», запишите свои метаданные с помощью обычного файлового ввода-вывода в «D: \ Movies \ Terminator: meta». Вы можете сделать то же самое, если хотите сохранить метаданные для определенного файла (в отличие от целой папки).

Если вы предпочитаете хранить свои метаданные в другом месте и просто иметь возможность обнаруживать перемещения / переименования на том же томе NTFS, вы можете использовать вызов API GetFileInformationByHandle (см. MSDN / en-us / library / aa364952 (VS 85) .aspx) для получения уникального идентификатора папки (объедините элементы VolumeSerialNumber и FileIndex). Этот идентификатор не изменится, если файл / папка будет перемещен / переименован на том же томе.

Answer 4

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

Answer 5

Как насчет хранения некоторых случайных целых чисел r _i и поиска байтов (r _i mod n), где n - размер файла? Для файлов с заголовками вы можете сначала их игнорировать, а затем выполнить этот процесс для оставшихся байтов.

Если ваши файлы на самом деле довольно разные (не просто разница где-то в одном байте, а, скажем, разница не менее 1%), то случайный выбор байтов это заметит. Например, при разнице в 1% в байтах 100 случайных байтов не будут замечены с вероятностью 1 / e ~ 37%; увеличение количества байтов, на которые вы смотрите, уменьшает эту вероятность в геометрической прогрессии.

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

Еще несколько советов:

• Вместо того, чтобы захватывать байты, берите большие куски, чтобы оправдать стоимость поиска.
• Я бы посоветовал всегда смотреть на первый блок файла или около того. Из этого вы можете определить тип файла и тому подобное. (Например, вы можете использовать программу file.)
• По крайней мере, взвесьте стоимость / выгоду чего-то вроде CRC всего файла. Это не так дорого, как настоящая криптографическая хеш-функция, но все же требует чтения всего файла. Плюс в том, что заметит разницу в один байт.

Answer 6

Эта работа звучит так, как будто она может быть более эффективно реализована на уровне файловой системы или с некоторой неопределенностью системы управления версиями (оба?).

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

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

Answer 7

Какие байты выбрать для образца?

Я думаю, что я бы попытался использовать некоторую арифметическую прогрессию, такую ​​как числа Фибоначчи. Их легко рассчитать, и они имеют уменьшающуюся плотность. Маленькие файлы имеют более высокий коэффициент выборки, чем большие файлы, и образец все равно будет проходить через точки во всем файле.

Answer 8

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

На самом деле, это весь смысл многоуровневой многоуровневой файловой системы, которую вы можете расширить различными способами, например, для поддержки сжатия или шифрования. Это то, что "vnodes" все о. Вы могли бы сделать это несколькими способами. Отчасти это зависит от платформы, на которую вы смотрите. Это намного проще в системах UNIX / Linux, которые используют концепцию VFS. Например, вы можете реализовать свой собственный слой в топе ext3 или что у вас есть.

** После прочтения ваших правок, больше вещей. Файловые системы уже делают это, как упоминалось ранее, используя такие вещи, как inode. Хеширование, вероятно, будет плохой идеей не только потому, что это дорого, но и потому, что два или более прообраза могут иметь одно и то же изображение; то есть два совершенно разных файла могут иметь одинаковое хешированное значение. Я думаю, что вы действительно хотите использовать метаданные того, что файловая система уже предоставляет. Это было бы проще в системе с открытым исходным кодом, конечно. :)