Le langage de programmation awk est piloté par les données, ce qui le rend propice à des traitements sur les big data. À titre d'exemple, on va effectuer une étude statistique sur les chiffres du plus grand nombre premier actuellement connu, dont l'écriture comporte 77 232 917 chiffres « 1 » en base 2, et 23 249 425 chiffres en base 10 : sont-ils équirépartis, ou y a-t-il une structure cachée dans ce nombre gigantesque ?
Le nom du langage awk est formé par les initiales de ses trois créateurs : Alfred Aho, Peter Weinberger et Brian Kernighan. Ce langage est orienté vers les données, supposées écrites sous forme d'un tableau dans un fichier texte. Il agit sur les lignes du tableau, l'une après l'autre, et les données de chaque ligne s'appellent $1, $2, $3, etc.
1. Nombres premiers
C'est l'abbé Mersenne qui a, au cours du XVIIe siècle, constaté que le nombre 3 qui s'écrit 11 en binaire, est premier, que le nombre 7 qui s'écrit 111 en binaire est premier aussi, ainsi que le nombre 31 qui s'écrit 11111 en binaire, 127 qui s'écrit 1111111 en binaire, etc. En fait, le nombre 15 qui s'écrit 1111 en binaire n'est pas premier, mais il comporte quatre chiffres binaires, et quatre n'est pas premier, alors que deux (nombre de chiffres binaires de 3), trois (nombre de chiffres binaires de 7), cinq (nombre de chiffres binaires de 31) et sept (nombre de chiffres binaires de 127) sont premiers. L'abbé Mersenne a donc trouvé une recette simple (du moins en binaire) pour construire des nombres premiers : écrire un nombre premier de chiffres 1 l'un à la suite de l'autre, en binaire. Mais cette recette ne marche pas toujours : 2047 (qui s'écrit 11111111111 en binaire ; soit onze chiffres binaires, et que onze est un nombre premier) n'est pas un nombre premier puisqu'il est égal à 23×89, comme le montre cette commande :
$ factor 2047
2047 : 23 89
Bien qu'il ne disposât pas de bash, c'est Leonhard Euler qui a découvert ce résultat environ un siècle après la découverte de Mersenne. Malgré cette erreur de Mersenne, les plus grands nombres premiers connus aujourd'hui sont des nombres de Mersenne (c'est-à-dire, des nombres dont l'écriture binaire ne comporte que des 1, et même un nombre premier de chiffre 1) et il y a même un projet appelé « Great Internet Mersenne Prime Search » visant à faire battre des records par des machines en réseau, lesquelles tournent généralement sous Linux, vu la puissance de calcul requise. C'est d'ailleurs sur leur site internet que l'on va chercher le fichier texte comportant les 23 249 425 chiffres de ce nombre en base 10 et awk sera chargé de faire des statistiques dessus.
2. Comment récupérer le nombre premier ?
Le plus grand nombre premier actuellement connu est écrit dans un fichier texte appelé M77232917.txt (d'environ 23 mébioctets) et compressé dans un fichier appelé M77232917.zip de 10 mébioctets seulement. On peut donc obtenir ce fichier par les commandes suivantes (récupérer le fichier, le décompresser puis nettoyer en enlevant le fichier compressé) :
$ wget http://www.mersenne.org/primes/digits/M77232917.zip
$ unzip M77232917.zip
$ rm M77232917.zip
Ce qui fait apparaître dans le dossier courant le fichier texte en question. Il est gros ce fichier texte d'ailleurs : en comptant un caractère par chiffre décimal, on s'attend à avoir un fichier de 23 249 425 octets et en fait il occupe 23 714 413 octets d'après la commande ls avec le paramètre -l. Cela fait tout de même 464 988 caractères qui ne sont pas des chiffres dans le fichier : les retours à la ligne.
3. Une petite séance awk
Un programme en awk ne lit pas de fichier, il agit dessus. Pour comprendre cette subtilité, rien de mieux qu'un Chuck Norris Fact comme celui-ci : « Chuck Norris ne se mouille pas, c'est l'eau qui se Chuck Norris ». De même, un programme awk ne traite pas les data, ce sont les data qui se traitent toutes seules en voyant le awk. On n'a donc pas à gérer des entrées, juste une sortie avec print qui affiche son argument dans la console. Les données du fichier s'appellent des champs (en anglais field) en awk. Une variable appelée NF contient justement le nombre de champs (Number of Fields). Le programme awk va juste boucler sur les champs que l'on va renommer chiffres puisque ce sont justement les chiffres du nombre premier.
3.1 Avec un fichier
Tout programme awk peut être écrit dans un fichier texte, avec l'extension .awk en général. Ceci dit, la plupart des programmes awk sont si courts qu'on les entre directement dans la console. Alors autant comparer les deux approches. Pour commencer, un petit nano stats.awk, juste histoire d'avoir un fichier dans lequel écrire le programme. L'éditeur de texte nano a été choisi, par exemple pour éviter d'entrer dans la querelle Vim/Emacs. Mais n'importe quel éditeur de texte convient bien entendu.
Le programme awk sera composé d'instructions réagissant à des motifs comme le chiffre courant (autrement dit, le chiffre en cours de lecture).
3.1.1 Séparateur de champs
Par défaut, le séparateur de champs en awk est l'espace. Mais ici les chiffres ne sont pas séparés par des espaces. Ils ne doivent pas connaître awk chez GIMPS - Great Internet Mersenne Prime Search(ou alors ils espèrent mettre les chiffres en forme pour faire un poster géant ?). On doit donc avant toute chose (c'est-à-dire sur le motif BEGIN qui est reconnu au lancement du programme) redéfinir la variable FS (Field Separator) comme étant vide de tout caractère. Ce qui s'écrit simplement :
BEGIN { FS="" }
Un programme awk s'écrit entre accolades et est toujours précédé du motif qui déclenche son exécution. Le programme principal ne sera pas précédé d'un motif spécial puisqu'il s'applique au fichier en cours de lecture.
3.1.2 Tableau d'effectifs
Il n'est pas nécessaire en awk, de déclarer les variables : elles se mettent à jour au fur des besoins. La variable effectifs va donc contenir le tableau et par exemple effectifs[4] contiendra in fine, le nombre de fois que le chiffre 4 apparaît dans l'écriture du grand nombre premier. Pour calculer ce nombre, on boucle sur les chiffres (de 1 à NF qui est le nombre total de chiffres) du nombre premier et dans cette boucle on incrémente (avec ++ comme en C, autre langage inventé par Kernighan) la case du tableau indexée par $chiffre : si chiffre=1 alors $chiffre contiendra le chiffre en première position, ici un 4, et effectifs[4]++ va rajouter une unité dans le tableau d'effectifs, puisqu'il y a un chiffre 4 de plus. La boucle s'écrit ainsi (sans motif explicite avant elle puisqu'elle agit sur tout le fichier) :
{ for(chiffre=1;chiffre<=NF;chiffre++) effectifs[$chiffre]++}
3.1.3 C'est tout !
Avec ces deux lignes d'awk, le tableau d'effectifs est constitué et on peut faire des statistiques dessus. Reste à l'afficher, ce qui se fait en bouclant sur les éléments du tableau d'effectifs et pour chacun d'eux, en l'affichant. Pour un résultat plus visible, on affiche le chiffre puis une sorte de flèche avec -> et enfin l'effectif de ce chiffre, le tout une fois qu'on a fini le programme principal awk, soit sur le motif END :
END { for(chiffre in effectifs) print(chiffre,"->",effectifs[chiffre]) }
3.1.4 Et ça donne quoi ?
Voici donc le contenu au complet du fichier stats.awk :
BEGIN { FS="" }
{ for(chiffre=1;chiffre<=NF;chiffre++) effectifs[$chiffre]++}
END { for(chiffre in effectifs) print(chiffre,"->",effectifs[chiffre]) }
Pour exécuter ce script, il faut invoquer la commande awk avec l'option -f qui veut dire qu'on lit le programme dans un fichier (on renonce pour l'instant au one-liner) puis le nom du fichier awk et enfin le nom du fichier à examiner :
$ awk -f stats.awk M77232917.txt
-> 232494
0 -> 2325846
1 -> 2324106
2 -> 2323306
3 -> 2325845
4 -> 2326305
5 -> 2325065
6 -> 2324655
7 -> 2324051
8 -> 2326039
9 -> 2324207
On constate deux problèmes : d'abord, un chiffre autre que les chiffres de 0 à 9 est présent 232 494 fois dans le fichier ; il s'agit des caractères non affichables style saut à la ligne et retour chariot. Ensuite, il a fallu environ 16 secondes pour obtenir cet affichage. Eh oui c'est ça les Big Data, ça prend du temps surtout sur mon vieux Raspberry Pi !
3.2 Version one-liner
En raccourcissant les noms des variables (c à la place de chiffre et e à la place d'effectifs), on peut écrire le programme en une seule ligne et se passer du nom de fichier awk et de l'option -f :
$ awk 'BEGIN {FS=""} {for(c=1;c<=NF;c++) e[$c]++} END {for(c in e) print(c,", ",e[c])}' M77232917.txt
4. Statistiques
L'affichage dans la console laisse penser que les chiffres sont bien équirépartis (chacun apparaît environ 2 325 000 fois dans l'écriture du grand nombre premier). Pour le vérifier, on peut faire un test de khi-deux avec un tableur. Mais pour ça, il faut pouvoir transmettre le tableau d'effectifs au tableur. Une façon simple pour ça est de faire une redirection de l'affichage vers un fichier texte qui sera ouvert par le tableur. En regardant attentivement le one-liner ci-dessus on peut voir qu'entre le chiffre et son effectif on écrit non plus la fausse flèche -> mais une virgule, ce qui permet d'enregistrer le résultat au format « comma separated value » (CSV, valeurs séparées par virgule) et pour peu qu'il ait l'extension .csv n'importe quel tableur digne de ce nom peut l'ouvrir.
4.1 Préparation du fichier
4.1.1 Version tableur
Si on modifie le fichier awk pour qu'au lieu de -> il affiche , dans la ligne 2 et qu'on utilise la commande suivante, alors on obtient un fichier result.csv qu'il est possible d'ouvrir avec un tableur, par exemple pour faire un diagramme :
$ awk -f stats.awk M77232917.txt > result.csv
Mais pour faire des stats, on propose d'utiliser awk, avec un autre séparateur du coup.
4.1.2 Version awk
En awk, le séparateur par défaut est l'espace, donc on propose de n'afficher que les chiffres et leurs effectifs. Cela donne une légère simplification du fichier awk :
BEGIN { FS="" }
{ for(chiffre=1;chiffre<=NF;chiffre++) effectifs[$chiffre]++}
END { for(chiffre in effectifs) print(chiffre,effectifs[chiffre]) }
Alors la commande suivante va produire un nouveau fichier result.txt dans un format plus awk-compatible que le csv :
$ awk -f stats.awk M77232917.txt > result.txt
4.2 Calcul de la moyenne
Pour calculer le chiffre moyen, on doit additionner les produits des chiffres par leurs effectifs et diviser le résultat par l'effectif total. Mais on voit que la première ligne du fichier result.txt contient un nombre à ne pas additionner parce qu'il n'est pas l'effectif d'un chiffre :
232494
0 2325846
1 2324106
2 2323306
3 2325845
4 2326305
5 2325065
6 2324655
7 2324051
8 2326039
9 2324207
4.2.1 Effectif total
L'effectif total est la somme des valeurs de la colonne $2, sauf la première ligne qui ne doit pas être additionnée puisqu'elle concerne les caractères non numériques. Pour cela, on utilise le motif ($1>=0) qui ne fait additionner l'effectif que si le chiffre est bien un chiffre (awk reconnaît un chiffre à ce qu'il est positif) :
$ awk '($1>=0) {total+=$2} END {print(total)}' result.txt
23249425
Cette fois-ci, même sur Raspberry Pi, le résultat est immédiat : le grand nombre premier possède 23 249 425 chiffres en base 10. Ce qui explique que le fichier occupe 23 mébioctets.
4.2.2 Total des chiffres
Comme le chiffre 4 apparaît 2 326 305 fois, il faut multiplier 4 par 2326305 pour prendre en compte toutes ses occurrences. Quand on est à la ligne du 4, ça donne $1*$2, et le nombre total de chiffres s'obtient par ce script :
$ awk '{somme+=$1*$2} END {print(somme)}' result.txt
104621260
Le total des 23 249 425 chiffres est donc 104 621 260. Le chiffre moyen est donc le quotient de ce nombre par le nombre total de chiffres :
$ awk '($1>=0) {total+=$2;somme+=$1*$2} END {print(somme/total)}' result.txt
4.49995
Le chiffre moyen du plus grand nombre premier connu est donc 4,49995 qui est très proche de 4,5. Si les chiffres sont équirépartis ce résultat était prévisible. N'empêche, ça peut faire son effet en soirée, de diffuser cette information !
Conclusion
Dans cet article on a vu comment faire des statistiques sur un volume de données important (23 249 425 chiffres qui sont ceux du plus grand nombre premier connu). Et on n'a utilisé aucun outil dédié de statistiques pour cela, on s'est juste servi d'awk qui est un langage assez minimaliste datant de plus de 40 ans. Et, faut-il le préciser, aucune framboise n'a été maltraitée durant la rédaction de cet article !
