vendredi 2 octobre 2009

Loi de Zipf sous Linux

Vers 1935, George Kingsley Zipf entreprit d'analyser la fréquence des mots dans Ulysses de James Joyce...

Après avoir classé les mots par leur fréquence d'apparition, il se serait aperçu que si le mot le plus fréquent apparaissait N fois, le dixième mot le plus fréquent apparaissait N/λ, le centième mot, N/λ², etc...

Il est aujourd'hui facile de vérifier ses travaux.

D'abord, il faut aller chercher Ulysses sur le Projet Gutenberg et en traitant le texte avec des outils standards Unix/Linux, on obtient assez facilement le résultat attendu.

Il suffit, en effet, d'envoyer le texte dans une série de filtres :

cat 4300-8.txt |

La première chose à faire est de transformer toutes les majuscules en minuscules pour que 'The' soit équivalent à 'the' :

|tr [A-Z] [a-z]

Ensuite, on sépare tous les mots pour en mettre un sur chaque ligne. Le plus simple est de substituer tous les caractères non alphabétiques par un retour à la ligne :

|sed 's/[^a-z]/\n/g'

Tant qu'à faire, supprimons toutes les lignes vides créées :

|awk '/[a-z]/{print $1;}'

Nous avons maintenant une liste de mots qu'il convient de trier :

|sort

Et compter chaque mot :

|uniq -c

Nous ne nous intéressons pas aux mots en eux-mêmes, mais au nombre de fois qu'ils apparaissent :

|awk '{print $1;}'

On va trier cette liste de fréquences par ordre descendant pour avoir la plus haute fréquence au premier rang (première ligne) :

|sort -rn

Et numéroter les lignes pour obtenir deux colonnes : le rang et la fréquence :

|pr -n -t

En résumé :

time cat 4300-8.txt|tr [A-Z] [a-z]|sed 's/[^a-z]/\n/g'|awk '/[a-z]/{print $1;}'|sort|uniq -c|awk '{print $1;}'|sort -rn|pr -n -t > zipf.data

Cela a pris, en gros, 9 secondes, bien moins que ce que le pauvre monsieur Zipf a dû y consacrer.

Si on trace le graphe log/log résultant avec Gnuplot

set logscale
set xlabel 'rang'
set ylabel 'frequence'
set title 'Loi de Zipf (Ulysses)'
set term png
set output 'UlyssesZipf.png'
plot 'zipf.data'

On obtient :




Un autre truc amusant (qui n'a probablement rien à voir avec Zipf) est la génération d'un graphique log/log qui montre 'le nombre 'y' de mots présents 'x' fois'.

À partir de la liste des fréquences, je compte combien de mots apparaissent un fois, deux fois,...

|sort -n|uniq -c

Et, comme on veut obtenir un graphique : nombre 'y de fois' qu'un mot apparaît 'x fois', il faut inverser les colonnes avant de l'injecter dans Gnuplot :

|awk '{print $2" "$1}'

En résumé :

time cat 4300-8.txt|tr [A-Z] [a-z]|sed 's/[^a-z]/\n/g'|awk '/[a-z]/{print $1;}'|sort|uniq -c|awk '{print $1;}'|sort -n|uniq -c|awk '{print $2" "$1;}' > data

Il ne reste plus qu'à 'gnuploter' tout ça :

set logscale
set term png
set output 'UlyssesZipf.png'
plot 'data'

Et voilà!

On 'voit bien' que sur un graphique log/log,
le nombre 'y' de fois qu'un mot apparaît 'x' fois
suit une loi de puissance.