Seunghyun Yoo

Posts | Development | About

[KR] How to find duplicates efficiently

컴퓨터를 사용하다보면 중복 파일들이 생긴다. 같은 파일들을 찾아내는 일이야 hash_sum(file_contents)으로 그룹을 만든 다음 (a) hash값이 같으면 ‘거의’ 같은 파일로 간주하거나 (b) 정 못 미더우면 byte-to-byte 비교를 하는 방법이 있다. hash들을 섞어쓰면 (b)에서 충돌이 발생할 확률은 극히 적어서 차라리 디스크가 갑자기 날아갈 확률이 더 높다고 할 수 있겠다.

여튼 (file_size, sha256_sum, md5_sum) 정도로 tuple을 만들어서 그룹을 만들게 되는데, 주의해야할 점이 있다. 하나의 파일에 대해서 접근하는 경로가 여럿일 수 있다는 점. 네트워크 드라이브와 같은 곳에서 중복이라고 생각하고 파일을 지웠는데, 다른 경로가 소위 “dangling pointer”가 되버리는 경우다. 아니면 symbolic link를 따라가서 파일을 읽게 되면 원래 파일을 지우고 symbolic link를 남겨두는 식이다. hard link는 파일 시스템에서 reference count를 관리하니 regular 파일처럼 취급해도 큰 상관은 없다. svn이나 git에서 object들을 관리하는 방식 덕에도 뒷통수를 얻어맞을 수 있는데, 숨김 파일 폴더에 identical한 파일들이 들어있어(파일명은 hash이며 flattened directory) 지워서는 안되는 원본 파일을 지우게 된다. 사실 이런 문제들은 예외 케이스들을 잘 보강하면 해결이 된다.

남은 것은 속도 문제인데, 기본적으로 hash sum을 구하기 위해서는 파일의 전체 내용을 읽어야 한다. 하지만 우리의 목적은 위 tuple을 “정확하게” 구하는 것이 아니라 중복 파일인지 여부를 판단하는 것이므로 hash sum을 모두 계산할 이유는 없다. 즉, 어떤 함수 f가 주어졌을 때 f(x1) != f(x2) 인 것을 빨리 발견하기만 하면 x1 != x2라는 결론을 내릴 수 있다. 그래서 가장 쉽게는 파일 사이즈가 다르면 다른 파일로 간주할 수 있고, 처음 chunk (크기는 적당히 1MB)의 hash만 봐도 되는 것이다. 파일이 다르다는 사실은 “확실하게” 얻을 수 있고, 파일이 같다는 사실은 확실하지는 않지만 확률이 높지는 않다. 이 확률 p를 낮추고 싶으면 그 뒤에 딸려오는 chunk들을 비교하면 되는 것이다.

이제 Python3의 yield 구문과 generator개념이 결합이 되어 코드가 훨씬 간결해지는데, 어떤 함수 chain [f1, f2, f3]이 있다고 가정을 하고 필요할 때마다 next를 불러서 확인하는 식이다. f1, f2, f3를 모두 evaluation하는 것이 아니라 처음 f1만 evaulation하여 파일들을 각각 다른 그룹으로 보내고, 중복 그룹이 발견되었다면 그 그룹 내에서만 f2를 수행하고, 단일 파일 그룹이 될 때까지 반복하면 된다. 최종적으로 같은 파일이라는 결론을 내리려면 끝까지 봐야하는 것은 동일하지만, 다른 파일들은 일찍이 다른 그룹으로 보내버릴 수 있는 것이다.

다음은 파이썬 소스 코드(여기서는 처음 1MB와 나중 1MB만 본다. 중간에 전송 오류가 난 경우는 없었다.):

import os
import hashlib
import collections


def compute_partial_hash_of(file_path, seek_pos, chunk_size):
    with open(file_path, "rb") as f:
        f.seek(seek_pos)
        data = f.read(chunk_size)
        if not data:
            return  # no more yield
        hashes = [hashlib.sha256(), hashlib.md5()]
        hashes[0].update(data)
        hashes[1].update(data)
        yield "_".join(map(lambda y: y.hexdigest(), hashes))


def make_challenge(file_path):
    chunk_size = 1048576
    file_size = os.path.getsize(file_path)
    yield file_size
    yield from compute_partial_hash_of(file_path, 0, chunk_size)
    yield from compute_partial_hash_of(file_path, file_size - chunk_size, chunk_size)


def fuzzy_group_files(target_directory):
    target_files = []
    for root, _, files in os.walk(target_directory):
        target_files.extend(map(lambda x: os.path.join(root, x), files))

    groups, challenge, challenge_result = init_challenge(target_files)

    found_challenge = True
    while found_challenge:
        found_challenge = False
        for _, v in groups.items():
            if len(v) > 1:
                for file_path in v:
                    if challenge[file_path] is not None:
                        try:
                            challenge_result[file_path].append(
                                next(challenge[file_path]))
                            found_challenge = True
                        except StopIteration:
                            challenge[file_path] = None
                            pass
        groups = regroup(challenge_result)
        print(collections.Counter(map(lambda x: len(x), groups.values())))
    return groups


def regroup(challenge_result):
    groups = {}  # Regroup items
    for file_path, v in challenge_result.items():
        key = "/".join(map(lambda x: str(x), v))
        if key not in groups:
            groups[key] = []
        groups[key].append(file_path)
    return groups


def init_challenge(target_files):
    groups = {"": []}
    challenge = {}
    challenge_result = {}
    for file_path in target_files:
        challenge[file_path] = make_challenge(file_path)
        challenge_result[file_path] = []
        groups[""].append(file_path)
    return groups, challenge, challenge_result


def main():
    target_directory = "/mnt/ea7ad856/large-files"
    groups = fuzzy_group_files(target_directory)
    for _, v in groups.items():
        if len(v) > 1:
            print("### Group ###")
            print("\n".join(v))


if __name__ == "__main__":
    main()