Quais são os métodos mais eficazes para procurar arquivos duplicados?

Question

1. verificar arquivos com a mesma extensão e mesmo tamanho
2. use alguma função hash (md5, md6 suponha que seja melhor)

O primeiro não é muito confiável porque o nome não faz parte do arquivo. O arquivo não pode ter extensão. O segundo é bastante lento em arquivos grandes.

Suponho que haja alguns métodos mais eficazes.

    

Answer 1

Não existem métodos mais eficazes.

Você pode verificar se os tamanhos dos arquivos são os mesmos, mas há uma chance muito real de um falso positivo. Verificar a extensão do arquivo é inútil porque você pode ter dois arquivos idênticos com extensões diferentes.

Você pode verificar se o conteúdo do arquivo corresponde exatamente, por exemplo. com o comando cmp , que faz parte de qualquer instalação do Unix. Isso é muito mais lento do que verificar o tamanho do arquivo, porque o tamanho é apenas uma leitura de metadados e uma comparação byte por byte requer a leitura de todos os arquivos.

Você pode computar uma soma de verificação, que é essencialmente a mesma que a anterior, mas (1) consome mais CPU no caso simples de dois arquivos e (2) torna a comparação de mais de dois arquivos muito mais fácil. A razão para isso é que você pode armazenar em cache a soma de verificação para que você não tenha que reler cada arquivo para cada outro arquivo, basta comparar as somas de verificação.

Se você tiver um tipo de arquivo conhecido, como um tipo de imagem, poderá realizar testes "melhores" para igualdade aproximada, se a igualdade aproximada for sua meta. Qualquer método desse tipo não consumiria menos CPU ou menos leituras de disco do que qualquer um dos métodos acima.

Se o seu sistema de arquivos é ZFS ou outro FS que faz checagem de arquivos ou bloqueia "nativamente" você pode comparar arquivos com eficiência simplesmente lendo metadados do sistema de arquivos.

Sua melhor aposta ao implementar um localizador de duplicatas genérico é usar uma solução pré-definida. Se você precisar fazer isso sozinho, deverá verificar e verificar todos os arquivos, manter um banco de dados dos resultados e, em seguida, atualizá-lo quando os arquivos forem alterados (ou periodicamente, se isso for melhor para o seu cenário). A verificação duplicada torna-se uma questão simples e eficiente de consultar o banco de dados.

    

Answer 2

Um método mais eficaz seria uma combinação para evitar comparações inúteis:

1. Agrupe arquivos pelo tamanho do arquivo.
2. Agrupe arquivos com base em um hash dos dados iniciais de cada arquivo.
3. Compare os arquivos em cada grupo de hash entre si usando uma função de hash.

O tamanho dos dados iniciais deve ser escolhido grande o suficiente para ser exclusivo o suficiente (não o cabeçalho).

Você pode considerar não verificar completamente arquivos grandes, mas sim verificar uma parte menor e listá-los como "arquivos grandes / possíveis duplicatas" em vez de "duplicatas exatas" e fornecer uma opção de verificação completa.

Como o phogg mencionou, se você precisa fazer esse comportamento regularmente:
Você pode querer atualizar o grupo de hash em um banco de dados toda vez que um arquivo for alterado ...