Comparaison et modification de deux fichiers volumineux

J'ai deux fichiers très volumineux (1 000 000 de lignes)

le fichier "A" est composé de lignes de 4 champs séparés par un ;

Extrait du fichier "A":
101429;137;01;0034;
101457;137;01;0036;
101587;137;01;0041;
101470;137;01;0043;
100342;137;01;0052;
96808;137;01;0056;

le fichier "B" est composé de lignes de 17 champs séparés par un ;

Extrait du fichier "B":
PA203961;APA203961;0;;;137;;;;01;0034;000099;G00257;16101995;03705;;
PA203962;APA203962;0;;;118;;;;01;0081;0000035;+00010;01011970;;;
PA203963;APA203963;0;;;118;;;;01;0083;0000500;G00257;16101995;03705;0029;
PA203964;APA203964;0;;;118;;;;01;0089;000000175;W00159;26061998;03881;0038;
PA203965;APA203965;0;;;118;;;;01;0096;000000104;F00271;23032007;;0039;
PA203966;APA203966;0;;;118;;;;01;0097;000000088;B00297;01011989;01651;0041;
PA203967;APA203967;2;;;118;;PAR203967;;01;0099;000000235;*00153;12122000;;0045;


Je souhaiterai rajouter à la fin des lignes du fichier "B" le premier champ du fichier A lorsque:
- le deuxième champ du fichier A est égal au sixième champ du fichier B
- et que le troisième champ du fichier A est égal au dixième champ du fichier B
- et que le quatrième champ du fichier A est égal au onzième champ du fichier B

(Voir champs en gras dans les premières lignes)

Comment le faire le plus rapidement possible?
Avec deux boucles while read c'est beaucoup trop long.
J'ai pensé à awk mais on ne peut pas mettre une boucle awk dans une autre.

Je suis bloqué...

Merci pour votre aide!

Bonjour,

Un premier jet, sans approfondir, sans tester. Je ne pense pas que l'on puisse facilement, en une passe, faire tout le travail. Voici comment je m'y prendrais:

1) Restructurer et trier fichier_A; mettre les 3 champs clés en début de ligne et n'en faire qu'un seul, puis trier selon ce champ:

Code:

---

awk -F ';' '{ printf "%s %s %s;%s\n", $2, $3, $4, $1 }' fichier_A | sort -t ';' -k 1,1 > fichier_A.tmp

---

2) Restructurer et trier fichier_B; même traitement qu'au point 1):

Code:

---

awk -F ';' '{ printf "%s %s %s %s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;\n", $6, $10, $11, $1, $2, $3, $4, $5, $7, $8, $9, $12, $13, $14, $15, $16" }' fichier_B | sort -t ';' -k 1,1 > fichier_B.tmp

---

3) Joindre (dans le sens des bases de données) les deux fichiers:

Code:

---

join -t ':' -v 1 fichier_B.tmp fichier_A.tmp > fichier_C.tmp

---

4) Restructurer les champs dans l'ordre original. Attention, il peut y avoir un champ de plus!

Code:

---

awk -F ';' ' { split($1, key, " "); printf "%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;%s;", $2, $3, $4, $5, $6, key[1], $7, $8, $9, key[2], key[3], $10, $11, $12, $13, $14}; if (NF == 15) {printf "%s;", $15} printf "\n" }' fichier_C.tmp > fichier_D.tmp

---

Attention:
* Ce dernier fichier (fichier_D.tmp) n'est plus trié dans le même ordre: la 1e ligne dans le fichier initial (fichier_B) sera peut-être la 18e dans le fichier final.
* Il faudra bien tester! Je ne fais jamais de script correct en une seule fois. Corrections bienvenues!
* Il faudrait peut-être ajouter un ';' au bout des lignes qui n'ont pas le champ supplémentaire (else à ajouter dans le awk).

Je peux dire que les join sont bien plus rapides que les boucles imbriquées. Je suis curieux de connaître les temps d'exécution, une fois que ça marchera correctement.

