¿Cómo comparar archivos de texto grandes?

Question

Tengo una pregunta general sobre su opinión sobre mi "técnica".

Hay 2 archivos de texto (file_1 y file_2) que deben compararse entre sí. Ambos son muy grandes (3-4 gigabytes, de 30,000,000 a 45,000,000 líneas cada uno). Mi idea es leer varias líneas (tantas como sea posible) de file_1 en la memoria, luego compararlas con todas las líneas de file_2. Si hay una coincidencia, las líneas de ambos archivos que coincidan se escribirán en un nuevo archivo. Luego continúe con las siguientes 1000 líneas de file_1 y también compare las de todas las líneas de file_2 hasta que pasé por file_1 por completo.

Pero esto realmente suena muy, muy lento y complicado para mí. ¿Puedes pensar en algún otro método para comparar esos dos archivos?

¿Cuánto tiempo cree que podría tomar la comparación? Para mi programa, el tiempo no importa tanto. No tengo experiencia en trabajar con archivos tan grandes, por lo tanto, no tengo idea de cuánto puede durar esto. No debería tomar más de un día sin embargo. ;-) Pero me temo que mi técnica podría llevar una eternidad ...

Una pregunta que me vino a la mente: ¿cuántas líneas leerías en la memoria? ¿El mayor número posible? ¿Hay alguna forma de determinar el número de líneas posibles antes de intentarlo realmente? Quiero leer tantos como sea posible (porque creo que es más rápido) pero me he quedado sin memoria con bastante frecuencia.

Gracias de antemano.

EDIT Creo que tengo que explicar mi problema un poco más.

El propósito no es ver si los dos archivos en general son idénticos (no lo son). Hay algunas líneas en cada archivo que comparten la misma "característica". He aquí un ejemplo: file_1 se ve algo como esto:

mat1 1000 2000 TEXT  //this means the range is from 1000 - 2000 
mat1 2040 2050 TEXT 
mat3 10000 10010 TEXT 
mat2 20 500 TEXT 

file_2 se parece a esto:

mat3 10009 TEXT 
mat3 200 TEXT 
mat1 999 TEXT 

TEXT se refiere a los caracteres y dígitos que no son de interés para mí, mat puede pasar de mat1 - mat50 y no están en orden; también puede haber 1000x mat2 (pero los números en la siguiente columna son diferentes). Necesito encontrar las líneas de ajuste de una manera que: matX sea la misma en ambas líneas comparadas y el número mencionado en file_2 se ajuste al rango mencionado en file_1. Entonces, en mi ejemplo, encontraría una coincidencia: la línea 3 de file_1 y la línea 1 de file_2 (porque ambas son mat3 y 10009 están entre 10000 y 10010). ¡Espero que esto lo aclare!

Así que mi pregunta es: ¿cómo buscarías las líneas correspondientes?

Sí, uso Java como mi lenguaje de programación.

EDIT Ahora dividí primero los archivos de gran tamaño para no tener problemas con la falta de memoria. También creo que es más rápido comparar (muchos) archivos más pequeños entre ellos que esos dos archivos enormes. Después de eso puedo compararlos de la manera que mencioné arriba. Puede que no sea la manera perfecta, pero todavía estoy aprendiendo ;-) No obstante, todos sus enfoques fueron muy útiles para mí, ¡gracias por sus respuestas!

Answer 1

Ahora que nos ha dado más detalles, el enfoque que tomaría se basa en el particionamiento previo y, opcionalmente, la clasificación antes de buscar coincidencias.

Esto debería eliminar una cantidad sustancial de comparaciones que de otra forma no coincidirían en el ingenuo enfoque de la fuerza bruta. En aras de la discusión, vamos a vincular ambos archivos a 40 millones de líneas cada uno.

Partición: Leer través file_1 y enviar todas las líneas que comienzan con mat1-file_1_mat1, y así sucesivamente. Haga lo mismo para file_2. Esto es trivial con un pequeño grep, o si desea hacerlo programáticamente en Java, es un ejercicio para principiantes.

Eso es una pasada a través de dos archivos para un total de 80 millones de líneas leídas, produciendo dos juegos de 50 archivos de 800,000 líneas cada uno en promedio.

