1. Información general
Este rápido tutorial le mostrará cómo encontrar la diferencia entre dos cadenas usando Java.
Para este tutorial, usaremos dos bibliotecas Java existentes y compararemos sus enfoques para este problema.
2. El problema
Consideremos el siguiente requisito: queremos encontrar la diferencia entre las cadenas “ ABCDELMN” y “ABCFGLMN”.
Dependiendo del formato que necesitemos para la salida, e ignorando la posibilidad de escribir nuestro código personalizado para hacerlo, encontramos dos opciones principales disponibles.
La primera es una biblioteca escrita por Google llamada diff-match-patch. Como afirman, la biblioteca ofrece algoritmos robustos para sincronizar texto sin formato .
La otra opción es la clase StringUtils de Apache Commons Lang.
Exploremos las diferencias entre estos dos.
3. parche de coincidencia de diferencias
A los efectos de este artículo, utilizaremos una bifurcación de la biblioteca de Google original, ya que los artefactos de la original no se publican en Maven Central. Además, algunos nombres de clases son diferentes del código base original y son más adherentes a los estándares de Java.
Primero, necesitaremos incluir su dependencia en nuestro archivo pom.xml :
org.bitbucket.cowwoc diff-match-patch 1.2 Entonces, consideremos este código:
String text1 = "ABCDELMN"; String text2 = "ABCFGLMN"; DiffMatchPatch dmp = new DiffMatchPatch(); LinkedList diff = dmp.diffMain(text1, text2, false);Si ejecutamos el código anterior, que produce la diferencia entre text1 y text2 , la impresión de la variable diff producirá esta salida:
[Diff(EQUAL,"ABC"), Diff(DELETE,"DE"), Diff(INSERT,"FG"), Diff(EQUAL,"LMN")]De hecho, la salida será una lista de objetos Diff , cada uno formado por un tipo de operación ( INSERT , DELETE o EQUAL ) y la porción de texto asociada con la operación .
Al ejecutar la diferencia entre text2 y text1, obtendremos este resultado:
[Diff(EQUAL,"ABC"), Diff(DELETE,"FG"), Diff(INSERT,"DE"), Diff(EQUAL,"LMN")]4. StringUtils
La clase de Apache Commons tiene un enfoque más simplista .
Primero, agregaremos la dependencia Apache Commons Lang a nuestro archivo pom.xml :
org.apache.commons commons-lang3 3.9 Luego, para encontrar la diferencia entre dos textos con Apache Commons, llamaríamos StringUtils # Difference :
StringUtils.difference(text1, text2)La salida producida será una cadena simple :
FGLMNMientras que ejecutar la diferencia entre text2 y text1 devolverá:
DELMNEste enfoque simple se puede mejorar usando StringUtils.indexOfDifference () , que devolverá el índice en el que las dos cadenas comienzan a diferir (en nuestro caso, el cuarto carácter de la cadena). Este índice se puede utilizar para obtener una subcadena de la cadena original , para mostrar qué es común entre las dos entradas , además de qué es diferente.
5. Desempeño
Para nuestros puntos de referencia, generamos una lista de 10,000 cadenas con una porción fija de 10 caracteres , seguida de 20 caracteres alfabéticos aleatorios .
Luego recorremos la lista y realizamos una diferencia entre el n-ésimo elemento y el n + 1 ° elemento de la lista:
@Benchmark public int diffMatchPatch() { for (int i = 0; i < inputs.size() - 1; i++) { diffMatchPatch.diffMain(inputs.get(i), inputs.get(i + 1), false); } return inputs.size(); }@Benchmark public int stringUtils() { for (int i = 0; i < inputs.size() - 1; i++) { StringUtils.difference(inputs.get(i), inputs.get(i + 1)); } return inputs.size(); }Finalmente, ejecutemos los puntos de referencia y comparemos las dos bibliotecas:
Benchmark Mode Cnt Score Error Units StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130.559 ± 1.501 ms/op StringDiffBenchmarkUnitTest.stringUtils avgt 50 0.211 ± 0.003 ms/op6. Conclusión
En términos de velocidad de ejecución pura, StringUtils es claramente más eficiente , aunque solo devuelve la subcadena de la que las dos cadenas comienzan a diferir.
Al mismo tiempo, Diff-Match-Patch proporciona un resultado de comparación más completo , a expensas del rendimiento.
La implementación de estos ejemplos y fragmentos está disponible en GitHub.