Comment supprimer les lignes en double dans un fichier texte?

126

Un de mes énormes fichiers texte (jusqu’à 2 Gio) contient environ 100 doublons exacts de chaque ligne qu’il contient (inutile dans mon cas, car le fichier est une table de données de type CSV).

Ce dont j'ai besoin, c’est d’éliminer toutes les répétitions (de préférence, mais cela peut être sacrifié pour une amélioration significative des performances) en maintenant l’ordre de séquence original. Dans le résultat, chaque ligne doit être unique. S'il y a 100 lignes égales (généralement, les doublons sont répartis dans le fichier et ne seront pas voisins), il ne restera plus qu'une seule de ces lignes.

J'ai écrit un programme en Scala (considérez-le en Java si vous ne connaissez pas Scala) pour l'implémenter. Mais peut-être existe-t-il des outils natifs C-écrits plus rapides capables de le faire plus rapidement?

MISE À JOUR: la awk '!seen[$0]++' filenamesolution semblait bien fonctionner pour moi tant que les fichiers étaient proches de 2 Gio ou moins, mais maintenant que je vais nettoyer un fichier de 8 Gio, cela ne fonctionne plus. Cela semble prendre une infinité sur un Mac avec 4 Go de RAM et un PC Windows 7 64 bits avec 4 Go de RAM et 6 Go échangés, la mémoire manque. Et je ne suis pas enthousiaste à l'idée d'essayer Linux avec 4 Go de RAM, compte tenu de cette expérience.

Ivan
la source
cela va détruire votre commande mais, avez-vous essayé de trier -u, je ne sais pas comment ou s'il peut fonctionner sur un fichier aussi
volumineux
5
C n’est souvent pas beaucoup plus rapide que Java, et si vous l’exécutez (dans l’ordre) maintenant, il y a de bonnes chances que cela se termine avant que vous obteniez une réponse ici, que vous la mettiez en œuvre et que l’exécution se termine; hors service, sort -usera probablement plus rapide.
Kevin

Réponses:

215

Une awksolution vue sur #bash (Freenode):

awk '!seen[$0]++' filename
enzotib
la source
1
Je viens d’essayer cela sur un fichier 2G et cela a pris trois minutes sur mon cahier. Pas mal. J'ai aussi essayé uniq nomfichier | awk '! seen [$ 0] ++', mais ce n'était pas plus rapide.
mgjk
C’est étonnamment plus rapide qu’une awkversion plus détaillée utilisant 2 recherches sur un tableau (expliquée plus en détail dans la réponse de Gilles): 0m36.132s vs 0m49.958s .. pour 50 millions de lignes .. Je pensais que le goulot d’étranglement serait l’E / S, mais la recherche de tableau supplémentaire est ... 1 million d'éléments dans le tableau semble avoir une
incidence
Mais comment cela se compare trier -u ....?
HashWizard
1
@HashWizard: cette commande ne trie pas, mais élimine chaque occurrence suivante de la même ligne
enzotib
1
@ MaxWilliams Oui, cela fonctionne si elles sont distribuées au hasard.
setholopolus
47

Il existe une méthode simple (qui n’est pas évidente), qui utilise des utilitaires standard et qui ne nécessite pas une mémoire importante sort, mais qui, dans la plupart des implémentations, offre des optimisations spécifiques pour les fichiers volumineux (un bon algorithme de tri externe). Un avantage de cette méthode est qu’elle ne boucle que sur toutes les lignes des utilitaires spéciaux, jamais des langages interprétés.

<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

Si toutes les lignes commencent par un caractère non-blanc, vous pouvez vous passer de certaines des options suivantes:

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

Pour une grande quantité de duplication, une méthode qui nécessite uniquement de stocker une copie de chaque ligne en mémoire fonctionnera mieux. Avec quelques frais d'interprétation, il y a un script awk très concis pour cela (déjà posté par enzotib ):

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

De manière moins concise: affichez !seen[$0] {print} {seen[$0] += 1}la ligne courante si elle n’a pas encore été vue, puis incrémentez le seencompteur de cette ligne (les variables non initialisées ou les éléments de tableau ont la valeur numérique 0).

Pour les longues lignes, vous pouvez économiser de la mémoire en ne conservant qu'une somme de contrôle non spoofable (par exemple, un résumé cryptographique) de chaque ligne. Par exemple, avec SHA-1, vous n'avez besoin que de 20 octets plus un temps système constant par ligne. Mais l'informatique digère est plutôt lente; cette méthode ne gagnera que si vous avez un processeur rapide (en particulier avec un accélérateur matériel pour calculer les résumés) et pas beaucoup de mémoire par rapport à la taille du fichier et des lignes suffisamment longues. Aucun utilitaire de base ne vous permet de calculer une somme de contrôle pour chaque ligne; vous devrez supporter les frais d'interprétation de Perl / Python / Ruby /… ou écrire un programme compilé dédié.

