algorithm - tamaño - ejemplos de diff en linux

Algoritmo Diff

Question

He estado buscando una explicación de un algoritmo de diferencias que funcione y sea eficiente.

Lo más cercano que tengo es este enlace a RFC 3284 (de varias publicaciones de blog de Eric Sink), que describe en términos perfectamente comprensibles el formato de datos en el que se almacenan los resultados de las diferencias. Sin embargo, no menciona en absoluto cómo un programa alcanzaría estos resultados mientras realizaba un diff.

Intento investigar esto por curiosidad personal, porque estoy seguro de que debe haber compensaciones al implementar un algoritmo diff, que a veces son bastante claras cuando se observan diferencias y se preguntan "¿por qué el programa diff eligió esto como un cambio? ¿en lugar de eso?"...

¿Alguien sabe dónde puedo encontrar una descripción de un algoritmo eficiente que termine generando VCDIFF?
Por cierto, si encuentra una descripción del algoritmo real utilizado por DiffMerge de SourceGear, sería incluso mejor.

NOTA: la subsecuencia común más larga no parece ser el algoritmo utilizado por VCDIFF, parece que está haciendo algo más inteligente, dado el formato de datos que utilizan.

¡Gracias!

Answer 1

Basado en el enlace que dio Emmelaich, también hay un gran desglose de Diff Strategies en el sitio web de Neil Fraser (uno de los autores de la biblioteca) .

Cubre estrategias básicas y hacia el final del artículo avanza al algoritmo de Myer y a la teoría de algunos gráficos.

Answer 2

Comenzaré mirando el código fuente real para diff, que GNU pone a available .

Para entender cómo funciona realmente ese código fuente, los documentos de ese paquete hacen referencia a los documentos que lo inspiraron:

El algoritmo básico se describe en "Un algoritmo de diferencia de O (ND) y sus variaciones", Eugene W. Myers, "Algorithmica" vol. 1 No. 2, 1986, pp. 251-266; y en "Un programa de comparación de archivos", Webb Miller y Eugene W. Myers, "Software - Práctica y experiencia", vol. 15 No. 11, 1985, pp. 1025-1040. El algoritmo se descubrió de forma independiente como se describe en "Algoritmos para correspondencia aproximada de cadenas", E. Ukkonen, "Información y control" vol. 64, 1985, pp. 100-118.

Leer los documentos y luego mirar el código fuente de una implementación debería ser más que suficiente para entender cómo funciona.

Answer 3

Ver http://code.google.com/p/google-diff-match-patch/

"Las bibliotecas Diff Match y Patch ofrecen algoritmos robustos para realizar las operaciones necesarias para sincronizar texto sin formato ... Actualmente disponible en Java, JavaScript, C ++, C # y Python"

También vea la página de wikipedia.org Diff y - " Bram Cohen: el problema de la diferencia ha sido resuelto "

Answer 4

Vine aquí buscando el algoritmo diff y luego hice mi propia implementación. Lo siento, no sé sobre vcdiff.

Wikipedia : A partir de una subsecuencia común más larga, es solo un pequeño paso obtener resultados de tipo diff: si un elemento está ausente en la subsecuencia pero está presente en el original, debe haber sido eliminado. (Las marcas ''-'', a continuación.) Si está ausente en la subsecuencia pero está presente en la segunda secuencia, debe haberse agregado. (Las marcas ''+'').

Bonita animación del algoritmo LCS aquí .

Enlace a una implementación rápida de LCS ruby ​​aquí .

Mi lenta y simple adaptación de rubí está abajo.

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts ''ORIG      ['' + original.join('', '') + '']''
  puts ''MODIFIED  ['' + modified.join('', '') + '']''
  puts ''LCS       ['' + subsequence.join('', '') + '']''
  puts ''DIFFS     ['' + diffs.join('', '') + '']''
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]

Answer 5

Un algoritmo de diferencia de O (ND) y sus variaciones es un documento fantástico y es posible que desee comenzar allí. Incluye pseudo-código y una buena visualización de los cruces de gráficos involucrados en hacer el diff.

La Sección 4 del documento presenta algunos refinamientos del algoritmo que lo hacen muy efectivo.

Implementar esto con éxito lo dejará con una herramienta muy útil en su caja de herramientas (y probablemente también una experiencia excelente).

Generar el formato de salida que necesita a veces puede ser complicado, pero si tiene conocimiento de los componentes internos del algoritmo, entonces debería poder generar todo lo que necesite. También puede introducir la heurística para afectar la producción y hacer ciertas concesiones.

Aquí hay una página que incluye un poco de documentación, código fuente completo y ejemplos de un algoritmo de diferencias usando las técnicas en el algoritmo antes mencionado.

El código fuente parece seguir de cerca el algoritmo básico y es fácil de leer.

También hay un poco de preparación de la entrada, que puede serle útil. Hay una gran diferencia en la salida cuando difiere por carácter o token (palabra).

¡Buena suerte!