Hvordan fjerne dupliserte linjer i en tekstfil?

En stor (opptil 2 GiB) tekstfil av meg inneholder omtrent 100 eksakte duplikater av hver linje i den (ubrukelig i mitt tilfelle, som filen er en CSV-lignende datatabell).

Det jeg trenger er å fjerne alle repetisjonene mens (helst, men dette kan ofres for en betydelig ytelsesforbedring) å opprettholde den opprinnelige rekkefølgen. I resultatet skal hver linje være unik. Hvis det var 100 like linjer (vanligvis er duplikatene spredt over filen og ikke vil være naboer), er det bare en av den typen som er igjen.

Jeg har skrevet et program i Scala (vurder det Java hvis du ikke vet om Scala) for å implementere dette. Men kanskje det er raskere C-skrevet innfødte verktøy som kan gjøre dette raskere?

OPPDATERING: awk "!seen[$0]++" filename -løsningen virket helt greit for meg så lenge filene var i nærheten av 2 GiB eller mindre, men nå som jeg skal rydde opp i en 8 GiB-fil, fungerer den ikke lenger. Det virker uendelig på en Mac med 4 GiB RAM og en 64-bit Windows 7 PC med 4 GiB RAM og 6 GiB-bytter går tom for minne. Og jeg føler meg ikke begeistret for å prøve det på Linux med 4 GiB RAM gitt denne opplevelsen.

Kommentarer

  • dette vil ødelegge bestillingen din, men har du prøvd sortering -u, vet jeg ikke hvordan eller om den kan kjøre på en så massiv fil
  • C er ofte ikke betydelig raskere enn Java, og hvis du ‘ kjører den (i rekkefølge) nå, der ‘ er en god sjanse for at den ‘ ll finish før du får svar her, implementer det, og det kjører ferdig; ute av drift, vil sort -u trolig være raskere.

Svar

En awk løsning sett på #bash (Freenode):

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

Kommentarer

  • Bare prøvde dette på en 2G-fil og det tok tre minutter på notatboken min. Ikke verst. Jeg prøvde også uniq filnavn | awk ‘! sett [$ 0] ++ ‘, men det var ikke ‘ t noen raskere.
  • @HashWizard: denne kommandoen sorterer ikke, men eliminerer hver neste forekomst av samme linje
  • Lurer du på hvordan denne kommandoen fungerer? – Se her: unix.stackexchange.com/questions/159695/how-does-awk-a0-work
  • @MaxWilliams ja , det fungerer som om de er tilfeldig fordelt.
  • bevar nye linjer eller linjer med mellomrom awk '/^\s*?$/||!seen[$0]++'

Svar

Det er en enkel (som ikke er åpenbar) metode ved bruk av standardverktøy som ikke krever stort minne bortsett fra å kjøre sort, som i de fleste implementeringer har spesifikke optimaliseringer for store filer (en god ekstern sorteringsalgoritme). En fordel med denne metoden er at den bare sløyfer over alle linjene i spesialverktøy, aldri i tolket språk.

<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 

Hvis alle linjene begynner med en tegn som ikke er mellomrom, kan du dispensere med noen av alternativene:

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

For en stor mengde duplisering, en metode som bare krever lagring av en enkelt kopi av hver linje i minnet vil fungere bedre. Med en viss tolkning overhead er det «et veldig kortfattet awk-skript for det (allerede postet av enzotib ):

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

Mindre kortfattet: !seen[$0] {print} {seen[$0] += 1}, dvs. skriv ut den nåværende linjen hvis den ikke har blitt sett ennå, og øk seen teller for denne linjen (uinitialiserte variabler eller matriseelementer har den numeriske verdien 0).

