¿Algoritmo de diferencia? [cerrado]

Question

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

Lo más cercano que tengo es este enlace a RFC 3284 (de varios blogs de Eric Sink publicaciones), 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 concesiones al implementar un algoritmo diff, que son bastante claros a veces cuando miras diffs y me pregunto por qué eligió el programa diff. ¿Esto es 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 utilizan.

Answer 1

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

La sección 4 del documento introduce algunos refinamientos en el algoritmo que lo hacen muy efectivo.

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

En ocasiones, generar el formato de salida que necesita puede ser complicado, pero si entiende los algoritmos internos, debe poder generar todo lo que necesite. 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 diff utilizando las técnicas del 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 de preparación de la entrada, que puede ser útil. Hay una gran diferencia en la salida cuando se difiere por carácter o token (palabra).

¡Buena suerte!

Answer 2

Comenzaría mirando el código fuente para diff, que GNU crea disponible .

Para una comprensión de 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 "Algoritmo de diferencia O (ND) y sus variaciones", Eugene W. Myers, 'Algorithmica' Vol. 1 No. 2, 1986, pp. 251-266; y en " Un archivo   Programa de comparación, Webb Miller y Eugene W. Myers, "Software - Practice and Experience", vol. 15 No. 11, 1985, pp. 1025-1040. El algoritmo se descubrió de forma independiente como se describe en "Algoritmos para la concordancia aproximada de cadenas", E. Ukkonen, 'Information and 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 comprender cómo funciona.

Answer 3

Consulte https://github.com/google/diff-match-patch

  

" Las bibliotecas Diff Match y Patch   Ofrecer algoritmos robustos para realizar el   Operaciones requeridas para sincronizar   Texto sin formato. ... Actualmente disponible   en Java, JavaScript, C ++, C # y   Python "

Consulte también la wikipedia.org página de Diff y - " Bram Cohen: el problema del diff se ha solucionado "

Answer 4

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

Wikipedia : Desde una subsecuencia común más larga, solo es un pequeño paso para obtener diferencias. como resultado: si un elemento está ausente en la subsecuencia pero está presente en el original, debe haberse eliminado. (Las marcas '& # 8211;', 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 un implementación de Ruby LCS aquí .

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

Basado en el enlace que dio Emmelaich, también hay una gran versión 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 hasta el algoritmo de Myer y algo de la teoría de los gráficos.