Моя цель - эффективно выполнить исчерпывающее сравнение дерева каталогов. Учитывая набор файлов F, я должен вычислить классы эквивалентности EQV = [F₁, F₂, F₃, ... Fₙ] так, чтобы fⱼ, fₖ ∈ EQV[i] iff (fⱼ is identical to fₖ) for all i, j, k.
Мой общий подход состоит в том, чтобы начать с одного большого класса, содержащего все начальные файлы, EQV₀ = [[f₁, f₂, ..., fₙ]], и неоднократно разбивать его на более совершенные классы EQV₁, EQV₂... EQVₘ₋₁ на основе некоторых m эвристик, например, размер файла, функция контрольной суммы 1, контрольная сумма 2. После применения всех m эвристик (EQVₘ₋₁) необходимо провести попарное сравнение всех файлов в каждом классе в EQVₘ₋₁. Поскольку этот последний шаг является квадратичным для каждого из классов в EQVₘ₋₁, т.е.
O(sum(n² for n in map(len, EQVₘ₋₁)) )
и, вероятно, будет узким местом моего алгоритма, если каждое разбиение m выполняется за линейное время, моя цель - сделать EQVₘ₋₁ как можно более плоским.
Я хотел бы иметь доступ к множеству хороших хеш-функций, которые я могу применить для минимизации коллизий на EQVₘ₋₁. Моя текущая идея состоит в том, чтобы использовать некоторую функцию контрольной суммы, предоставляемую библиотекой, такую как adler, и генерировать ее варианты, просто применяя ее к разным начальным байтам в файле. Другой — сначала применить быстрые хэш-функции, такие как adler, а затем более дорогие, такие как md5, только к тем классам, которые все еще слишком велики.
Учитывая, что я могу вычислить все хэши для данного файла всего за одно чтение этого файла, как я могу вычислить множество хэшей, которые помогут мне различать неидентичные файлы?
В качестве альтернативы, каков хороший список хэш-функций, доступных в python, которые не являются криптографически безопасными?
Редактировать: кажется, что другая идея использует «отпечаток пальца рабина» на основе фиксированного набора случайно сгенерированных входных данных. Будет ли это иметь смысл для этой цели? http://en.wikipedia.org/wiki/Rabin_fingerprint
