Eliminación de líneas duplicadas en un archivo usando Java

Question

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 declaración while anidada para comparar cada línea en un archivo con el resto 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.

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

Answer 1

Hmm ... 40 megs parece lo suficientemente pequeño para que pueda construir un Set de las líneas y luego imprimirlas todas hacia atrás. Esto sería mucho más rápido que hacerlo con O (n). Trabajo de E/S.

que sería algo así (haciendo caso omiso de excepciones):

public void stripDuplicatesFromFile(String filename) { 
    BufferedReader reader = new BufferedReader(new FileReader(filename)); 
    Set<String> lines = new HashSet<String>(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, se puede utilizar un LinkedHashSet en lugar de un HashSet. Dado que los elementos se almacenan por referencia, la sobrecarga de una lista vinculada adicional debe ser insignificante en comparación con la cantidad real de datos.

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

Answer 2

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

Set<String> uniqueStrings = new HashSet<String>(); 

// 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 
    // i.e. System.out.println(uniqueString); 
} 

Answer 3

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

Answer 4

Algo como esto, tal vez:

BufferedReader in = ...; 
Set<String> 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 lo que HashSet (mientras que ser un poco más rápido para las operaciones de búsqueda/insertar) reordenará todas las líneas.

Answer 5

El enfoque Hash Set es correcto, pero puede ajustarlo 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 lo necesita.

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 la última ficha y striping en la salida.

Answer 6

Si usted podría utilizar UNIX Comandos de shell que podría hacer algo como lo siguiente:

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

Esto sería iterar a través de todo su archivo y sólo pasar cada ocurrencia única vez por llamada SED. De esta manera, no estás haciendo un montón de búsquedas que has hecho antes.

Answer 7

• Leer en el archivo, almacenar el número de línea y la línea: O (n)
• ordenar en orden alfabético: O (n log n)
• eliminar duplicados: O (n)
• Ordenar en su orden de número de línea original: o (n log n)

Answer 8

Hay dos soluciones escalables, donde por escalable memoria me refiero disco y no se basa, dependiendo de si el procedimiento debe ser estable o no, donde por estable quiero decir que el orden después de eliminar duplicados es lo 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 se puede hacer casi sin memoria, al comparar solo la línea actual en cada archivo, ya que la siguiente línea garantiza que 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 se moleste en 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 arriba.

Answer 9

Si el orden no importa, la simplest way is shell scripting:

<infile sort | uniq > outfile 

Answer 10

¿Importa el orden en que las líneas vienen, y el número de duplicados ¿Usted está contando en ver?

Si no es así, y si usted está contando con una gran cantidad de duplicados (es decir, mucho más lectura de la escritura) Me También pienso en paralelización la solución hashset, con el hashset como recurso compartido.

Answer 11

Bien, la mayoría de las respuestas son un poco tontas y lentas, ya que implica agregar líneas a un hashset o lo que sea y luego volver a moverlo desde ese conjunto. Te voy a enseñar la solución más óptima en pseudocódigo: chicos

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, no hacen que sea más difícil de lo que tiene que ser. :-) Ni se moleste en ordenar, no es necesario.

Answer 12

Un enfoque similar

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

Answer 13

he hecho dos supuestos para esta solución eficiente:

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

Basado en estos solución supuestos es: 1.read una línea, guardar la longitud en la HashMap como clave, así que tenemos hashmap más ligero.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 blobs 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 duplicate found elimine ambas líneas y guarde el desplazamiento -1 en esos lugares en la lista.

por lo que considerar la complejidad y el uso de memoria:

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

Complejidad de tiempo - si no hay duplicados, pero todas las líneas de igual longitud teniendo en cuenta la duración 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 de los casos.

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.

Answer 14

void deleteDuplicates(File filename) throws IOException{ 
    @SuppressWarnings("resource") 
    BufferedReader reader = new BufferedReader(new FileReader(filename)); 
    Set<String> lines = new LinkedHashSet<String>(); 
    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"); 
}