A blog about data, information and IT, by Mario Alberich

Jul 11
2007

Organización de la información personal - I: eliminando archivos duplicados


Consideraciones previas

Una de las primera cosas que debo decir antes de entrar en detalle, es que la detección de duplicados no debe conducir al borrado indiscriminado de las copias aparentemente inútiles. Por poner mi caso, el proceso de borrado se ha limitado a documentos, hojas de cálculo y demás archivos de trabajo. Por lo tanto, no he intentado eliminar programas, bibliotecas dinámicas (SO en linux, DLL en Windows) ni otras utilidades. Me he centrado en archivos pasivos, que no forman parte de procesos ni programas, cosa que recomiendo a todo aquel que no tenga claras las consecuencias de borrar lo que no debe borrarse. Para eso existen otras herramientas y probablemente otros tutoriales.

En segundo término, es importante aclarar que aunque se traten de dos documentos idénticos, hay que tener en cuenta el por qué se borran unos u otros, y si es necesario. Al revés del refrán, vale más la pena tener cien documentos duplicados a mano que uno volando. Eso siempre que tengas claro qué es lo bueno y qué es lo malo.

Una vez dicho eso, sólo quiero añadir que mi uso más intensivo se ha centrado a las utilidades de Linux, aunque he echado un vistazo y he testeado una utilidad en Windows sin incidencias remarcables.


Conceptos base para la detección de duplicados


LA gestión de archivos: Unix y Windows

Existen varias utilidades posibles para la detección y eliminación de duplicados. Sólo hay que pensar que UNIX es un sistema operativo más pensado desde sus inicios para el uso en grandes servidores, con gran cantidad de datos y por lo tanto con más dificultades en la gestión y administración de sistemas.

Dentro de esta gestión de sistemas se encuentran las utilidades de copia de seguridad, integridad del sistema de archivos y demás. La detección de archivos duplicados es una tarea accesoria que se puede realizar puntualmente, pero que desde luego toma su tiempo llevar a cabo sin las herramientas básicas.

Windows, por su lado, ha ido mejorando la estructura de directorios para poder diferenciar las ubicaciones de los archivos de programas y los documentos de trabajo del usuario. Sin que se haya conseguido concienciar más a una parte de usuarios que se obcecan en montar murales de documentos en su escritorio, lo cierto es que algo han conseguido. Por otro lado, las utilidades de gestión del sistema se han ido introduciendo con el tiempo. Me reservo mi opinión, porque entre otras cosas, no me considero un experto en sistemas, y mucho menos de Windows.


Optimización del proceso de comparación

Comparar dos archivos byte a byte sería una verdadera locura. Encontrar archivos duplicados en una lista de 10000 implicaría efectuar hasta (10000*9.999)/2=49.995.000 de revisiones en los archivos, lo que es computacionalmente muy ineficiente.

También es cierto que cuando se identifica un duplicado nos ahorramos recorrer tantas veces los archivos, pero en el caso que no hubiera ni un solo archivo idéntico en todo el sistema, recorrerías todas esas veces los archivos. Al final del proceso, además de tener claro que no tienes duplicados, quizá también debas plantearte un cambio de disco duro... Vamos, que no van por ahí los tiros.

Para identificar la duplicidad de archivos, el método pasa por establecer algoritmos que de generen una clave única de tales archivos, y así pueda compararse archivo por archivo, si las claves coinciden. Este es un procedimiento mucho más eficiente que el anterior, porque como máximo hay que recorrer 10000 veces los archivos (lo cual reduce en 9999 veces el volumen máximo de tareas a realizar).

A pesar de esto, es probable que en la mayoría de casos con leer pequeños bloques de unos cuantos bytes de un archivo ya se pueda descartar candidatos a duplicados, con lo que aún nos ahorramos el recorrer gran parte de los archivos (y eso es importante si los archivos son grandes).

Como se ve, existen varios trucos basados en el muestreo que permiten agilizar el proceso sin perder coherencia en el proceso. Como siempre que se realiza un proceso de muestreo, lo importante es la representatividad y no el tamaño de la muestra. Si con un byte tuviéramos suficiente, no sería necesario coger dos.


Algoritmos de generación de claves de resumen

Los métodos básicos para la detección de archivos duplicados es el cálculo de las claves de tipo resumen (o digest), como por ejemplo los algoritmos MD5, ó SHA1. Son casos concretos y hay bastantes más. El más utilizado es el MD5, especialmente debido a su popularidad y grado de implantación. Aunque ya no sirve como algoritmo criptográfico, es más que suficiente para la detección e indexación fiable de archivos.

Las claves de tipo digest asignan un valor de clave en base al contenido del archivo. Esta clave, a efectos prácticos, es única. Digo que lo es a efectos prácticos porque aunque se han detectado coincidencias (lo que se llama comúnmente colisiones) en la generación de claves, es prácticamente imposible que dos archivos coincidan en su clave. Por ejemplo, la clave MD5 consta de 32 dígitos hexadecimales (valores 0..F): considerando que se trata de variaciones con repetición, nos da un total de 1.208925819614629175e+24 combinaciones posibles, si no me equivoco (no, no lo he hecho mentalmente...).

Un ejemplo de clave md5 sería: 5a948ab8f80483be4e495c8c8fba39cd

Si tuvieras 1 millón de archivos a comparar, existiría una probabilidad de 1 entre 1018 de que dos de tus archivos tuvieran esta misma clave MD5, sin que fueran idénticos en contenido. La probabilidad es teórica (si el algoritmo fuera perfecto), pero en cualquier caso creo que quedan claras las proporciones, así que doy por hecho que entiendes que es difícil que dos archivos diferentes pasen por idénticos, a no ser que esa sea tu intención.

