Глава 23 · Часть IV · Реализуем SafeSort

Находим группы дубликатов

Одна функция превращает список файлов в группы подтверждённых дубликатов и ничего не удаляет.

SafeSort · Часть 4 из 6
Git и GitHubПланированиеПроектРеализацияТесты и CIРелиз

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

src/safesort/duplicates.py
def files_equal(path_a: Path, path_b: Path, chunk_size: int = DEFAULT_CHUNK_SIZE) -> bool:
    """Финальное подтверждение — совпадающий дайджест не гарантия."""
    with path_a.open("rb") as file_a, path_b.open("rb") as file_b:
        while True:
            chunk_a = file_a.read(chunk_size)
            chunk_b = file_b.read(chunk_size)
            if chunk_a != chunk_b:
                return False
            if not chunk_a:
                return True

def find_duplicates(files: list[FileInfo]) -> list[DuplicateGroup]:
    by_size = defaultdict(list)
    for file in files:
        by_size[file.size].append(file)

    groups = []
    for size, candidates in by_size.items():
        if len(candidates) < 2:
            continue
        by_digest = defaultdict(list)
        for candidate in candidates:
            digest = sha256_file(candidate.path)
            by_digest[digest].append(candidate)
        for digest, matched in by_digest.items():
            if len(matched) < 2:
                continue
            exact_groups = []
            for candidate in matched:
                for exact_group in exact_groups:
                    if files_equal(exact_group[0].path, candidate.path):
                        exact_group.append(candidate)
                        break
                else:
                    exact_groups.append([candidate])
            for exact_group in exact_groups:
                if len(exact_group) >= 2:
                    groups.append(DuplicateGroup(size=size, digest=digest, files=tuple(exact_group)))
    return groups

Один bucket с одинаковыми размером и дайджестом остаётся только набором кандидатов. Алгоритм сравнивает кандидата с представителем каждой уже найденной группы: при равенстве добавляет его туда, иначе создаёт новый класс. Поэтому даже искусственно вызванная коллизия SHA-256 может дать несколько независимых групп точного содержимого.

Тест-чекпойнт: два одинаковых файла

tests/test_duplicates.py
def test_equal_content_forms_one_group(tmp_path):
    a = tmp_path / "a.bin"
    b = tmp_path / "b.bin"
    a.write_bytes(b"same")
    b.write_bytes(b"same")

    groups = find_duplicates(scan(tmp_path, Config()))

    assert len(groups) == 1
    assert {item.path for item in groups[0].files} == {a, b}
files_equal() — та же идея, что и sha256_file(): читать блоками
Побайтовая сверка читает оба файла кусками по мегабайту и сравнивает кусок с куском, а не загружает файлы в память целиком — то же соображение, что и на предыдущей странице про sha256_file(). Как только один из кусков не совпал, сравнение сразу останавливается: незачем дочитывать оставшуюся часть заведомо разных файлов.
Пустые файлы тоже могут быть дубликатами
Два файла нулевого размера побайтово идентичны: у обоих попросту нет байтов. find_duplicates() не делает для этого случая никакого исключения — они естественно попадают в одну группу по размеру (0) и в одну группу по дайджесту пустого содержимого. Позже мы проверим это отдельным тестом.

Реальный вывод команды duplicates для каталога с тремя парами совпадений:

~/safesort $ safesort duplicates ~/Downloads
Found 3 duplicate group(s):
Group 1: 2 files, 2097289 bytes each, sha256=44f70488694a224316549d0752fe6fdec636df12d58e85681eacc85e180b1f8c
Downloads/bigfile_b.dat
Downloads/bigfile_a.dat
Group 2: 2 files, 0 bytes each, sha256=e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
Downloads/empty_b.bin
Downloads/empty_a.bin
Group 3: 2 files, 28 bytes each, sha256=f3b439399a805a21e826bbd4111ca4c4615e492934f53bbb2be042e7c97530cc
Downloads/copy_of_notes.txt
Downloads/notes.txt
duplicates сообщает о группах и не удаляет файлы
Первая версия программы не удаляет ни один файл из найденной группы, и в коде find_duplicates() нет ни одного вызова, который удаляет файлы, даже отключённого или закомментированного. Автоматическое удаление дубликатов сознательно вынесено за рамки первой версии: решение о том, какой из одинаковых файлов оставить, требует контекста, которого у программы нет.
Практика: группируем файлы в дубликаты
Интерактивный ноутбук в браузере: Python 3.14 через Pyodide, без установки
Открыть практику →
Чекпойнт · Issue #9
git commit -m "feat: add duplicate detection with byte-level confirmation"
Слился как Pull Request #20. Три страницы (23-17–23-19) книги соответствуют одному PR в репозитории: группировка по размеру, хеш и байтовое подтверждение относятся к одному Issue, который объяснён по шагам.
Статус в реальном Project: Done