O nosso objetivo é criar uma linha de comando que, dados um ou mais diretórios, identifique arquivos suspeitos de terem conteúdos duplicados.

Desafio proposto por Roberto Tyszler.

Uma boa abordagem para este tipo de problema é buscar um atributo do arquivo que seja virtualmente impossível de ser compartilhado por coincidência com outro arquivo qualquer. Atributos como nomes, data e hora de criação e tamanho em bytes, embora sejam capazes de nos dar pistas, podem nos levar a falsos positivos ou, pior, a ignorar as verdadeiras duplicatas.

Por este motivo, nós adotaremos uma solução que, dependendo do tamanho e da quantidade de arquivos a serem verificados, pode ser mais lenta, mas é muito menos suscetível a resultados enganosos: o cálculo da hash do arquivo com a ferramenta sha256sum (GNU coreutils).

Ao ser executado recebendo um ou mais nomes de arquivos como argumentos, o sha256sum produz uma saída assim:

:~$ sha256sum foto-da-familia.png foto-do-passeio.png foto-do-perfil.png
8201e745a87d71b62d7b2a76cef0c8741c33c1452660bb624a6e984aed7e3c37  foto-da-familia.png
d2d137bc99f11c13fa59a7ce2b1147ad8d9fb06d464727078033cd1ec2d99525  foto-do-passeio.png
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  foto-do-perfil.png

Onde devemos observar que:

• A hash SHA-256 retornada terá sempre 64 caracteres de comprimento;
• Entre a hash e o nome do arquivo existe um espaço e um caractere que determina o método do cálculo, podendo ser um espaço (cálculo por texto) ou um asterisco (cálculo binário);
• Mesmo que os nomes de dois arquivos sejam diferentes, se eles tiverem a mesma hash, é praticamente impossível que não tenham o mesmo conteúdo.

Definido o atributo que utilizaremos como referência, o nosso trabalho será:

1. Especificar uma lista de arquivos a serem analisados;
2. Calcular a hash de cada um deles e...
3. Filtrar a saída de modo que tenhamos apenas os nomes dos arquivos duplicados.

Como já sabemos calcular a hash, vamos nos concentrar nos outros dois procedimentos.

É na especificação da lista de arquivos que podemos decidir se trabalharemos apenas com os recursos do shell (uma expansão) ou se utilizaremos outra ferramenta, tal como o find (GNU findutils): se quisermos analisar arquivos em diretórios aninhados ou com uma quantidade muito grande de arquivos, pode ser mais interessante trabalhar com o find, mas podemos dispensar a execução de mais um programa se trabalharmos com uma expansão do shell.

Aqui, uma simples expansão de nomes de arquivos, associada ou não a expansões de listas de palavras com chaves, pode ser o bastante, por exemplo:

# Todos os arquivos do diretório 'imgs'...
:~$ sha256sum imgs/*

# Todos os arquivos 'jpg' e 'png' do diretório 'fotos'...
:~$ sha256sum fotos/*.{png,jpg}

Se quisermos expandir subdiretórios, também é relativamente simples, observe:

:~$ printf '%s\n' imgs/{fotos/*,fotos/*/*}.{jpg,jpeg,png}
imgs/fotos/*.jpeg <----------------------- não expandiu!
imgs/fotos/foto01.png
imgs/fotos/foto02.png
imgs/fotos/foto03.png
imgs/fotos/imagem01.jpg
imgs/fotos/diversas/aniversario.png
imgs/fotos/diversas/cartoon.png
imgs/fotos/diversas/logo-banda.jpg
imgs/fotos/*/*.jpeg <---------------------- não expandiu!

Com subdiretórios ou não, se especificarmos padrões genéricos demais, nós estaremos diante do primeiro problema: os nomes que não expandem. Por padrão, o shell não executa a expansão de padrões que não encontrem correspondência na lista de arquivos. Em vez disso, o padrão é tratado como uma palavra normal que será utilizada como argumento do programa ou do comando que está sendo executado.

