Ce TP est à rendre par mail en fin de séance à : edauce@centrale-marseille.fr
%pylab inline
import unicodedata
import re
import string
import math
Soit un document texte $d$.
Il est possible grâce aux expressions régulières d’extraire de ce texte l’ensemble des mots qu’il contient.
Soit $t$ un terme de $d$. On nomme fréquence $f(t)$ le nombre d’apparitions de ce terme dans le texte divisé par le nombre total de mots du texte.
Cette fréquence étant connue pour chaque terme, il est possible de trier les termes par ordre décroissant de fréquence.
Si l'on dresse une table de l'ensemble des termes différents d'un texte quelconque, classés par ordre de fréquences décroissantes, on constate que la fréquence d'un terme $f(t)$ est inversement proportionnelle à son rang $r(t)$ dans la liste , soit:
$$f(t) \simeq \frac{K}{r(t)}$$Cette égalité, qui n'est vraie qu'en approximation, est indépendante des locuteurs, des types de textes et des langues. Il semble ainsi qu'il s'agisse véritablement d'un trait général des énoncés textuels.
On souhaite tester cette propriété sur un ou plusieurs textes. Il est nécessaire pour que l’approximation soit valable de prendre un texte de grande taille.
Vous trouverez à l’adresse http://www.gutenberg.org/catalog/ de nombreux textes en de nombreuses langues. On vous demande d'établir la fréquence des différents mots sur un corpus de plus de 10000 mots, et de vérifier la validité de la loi de Zipf.
Sur le site de Gutenberg, choisissez un texte au format “texte brut utf-8”. Par exemple :
http://www.gutenberg.org/cache/epub/17489/pg17489.txt
Enregistrez ce fichier dans le même dossier que le notebook, puis ouvrez-le comme ci-dessous:
f = open('pg17489.txt', 'r')
Le but est maintenant de compter (de manière approximative) le nombre total de mots.
Rappel : un mot est simplement défini par l’expression régulière r'\b\w+\b'
.
La commande re.findall(r'\b\w+\b',texte)
crée une liste contenant les mots d'un texte.
On cherche maintenant à compter la fréquence d’apparition de chaque terme. Il faut donc pour chaque terme différent définir un compteur qui sera incrémenté à chaque fois que le terme est rencontré dans le texte. Pour faire cela, on utilisera une structure de données de type dictionnaire.
Chaque terme est une clé du dictionnaire. La valeur associée correspond au nombre d’apparitions du terme dans le texte.
Construisez un dictionnaire vide, puis, pour chaque mot trouvé, si le mot est inconnu, créer une entrée dans le dictionnaire, sinon incrémenter le compteur de ce mot.
Le nombre de termes est égal au nombre d’entrées du dictionnaire après avoir parcouru tout le texte.
Remarque : vous pouvez améliorer votre dictionnaire en mettant tous les mots rencontrés en minuscules. (utilisez, par exemple, str.lower(mot)
qui transforme les majuscules rencontrées dans le mot en minuscules).
1. Affichez le nombre de termes utilisés et comparez-le au nombre total de mots trouvé précédemment.
2. Affichez le nombre d'apparitions des mots 'à'
, 'garçon'
, et 'étoilée'
.
Pour établir la loi de Zipf, il faut établir un classement sur les termes en fonction de leur fréquence.
Pour réaliser ce classement, nous allons créer une nouvelle structure de données qui est une liste $L$ contenant des tuples (fréquence, terme)
Pour chaque entrée t : n
du dictionnaire, ajouter à la liste $L$ le tuple (n/nb_mots,t)
où nb_mots est le nombre total de mots.
Il faut maintenant classer les tuples selon l’ordre décroissant de la fréquence. Pour cela, utilisez la méthode sort
appliquée à la liste, en précisant que l’ordre de classement est inversé (reverse = True
).
La fréquence d’apparition des lettre diffère d’une langue à l’autre. Nous chercherons à déterminer à quel langage appartient un texte en étudiant la fréquence d’apparition des lettre qui le composent.
Pour déterminer la langue d’un document, on calculera les fréquences d’apparition typiques de lettres pour différents langages, par exemple l’italien, l’anglais, le français et l’allemand, en choisissant des textes d’au moins 10000 lignes, par exemple :
Pour un langage donné, l’information de Shannon associée à une lettre $\alpha$ vaut : $$I(\alpha) = -\log 2(p(\alpha)) $$ où $p(\alpha)$ est la probabilité d’apparition de la lettre.
L'entropie d'une langue donnée se définit comme: $$H = -\sum_{\alpha \in A} p(\alpha) \log 2(p(\alpha)) $$ où A est l'alphabet.
En vous inspirant de l’exercice précédent, ouvrez un document texte (pris par exemple dans la base Gutenberg) et :
Remarque : pour des raisons de simplicité, on ne s’intéressera qu’aux caractères non-accentués.
Soit d le document étudié. Pour supprimer des accents :
import unicodedata
d = unicodedata.normalize('NFKD', d)
d = str(d.encode('ascii', 'ignore'))
On définit la distance euclidienne entre 2 documents textes d1 et d2 comme :
$$\text{dist}(d1,d2) = \sqrt{\sum_{\alpha \in A} (h_1(\alpha) - h_2(\alpha))^2}$$
où A est l’alphabet, avec :
$$ h_1(\alpha) = - p_1(\alpha) \log_2(p_1(\alpha))$$
où $p_1(\alpha)$ est la frequence du caractère $\alpha$ dans le document 1.
De même : $$ h_2(\alpha) = - p_2(\alpha) \log_2(p_2(\alpha))$$ où $p_2(\alpha)$ est la frequence du caractère $\alpha$ dans le document 2.
On cherche à déterminer la langue dans laquelle est écrit un document d.
Pour deux distributions de probabilités discrètes P et Q la divergence de Kullback–Leibler de P par rapport à Q est définie par : $$ D_{KL}(P||Q) = \sum_{\alpha \in A} P(\alpha) \log \frac{P(\alpha)}{Q(\alpha)}$$
Le programme doit déterminer la langue d’un texte inconnu $d$
trouve_langue
qui prend en argument une chaine de caractères et affiche la langue dans laquelle le texte est écrit (celle pour laquelle la divergence de KL est minimale)
En cryptographie on s'occupe d’unigrammes, de bigrammes et de trigrammes de lettres.
Voici pour un texte anglais, le nombre d'apparition des 10 bigrammes et des 10 trigrammes les plus fréquents :
Bigrammes | TH | HE | IN | ER | AN | RE | ES | ON | ST | NT |
---|---|---|---|---|---|---|---|---|---|---|
Nombres | 3020 | 2496 | 2078 | 1821 | 1676 | 1467 | 1345 | 1318 | 1290 | 1267 |
Remarques : les 52 (sur 676) bigrammes les plus fréquents, représentent plus de la moitié de toutes les occurrences.
Trigrammes | THE | AND | ING | ENT | ION | NTH | TER | INT | OFT | THA |
---|---|---|---|---|---|---|---|---|---|---|
Nombres | 2069 | 819 | 607 | 487 | 428 | 381 | 367 | 357 | 355 | 355 |
En prenant en compte les espaces et signes de ponctuation entre les mots, on peut aussi générer les informations suivantes :
On vous demande d'établir les mêmes statistiques pour le français, l'allemand et l'italien (avec des bases de lettres de taille > 30.000 lettres). Fournir également les mots de 2 lettres et de 3 lettres les plus fréquents.
Pour générer du “pseudo-texte” en francais, on vous demande de réaliser un modèle bi-gramme, qui génère une suite de caractères proportionnellement à leur probabilité conditionnelle p(α|β) où β est le caractère précédent le caractère à générer.
Vous utiliserez la fonction numpy.random.multinomial()
de la librairie numpy
pour effectuer le tirage.