¿Cuál es el mejor algoritmo de diferencia basado en (palabra o carácter)?

Question

Entonces, quiero ser capaz de encontrar la diferencia entre dos cadenas por palabra (quizás más rápido que por personaje, si por personaje es más rápido entonces me gustaría hacerlo de esa manera).

Aquí es un ejemplo de lo que quiero lograr: Fuente texto:

Hello there! 

Texto Modificado:

Helay scere? 

diff:

Hel[lo](ay) [th](sc)ere[!](?) 

• el texto entre corchetes es lo que se eliminó, el paréntesis es lo que se añadió el texto

hay una especie de una manera súper hacker para hacer esto utilizando una herramienta de línea de comandos, tales como opendiff, pero requiere un carácter de nueva línea entre medio de cada personaje, como opendiff está basada en la línea.

Estoy usando ruby, y no he encontrado ninguna herramienta para hacer esto ... pero el lenguaje no es terriblemente importante, ya que los algoritmos se pueden portar con bastante facilidad.

gracias.

Answer 1

Aquí es una gema de rubíes que no diffing de cadenas: http://rubydoc.info/gems/diff-lcs/1.1.3/frames

Antes de la mano, que acabo de hacer (en el IRB)

require 'rubygems' 
require 'diff/lcs' 
require 'diff/lcs/array' 
require 'diff/lcs/string' 

Por lo tanto, escribir la lógica para insertar, los marcadores eliminados e insertados en línea se vuelven triviales gracias a esta variedad de cambios 2D.

Aunque no estoy seguro de si esta es la mejor manera.

Answer 2

Es posible que desee comprobar esto: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem. No es difícil de implementar.

Answer 3

Una solución será encontrar la distancia de edición entre las cadenas.

Answer 4

Entonces, lo que puede hacer en varias ocasiones utilizar el LCS (como se relacionó anteriormente) para encontrar todas las cadenas comunes y eliminarlas de ambas cadenas, reemplazándolas por otra cadena, digamos un "*". Luego itera a través de ambas cadenas al mismo tiempo, y vuelve a conectar las partes juntas común y distinta.

Ejemplo

A) Hello there! 
B) Helay scere? 

LCS detection gives us ["Hel"," ","ere"], and after replacement we have 
A) *lo*th*! 
B) *ay*sc*? 

Now you split on the delimiter ("*") giving you 
A) ["lo","th","!"] 
B) ["ay","sc","?"] 

y desde aquí se acaba de ir a hacer mallado sencilla. Algo clave para tener en cuenta es que puede haber entradas nulas, por ejemplo, si usted está haciendo este método de "Hell" y "Hel" que finalmente va a conseguir

Common LCS) ["Hel"] 
A) ["l"] 
B) [""] 

meaning your result will be Hel[l]() 

Esperemos que sea aceptable.

Answer 5

Eche un vistazo a https://github.com/pvande/differ.Esta joya hace lo que está buscando