Então, em dado momento, o utilitário sha256sum, com a expansão do exemplo acima, teria que lidar com os nomes de arquivos inexistentes (imgs/fotos/*.jpeg e imgs/fotos/*/*.JPG), resultando em algo assim:

:~$ sha256sum imgs/fotos/*.jpeg imgs/fotos/*/*.JPG
sha256sum: 'imgs/fotos/*.jpeg': Arquivo ou diretório inexistente
sha256sum: 'imgs/fotos/*/*.JPG': Arquivo ou diretório inexistente

O que nos obriga a redirecionar a saída de erros para o dispositivo nulo (/dev/null):

:~$ sha256sum imgs/fotos/*.jpeg imgs/fotos/diversas/*.JPG 2> /dev/null
:~$

O segundo problema pode advir da expansão de uma lista arquivos grande demais, por exemplo:

:~/backup$ ls | wc -l
175869
:~/backup$ sha256sum *
bash: /usr/bin/sha256sum: Argument list too long

Aqui, a pasta backup possui mais de 175 mil arquivos, o que provoca um erro de excesso de argumentos. Trata-se de um limite imposto pelo kernel Linux, que define um comprimento máximo de 128kbytes para listas de argumentos, o que podemos conferir no cabeçalho limits.h:

:~$ grep ARG_MAX /usr/include/linux/limits.h
#define ARG_MAX       131072	/* # bytes of args + environ for exec() */

Minha gratidão ao professor Kretcheu por localizar a explicação do erro de excesso de argumentos na wiki do Debian.

Esta é uma das principais justificativas para considerarmos o uso do utilitário find.

Para evitar a expansão de um número exagerado de argumentos, nós temos a alternativa de executar o sha256sum individualmente para cada um dos nomes de arquivos encontrados pelo utilitário find (GNU findutils), por exemplo:

:~$ find ~/imgs/fotos -type f -exec sha256sum '{}' \;
08777b636e947c1e50441bfeaab2791f7e9369b65c6f8ef1305f2ecd230236c4  imgs/fotos/foto01.png
b865c4ec44967910598ff14150c5d6d7c3eb58813927f6c903e3c7b39c276418  imgs/fotos/foto02.png
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  imgs/fotos/foto03.png
2d19c3b0d447c8e2b0744281a083599c499cf5f2a14c5041ef60c917b11f15e1  imgs/fotos/imagem01.jpg
b04457555dcbacfbd2b78e334b71c3d7cb22636c2312cdc94323dd6ef667fbf7  imgs/fotos/diversas/aniversario.png
c85d984e9fbe201b35b4cab2ecdc0ef6c2a9a0f352585c4968e63b9706cf3653  imgs/fotos/diversas/cartoon.png
99157afa06643a0cf0ad3c2d4bda5315a87777dcce3a927d5b451cbac7d5703f  imgs/fotos/diversas/logo-banda.jpg

Explicando os argumentos:

• -type f - retorna apenas nomes de arquivos comuns;
• -exec - executa um dado comando;
• '{}' - será substituído pelos nomes encontrados;
• \; - indica o término do comando a ser executado.

Alguns detalhes importantes:

• As chaves ({}) são escritas entre aspas simples para que os nomes de arquivos contendo espaços e caracteres especiais do shell sejam tratados como palavras únicas.
• O ponto e vírgula (;) precisa ser escapado para não ser confundido como o operador de encadeamento de comandos do shell.
• A opção -exec pode receber o terminador + (em vez do \;). Assim, os nomes encontrados seriam acumulados como argumentos do comando, que seria executado apenas uma vez, mas é exatamente o acúmulo de argumentos que precisamos evitar.

Outra opção do find que pode ser interessante considerar é a -maxdepth, que limita os níveis de subdiretórios, contados a partir do diretório inicial informado, que serão pesquisados. Deste modo, se quisermos investigar apenas o diretório inicial informado, nós definimos -maxdepth com o valor 1; para mais um subnível, nós definimos como 2 e assim por diante:

:~$ find ~/imgs/fotos -maxdepth 1 -type f -exec sha256sum '{}' \;
08777b636e947c1e50441bfeaab2791f7e9369b65c6f8ef1305f2ecd230236c4  imgs/fotos/foto01.png
b865c4ec44967910598ff14150c5d6d7c3eb58813927f6c903e3c7b39c276418  imgs/fotos/foto02.png
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  imgs/fotos/foto03.png
2d19c3b0d447c8e2b0744281a083599c499cf5f2a14c5041ef60c917b11f15e1  imgs/fotos/imagem01.jpg

A opção -maxdepth precisa ser escrita antes da opção -type ou será impresso um aviso (warning) na saída junto com os resultados.

Independente do método utilizado, digamos que esta seja a saída obtida:

3fc5152426c0b46a02032f2791eff03939c6768c92dd4c30be89bd7069da1135  /home/blau/imgs/fotos/imagem-09.jpg
d2d137bc99f11c13fa59a7ce2b1147ad8d9fb06d464727078033cd1ec2d99525  /home/blau/imgs/fotos/imagem-04.jpg
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/suspeito.jpg
54a205cc87c5eb79059aad7f0726976517d99ac79f0720a85ab54ef5293cc933  /home/blau/imgs/fotos/imagem-11.jpg
16d325da58e2d108ba5c9192cf4a942ed99aa3d4007b883fb81a79d3c6d28f53  /home/blau/imgs/fotos/imagem-02.png
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/dup1-suspeito.jpg
e005fd7a073afb0507a887f1c604f650fbd39a83e76f3505f3c83c4657937beb  /home/blau/imgs/fotos/imagem-10.jpg
776803f12a7f63f637f49b1d145659c92b30b70f04546c55c4ced787d264f1b2  /home/blau/imgs/fotos/imagem-12.jpg
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/dup2-suspeito.jpg
2d19c3b0d447c8e2b0744281a083599c499cf5f2a14c5041ef60c917b11f15e1  /home/blau/imgs/fotos/imagem-20.png

Repare que os arquivos suspeito.jpg, dup1-suspeito.jpg e dup2-suspeito.jpg (propositalmente nomeados desta forma) possuem a mesma hash: ou seja, possuem o mesmo conteúdo. O nosso objetivo, então, é fazer com que apenas esses nomes sejam exibidos. Para isso, nós temos o utilitário uniq (GNU coreutils). Com a opção -D, é possível obter apenas as linhas duplicadas de uma saída de texto, mas nós temos dois problemas para resolver antes:

• Não há linhas de texto repetidas!
• O uniq só pode detectar a duplicidade de linhas consecutivas.

O segundo problema é simples de ser resolvido com o utilitário sort (GNU coreutils):

:~$ [SAÍDA_DO_COMANDO] | sort
16d325da58e2d108ba5c9192cf4a942ed99aa3d4007b883fb81a79d3c6d28f53  /home/blau/imgs/fotos/imagem-02.png
2d19c3b0d447c8e2b0744281a083599c499cf5f2a14c5041ef60c917b11f15e1  /home/blau/imgs/fotos/imagem-20.png
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/dup1-suspeito.jpg
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/dup2-suspeito.jpg
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/suspeito.jpg
3fc5152426c0b46a02032f2791eff03939c6768c92dd4c30be89bd7069da1135  /home/blau/imgs/fotos/imagem-09.jpg
54a205cc87c5eb79059aad7f0726976517d99ac79f0720a85ab54ef5293cc933  /home/blau/imgs/fotos/imagem-11.jpg
776803f12a7f63f637f49b1d145659c92b30b70f04546c55c4ced787d264f1b2  /home/blau/imgs/fotos/imagem-12.jpg
d2d137bc99f11c13fa59a7ce2b1147ad8d9fb06d464727078033cd1ec2d99525  /home/blau/imgs/fotos/imagem-04.jpg
e005fd7a073afb0507a887f1c604f650fbd39a83e76f3505f3c83c4657937beb  /home/blau/imgs/fotos/imagem-10.jpg

Repare que as hashs duplicadas, embora contenham textos diferentes, agora estão em linhas consecutivas e o uniq poderá fazer sua parte no trabalho. Então, nós só precisamos determinar o que o utilitário deverá comparar para tratar as linhas como repetidas.

