Comment trouver des lignes en double dans de nombreux fichiers volumineux?

9

J'ai ~ 30k fichiers. Chaque fichier contient environ 100 000 lignes. Une ligne ne contient aucun espace. Les lignes d'un fichier individuel sont triées et dupliquées gratuitement.

Mon objectif: je veux trouver toutes les lignes en double dans deux fichiers ou plus, ainsi que les noms des fichiers contenant des entrées en double.

Une solution simple serait la suivante:

cat *.words | sort | uniq -c | grep -v -F '1 '

Et puis je courrais:

grep 'duplicated entry' *.words

Voyez-vous un moyen plus efficace?

Lars Schneider
la source

Réponses:

13

Étant donné que tous les fichiers d'entrée sont déjà triés, nous pouvons contourner l'étape de tri réelle et simplement utiliser sort -mpour fusionner les fichiers ensemble.

Sur certains systèmes Unix (à ma connaissance uniquement Linux), cela peut suffire

sort -m *.words | uniq -d >dupes.txt

pour obtenir les lignes dupliquées écrites dans le fichier dupes.txt.

Pour trouver de quels fichiers proviennent ces lignes, vous pouvez alors faire

grep -Fx -f dupes.txt *.words

Cela demandera grepde traiter les lignes entre dupes.txt( -f dupes.txt) comme des modèles de chaînes fixes ( -F). grepexigera également que la ligne entière corresponde parfaitement du début à la fin ( -x). Il imprimera le nom du fichier et la ligne sur le terminal.

Unices non Linux (ou même plus de fichiers)

Sur certains systèmes Unix, 30000 noms de fichiers se développeront en une chaîne trop longue pour passer à un seul utilitaire (la signification sort -m *.wordséchouera avec Argument list too long, ce qui se produit sur mon système OpenBSD). Même Linux s'en plaindra si le nombre de fichiers est beaucoup plus important.

Trouver les dupes

Cela signifie que dans le cas général (cela fonctionnera également avec bien plus que 30000 fichiers), il faut "découper" le tri:

rm -f tmpfile
find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

Alternativement, créer tmpfilesans xargs:

rm -f tmpfile
find . -type f -name '*.words' -exec sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh {} +

Cela trouvera tous les fichiers dans le répertoire courant (ou ci-dessous) dont les noms correspondent *.words. Pour un morceau de taille appropriée de ces noms à la fois, dont la taille est déterminée par xargs/ find, il les fusionne dans le tmpfilefichier trié . S'il tmpfileexiste déjà (pour tous sauf le premier bloc), ce fichier est également fusionné avec les autres fichiers du bloc actuel. Selon la longueur de vos noms de fichiers et la longueur maximale autorisée d'une ligne de commande, cela peut nécessiter plus ou beaucoup plus de 10 exécutions individuelles du script interne ( find/ le xargsfera automatiquement).

Le shscript "interne" ,

if [ -f tmpfile ]; then
    sort -o tmpfile -m tmpfile "$@"
else
    sort -o tmpfile -m "$@"
fi

utilise sort -o tmpfilepour sortir vers tmpfile(cela n'écrasera pas tmpfilemême si c'est aussi une entrée pour sort) et -mpour faire la fusion. Dans les deux branches, "$@"s'étendra à une liste de noms de fichiers entre guillemets individuels transmis au script à partir de findou xargs.

Ensuite, il suffit d' exécuter uniq -dsur tmpfilepour obtenir toutes les lignes qui sont dupliquées:

uniq -d tmpfile >dupes.txt

Si vous aimez le principe "DRY" ("Ne vous répétez pas"), vous pouvez écrire le script interne comme

if [ -f tmpfile ]; then
    t=tmpfile
else
    t=/dev/null
fi

sort -o tmpfile -m "$t" "$@"

ou

t=tmpfile
[ ! -f "$t" ] && t=/dev/null
sort -o tmpfile -m "$t" "$@"

D'où viennent-ils?

Pour les mêmes raisons que ci-dessus, nous ne pouvons pas utiliser grep -Fx -f dupes.txt *.wordspour trouver d'où proviennent ces duplications, nous utilisons donc à findnouveau:

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt {} +

Puisqu'il n'y a pas de traitement "compliqué" à faire, nous pouvons invoquer grepdirectement depuis -exec. L' -execoption prend une commande utilitaire et placera les noms trouvés dans {}. Avec +à la fin, findplacera autant d'arguments à la place {}que le shell actuel prend en charge dans chaque appel de l'utilitaire.

Pour être totalement correct, on peut vouloir utiliser soit

find . -type f -name '*.words' \
    -exec grep -H -Fx -f dupes.txt {} +

ou

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt /dev/null {} +

pour être sûr que les noms de fichiers sont toujours inclus dans la sortie de grep.

La première variante utilise grep -Hpour toujours afficher les noms de fichiers correspondants. La dernière variante utilise le fait qui grepinclura le nom du fichier correspondant si plus d'un fichier est donné sur la ligne de commande.

Cela est important car le dernier morceau de noms de fichiers envoyé grepdepuis ne findpeut en fait contenir qu'un seul nom de fichier, auquel cas grepil ne le mentionnerait pas dans ses résultats.


Matériel bonus:

Dissection de la commande find+ xargs+ sh:

find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

find . -type f -name '*.words'générera simplement une liste de chemins à partir du répertoire courant (ou ci-dessous) où chaque chemin est celui d'un fichier normal ( -type f) et qui a un composant de nom de fichier à la fin qui correspond *.words. Si seul le répertoire courant doit être recherché, on peut ajouter -maxdepth 1après le ., avant -type f.

-print0s'assurera que tous les chemins trouvés sont sortis avec un caractère \0( nul) comme délimiteur. Il s'agit d'un caractère qui n'est pas valide dans un chemin Unix et il nous permet de traiter les chemins d'accès même s'ils contiennent des caractères de nouvelle ligne (ou d'autres choses étranges).

finddirige sa sortie vers xargs.

xargs -0lira la \0liste de chemins d'accès délimitée et exécutera l'utilitaire donné à plusieurs reprises avec des morceaux de ceux-ci, en s'assurant que l'utilitaire est exécuté avec juste assez d'arguments pour ne pas faire se plaindre le shell d'une liste d'arguments trop longue, jusqu'à ce qu'il n'y ait plus d'entrée de find.

L'utilitaire invoqué par xargsest shavec un script donné sur la ligne de commande sous forme de chaîne utilisant son -cindicateur.

Lors de l'appel sh -c '...some script...'avec les arguments suivants, les arguments seront disponibles pour le script dans $@, à l' exception du premier argument , qui sera placé $0(c'est le "nom de la commande" que vous pouvez repérer, par exemple topsi vous êtes assez rapide). C'est pourquoi nous insérons la chaîne shcomme premier argument après la fin du script réel. La chaîne shest un argument factice et peut être n'importe quel mot (certains semblent préférer _ou sh-find).

Kusalananda
la source
À la fin de votre 1er bloc de script shell, à quoi ça sert fi' sh?
dan
@danielAzuelos Le fiest la fin de l' ifinstruction dans le shscript shell "interne" . La 'fin de ce script shell (le script entier est une chaîne entre guillemets simples). Le shsera passé au script interne dans $0(ne fait pas partie de $@, qui contiendra les noms de fichiers). Dans ce cas, cette shchaîne peut en fait être n'importe quel mot. Si vous omettez shà la fin, le premier nom de fichier serait transmis $0et ne ferait pas partie du traitement effectué par le script shell interne.
Kusalananda
8

Les lignes d'un fichier individuel sont triées et dupliquées gratuitement.

Ce qui signifie que vous pourriez probablement trouver une utilité pour sort -m:

 -m, --merge
        merge already sorted files; do not sort

L'autre alternative évidente à cette opération serait awkde collecter simplement les lignes dans un tableau et de les compter. Mais comme l'a commenté @ dave_thompson_085 , ces 3 000 millions de lignes (ou autant de lignes uniques) prendraient probablement une quantité considérable de mémoire à stocker, de sorte que cela pourrait ne pas fonctionner très bien.

ilkkachu
la source
3

Avec awk, vous pouvez obtenir toutes les lignes répétées dans tous les fichiers en une seule commande courte:

$ awk '_[$0]++' *.words

Mais il répétera les lignes si une ligne existe 3 fois ou plus.
Il existe une solution pour obtenir uniquement le premier doublon:

$ awk '_[$0]++==1' *.words

Cela devrait être assez rapide (si les répétitions sont peu nombreuses) mais consommera beaucoup de mémoire pour garder toutes les lignes en mémoire. Peut-être, selon vos fichiers réels et vos répétitions, essayez d'abord avec 3 ou quatre fichiers.

$ awk '_[$0]++==1' [123]*.words

Sinon, vous pouvez faire:

$ sort -m *.words | uniq -d

Qui imprimera les lignes répétées uniq.

Isaac
la source
2
+1 poursort -m * | uniq -d
Jeff Schaller
awk peut éviter les répétitions avec 'x[$0]++==1'mais aura en effet besoin de beaucoup de mémoire; si les lignes 3G ont disons des valeurs distinctes de 1G, et si votre awk a besoin de dire 50 octets pour une entrée de hasharray mappant une chaîne (probablement courte) à la valeur unit, c'est 50 Go. Pour une entrée triée, vous pouvez le faire uniq -dmanuellement avec awk '$0==p&&n++==1;$0!=p{p=$0;n=1}'mais pourquoi s'embêter?
dave_thompson_085
@ dave_thompson_085 Merci pour le concept de ==1, bonne idée.
Isaac
En supposant que 30000 fichiers avec 100000 lignes de 80 caractères chacun et aucun doublon , cela nécessitera awkde stocker 2,4E11 octets (223 Gio).
Kusalananda
sort -m *.words | uniq -dfonctionne très bien! Après le processus, je cours greppour trouver un fichier contenant une entrée dupliquée. Voyez-vous un moyen d'imprimer au moins un nom de fichier qui contient une entrée dupliquée?
Lars Schneider
3

Solution optimisée sort+ uniq:

sort --parallel=30000 *.words | uniq -d
  • --parallel=N - changer le nombre de tris exécutés simultanément en N
  • -d, --repeated - imprimer uniquement les lignes en double, une pour chaque groupe
RomanPerekhrest
la source