Diff

En informática, diff es una utilidad para la comparación de archivos que genera las diferencias entre dos archivos o los cambios realizados en un archivo determinado comparándolo con una versión anterior del mismo archivo. Diff expone los cambios realizados por línea en los archivos de texto. Las implementaciones modernas también soportan archivos binarios.^[1]​ El resultado se conoce como diff o patch ya que el mismo puede ser aplicado con el programa Unix patch. El resultado de la comparación de un archivo similar también se llama "diff". De la misma manera que se usa la palabra "grep" para describir la acción de buscar, la palabra diff se usa en la jerga como un verbo que se refiere al cálculo de cualquier diferencia. Un ejemplo de diff.

La utilidad diff fue desarrollada a comienzos de los años setenta en el sistema operativo Unix que estaba creándose en AT&T Bell Labs en Murray Hill, Nueva Jersey. La versión final, que apareció por primera vez con la 5.ª edición de Unix en 1974, fue toda ella escrita por Douglas McIlroy. Este trabajo fue publicado en un artículo de 1976 coescrito con James W. Hunt que desarrolló un prototipo inicial de diff.^[2]​

El trabajo de McIlroy fue precedido e influido por el programa comparison de Steve Johnson en GECOS y por el programa proof de Mike Lesk también originado en Unix y, como diff, producía cambios línea a línea e incluso utilizaba paréntesis angulares (">" y "<") para presentar las inserciones y borrados de línea en el resultado del programa. Las heurísticas utilizadas en estas primeras aplicaciones fueron, sin embargo, juzgadas como no fiables. La utilidad potencial de la herramienta diff provocó que McIlroy acometiese la investigación y diseño de una herramienta más robusta que podía usarse en una gran variedad de tareas pero que al tiempo se condujese bien en los procesos y con las limitaciones de tamaño del hardware de PDP-11. Su análisis del problema lo llevó a cabo con la colaboración de distintas personas de Bell Labs como Alfred Aho, Elliot Pinson, Jeffrey Ullman y Harold S. Stone.

En el contexto de Unix, el uso del editor de línea ed proveía diff con la habilidad natural para crear órdenes de edición útiles. Estas órdenes de edición, cuando se grababan en un archivo, podían, junto con el archivo original, ser reconstituidas completamente por ed en el archivo modificado. Esto reducía enormemente el necesario almacenamiento secundario para mantener las distintas versiones de un archivo. McIlroy consideró escribir un post-procesador para diff donde una variedad de formatos de resultados pudiesen ser diseñados e implementados, pero encontró que era más frugal y sencillo hacer que diff fuese el responsable de generar la sintaxis y la información de entrada de orden contrario aceptada por el comando ed. En 1985, Larry Wall compuso una utilidadh, patch, que generalizó y extendió la habilidad para modificar archivos con resultado diff. Los modos de Emacs permiten también convertir el formato de patches e incluso editar patches interactivamente.

En los primeros años de diff, los usos habituales eran la comparación de cambios en la fuente del código del software y el marcado de documentos técnicos, la verificación de la salida de errores de programa, la comparación de listados de sistemas de archivos y el análisis del código del montaje del ordenador. La salida apuntada por ed fue modificada para proporcionar compresión a una secuencia de modificaciones hecha a un archivo. La Source Code Control System (SCCS) y su habilidad para archivar revisiones apareció a finales de los años setenta como consecuencia de almacenar órdenes de edición de diff.

El Project Xanadu es un predecesor conceptual de diff. Era un proyecto de hipertexto concebido por primera vez en 1960 que debía incluir una versión de un sistema de seguimiento necesario para su característica de "transpointing windows". La característica subsumía las diferencias de archivos en el término expansivo "transclusión", en el que un documento incluía en él partes de otros documentos o revisiones.

La operación de diff se basa en resolver el problema Problema de subsecuencia común más larga (LCS).

En el problema LCS, se tienen dos secuencias de ítems:

       a b c d f g h j q z

       a b c d e f g i j k r x y z

y se desea encontrar la secuencia más larga de ítems que se presenta en las dos secuencias originales en el mismo orden. Esto es, se quiere encontrar una nueva secuencia que pueda obtenerse de la primera secuencia eliminando algunos ítems, y de la segunda secuencia eliminando otros ítems. Se quiere también que esta secuencia sea tan larga como sea posible. En este caso es:

       a b c d f g j z

