Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révisionLes deux révisions suivantes | ||
tc_info:2020_cm_textes [2023/11/29 17:15] – [1 Données texte] edauce | tc_info:2020_cm_textes [2023/11/30 00:03] – [5. Modèles génératifs] edauce | ||
---|---|---|---|
Ligne 137: | Ligne 137: | ||
* Il existe une fonction '' | * Il existe une fonction '' | ||
* Exemple : | * Exemple : | ||
- | < | + | < |
- | s = 'paul.poitevin@centrale-marseille.fr' | + | String |
- | b = s.encode() | + | |
+ | // Encodage de la chaîne en bytes en utilisant UTF-8 | ||
+ | byte[] | ||
+ | |||
+ | // Affichage des bytes encodés | ||
+ | for (byte byteValue : b) { | ||
+ | System.out.print(byteValue + " "); | ||
+ | } | ||
</ | </ | ||
+ | |||
+ | ce qui affiche: | ||
+ | < | ||
+ | 112 97 117 108 46 112 111 105 116 101 118 105 110 64 99 101 110 116 114 97 108 101 45 109 97 114 115 101 105 108 108 101 46 102 114 | ||
+ | </ | ||
+ | |||
Un nombre en base 256 est difficile à lire et interpréter. On le traduit en base 10 : | Un nombre en base 256 est difficile à lire et interpréter. On le traduit en base 10 : | ||
- | < | + | < |
- | i = int.from_bytes(b, byteorder=' | + | // Conversion des bytes en BigInteger |
- | print("i =", i) | + | BigInteger bigInteger |
+ | |||
+ | // Affichage du résultat | ||
+ | System.out.println("i = " | ||
</ | </ | ||
Ce qui donne : | Ce qui donne : | ||
Ligne 231: | Ligne 247: | ||
Cette approche a un inconvénient : après une comparaison infructueuse, | Cette approche a un inconvénient : après une comparaison infructueuse, | ||
- | ** Algorithme de Knuth-Morris-Pratt | + | ** Algorithme de Boyer-Moore ** |
- | L' | + | L' |
* On suppose qu'on peut tester si un caractère '' | * On suppose qu'on peut tester si un caractère '' | ||
* Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | * Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | ||
* On commence par chercher la position '' | * On commence par chercher la position '' | ||
- | * On inspecte la chaîne | + | * Soit '' |
- | * Soit '' | + | * Si '' |
- | * On note '' | + | * Sinon on note '' |
- | * Le décalage est égal à '' | + | * si '' |
- | * Si on ne trouve rien (ou si le décalage vaut 0), le décalage vaut '' | + | * Sinon le décalage est égal à '' |
<note tip> | <note tip> | ||
Ligne 253: | Ligne 269: | ||
CHINE | CHINE | ||
CHINE | CHINE | ||
- | CHINE | + | |
- | | + | |
- | CHINE | + | |
CHINE | CHINE | ||
RECHERCHE DE CHAINES CODEES EN MACHINE | RECHERCHE DE CHAINES CODEES EN MACHINE | ||
</ | </ | ||
- | < | ||
- | Algo : recherche améliorée (Knuth-Morris-Pratt) | ||
- | Données : d, t : chaînes de caractères | ||
- | Début: | ||
- | n = len (d) | ||
- | m = len (t) | ||
- | i <-- m - 1 | ||
- | tant que i < n : | ||
- | # PRE-TRAITEMENT | ||
- | j <-- 0 | ||
- | tant que j < m - 1: | ||
- | c = d[i - j] | ||
- | si c appartient à t[:m-j-1] | ||
- | k <-- dernière_occurrence(c, | ||
- | | ||
- | break | ||
- | sinon | ||
- | j += 1 | ||
- | si j == m - 1 ou si décalage == 0: | ||
- | | ||
- | # TRAITEMENT | ||
- | j <-- 0 | ||
- | tant que j < m : | ||
- | si t[m - j - 1] = d[i - j] | ||
- | j += 1 | ||
- | sinon | ||
- | break | ||
- | si j = m: | ||
- | retourner i - m + 1 | ||
- | # DECALAGE | ||
- | i <-- i + decalage | ||
- | retourner -1 | ||
- | Fin | ||
- | </ | ||
- | |||
=== 2.2 Compter les mots === | === 2.2 Compter les mots === | ||
Ligne 446: | Ligne 426: | ||
* Les classes d' | * Les classes d' | ||
* En python, les expressions régulières s' | * En python, les expressions régulières s' | ||
+ | * Les expressions régulières (regex) servent à décrire des motifs complexes à chercher (" | ||
+ | |||
Traduction de l' | Traduction de l' | ||
Ligne 456: | Ligne 438: | ||
* reconnaître une expression arithmétique | * reconnaître une expression arithmétique | ||
* vérifier la syntaxe d'un code informatique | * vérifier la syntaxe d'un code informatique | ||
- | |||
- | |||
=== Syntaxe des expressions régulières Python === | === Syntaxe des expressions régulières Python === | ||
Ligne 496: | Ligne 476: | ||
accepte tous les mots de 3 lettres | accepte tous les mots de 3 lettres | ||
- | **Branchements et Récursion** | + | **Branchements et itération** |
* Les parenthèses permettent : | * Les parenthèses permettent : | ||
* de factoriser une expression (qui peut alors être traitée comme une transition) | * de factoriser une expression (qui peut alors être traitée comme une transition) | ||
* '' | * '' | ||
- | * de définir des branchements : | + | * de définir des branchements |
* '' | * '' | ||
Ligne 507: | Ligne 487: | ||
* ''?'' | * ''?'' | ||
+ | <note tip> ** Récapitulatif ** | ||
+ | |||
+ | 1. **Caractères littéraux :** | ||
+ | * Les caractères alphabétiques et numériques sont traités littéralement. Par exemple, le motif ''" | ||
+ | |||
+ | 2. **Caractères spéciaux :** | ||
+ | * Certains caractères ont une signification spéciale dans une expression régulière et doivent être échappés s'ils doivent être traités littéralement. Ces caractères spéciaux incluent '' | ||
+ | |||
+ | 3. **Classes de caractères :** | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 4. **Caractères génériques :** | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 5. **Quantificateurs :** | ||
+ | * '' | ||
+ | * '' | ||
+ | * ''?'' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 6. **Ancrages :** | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 7. **Groupes et Alternatives :** | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 8. **Échappement :** | ||
+ | * '' | ||
+ | |||
+ | </ | ||
==exemples== | ==exemples== | ||
Ligne 536: | Ligne 558: | ||
* début de mot : '' | * début de mot : '' | ||
* complétions possibles : '' | * complétions possibles : '' | ||
+ | |||
+ | ** Autre exemple:** | ||
+ | {{https:// | ||
==== 4 Comparaison/ | ==== 4 Comparaison/ | ||
On cherche à exprimer une distance entre deux chaînes de caractères. | On cherche à exprimer une distance entre deux chaînes de caractères. | ||
Ligne 660: | Ligne 685: | ||
{{: | {{: | ||
+ | |||
+ | ===== 5. Modèles génératifs ===== | ||
+ | |||
+ | Soit un document $d$ : | ||
+ | * constitué de $T$ symboles $d[1]$, …, $d[i]$, …. | ||
+ | * appartenant à l' | ||
+ | |||
+ | |||
+ | Une description statistique d’un texte correspond à un histogramme qui porte sur un ensemble de symboles : | ||
+ | |||
+ | {{: | ||
+ | |||
+ | <note tip> | ||
+ | Modèles probabiliste : la suite de symbole observés (le message) est générée par un processus aléatoire: | ||
+ | $d = (d_1, d_2, ..., d_T$) | ||
+ | * chaque $d_i$ est la réalisation d'un tirage aléatoire | ||
+ | * obéissant à une distribution de probabilité $p$ | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | Les symboles sont au choix : | ||
+ | * des caractères appartenant à un alphabet | ||
+ | * des termes appartenant à un vocabulaire | ||
+ | </ | ||
+ | |||
+ | === 5.1 Modèles probabilistes === | ||
+ | |||
+ | Les modèles probabilistes interprètent les données de type texte comme étant générées par une distribution de probabilité $P$ inconnue. | ||
+ | |||
+ | La distribution $P$ définit le langage utilisé dans le texte. On ne s' | ||
+ | |||
+ | === Fréquence d'un symbole === | ||
+ | |||
+ | Soit $\alpha \in A$ un symbole de l' | ||
+ | |||
+ | On a par définition~: | ||
+ | $$\sum_{\alpha \in V} P(X=\alpha) = 1$$ | ||
+ | |||
+ | |||
+ | < | ||
+ | **Exemple**: | ||
+ | $$\boldsymbol{p}_\text{Français} = (0.0942, 0.0102, 0.0264, | ||
+ | où | ||
+ | * $p_1 = 0.0942$ est la fréquence de la lettre ' | ||
+ | * $p_2 = 0.0102$ est la fréquence d' | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | |||
+ | === Probabilité jointe === | ||
+ | |||
+ | On s' | ||
+ | |||
+ | Soient $\alpha$ et $\beta$ deux symboles de l' | ||
+ | |||
+ | < | ||
+ | * Les séquences de deux caractères sont classiquement appelées des // | ||
+ | * On définit de même les // | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | On notera $\boldsymbol{P}_\mathcal{L}$ la matrice des fréquences des bigrammes dans un langage $\mathcal{L}$ donné, où $P_{ij}$ donne la fréquence du bigramme $(\alpha_i, | ||
+ | |||
+ | < | ||
+ | **Exemple**: | ||
+ | $$\boldsymbol{P}_\text{Français} = 10^{-5} \times \left( | ||
+ | \begin{array}{cccc} | ||
+ | 1.5 & 116.8 & 199.1 & ...\\ | ||
+ | 62.8 & 1.6 & 0.14 & ...\\ | ||
+ | 184.8 & 0 & 52.4 & ...\\ | ||
+ | & | ||
+ | \end{array} | ||
+ | \right)$$ | ||
+ | |||
+ | |||
+ | où | ||
+ | * $P_{11} = 1.5 \times 10^{-5}$ est la fréquence du bigramme ' | ||
+ | * $P_{12} = 116.8 \times 10^{-5}$ est la fréquence d' | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | avec bien sûr : | ||
+ | $$\sum_{(i, | ||
+ | |||
+ | <note tip> | ||
+ | voir {{http:// | ||
+ | </ | ||
+ | |||
+ | La **probabilité conditionnelle** du caractère $\beta$ étant donné le caractère précédent $\alpha$ est définie comme : | ||
+ | |||
+ | $$P(Y = \beta | X=\alpha) = \frac{|\xi \in \Xi : (X, | ||
+ | |||
+ | <note tip> | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | Soit en français : | ||
+ | |||
+ | < | ||
+ | $$ | ||
+ | M_\text{Français} = \left( | ||
+ | \begin{array}{cccc} | ||
+ | 0.0016 & 0.0124 & 0.0211 & ...\\ | ||
+ | 0.0615 & 0.0016 & 0.0001 & ...\\ | ||
+ | 0.0700 & 0.0000 & 0.0198 & ...\\ | ||
+ | & ... &&& | ||
+ | \end{array} | ||
+ | \right) | ||
+ | $$ | ||
+ | où : | ||
+ | * $M_{11}$ est la probabilité de voir un ' | ||
+ | * $M_{12}$ est la probabilité de voir un ' | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | La matrice des probabilités conditionnelles $M$ permet de définir un **modèle génératif** de langage inspiré des **processus aléatoires de Markov**: | ||
+ | * La production d'un mot ou d'un texte est modélisée comme un parcours aléatoire sur une chaîne de Markov définie par la matrice de transitions $M$. | ||
+ | * La fréquence d' | ||
+ | |||
+ | < | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | On peutétendre ce principe à la distribution des mots dans les textes, ce qui permet de produire des //modèles génératifs de langage//. | ||
+ | |||
+ | * Exemple : le pseudo latin (" | ||
+ | * Exemple de pseudo-français (Utilisant une trace (mémoire) de 1 mot): | ||
+ | <note tip> | ||
+ | //j'ai vu parfois des yeux, remonter vers toi bien fatiguée! n'est pas un appel de la terre– je hume à coups mutins les voiles la blafarde lumière puisée au delà les vieux flacon débouché rien ne puis la pourriture les forêts ou bien que vénus par des choses dans les forts des senteurs confondues de ma chère, prêtre orgueilleux danse amoureusement l' | ||
+ | </ | ||
+ | |||
+ | === 5.2 Espaces de plongement (Word embedding) === | ||
+ | Le plongement des mots (word embedding) | ||
+ | * est une technique en traitement automatique du langage naturel (TALN) | ||
+ | * qui consiste à représenter les mots **sous forme de vecteurs de nombres réels dans un espace vectoriel**. | ||
+ | * L' | ||
+ | * de projeter les mots dans cet espace vectoriel | ||
+ | * où la proximité spatiale entre les vecteurs reflète la sémantique des mots. | ||
+ | |||
+ | <note tip> | ||
+ | Largement utilisés dans diverses tâches de traitement du langage naturel: | ||
+ | - classification de texte, | ||
+ | - la traduction automatique, | ||
+ | - l' | ||
+ | - la recherche d' | ||
+ | </ | ||
+ | |||
+ | |||