Para isso, nós temos duas opções: ignorar uma quantidade de palavras (campos) no início da linha ou limitar a comparação a uma quantidade de caracteres também no início da linha. Nós não podemos ignorar a primeira palavra da linha, que é justamente onde está a informação duplicada -- se fosse o caso, a opção do uniq para isso seria -f NÚMERO_DE_CAMPOS. Portanto, o que faremos é limitar a comparação apenas aos primeiros 64 caracteres da linha (a hash) com a opção -w ( de width, largura):

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/dup1-suspeito.jpg
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/dup2-suspeito.jpg
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90  /home/blau/imgs/fotos/suspeito.jpg

No fim das contas, da saída que temos até agora, nós queremos apenas os nomes dos arquivos, o que podemos fazer de muitas formas, por exemplo:

• Utilitários 'tr' e 'cut';
• Interpretador AWK;
• Editor de fluxos de texto 'sed';
• Até com o 'grep'!

Com o utilitário tr, nós podemos eliminar os espaços duplicados entre a hash e o nome do arquivo para que o utilitário cut possa quebrar a linha em apenas dois campos, dois quais, nós queremos apenas o segundo:

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | tr -s ' ' | cut -d' ' -f2
/home/blau/imgs/fotos/dup1-suspeito.jpg
/home/blau/imgs/fotos/dup2-suspeito.jpg
/home/blau/imgs/fotos/suspeito.jpg

Explicando os comandos:

• Em tr -s ' ', a opção -s remove ocorrências duplicadas consecutivas do caractere indicado.

• Em cut -d' ' -f2, a opção -d serve para especificar o delimitador de campos, enquanto a opção -f é utilizada para especificar os campos que serão impressos.

Sem o tr, o cut quebraria a linha em 3 campos (o segundo, entre os dois espaços, seria uma string vazia), logo, o campo do nosso interesse seria o terceiro:

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | cut -d' ' -f3
/home/blau/imgs/fotos/dup1-suspeito.jpg
/home/blau/imgs/fotos/dup2-suspeito.jpg
/home/blau/imgs/fotos/suspeito.jpg

Eventualmente, o nome do arquivo pode conter espaços, o que torna mais seguro especificar que queremos que sejam exibidos todos os campos a partir do segundo (ou do terceiro) em diante:

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | tr -s ' ' | cut -d' ' -f2-

Obviamente, nós poderíamos criar um script em AWK para tratar toda a saída do comando sha256sum, mas isso envolveria um conjunto de conhecimentos muito específicos da linguagem. Contudo, para exibir apenas partes de linhas de texto, o AWK pode oferecer soluções bastante compactas e simples.

No exemplo, cada linha da saída possui duas palavras que serão vistas pelo AWK como dois campos (os espaços repetidos são ignorados na numeração de campos). Sendo assim, nós podemos fazer com que apenas o segundo campo seja impresso na saída:

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | awk '{print $2}'
/home/blau/imgs/fotos/dup1-suspeito.jpg
/home/blau/imgs/fotos/dup2-suspeito.jpg
/home/blau/imgs/fotos/suspeito.jpg

O problema, novamente, é que os nomes de arquivos podem conter espaços, o que pode nos obrigar a escrever um código mais complexo:

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | awk '{print substr($0, index($0, $2))}'

Aqui, nós utilizamos a função interna do AWK substr para imprimir toda a linha ($0) a partir do caractere que está na posição do início do segundo campo ($2), que é o valor retornado pela função index. Deste modo, nós teremos todo o conteúdo da linha a partir do segundo campo.

Em algumas situações, recorrer às expressões regulares pode ser bem mais simples e eficaz do que contar com ferramentas que tratam de linhas de texto como campos de dados delimitados de alguma forma. Nos sistemas operacionais unix-like e no GNU, existem dois utilitários especializados no trabalho com expressões regulares: o editor de fluxos de texto sed e o buscador de linhas segundo padrões de texto grep.