De la subsecuencia común más larga solo hay un pequeño paso para conseguir un resultado del tipo de diff:

       e   h i   q   k r x y 
       +   - +   -   + + + +

Es invocado desde la línea de comando con los nombres de dos archivos: diff original new. El resultado del comando representa los cambios requeridos para hacer que el archivo original se convierta en el nuevo archivo.

Si original y nuevo son directorios, entonces diff se ejecutará sobre cada archivo que exista en ambos directorios. Una opción, -r, hará que cualesquiera subdirectorios emparejados comparen archivos entre directorios.

Todos los ejemplos en el artículo usan los archivos original y nuevo:

Esta parte del
documento ha permanecido 
igual de versión a
versión. No debería 
ser mostrada si no 
cambia. Ya que eso
no ayudaría a 
comprimir el tamaño de los
cambios.

Este párrafo contiene
texto que está anticuado.
Será borrado en 
breve.

Es importante revisar
deternidamente este documento. Por
otro lado, una
palabra mal escrita no es
el fin del mundo.
Nada de lo que hay en lo que queda
de este párrafo necesita
ser cambiado. Cualquier cosa puede
añadirse después de él.

Esta es una importante
noticia. ¡Debería
por lo tanto situarse al 
comienzo de este
documento!

Esta parte del
documento ha permanecido 
igual de versión a
versión. No debería 
ser mostrada si no 
cambia. Ya que eso
no ayudaría a
comprimir nada.

Es importante revisar
detenidamente este documento. Por
otro lado, una
palabra mal escrita no es
el fin del mundo.
Nada de lo que hay en lo que queda
de este párrafo necesita
ser cambiado. Cualquier cosa puede
añadirse después de él.

Este párrafo contiene
importantes nuevas adiciones
a este documento.

El comando diff original nuevo produce el siguiente resultado diff normal:

0a1,6
> Esta es una importante
> noticia. ¡Debería
> por lo tanto situarse al 
> comienzo de este
> documento!
>
8,14c14
< comprimir el tamaño de los
< cambios.
<
< Este párrafo contiene
< texto que está anticuado.
< Será borrado en
< breve.
---
> comprimir nada.
17c17
< deternidamente este documento. Por
---
> detenidamente este documento. Por
24a25,28
>
> Este párrafo contiene
> importantes nuevas adiciones
> a este documento.

En este formato de salida tradicional, a sustituye a añadido, d a borrado (deleted) y c a cambiado. Los números de línea del archivo original aparecen antes de a/d/c y los del archivo modificado después. Los paréntesis angulares aparecen al comienzo de las líneas que son añadidas, borradas o cambiadas. Las líneas añadidas se incluyen en el archivo original para aparecer en el archivo nuevo. Las líneas borradas se eliminan del archivo original para ser borradas en el archivo nuevo.

Por defecto, las líneas comunes a los dos archivos no se muestran. Las líneas que se han movido se muestran como añadidas en su nuevo lugar y como borradas en su antiguo lugar.^[3]​

La mayoría de las implementaciones de diff se han mantenido aparentemente sin cambios desde 1975. Las modificaciones consisten en mejoras en el algoritmo base, la adición de características útiles al comando y el diseño de un nuevos formatos de salida. El algoritmo básico se describe en el artículo An O(ND) Difference Algorithm and its Variations de Eugene W. Myers^[4]​ y en A File Comparison Program de Webb Miller and Myers.^[5]​ El algoritmo fue descubierto independientemente y descrito en Algorithms for Approximate String Matching, de E. Ukkonen.^[6]​ Las primeras ediciones del programa diff fueron diseñadas para la comparación de líneas de archivos de texto dejando que el carácter newline delimitase las líneas. En los años ochenta, la ayuda para los archivos binarios dio lugar a un cambio en el diseño y la implementación de la aplicación.

Un edit script puede generarse por medio de versiones modernas de diff con la opción -e. option. El edit script resultante para el ejemplo anterior es el siguiente:

24a

Este párrafo contiene
importantes nuevas adiciones
a este documento.
.
17c
detenidamente este documento. Por
.
8,14c
comprimir nada.
.
0a
Esta es una importante
noticia! Debería
por lo tanto ser situada al
comienzo de este
documento! 
.

• Distancia de Levenshtein

• Sitio oficial (en inglés)