Eliminar líneas duplicadas en un archivo usando Java

Como parte de un proyecto en el que estoy trabajando, me gustaría limpiar un archivo que genero de entradas de línea duplicadas. Sin embargo, estos duplicados a menudo no se producirán cerca uno del otro. Se me ocurrió un método para hacerlo en Java (que básicamente hizo una copia del archivo, luego usé una instrucción while anidada para comparar cada línea en un archivo con el rest del otro). El problema es que mi archivo generado es bastante grande y pesado de texto (alrededor de 225k líneas de texto, y alrededor de 40 megas). ¡Estimo que mi proceso actual demorará 63 horas! Esto definitivamente no es aceptable.

Sin embargo, necesito una solución integrada para esto. Preferiblemente en Java. ¿Algunas ideas? ¡Gracias!

Hmm … 40 megas parece lo suficientemente pequeño como para que puedas construir un Set de líneas y luego imprimirlas todas nuevamente. Esto sería mucho más rápido que hacer trabajo de E / S O (n 2 ).

Sería algo como esto (ignorando excepciones):

 public void stripDuplicatesFromFile(String filename) { BufferedReader reader = new BufferedReader(new FileReader(filename)); Set lines = new HashSet(10000); // maybe should be bigger String line; while ((line = reader.readLine()) != null) { lines.add(line); } reader.close(); BufferedWriter writer = new BufferedWriter(new FileWriter(filename)); for (String unique : lines) { writer.write(unique); writer.newLine(); } writer.close(); } 

Si el orden es importante, puede usar un LinkedHashSet lugar de un HashSet . Dado que los elementos se almacenan por referencia, la sobrecarga de una lista enlazada adicional debe ser insignificante en comparación con la cantidad real de datos.

Edición: Como lo señaló el Taller Alex, si no le importa hacer un archivo temporal, simplemente puede imprimir las líneas a medida que las lee. Esto le permite usar un HashSet simple en lugar de LinkedHashSet . Pero dudo que notara la diferencia en una operación de enlace de E / S como esta.

Bueno, la mayoría de las respuestas son un poco tontas y lentas, ya que implica agregar líneas a algún hashset o lo que sea y luego volver a moverlo de ese conjunto. Déjame mostrar la solución más óptima en pseudocódigo:

 Create a hashset for just strings. Open the input file. Open the output file. while not EOF(input) Read Line. If not(Line in hashSet) Add Line to hashset. Write Line to output. End If. End While. Free hashset. Close input. Close output. 

Por favor, chicos, no lo hagas más difícil de lo necesario. 🙂 No te preocupes por la clasificación, no es necesario.

Un enfoque similar

 public void stripDuplicatesFromFile(String filename) { IOUtils.writeLines( new LinkedHashSet(IOUtils.readLines(new FileInputStream(filename)), "\n", new FileOutputStream(filename + ".uniq")); } 

Algo como esto, tal vez:

 BufferedReader in = ...; Set lines = new LinkedHashSet(); for (String line; (line = in.readLine()) != null;) lines.add(line); // does nothing if duplicate is already added PrintWriter out = ...; for (String line : lines) out.println(line); 

LinkedHashSet mantiene el orden de inserción, a diferencia de HashSet que (aunque es ligeramente más rápido para la búsqueda / inserción) reordenará todas las líneas.

Puede usar Establecer en la biblioteca Colecciones para almacenar valores únicos y visibles a medida que lee el archivo.

 Set uniqueStrings = new HashSet(); // read your file, looping on newline, putting each line into variable 'thisLine' uniqueStrings.add(thisLine); // finish read for (String uniqueString:uniqueStrings) { // do your processing for each unique String // ie System.out.println(uniqueString); } 

Pruebe con un HashSet simple que almacena las líneas que ya ha leído. Luego itere sobre el archivo. Si te encuentras con duplicados, simplemente se ignoran (ya que un Conjunto solo puede contener cada elemento una vez).

  • Leer en el archivo, almacenando el número de línea y la línea: O (n)
  • Ordenarlo en orden alfabético: O (n log n)
  • Eliminar duplicados: O (n)
  • Clasifíquelo en su orden de número de línea original: O (n log n)

Si el orden no importa, la forma más simple es la creación de scripts en shell :

  outfile 

El enfoque Hash Set está bien, pero puede modificarlo para no tener que almacenar todas las cadenas en la memoria, sino un puntero lógico a la ubicación en el archivo para que pueda volver a leer el valor real solo en caso de que lo necesite.

Otro enfoque creativo es agregar a cada línea el número de la línea, luego ordenar todas las líneas, eliminar los duplicados (ignorando el último token que debería ser el número), y luego ordenar nuevamente el archivo por el último token y eliminarlo en la salida.

Si pudiera usar los comandos de shell de UNIX, podría hacer algo como lo siguiente:

 for(i = line 0 to end) { sed 's/\$i//2g' ; deletes all repeats } 

Esto recorrería su archivo completo y solo pasaría cada evento único una vez por llamada. De esta manera, no estás haciendo un montón de búsquedas que has hecho antes.

Hay dos soluciones escalables, donde por escalable me refiero al disco y no a la memoria, dependiendo de si el procedimiento debe ser estable o no, mientras que por estable me refiero a que el orden después de eliminar los duplicados es el mismo. si la escalabilidad no es un problema, simplemente use la memoria para el mismo tipo de método.

Para la solución no estable, primero clasifique el archivo en el disco. Esto se hace dividiendo el archivo en archivos más pequeños, clasificando los trozos más pequeños en la memoria y luego fusionando los archivos en orden ordenado, donde la fusión ignora los duplicados.

La fusión en sí misma se puede hacer casi sin memoria, comparando solo la línea actual en cada archivo, ya que se garantiza que la siguiente línea será mayor.

La solución estable es un poco más complicada. Primero, clasifique el archivo en fragmentos como antes, pero indique en cada línea el número de línea original. Luego, durante la “fusión” no moleste almacenar el resultado, solo los números de línea que se eliminarán.

Luego copie el archivo original línea por línea, ignorando los números de línea que ha almacenado anteriormente.

¿Importa en qué orden vienen las líneas y cuántos duplicados estás contando?

De lo contrario, y si cuenta con una gran cantidad de duplicados (es decir, mucho más lectura que escritura), también pienso en paralelizar la solución de hashset, con el hashset como recurso compartido.

He hecho dos suposiciones para esta solución eficiente:

  1. Hay un equivalente de Blob de línea o podemos procesarlo como binario
  2. Podemos guardar el desplazamiento o un puntero al inicio de cada línea.

Sobre la base de estas suposiciones, la solución es: 1. leer una línea, guardar la longitud en el hashmap como clave, por lo que tenemos un hashmap más claro. Guarde la lista como la entrada en hashmap para todas las líneas que tienen esa longitud mencionada en la clave. La construcción de este hashmap es O (n). Al mapear los desplazamientos para cada línea en el hashmap, compare los borrones de línea con todas las entradas existentes en la lista de líneas (desplazamientos) para esta longitud de clave, excepto la entrada -1 como offset.if duplicado encontrado, elimine ambas líneas y guarde el desplazamiento – 1 en esos lugares en la lista.

Así que considere la complejidad y el uso de la memoria:

Memoria Hashmap, complejidad de espacio = O (n) donde n es el número de líneas

Complejidad del tiempo: si no hay duplicados pero todas las líneas de igual longitud tienen en cuenta la longitud de cada línea = m, considere el no de líneas = n, entonces eso sería, O (n). Como suponemos que podemos comparar blob, el m no importa. Ese fue el peor caso.

En otros casos, ahorramos en las comparaciones, aunque necesitaremos poco espacio adicional en hashmap.

Además, podemos usar mapreduce en el lado del servidor para dividir el conjunto y fusionar los resultados más tarde. Y usando la longitud o el inicio de la línea como la clave del asignador.

 void deleteDuplicates(File filename) throws IOException{ @SuppressWarnings("resource") BufferedReader reader = new BufferedReader(new FileReader(filename)); Set lines = new LinkedHashSet(); String line; String delims = " "; System.out.println("Read the duplicate contents now and writing to file"); while((line=reader.readLine())!=null){ line = line.trim(); StringTokenizer str = new StringTokenizer(line, delims); while (str.hasMoreElements()) { line = (String) str.nextElement(); lines.add(line); BufferedWriter writer = new BufferedWriter(new FileWriter(filename)); for(String unique: lines){ writer.write(unique+" "); } writer.close(); } } System.out.println(lines); System.out.println("Duplicate removal successful"); }