Ordenando: para cada partición, tipo de acuerdo con el valor numérico en sólo la segunda columna (el límite inferior de file_1 y el número real de file_2). Incluso si 800,000 líneas no pueden caber en la memoria, supongo que podemos adaptar el tipo de fusión externa bidireccional y realizar esto más rápido (menos lecturas generales) que una clase del espacio sin particionar entero.

Comparación: Ahora sólo hay que repetir una vez través de los dos pares de file_1_mat1 y file_2_mat1, sin necesidad de guardar nada en la memoria, la salida de partidos a su archivo de salida. Repita para el resto de las particiones sucesivamente. No es necesario un paso final de "fusión" (a menos que esté procesando particiones en paralelo).

Incluso sin la etapa de clasificación, la comparación ingenua que ya está haciendo debería funcionar más rápido en 50 pares de archivos con 800,000 líneas cada uno en lugar de dos archivos con 40 millones de líneas cada uno.

Answer 2

hay una compensación: si lee una gran parte del archivo, guarda el disco seek time, pero es posible que haya leído información que no necesitará, ya que el cambio se encontró en las primeras líneas.

Probablemente deberías ejecutar algunos experimentos [benchmarks], con un tamaño de porción variable, para averiguar cuál es la porción óptima para leer, en el caso promedio.

Answer 3

intentan evitar consumir memoria y hacer que consuman más discos. quiero decir dividir cada archivo en partes de tamaño cargables y compararlas, esto puede tomar algo de tiempo extra pero lo mantendrá seguro lidiando con los límites de memoria.

Answer 4

Nunca he trabajado con archivos tan grandes, pero esta es mi idea y debería funcionar.

Podrías mirar el hash. Usando SHA-1 Hashing.

importar los siguientes

import java.io.FileInputStream; 
import java.security.MessageDigest; 

Una vez que el archivo de texto, etc se ha cargado tenerlo bucle a través de cada línea y en la impresión final a cabo el hash. Los siguientes enlaces de ejemplo profundizarán.

StringBuffer myBuffer = new StringBuffer(""); 
//For each line loop through 
    for (int i = 0; i < mdbytes.length; i++) { 
     myBuffer.append(Integer.toString((mdbytes[i] & 0xff) + 0x100, 16).substring(1)); 
    } 
System.out.println("Computed Hash = " + sb.toString()); 

SHA Code example focusing on Text File

SO Question about computing SHA in JAVA (Possibly helpful)

Another sample of hashing code.

simple leer cada archivo seperatley, si el valor hash para cada archivo es el mismo al final del proceso, entonces los dos archivos son idénticos . Si no, entonces algo está mal.

Luego, si obtienes un valor diferente, puedes hacer la verificación línea por línea que lleva mucho tiempo.

En general, parece que leer línea por línea, línea por línea, etc. tomaría para siempre. Haría esto si estás tratando de encontrar cada diferencia individual. Pero creo que los hash serían más rápidos para ver si son lo mismo.

SHA checksum

Answer 5

Sin seguro de lo bueno una respuesta que sería - pero echar un vistazo a esta página: http://c2.com/cgi/wiki?DiffAlgorithm - resume unos algoritmos de diferenciación. El algoritmo de Hunt-McIlroy es probablemente la mejor implementación. Desde esa página también hay un enlace a una implementación java de la diferencia GNU. Sin embargo, creo que una implementación en C/C++ y compilada en código nativo será mucho más rápida. Si está atrapado con java, es posible que desee considerar JNI.

Answer 6

En un mundo ideal, podría leer en cada línea de archivo_2 en memoria (probablemente utilizando un objeto de búsqueda rápida como HashSet, dependiendo de sus necesidades), luego leer en cada línea del archivo_1 de a una por vez y compárelo con su estructura de datos que contiene las líneas del archivo_2.

Como ya ha dicho, se ha quedado sin memoria, creo que una estrategia de tipo dividir y vencer sería lo mejor. Podría usar el mismo método que mencioné anteriormente, pero lea en la mitad (o en un tercio, un cuarto ... dependiendo de la cantidad de memoria que pueda usar) de las líneas del archivo_2 y guárdelas, luego compare todas las líneas en archivo_1. Luego lea en la siguiente mitad/tercer/trimestre/lo que sea en la memoria (reemplazando las líneas anteriores) y vuelva a pasar por el archivo_1. Significa que tiene que pasar por el archivo_1 más, pero debe trabajar con sus limitaciones de memoria.

---