For lange linjer kan du lagre minne ved å holde bare en kontrollsum som ikke kan spoofes (f.eks. en kryptografisk sammendrag) av hver linje . Hvis du for eksempel bruker SHA-1, trenger du bare 20 byte pluss en konstant overhead per linje. Men databehandling er ganske treg; denne metoden vil bare vinne hvis du har en rask CPU (spesielt en med en maskinvareakselerator for å beregne fordøyelsene) og ikke mye minne i forhold til filstørrelsen og tilstrekkelig lange linjer. Ingen grunnleggende verktøy lar deg beregne en kontrollsum for hver linje; du må bære tolkningen over Perl / Python / Ruby / … eller skrive et dedikert kompilert program.

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

Kommentarer

  • @Gilles Basert på forklaringen din på awk '!seen[$0]++', betyr det at hvis awk ser to duplikatlinjer, vil den beholde den alltid første og ignorere alle påfølgende? (Eller beholder den siste?)
  • @ user779159 Den beholder den første: hver inndatelinje skrives enten ut umiddelbart (første forekomst) eller ikke i det hele tatt (gjentatt forekomst).
  • Men hvordan sammenligner det med sortering -u …?
  • @HashWizard En vanlig sort -u endrer rekkefølgen.Svaret mitt viser løsninger som bevarer rekkefølgen (rekkefølgen av første hendelser, for å være presis).
  • @ Gilles vil du si at det er raskere enn sortering -u for store filer (10G) med 50% duplikater ?

Svar

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

Merk at utdatafilen vil bli sortert.

Kommentarer

  • Ikke så raskt som awk -kommandoen i andre svar, men konseptuelt enkelt!
  • @Johann Jeg gjør dette ganske ofte på filer med hundretusenvis (til og med millioner) korte, nye linjeterminerte strenger. Jeg får resultatene ganske raskt for eksperimentene jeg gjør. Det kan være viktigere hvis det brukes i skript som kjøres igjen og igjen, tidsbesparelser kan være betydelige.
  • Bruk sort -u for å fjerne duplikater under sorteringen, heller enn etter. (Og lagrer minnebåndbredde) som ledes til et annet program). Dette er bare bedre enn awk -versjonen hvis du også vil sortere utdataene dine. (OP på dette spørsmålet ønsker at den opprinnelige bestillingen hans skal bevares , så dette er et godt svar for en litt annen brukstilfelle.)
  • Tok omtrent et minutt, for meg, for en 5,5 millioner linjefil (totalt 1,8 GB). Strålende.

Svar

Forutsatt at du har råd til å beholde like mye som den av dupliserte filen i minnet ( Hvis dataene dine faktisk dupliseres med en faktor 100, bør det være omtrent 20MiB + overhead), kan du gjøre dette veldig enkelt med Perl.

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

Dette bevarer bestillingen også.

Du kan trekke ut antall forekomster av hver linje fra %dup hash hvis du ønsker det, som en ekstra gratis bonus.

Hvis du foretrekker awk, bør dette også gjøre det (samme logikk som perl-versjonen, samme bestilling, samme data samlet i dup variabel):

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

Kommentarer

  • Dette er for bra @Mat, jeg var i ferd med å slurre filen, lol ;-).
  • Venter nå på @ManAtWork for hans sed og awk magic weavery også 🙂
  • fantastisk igjen for awk-tipset: – )
  • Er det mulig å endre perl-skriptet til bare å fjerne e duplisere tilstøtende linjer?
  • @dumbledad: uniq gjør det helt av seg selv

Svar

Ettersom ingen andre svar ga støtte på stedet, er det ett:

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

Kommentarer

  • Bevarer dette bestillingen? Forresten, dette fungerte ikke for meg. Min versjon er: GNU Awk 4.0.2
  • @Leonid ja, det gjør den. Den skriver ut den første forekomsten av en hvilken som helst unik linje. Inplace-støtten ble først introdusert i versjon 4.1, som ble utgitt i 2013.
  • Dette burde være svaret. Det ‘ sletter faktisk den dupliserte strengen i den eksisterende eller gjeldende filen der toppsvaret og de fleste av svarene her bare skriver ut uniq / dupliserte strenger og ikke gjør noe, og vi må lage en annen utgang for å lagre resultatet.