Algorithmiquement parlant, le seul moyen que je vois d'éviter la double boucle (O(n2)=1Mx1M arggl), c'est effectivement de procéder avec un tri.
Peut importe que tu réordonne les colonnes ou non. Il faut que tu ais 1 tri alphabétique sur les trois champs de fin du fichier 1, et sur les trois champs qui t'intéresses dans le fichier 2.
Un tri c'est O(nlog(n)), et dans ton cas, ca veux dire 6M d'itération.

Ensuite, il fut que tu fasse avancer tes lignes dans tes deux fichiers en fonction de tes comparaisons. C'est probablement comme ça que fait le join de jmelyn. Si c'est pas le cas, ca sera catastrophique, et il faudra le faire à la main, et dans ce cas passer à un langage capable de faire tout ça sans trop de souci (perl, python, ruby, etc.)

Il est vrai que je n'ai pas expliqué la manière dont j'ai résolu le problème:

Faire correspondre des champs est typique du travail en bases de données et en shell il existe la commande join. Celle-ci n'est pas aussi souple que les requêtes SQL, mais c'est déjà pas mal. Il existe notammant la restriction de n'utiliser qu'une seule clé par table (fichier) et chacune doit être triée sur la clé (pour une raison d'optimisation de la commande*).

Donc les deux premières lignes que je propose sont là pour formatter les deux fichiers d'entrée afin qu'ils puissent être acceptés par la commande join. Il y a 2 formattages avec tri. Puis il y a le join lui-même (la commande est simple). Et enfin un nouveau formattage pour retrouver la suite originale des champs.

Malheureusement, je ne peux "dé-trier" de manière simple parce que je ne connais pas la signification des champs. Peut-être y a-t-il un champ strictement croissant pour remettre bon ordre dans les lignes...

* Edit: Le join (jointure en français) est optimisé. Pour faire correspondre chaque élément des clés des deux tables, la commande ne relit pas toute la table mais seulement de là où elle avait arrêté au tour précédent puisque les clés précédentes sont "inférieures". Le tri de la table en fonction de sa clé est donc indispensable au fonctionnement correcte de la commande. Hum... clair?

Un grand merci à jmelyn!

Avec deux trois modif, je suis arrivé à traiter en 2 minutes les fichiers de
1 000 000 de lignes pour le fichier B et 200 000 pour le fichier A.

Je pense qu'on peut même faire mieux, le shell m'avertit que le sort sur une entrée redirigée est plus lent que sur un fichier.
Donc on peut gratter quelques secondes...

Encore merci jmelyn!

C'est bien sûr que ça marche? Pas d'erreur ou d'oubli dans le fichier final? Il est vraiment difficile de trouver les problèmes avec de si gros fichiers.

Je ne sais pas s'il est bon de faire des pipes (|) plutôt que de passer par des fichiers parce que les volumes de données sont vraiment gros et il faut beaucoup de mémoire. Par contre, il serait possible de paralléliser les deux premières commandes sur une machine multi-processeurs: puisque ce sont deux sort, on doit pouvoir gagner plus que quelques secondes. Je crois que c'est simple, mais j'avoue ici mon incompétence...

Par curiosité, y a-t-il des temps pour la solution des boucles imbriquées?

En fait, après un peu de lecture, il semble que la parallélisation soit facile à réaliser (2 modifs):

Code:

---

1 2 3 4 5

awk -F ';' '... fichier_A.tmp & awk -F ';' '... fichier_B.tmp wait join... fichier_C.tmp awk -F ';' '... fichier_D.tmp

---

Il y a intérêt à agir de la sorte si:

• Il y a plusieurs processeurs dans la machine ou le processeur est multi-core (ou les deux!)
• Les deux fichiers à trier sont volumineux.

Là aussi quelques mesures de temps seraient appréciées (genre time fichier_script).

Je doute que la parallélisation soit un gros atout. Sur une machine réelle, les temps du sort seront probablement dominé par les accès disques. Et le fait d'en faire deux en même temps risque plus de dégrader ces accès, de perturber le cache, etc.

Sinon, bravo, joli solution. Je n'aurais pas su faire ça en shell. join est une commande à retenir...