EDIT: En respuesta al detalle añadido en su pregunta, me gustaría cambiar mi respuesta en parte. En lugar de leer en todo el archivo_2 (o en fragmentos) y leer en el archivo_1 una línea a la vez, invierta eso, ya que el archivo_1 contiene los datos para verificar.

También, con respecto a la búsqueda de las líneas correspondientes. Creo que la mejor manera sería hacer algún procesamiento en el archivo_1. Cree un HashMap<List<Range>> que asigne una cadena ("mat1" - "mat50") a una lista de Range s (solo un contenedor para un startOfRange int y un endOfRange int) y rellene con los datos del archivo_1. Luego escriba una función como (ignorando la comprobación de errores)

boolean isInRange(String material, int value) 
{ 
    List<Range> ranges = hashMapName.get(material); 
    for (Range range : ranges) 
    { 
     if (value >= range.getStart() && value <= range.getEnd()) 
     { 
      return true; 
     } 
    } 
    return false; 
} 

y llámelo para cada línea (analizada) de file_2.

Answer 7

De hecho, eso podría llevar un tiempo. Tienes que hacer 1,200,000,000 de comparaciones de líneas. Existen varias posibilidades para acelerar eso en un orden de magnitud:

Uno sería ordenar el archivo2 y hacer una especie de búsqueda binaria a nivel de archivo. Otro enfoque: calcule una suma de comprobación de cada línea y busque eso. Dependiendo de la longitud de línea promedio, el archivo en cuestión sería mucho más pequeño y realmente puede hacer una búsqueda binaria si almacena las sumas de verificación en un formato fijo (es decir, un largo)

El número de líneas que lee a la vez del archivo_1 no importa , sin embargo. Esto es una micro-optimización frente a una gran complejidad.

Answer 8

Si quieres un enfoque simple: puedes mezclar los dos archivos y comparar el hash. Pero es probable que sea más rápido (especialmente si los archivos difieren) para usar su enfoque. Acerca del consumo de memoria: solo asegúrate de usar suficiente memoria, sin búfer para este tipo, una cosa es una mala idea.

Y todas esas respuestas sobre hashes, sumas de comprobación, etc.: no son más rápidas. Tienes que leer todo el archivo en ambos casos. Con hashes/checksums, incluso tiene que calcular algo ...

Answer 9

Lo que puede hacer es ordenar cada archivo individual. p.ej. el UNIX sort o similar en Java. Puede leer los archivos ordenados una línea a la vez para realizar una fusión.

Answer 10

¿Qué pasa con el uso de control de fuente como Mercurial? No sé, tal vez no sea exactamente lo que quieres, pero esta es una herramienta diseñada para rastrear los cambios entre revisiones. Puede crear un repositorio, cometer el primer archivo, a continuación, sobrescribir con otra un cometer el segundo:

hg init some_repo 
cd some_repo 
cp ~/huge_file1.txt . 
hg ci -Am "Committing first huge file." 
cp ~/huge_file2.txt huge_file1.txt 
hg ci -m "Committing second huge file." 

Desde aquí se puede obtener un diff, que le dice qué se diferencian las líneas. Si pudieras de alguna manera usar esa diferencia para determinar qué líneas eran iguales, estarías todo listo.

Es solo una idea, alguien me corrige si me equivoco.

Answer 11

Creo que su camino es bastante razonable.

Me imagino diferentes estrategias; por ejemplo, puede ordenar ambos archivos antes de comparar (donde es eficiente la implementación de filesort, y la utilidad de ordenamiento de UNIX puede ordenar varios archivos de Gbs en minutos) y, mientras está ordenada, puede comparar archivos secuencialmente, leyendo línea por línea.

Pero esto es un camino bastante complejo: necesita ejecutar un programa externo (ordenar), o escribir una implementación eficiente comparable de filesort en java usted mismo, lo cual no es una tarea fácil en sí misma. Por lo tanto, en aras de la simplicidad, creo que la forma de leer fragmentada es muy prometedora;

En cuanto a cómo encontrar un bloque razonable - en primer lugar, puede no ser correcto lo que "cuanto más - mejor" - Creo que el tiempo de todo el trabajo crecerá asintóticamente, a una línea constante. Entonces, puede ser que esté cerca de esa línea más rápido de lo que cree, necesita un punto de referencia para esto.

Siguiente - usted puede leer líneas para amortiguar así:

final List<String> lines = new ArrayList<>(); 
try{ 
    final List<String> block = new ArrayList<>(BLOCK_SIZE); 
    for(int i=0;i<BLOCK_SIZE;i++){ 
     final String line = ...;//read line from file 
     block.add(line); 
    } 
    lines.addAll(block); 
}catch(OutOfMemory ooe){ 
    //break 
} 

Así que leer tantas líneas, como se puede - que abandonó el último BLOCK_SIZE de memoria libre. BLOCK_SIZE debe ser grande en cuanto al resto de su programa se ejecute sin OOM

Answer 12

Si desea saber exactamente si los archivos son diferentes o no, entonces no hay una solución mejor que la suya, comparando secuencialmente.

Sin embargo, puede hacer algunas heurísticas que pueden indicarle con algún tipo de probabilidad si los archivos son idénticos. 1) Compruebe el tamaño del archivo; eso es lo más fácil 2) Tome una posición de archivo aleatorio y compare el bloque de bytes comenzando en esta posición en los dos archivos. 3) Repita el paso 2) para lograr la probabilidad necesaria.

Debe calcular y probar cuántas lecturas (y tamaño de bloque) son útiles para su programa.

Answer 13

Mi solución sería producir primero un índice de un archivo, luego usarlo para hacer la comparación. Esto es similar a algunas de las otras respuestas en que usa hash.

Menciona que el número de líneas es de hasta aproximadamente 45 millones. Esto significa que podría (potencialmente) almacenar un índice que usa 16 bytes por entrada (128 bits) y usaría aproximadamente 45,000,000 * 16 = ~ 685MB de RAM, lo cual no es irracional en un sistema moderno. Hay gastos generales en el uso de la solución que describo a continuación, por lo que aún puede encontrar que necesita utilizar otras técnicas, como archivos mapeados en memoria o tablas basadas en disco para crear el índice. Consulte Hypertable o HBase para ver un ejemplo de cómo almacenar el índice en una tabla de hash rápida basada en disco.

Así, en su totalidad, el algoritmo sería algo así como:

1. Crear un mapa hash que mapea a una larga lista de Longs (HashMap < largo, largo Lista < >>)
2. Obtener el hash de cada línea en el primer archivo (Object.hashCode debe ser suficiente)
3. Obtener el desplazamiento en el fichero de la línea para que pueda encontrar de nuevo más tarde
4. Añadir el desplazamiento a la lista de líneas a juego con hashcodes en el mapa hash
5. comparar cada línea de la segundo archivo al conjunto de desplazamientos de línea en el índice
6. mantener ningún tipo de líneas que tienen entradas coincidentes

EDIT: en respuesta a su pregunta editada, esto no sería de gran ayuda en sí mismo. Podrías simplemente hacer hash en la primera parte de la línea, pero solo crearía 50 entradas diferentes. Sin embargo, podría crear otro nivel en la estructura de datos, lo que correlacionaría el inicio de cada rango con el desplazamiento de la línea de donde provenía.

Así que algo así como index.get("mat32") devolvería un TreeMap de rangos. Puede buscar el rango anterior al valor que está buscando lowerEntry(). En conjunto, esto le daría una comprobación bastante rápida para ver si una determinada combinación de matX/número estaba en uno de los rangos que está buscando.

Answer 14

Probaría lo siguiente: para cada archivo que esté comparando, cree archivos temporales (me refiero a ellos como un archivo parcial más adelante) en el disco que representa cada letra alfabética y un archivo adicional para todos los demás caracteres. luego lea todo el archivo línea por línea. Al hacerlo, inserte la línea en el archivo correspondiente que corresponda a la letra con la que comienza. ya que lo ha hecho para ambos archivos, ahora puede limitar la comparación para cargar dos archivos más pequeños a la vez. una línea que comienza con A, por ejemplo, puede aparecer solo en un archivo parcial y no será necesario comparar cada archivo parcial más de una vez. Si los archivos resultantes todavía son muy grandes, puede aplicar la misma metodología en los archivos parciales resultantes (archivos de letras específicas) que se comparan creando archivos según la segunda letra en ellos. el intercambio de aquí sería el uso de un gran espacio de disco temporalmente hasta que el proceso haya finalizado. en este proceso, los enfoques mencionados en otros posts aquí pueden ayudar a tratar los archivos parciales de manera más eficiente.