<input perl -MDigest::MD5 -ne '$seen{Digest::MD5::md5($_)}++ or print' >output
Gilles
la source
@Gilles En vous basant sur votre explication awk '!seen[$0]++', cela signifie-t-il que si awk voit 2 lignes en double, il gardera toujours la première et ignorera toutes les lignes suivantes? (Ou il gardera le dernier?)
user779159
1
@ user779159 La première est conservée: chaque ligne de saisie est soit imprimée immédiatement (première occurrence), soit pas du tout (répétition).
Gilles
Mais comment cela se compare trier -u ...?
HashWizard
@HashWizard Un plain sort -uchange l'ordre. Ma réponse montre des solutions qui préservent l'ordre (l'ordre des premières occurrences, pour être précis).
Gilles
@ Gilles dirais-tu qu'il est plus rapide que sort -u pour les gros fichiers (10G) avec 50% de doublons?
HashWizard
25
sort -u big-csv-file.csv > duplicates-removed.csv

Notez que le fichier de sortie sera trié.

Vladislavs Dovgalecs
la source
1
Pas aussi vite que la awkcommande dans d'autres réponses, mais conceptuellement simple!
Johann
@Johann Je le fais assez souvent sur des fichiers contenant des centaines de milliers (voire des millions) de petites chaînes terminées par une nouvelle ligne. Je reçois les résultats assez rapidement pour les expériences que je fais. Cela peut être plus important si utilisé dans des scripts qui sont exécutés à plusieurs reprises, les gains de temps peuvent être considérables.
Vladislavs Dovgalecs
1
Utilisez cette option sort -upour supprimer les doublons pendant le tri, plutôt qu'après. (Et économise de la bande passante mémoire) en le dirigeant vers un autre programme). Ce n'est que mieux que la awkversion si vous voulez que votre sortie soit triée aussi. (Le PO sur cette question veut que sa commande originale soit préservée , alors c'est une bonne réponse pour un cas d'utilisation légèrement différent.)
Peter Cordes
A pris environ une minute, pour moi, pour un fichier en ligne de 5,5 millions (1,8 Go au total). Brillant.
Max Williams
18

En supposant que vous puissiez vous permettre de conserver autant que le fichier dédupliqué en mémoire (si vos données sont effectivement dupliquées par un facteur 100, cela devrait représenter environ 20 Mo + de temps système), vous pouvez le faire très facilement avec Perl.

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

Cela préserve l'ordre aussi.

Vous pouvez extraire le nombre d'occurrences de chaque ligne du %duphachage si vous le souhaitez, sous forme de bonus gratuit.

Si vous préférez awk, vous devriez le faire aussi (même logique que la version de Perl, même ordre, mêmes données rassemblées dans la dupvariable):

$ awk '{if (++dup[$0] == 1) print $0;}' input_file > output_file
Tapis
la source
C'est trop bon @Mat, j'étais sur le point de slurp le fichier, lol ;-).
Nikhil Mulley
En attente de @ManAtWork pour ses magiciens sed et awk aussi :-)
Nikhil Mulley
génial encore pour le conseil awk :-)
Nikhil Mulley
1
Est-il possible de changer le script Perl pour ne supprimer que les lignes dupliquées adjacentes?
Dumbledad
2
@dumbledad: le uniqfait-il tout seul
Mat
3

Aucune autre réponse n'ayant fourni de support sur place, en voici une:

gawk -i inplace '!a[$0]++' file
Jan Chren - rindeal
la source
Est-ce que cela préserve l'ordre? À propos, cela n'a pas fonctionné pour moi. Ma version est:GNU Awk 4.0.2
Leonid
1
@ Leonid oui, c'est le cas. Il imprime la première occurrence d'une ligne unique. Le support inplace a été introduit pour la première fois dans la version 4.1, sortie en 2013.
Jan Chren - rindeal le
3

Vous pouvez utiliser uniq http://www.computerhope.com/unix/uuniq.htm

uniq signale ou filtre les lignes répétées d'un fichier.

Mahmoud Zalt
la source
Lorsque vous répondez, il est préférable d' expliquer POURQUOI votre réponse est la bonne. Alors, en quoi cette réponse diffère-t-elle de plusieurs réponses précédentes?
Stephen Rauch
1
Sur la page de manuel uniq: Remarque: 'uniq' does not detect repeated lines unless they are adjacent. vous devez donc d'abord le trier et perdre l'ordre des lignes non dupliquées.
Vindolin
2

Python One liners:

python -c "import sys; lines = sys.stdin.readlines(); print ''.join(sorted(set(lines)))" < InputFile
Rahul Patil
la source
cela fait que le fichier entier est inséré dans la mémoire et peut ne pas convenir au problème du PO. Aussi pas garanti pour maintenir l'ordre
iruvar
Merci pour la suggestion, je viens d'apprendre le python .. je viens de l'essayer pour apprendre ... :)
Rahul Patil
Voici une version Python 2.7 qui n'est pas une ligne mais qui retourne (de manière succincte) des lignes uniques en préservant l'ordre sans charger le fichier entier en mémoire ni créer une seule chaîne gigantesque à alimenter
iruvar
Merci @ 1_CR J'ai quelque chose à apprendre aujourd'hui :)OrderedDict
Rahul Patil
0

Aucune des réponses ici ne fonctionnant pour moi sur mon Mac, j'ai donc écrit un script python simple qui fonctionne pour moi. J'ignore les espaces de début et de fin et je ne me soucie pas de la consommation de mémoire.

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)

Enregistrez ce qui précède dans unique.py et exécutez-le comme ceci:

python unique.py inputfile.txt outputfile.txt
Jared
la source
-1

Avec bash 4, une solution pure-bash tirant parti des tableaux associatifs peut être utilisée. Voici un exemple

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
iruvar
la source
2
N'utilisez pas de readboucles pour traiter de gros fichiers texte. bash doit lire un octet à la fois pour éviter de dépasser une nouvelle ligne. Bash n’est pas très rapide en traitement de texte en général par rapport à awk. Si vous utilisez ceci, vous read -raéviterez de manger des barres obliques inverses dans votre entrée. N'oubliez pas non plus unset llist après la boucle, si vous mettez ceci dans une fonction shell ou si vous l'utilisez de manière interactive.
Peter Cordes
2
@PeterCordes, ou vous pourriez avoir simplement référencé ce :-)
Iruvar