Para efeito de aplicar alterações em linhas de texto que correspondam ao padrão descrito por uma expressão regular, o sed pode oferecer mais recursos. Por exemplo, nós podemos localizar e remover o padrão buscado com uma expressão regular muito simples aplicada a um único comando do editor: o comando s (substitute):

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | sed 's/^.*  //'
/home/blau/imgs/fotos/dup1-suspeito.jpg
/home/blau/imgs/fotos/dup2-suspeito.jpg
/home/blau/imgs/fotos/suspeito.jpg

A sintaxe do comando s pode ser lida assim:

s(ubstituir)/PADRÃO/POR_ISTO/

Onde PADRÃO é uma expressão regular representando a parte da linha do texto que deverá ser substituída e POR_ISTO é qualquer string a ser utilizada em troca. Como podemos notar no exemplo, nós montamos o comando s de modo que, encontrado o padrão definido na expressão regular, ele fosse substituído por nada:

sed 's/^.*  //'
            ↑

Por sua vez, o padrão que nós especificamos corresponde à hash seguida de dois espaços, conforme podemos ver abaixo:

  +------ Início da linha
  |
  |+----- Seguida de qualquer caractere
  ||
  ||+---- Em qualquer quantidade (inclusive nenhum)
  |||
  ||| +-- Seguido de dois espaços
  ↓↓↓ ↓
s/^.*  //

O que corresponde exatamente à hash seguida dos dois espaços nas linhas produzidas pelo nosso comando.

Mesmo não sendo um editor, o grep oferece diversas alternativas de exibição dos resultados de suas buscas. Entre elas, nós temos a opção -o (only), que faz o grep exibir apenas a parte da linha encontrada que corresponda exatamente ao padrão buscado (que, no caso, é representado pela mesma expressão regular utilizada no sed):

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | grep -o '^.*  '
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90
319b675c242bd7135cb203e46fb0bd109299fa2b35963a42e7fd0dc31a55aa90

Contudo, o que queremos é justamente a parte que não correspondeu ao padrão, o que nos leva a buscar soluções na própria expressão regular, especialmente em um operador das especificações Perl de expressões regulares: o operador \K (variable-lenght look behind). Com o \K, toda a parte da expressão que vier antes dele será considerada no momento de buscar correspondências, mas apenas a parte que vier depois será registrada para uso em um eventual processamento posterior.

Sendo assim, nós precisamos representar um padrão que corresponda a toda a linha, posicionando o operador \K imediatamente após a parte que queremos descartar. Antes disso, porém, nós precisamos informar ao grep que as especificações PCRE serão utilizadas, o que faremos com a opção -P:

:~$ [SAÍDA_DO_COMANDO] | sort | uniq -w 64 -D | grep -oP '^.*  \K.*'
/home/blau/imgs/fotos/dup1-suspeito.jpg
/home/blau/imgs/fotos/dup2-suspeito.jpg
/home/blau/imgs/fotos/suspeito.jpg

Para uma pesquisa envolvendo uma quantidade relativamente pequena de arquivos, uma simples expansão de nomes de arquivos, com recursos do próprio shell, pode ser o suficiente. neste caso, nós teremos que observar os seguintes cuidados com:

• Nome de arquivos que contenham espaços: apenas com a expansão, não há como tratar os eventuais espaços nos nomes dos arquivos.
• Padrões sem correspondência: por padrão, o shell não expande padrões que não encontrem correspondência na lista de arquivos dos diretórios indicados, o que causaria um erro na execução do sha256sum. Isso não interromeperia a execução, mas produziria uma saída inconsistente.

A vantagem dessa abordagem é a simplicidade e a rapidez da solução, inclusive no que tange à facilidade de especificar melhor os tipos de arquivos que serão investigados. Já se a quantidade de arquivos nos diretórios for muito grande, é bem mais interessante recorrer ao find e evitar o risco de excesso de argumentos.

Como última observação, não podemos nos esquecer de que, dependendo do tamanho dos arquivos, o cálculo da hash pode ser demorado, mas ainda é um procedimento que vale a pena automatizar, visto que seria imensamente mais trabalhoso tentar abrir arquivo por arquivo para verificar se os conteúdos são iguais.