Algoritmo de diferencia? [cerrado]

He estado buscando una locura por una explicación de un algoritmo diff que funciona y es eficiente.

Lo más cercano que obtuve 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 diferencias. Sin embargo, no se menciona en absoluto cómo un programa alcanzaría estos resultados al hacer una diferencia.

Estoy tratando de 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 miras diffs y te preguntas "¿por qué el programa diff eligió esto como un cambio? ¿en lugar de eso?"...

¿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 aún mejor.

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

Un algoritmo de diferencia O (ND) y sus variaciones es un documento fantástico y es posible que desee comenzar allí. Incluye pseudocódigo y una buena visualización de los recorridos del gráfico involucrados en hacer la diferencia.

Sección 4 del documento presenta algunas mejoras en el algoritmo que lo hacen muy efectivo.

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

Generar el formato de salida que necesita a veces puede ser complicado, pero si comprende los aspectos internos del algoritmo, entonces debería poder generar todo lo que necesita. También puede introducir heurísticas para afectar la salida y hacer ciertas compensaciones.

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 mencionado anteriormente.

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

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

¡Buena suerte!

Comenzaría mirando el código fuente real de diff, que GNU pone a disposición .

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

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

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

Ver https://github.com/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"

Consulte también la página de diferencias de wikipedia.org y - " Bram Cohen: el problema de diferencias se ha resuelto "

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, solo es un pequeño paso para obtener una salida de tipo diff: si un elemento está ausente en la subsecuencia pero está presente en el original, debe haberse eliminado. (Las marcas '-', a continuación.) Si está ausente en la subsecuencia pero está presente en la segunda secuencia, debe haberse agregado. (Las marcas '+').

Buena animación del algoritmo LCS aquí .

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

Mi lenta y simple adaptación 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]

Basado en el enlace que Emmelaich le dio, también hay un gran descuido 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 hacia el algoritmo de Myer y algo de teoría de grafos.