Svar

Du kan bruke uniq http://www.computerhope.com/unix/uuniq.htm

uniq rapporterer eller filtrerer ut gjentatte linjer i en fil.

Kommentarer

  • Når du gir svar, er det å foretrekke å gi noen forklaringer på HVORFOR svaret ditt er det. Så, hvordan skiller dette svaret seg fra flere av de forrige svarene?
  • Fra uniq man-siden: Merk: 'uniq' does not detect repeated lines unless they are adjacent. Så du må først sortere det og løse rekkefølgen på de ikke-dupliserte linjene.

Svar

Python One liners:

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

Kommentarer

  • dette fører til at hele filen slurpes i minnet og passer kanskje ikke til OP ‘ -problemet. Heller ikke garantert å beholde orden
  • Takk for forslaget, jeg ‘ har nettopp lært python .. bare prøvd dette for læringsformål ..:)
  • Her ‘ s en Python 2.7-versjon som ikke er en en-liner, men (kortfattet) returnerer unike linjer med bevaringsrekkefølge uten å laste hele filen i minnet eller opprette en eneste gigantisk streng som skal mates for å skrive ut
  • Takk @ 1_CR Jeg har noe lært i dag 🙂 OrderedDict

Svar

Ingen av svarene her fungerte for meg på min Mac, så jeg skrev en enkel python skript som fungerer for meg. Jeg ignorerer ledende / etterfølgende mellomrom og bryr meg heller ikke om minneforbruk.

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) 

Lagre ovenstående til unike.py og løp slik:

python unique.py inputfile.txt outputfile.txt 

Svar

LØSNING UTEN VEDLIKEHOLD AV DEN ORIGINALE SEKVENSORDENEN

Jeg gjorde det med følgende kodebit.

sort duplicates.txt | uniq > noDuplicates.txt 

sort -kommandoen sorterer linjene alfabetisk, og kommandoen uniq fjerner duplikatene.

MERK: Hvorfor vi sorterte linjene først er at uniq oppdager ikke dupliserte linjer med mindre de ligger ved siden av.

Kommentarer

  • Spørsmålet ber om en metode (helst ) som opprettholder inngangsrekkefølgen; kunne du redigere svaret ditt for å adressere det? Merk at det finnes eksisterende svar ved hjelp av sort som opprettholder inngangsrekkefølgen, og ett svar ved hjelp av sort uten å opprettholde inngangsrekkefølgen, men på en mer effektiv måte enn å røre til uniq.
  • @StephenKitt Edited. Jeg inspiserte andre svar, men kunne ikke ‘ ikke finne noe bare med grunnleggende kommandoer. Takk for tilbakemeldingen.
  • Jeg ga deg en lenke til et svar med bare grunnleggende kommandoer, faktisk bare en kommando, sort -u (som er en del av POSIX ) ;-).
  • @StephenKitt Jeg så svaret. Mine er også en måte å håndtere problemet på. Hva vil du at jeg skal gjøre mer? Skal jeg slette svaret?
  • Nei, ikke slett svaret ditt; Jeg ville bare være sikker på at du var klar over det andre svaret, gitt at du sa at du “ikke kunne ‘ ikke finne noe bare med grunnleggende kommandoer”.

Svar

Med bash 4, en ren-bash-løsning som utnytter assosiative matriser kan brukes. Her er et eksempel

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 

Kommentarer

  • Don ‘ t bruk read sløyfer for å behandle store tekstfiler. bash må lese en-byte-om-gangen for å unngå å overskride en ny linje. Bash er heller ikke veldig rask til tekstbehandling generelt sammenlignet med awk. Hvis du bruker dette, vil read -ra unngå å ta tilbakeslag i innspillene dine. Ikke glem ‘ t å unset llist etter løkken, hvis du legger dette i en skallfunksjon eller bruk den interaktivt.
  • @PeterCordes, eller du kunne bare ha referert til dette 🙂

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *