Come rimuovere le righe duplicate allinterno di un file di testo?

Un mio file di testo enorme (fino a 2 GiB) contiene circa 100 duplicati esatti di ogni riga (inutile nel mio caso, poiché il file è una tabella dati simile a CSV).

Quello di cui ho bisogno è rimuovere tutte le ripetizioni mentre (preferibilmente, ma questo può essere sacrificato per un significativo aumento delle prestazioni) mantenendo lordine della sequenza originale. Nel risultato ogni linea deve essere unica. Se ci fossero 100 righe uguali (di solito i duplicati sono sparsi nel file e non saranno vicini) ne rimarrà solo uno del tipo.

Ho scritto un programma in Scala (consideralo Java se non conosci Scala) per implementarlo. Ma forse ci sono strumenti nativi scritti in C più veloci in grado di farlo più velocemente?

AGGIORNAMENTO: la soluzione awk "!seen[$0]++" filename sembrava funzionare bene per me finché i file erano vicino a 2 GiB o più piccoli, ma ora che devo ripulire un file da 8 GiB non funziona più. Sembra che ci voglia infinito su un Mac con 4 GiB di RAM e un PC Windows 7 a 64 bit con 4 GiB di RAM e lo scambio di 6 GiB esaurisce la memoria. E non mi sento entusiasta di provarlo su Linux con 4 GiB di RAM vista questa esperienza.

Commenti

  • questo distruggerà il tuo ordine ma, hai provato sort -u, non ho idea di come o se possa essere eseguito su un file così grande
  • C spesso non è significativamente più veloce di Java e se ‘ lo stai eseguendo (in ordine) ora, ‘ ci sono buone probabilità che ‘ finirà prima di ottenere una risposta qui, implementalo e finirà di funzionare; fuori servizio, sort -u sarà probabilmente più veloce.

Risposta

Una soluzione awk vista su #bash (Freenode):

awk "!seen[$0]++" filename 

Commenti

  • Ho appena provato su un file 2G e ci sono voluti tre minuti sul mio notebook. Non male. Ho anche provato uniq filename | awk ‘! visto [$ 0] ++ ‘, ma non era ‘ in alcun modo più veloce.
  • @HashWizard: questo comando non ordina, ma elimina ogni successiva occorrenza della stessa riga
  • Ti chiedi come funziona questo comando? – Vedi qui: unix.stackexchange.com/questions/159695/how-does-awk-a0-work
  • @MaxWilliams yes , funziona se sono distribuiti in modo casuale.
  • conserva le nuove righe o le righe con spazi awk '/^\s*?$/||!seen[$0]++'

Risposta

Esiste un metodo semplice (che non vuol dire ovvio) che utilizza utilità standard che “non richiede una grande memoria se non per eseguire sort, che nella maggior parte delle implementazioni ha ottimizzazioni specifiche per file enormi (un buon algoritmo di ordinamento esterno). Un vantaggio di questo metodo è che esegue il ciclo solo su tutte le righe allinterno di utilità speciali, mai allinterno di linguaggi interpretati.

<input nl -b a -s : | # number the lines sort -t : -k 2 -u | # sort and uniquify ignoring the line numbers sort -t : -k 1n | # sort according to the line numbers cut -d : -f 2- >output # remove the line numbers 

Se tutte le righe iniziano con un carattere diverso da spazi, puoi fare a meno di alcune delle opzioni:

<input nl | sort -k 2 -u | sort -k 1n | cut -f 2- >output 

Per una grande quantità di duplicazioni, un metodo che richiede solo larchiviazione di una singola copia di ogni riga in memoria funzionerà meglio. Con un po di sovraccarico di interpretazione, esiste “uno script awk molto conciso per questo (già pubblicato da enzotib ):

<input awk "!seen[$0]++" 

Meno conciso: !seen[$0] {print} {seen[$0] += 1}, ovvero stampa la riga corrente se “non è stata ancora vista, quindi incrementa seen contatore per questa riga (le variabili non inizializzate o gli elementi dellarray hanno il valore numerico 0).

Per le righe lunghe, puoi risparmiare memoria mantenendo solo un checksum non falsificabile (ad esempio un digest crittografico) di ogni riga . Ad esempio, utilizzando SHA-1, sono necessari solo 20 byte più un overhead costante per riga. Ma il calcolo dei digest è piuttosto lento; questo metodo vincerà solo se hai una CPU veloce (specialmente una con un acceleratore hardware per calcolare i digest) e non molta memoria rispetto alla dimensione del file e righe sufficientemente lunghe. Nessuna utilità di base consente di calcolare un checksum per ogni riga; devi sopportare il sovraccarico di interpretazione di Perl / Python / Ruby / … o scrivere un programma compilato dedicato.

<input perl -MDigest::MD5 -ne "$seen{Digest::MD5::md5($_)}++ or print" >output 

Commenti

  • @Gilles Sulla base della tua spiegazione di awk '!seen[$0]++', significa che se awk vede 2 righe duplicate, manterrà sempre la prima e ignorerà tutte quelle successive? (O manterrà lultima?)
  • @ user779159 Mantiene la prima: ogni riga di input viene stampata immediatamente (prima occorrenza) o non viene stampata affatto (occorrenza ripetuta).
  • Ma come si confronta con sort -u …?
  • @HashWizard Un semplice sort -u cambia lordine.La mia risposta mostra soluzioni che preservano lordine (lordine delle prime occorrenze, per essere precisi).
  • @Gilles diresti che è più veloce di sort -u per file di grandi dimensioni (10G) con il 50% di duplicati ?

Risposta

sort -u big-csv-file.csv > duplicates-removed.csv 

Tieni presente che il file di output essere ordinato.

Commenti

  • Non veloce come il comando awk in altre risposte, ma concettualmente semplice!
  • @Johann Lo faccio abbastanza spesso su file con centinaia di migliaia (anche milioni) di stringhe brevi con terminazione di nuova riga. Ottengo i risultati abbastanza velocemente per gli esperimenti che sto facendo. Può essere più importante se utilizzato in script che vengono eseguiti più volte, il risparmio di tempo può essere considerevole.
  • Usa sort -u per rimuovere i duplicati durante lordinamento, piuttosto che dopo. (E salva la larghezza di banda della memoria) collegandolo a un altro programma). Questa è solo meglio della versione awk se vuoi che anche il tuo output sia ordinato. (LOP su questa domanda vuole che il suo ordine originale conservato , quindi questa è una buona risposta per un caso duso leggermente diverso.)
  • Ci è voluto circa un minuto, per me, per un file di 5,5 milioni di righe (1,8 GB in totale). Fantastico.

Risposta

Supponendo che tu possa permetterti di conservare in memoria tanto quanto il file deduplicato ( se i tuoi dati sono effettivamente duplicati di un fattore 100, che dovrebbe essere di circa 20 MiB + overhead), puoi farlo molto facilmente con Perl.

$ perl -ne "print unless $dup{$_}++;" input_file > output_file 

Questo conserva anche lordine.

Puoi estrarre il numero di occorrenze di ogni riga dallhash %dup se lo desideri, come bonus gratuito aggiuntivo.

Se preferisci awk, dovrebbe farlo anche questo (stessa logica della versione perl, stesso ordinamento, stessi dati raccolti nel dup variabile):

$ awk "{if (++dup[$0] == 1) print $0;}" input_file > output_file 

Commenti

  • Questo è troppo buono @Mat, I stava per ingoiare il file, lol ;-).
  • Ora sto aspettando @ManAtWork anche per la sua tessitura magica di sed e awk 🙂
  • di nuovo fantastico per il suggerimento awk: – )
  • È possibile cambiare lo script perl in solo remov e duplica le righe adiacenti?
  • @dumbledad: uniq fa tutto da solo

Answer

Poiché nessunaltra risposta ha fornito assistenza in loco, eccone una:

gawk -i inplace "!a[$0]++" file 

Commenti

  • Ciò preserva lordine? A proposito, questo non ha funzionato per me. La mia versione è: GNU Awk 4.0.2
  • @Leonid sì, lo fa. Stampa la prima occorrenza di ogni riga univoca. Il supporto inplace è stato introdotto per la prima volta nella versione 4.1, rilasciata nel 2013.
  • Questa dovrebbe essere la risposta. ‘ in realtà elimina la stringa duplicata nel file esistente o corrente in cui la risposta principale e la maggior parte delle risposte qui stampano solo le stringhe uniq / duplicate senza fare nulla e dobbiamo creare un altro output per memorizzare il risultato.

Risposta