¿Y qué haces si te sucede? Bueno... pues dado lo poco probable del asunto, y que la máquina ya te reduce el trabajo, siempre puedes abrir los dos archivos y comparar. Pero vamos, yo he hecho el tratamiento sobre más de 150.000 archivos y no ha habido errores de este tipo.


Herramientas de búsqueda de duplicados en Linux

En Linux he testeado dos: la primera, llamada fslint, es una utilidad a nivel de escritorio que además de detectar duplicados, permite identificar otros problemas del sistema de archivos (datos colgando, partes corruptas del disco, etc).

Por mi familiaridad con la línea de comandos, descarté fslint en el momento de conocer de la existencia de fdupes, aunque si tenéis más interés en utilizar fslint os recomiendo que lo utilicés para hacer revisiones de volúmenes de datos no muy grandes: si se pasa mucho rato comparando, a veces se queda colgado.


:~# fdupes -r . > duplicados.txt
Progress [0/154304] 0%

El resultado de fdupes se guarda en el archivo duplicados.txt, que contiene una lista de resultados con un formato parecido al siguiente:


archivo1.txt
archivo2.txt
...
archivoN.txt
[espacio]
archivo1.dat
archivo2.dat
[espacio]

Cada grupo de archivos (los que no se separan por una línea en blanco) son archivos duplicados. Cuantos más archivos en cada bloque, más duplicaciones.

La tarea sucia está hecha y ahora nos queda a nosotros hacer una parte de tarea manual. Para ello será necesario abrir el archivo duplicados.txt y dejar sólo los archivos que queremos eliminar. Es decir, debemos borrar de la lista de archivo todas aquellas entradas que queremos conservar.

Una vez hecho esto, sólo nos queda invocar a nuestro querido awk para que convierta cada entrada en una línea de comando del shell:


# awk '{gsub(/ |\(|\)/,"\\\&");print "rm "$0}' < duplicados.txt | sh

Es decir, para cada línea del archivo duplicados.txt (< duplicados.txt) creo una línea que empiece por rm e incluya todo el contenido de la línea (print "rm "$0), enviando el resultado a ejecutar al shell (... | sh).

Con esto, se ejecuta línea por línea todos los archivos a eliminar. El comando gsub "escapa" los caracteres especiales que el shell podría malinterpretar como parte del comando a ejecutar y no como parte del nombre del archivo. Por ejemplo, los nombres que incluyen paréntesis o los que incluyan espacios, incluirán contrabarras para evitar ambigüedades al shell.

Con este proceso, que en mi caso, con 150.000 archivos (muchos pequeños) duró unas dos horas entre fdupes, procesado manual del archivo y limpieza final, hemos eliminado los archivos duplicados.


Duplicados en sistemas windows

Como ya he dicho antes, mi testeo en sistemas Windows ha sido muy limitado, por lo que os refiero al artículo de Techrepublic sobre limpieza de duplicados que habla sobre la instalación y ejecución del programa que he testeado: Dupfinder.

Esta aplicación funciona, cómo no, con interficie gráfica. Eso lo hace mucho más amena para los usuarios no muy dados a la línea de comandos. El funcionamiento es esencialmente el mismo, aunque es imposible decir si el criterio utilizado para detectar si dos archivos son duplicados es exactamente el mismo o no que en casos como fdupes.


Conclusiones

Hasta aquí la primera parte de mis tareas de reorganización de la información personal. Espero que te haya servido de ayuda toda esta información. En mi caso pude liberar un 10% de mi espacio en disco (es mucho, principalmente debido a copias de seguridad no comprimidas y archivos de gran tamaño), aunque lo más importante es que esto me permite reducir tiempo para las tareas posteriores de reorganización de los archivos existentes.

En mi opinión, lo importante es cargarse de paciencia e ir avanzando. Si no puedes cerrar la limpieza en un solo día, no pasa nada: continúa en otro momento. Lo importante es que al acabar tengas los archivos necesarios, ni más ni menos.

Tags

gestión documental 10     Recuperación información 11     Linux 7     Usabilidad 5     open source 3     Tagging 12     lógica borrosa 2     fuentes de información 12     Google 6     off-topic 6     spam 2     grafos 6     Web social 11     modelización 12     Productividad 11     buscadores 2     utilidades 17     Profesionales 9     SEO 5     estándares 3     veracidad 3     relevancia 2     lingüística 2     PLN 2     lenguajes documentales 2     apis-mashups 3     reseñas 7     Flash 7     Gráficos estadísticos 13     Publicidad 3     Innovación 5     muestreo estadístico 9     PHP 14     internet 2     testeo 12     desarrollo 3     visualizacion 36     javascript 16     datos abiertos 9     elecciones 2     simulación 5     html5 7     phing 9     ssh 2     seguridad 3     indicadores 2     demografía 3     media 2     algoritmos 7     shell 4     mysql 2     backup 2     big data 6     twitter 2     d3js 11     revealjs 2     metodología 6     data-journalism 6     smartcities 2     NYT 2     privacidad 3     benchmarking 4     recopilaciones 21     magento 5     formacion 2     github 2     HHVM 3     psicología 2     angularjs 3     grep 2     nodejs 5     promises 2     mapreduce 3     crossfilter 2     exploración de datos 2     machine learning 2    

© 2007 and beyond Mario Alberich, licensed under CC-BY-SA unless stated otherwise.