Puoi utilizzare uniq http://www.computerhope.com/unix/uuniq.htm

uniq segnala o filtra le righe ripetute in un file.

Commenti

  • Quando si fornisce una risposta è preferibile fornire qualche spiegazione sul PERCHÉ la tua risposta è quella giusta. Quindi, in che modo questa risposta differisce da molte delle risposte precedenti?
  • Dalla pagina man di uniq: Nota: 'uniq' does not detect repeated lines unless they are adjacent. Quindi devi prima ordinarla e perdere lordine delle righe non duplicate.

Risposta

Linee di Python One:

python -c "import sys; lines = sys.stdin.readlines(); print "".join(sorted(set(lines)))" < InputFile 

Commenti

  • questo fa sì che lintero file venga caricato in memoria e potrebbe non essere adatto al problema dellOP ‘. Inoltre non è garantito il mantenimento dellordine
  • Grazie per il suggerimento, ‘ ho appena imparato a usare Python .. lho provato solo per scopi di apprendimento .. 🙂
  • Qui ‘ s una versione di Python 2.7 che non è una riga singola ma (succintamente) restituisce righe uniche mantenendo lordine senza caricare lintero file in memoria o creare una singola stringa gigantesca da alimentare per la stampa
  • Grazie @ 1_CR ho qualcosa da imparare oggi 🙂 OrderedDict

Risposta

Nessuna delle risposte qui ha funzionato per me sul mio Mac, quindi ho scritto un semplice Python script che funziona per me. Ignoro gli spazi iniziali / finali e non mi interessa nemmeno il consumo di memoria.

import sys inputfile = sys.argv[1] outputfile = sys.argv[2] with open(inputfile) as f: content = f.readlines() content = [x.strip() for x in content] my_list = list(set(content)) with open(outputfile, "w") as output: for item in my_list: output.write("%s\n" % item) 

Salva quanto sopra come unico.py ed esegui in questo modo:

python unique.py inputfile.txt outputfile.txt 

Answer

SOLUZIONE SENZA MANTENERE LORDINE DI SEQUENZA ORIGINALE

Lho fatto con il seguente pezzo di codice.

sort duplicates.txt | uniq > noDuplicates.txt 

Il comando sort ordina le righe in ordine alfabetico e il comando uniq rimuove i duplicati.

NOTA: Il motivo per cui abbiamo ordinato prima le righe è che uniq non rileva righe duplicate a meno che non siano adiacenti.

Commenti

  • La domanda richiede un metodo (preferibilmente ) che mantiene lordine di input; potresti modificare la tua risposta per risolvere il problema? Tieni presente che esistono risposte esistenti utilizzando sort che mantiene lordine di immissione e una risposta utilizzando sort senza mantenere lordine di input ma in modo più efficiente rispetto al collegamento a uniq.
  • @StephenKitt Edited. Ho esaminato altre risposte, ma non sono riuscito a ‘ trovare nulla solo con i comandi di base. Grazie per il tuo feedback.
  • Ti ho fornito un link a una risposta con solo comandi di base, in effetti un solo comando, sort -u (che fa parte di POSIX ) ;-).
  • @StephenKitt Ho visto quella risposta. Il mio è anche un modo per gestire il problema. Cosa vuoi che faccia di più? Devo eliminare la risposta?
  • No, non eliminare la tua risposta; Volevo solo assicurarmi che fossi a conoscenza dellaltra risposta, dato che hai detto che “non puoi ‘ trovare qualcosa solo con i comandi di base”.

Answer

Con bash 4, una soluzione di puro bash che sfrutta array associativi può essere utilizzato. Ecco un esempio

unset llist; declare -A llist; while read -r line; do if [[ ${llist[$line]} ]]; then continue else printf "%s\n" "$line" llist[$line]="x" fi done < file.txt 

Commenti

  • Don ‘ utilizzare read cicli per elaborare file di testo di grandi dimensioni. bash deve leggere un byte alla volta per evitare di superare una nuova riga. Bash inoltre non è molto veloce nellelaborazione del testo in generale rispetto ad awk. Se lo usi, read -ra eviterà di mangiare backslash nel tuo input. Inoltre, non ‘ t dimenticare di unset llist dopo il ciclo, se lo inserisci in una funzione di shell o usalo in modo interattivo.
  • @PeterCordes, oppure avresti potuto fare riferimento a questo 🙂

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *