Génération de texte aléatoire

Découverte de la théorie de l'information de Shannon au travers d'une implémentation en python.

Présentation

Le language naturel désigne la langue telle qu'elle est parlée ou écrite, formée par évolutions successives. Le language formel par opposition, a l'ensemble de sa structure définie par une unique syntaxe.

Un language formel a toutes ses propriétés décrites par sa grammaire ou syntaxe, tandis qu'un language naturel permet de nombreuses adaptations de sa grammaire en fonction du contexte, et une grande partie de ce qui la structure n'est pas décrite formellement, et repose sur le contexte, équilibre des phrases, et le sens. Il est par exemple possible d'écrire une phrase grammaticalement correcte ne constituant aucune information.

L'étude de l'information textuelle ne peut donc pas se reposer uniquement sur une analyse formelle de la grammaire de la langue. La théorie de l'information propose un modèle d'analyse d'information qui n'est pas basée sur une grammaire ou syntaxe.

Celle-ci offre un moyen d'estimer la richesse d'information porté par un message, par rapport à un contexte. Celà se fait par la mesure de l'entropie: elle mesure à quel point les évènement qui se produisent sont prédictible. Ainsi, un évènement qui conforme à sa prédiction n'apporte que peu d'information, car il était prédictible.

Dans l'autre sens, si un évènement n'apporte aucune information, il est donc entièrement prédictible. Nous avons vérifié cet aspect par la génération d'un texte aléatoire d'après une source de texte. Un texte existant sert de modèle pour les prédictions et la génération.

Afin de permettre une prédiction, l'analyse du texte peut se faire au niveau au niveau séquences de lettres, de phonèmes, de syllabes, de mots, de groupes grammaticaux, de structures des phrases, dans l'agencement de plusieurs phrases... Notre étude se limite à la séquence des lettres.

Principe général de la théorie de l'information

La quantité d'information portée par un élément (un symbole) dépend de son contexte. Dans notre cas, les symboles sont les lettres et le contexte les lettres précédentes dans le texte.

Le logarithme est utilisé dans l'expression de la quantité d'information. Il peut s'approcher de manière inexacte, mais intuitive comme il suit: Le logarithme d'un nombre dans une base correspond au nombre de fois qu'il faut le diviser par la base pour arriver à l'unité.

On peut alors considérer ces nombres come étant des cardinaux d'ensembles: diviser un nombre par deux est diviser un cardinal par deux, et donc écarter la moitié des éléments de l'ensemble. Le logarithme de base 2 d'un nombre est alors le nombre de fois qu'il est nécessaire de séparer l'ensembre en 2 (soit diviser le cardinal par 2), pour arriver à l'unité: un cardinal de 1: un ensemble d'un élément. Il y aura alors eu une ou plusieurs étapes de division, ou séparation d'un ensemble en deux. Et écarter la moitié d'un ensemble revient à choisir une des deux parties, c'est à dire de faire un choix dichotomique entre deux moitiés.

On en vient alors à cette image: le logarithme de base 2 d'un nombre est le nombre de choix dichotomiques à réaliser pour isoler un élément d'un ensemble, c'est à dire pour réduire le cardinal à 1. Dans l'autre sens, chaque élément peut être discriminé parmi un ensemble par une suite de choix dichotomiques, et le nombre de choix est ainsi le logarithme du cardinal de l'ensemble. C'est le nombre de fois que le l'ensemble est divisé pour accéder à cet élément.

En ne considérant non plus un ensemble, mais un échantillon, dans lequel les éléments peuvent être répétés: Il est toujours possible de procéder à un certain nombre de séparation dichotomique pour discriminer un élément de l'échantillon, mais comme un échantillon comprote des répétitions, il est alors possible d'arriver à un choix dichotomique entre deux éléments identiques. Il n'est alors plus nécessaire de procéder à ce choix pour désigner l'élément. Le nombre de choix ne sera plus le logarithme du cardinal, mais le logarithme du cardinal moins 1, puisqu'il y a un choix/division en moins à effectuer.

Le nombre de choix/divisions à réaliser pour discriminer un élément dépends donc de l'effectif de l'élément dans l'échantillon. Il ne faut donc plus arriver à un un unique élément, mais à une collection d'éléments identiques.

Il faut ainsi retirer le nombre de divisions qui ne discriminent aucun élément: le nombre de divisions dichotomiques parmis un ensemble déléments identiques: le logarithme à base 2 du cardinal de l'ensemble d'éléments identiques:

            ╭          ╮        ╭               ╮
=      log  │ #(total) │ - log  │ #(identiques) │
          2 ╰          ╯      2 ╰               ╯

     ╭                                            ╮
     │      ╭               ╮        ╭          ╮ │
=  - │ log  │ #(identiques) │ - log  │ #(total) │ │
     │    2 ╰               ╯      2 ╰          ╯ │
     ╰                                            ╯

          ╭               ╮
          │ #(identiques) │
=  - log  │ ───────────── │
        2 │ #(total)      │
          ╰               ╯

On divise ici l'effectif d'un élément par le cardinal de l'échantillion, ce qui est l'expression de la fréquence d'un élément dans cet échantillon ; ou d'une probabilité si l'on s'intéresse à des évènements:

          ╭                      ╮
=  - log  │ probabilité(élément) │
        2 ╰                      ╯

On retrouve donc l'expression de la quantité d'information portée par un symbole. Celle-ci correspond ainsi au nombre de fois qu'il faut diviser un ensemble pour discriminer un élément, ou encore le nombre de choix à effectuer pour accéder à un élément, c'est à dire la quantité d'information à apporter pour décrire entièrement l'élément.

On s'intéresse alors à la somme de la quantité d'information contenue par un échantillon, puis entropie, en comparant l'entropie d'un échantillon avec répétition d'évènement et un sans.

Implémentation

La génération d'un texte aléatoire consiste en deux étapes :

Celà met en évidence qu'il est possible, d'extraire une forme d'information du texte. Dans le cadre de cette étude, le seule la séquence des lettres sera étudiée.

1. Répartition des lettres dans un texte

1.1 Analyse de leurs féquences

La répartition des lettres dans un texte permet de le caractériser. Si on observe la fréquence d'apparition de chaque lettre, l'analyse du texte est alors un ensemble de chaque lettre avec sa fréquence d'apparition, qu'on peut représenter par ce type de structure:

{
	lettre 1: fréquence associée 1;
	lettre 2: fréquence associée 2;
	lettre 3: fréquence associée 3;
	...
}

L'analyse consiste donc récolter l'effectif de chaque lettre, que l'on peut stocker dans une structure de dictionnaire:

# Les lettres du texte sont parcourues
# séquentiellement depuis le début

for letter in text:

	# Si la lettre est rencontrée pour la
	# première fois, elle est ajoutée au
	# dictionnaire
	if not letter in description:
		description[letter] = 1;

	# Sinon, l'effectif de cette lettre est
	# incrémentée.
	else:
		description[letter] += 1;

Le dictionnaire description contient les effectifs de chaque lettre, qu'il faut alors convertir en fréquences pour chaque entrée. Celà se fait en divisant les effectifs associés à chacune des lettres par l'effectif total (la taille du texte).

1.2. Génération de texte aléatoire

Une fois le dictionnaire de fréquences construit, il est envisagé de l'exploîter pour la génération de texte. Les lettres sont tirées au sort, les unes à la suite des autres, avec une probabilité d'être choisie qui suit les fréquences tu texte analysé.

La source de hasard est un nombre réel entre 0 et 1 qui ne permet pas d'être pondéré par des fréquences. Celà aura lieu dans l'autre sens: sur l'échelle des réels entre 0 et 1 est découpé en intervals, un par lettre rencontré dans le texte.

La largeur de chaque interval est pondérée par la fréquence d'occurence de chaque lettre. Ainsi, un nombre aléatoire choisit entre 0 et 1 aura une chance d'atteindre une lettre avec une probabilité correspondante à la largeur de son interval, c'est à dire la fréquence de cette lettre. Cette représentation s'obtient d'après les effectifs par le calcul de la fréquence normalisée et cumulée croissante

Celà s'obtient en triant le dictionnaire d'effectifs dans l'ordre choisit (ici, l'ordre Unicode 9) en divisant chaque effectif par l'effectif total( normalisée)...

norm = {}

for lettre in sorted(effectifs):
	norm[lettre] = effectifs[lettre] / total

... et en sommant chaque valeur avec les valeurs précédentes (cumulées croissantes)...

for lettre, fréq in norm:
	p = norm_cumul_croiss[lettre] = fréq + p

Les valeurs obtenues sont alors entre 0 et 1 (sauf approximation sur les types float [2]) et il est alors possible de choisir une lettre aléatoire avec une probabilité correspondant aux fréquences observées, d'arpès un nombre aléatoire:

seuil = random.random()
choisie = ""

for lettre, fréquence in norm_cumul_croiss:
	if fréquence > seuil
		choisie = lettre
		break

Il est alors possible de réitérer l'expérience pour produire un texte entier.

2. Utilisation de préfixes comme contexte

La analyse de la fréquence de chaque lettre dans le texte ne prend pas en compte la séquence des lettres, à la différence de l'analyse par préfixes.

2.1. Fréquences en fonction des préfixes

Une analyse similaire à la précédente est réalisée, mais pour chaque lettre, l'information des lettres précédant le texte est conservée: est construit un dictionnaire de tout les préfixes de taille donnée du texte. Pour chaque préfixe est répertorié l'ensemble des lettres qui suivent à différentes apparitions du préfixe dans le texte.

De plus, pour chacune de ces lettres suivant un préfixe, la fréquence est également observée.

La structure construite est un dictionnaire préfixe-sous-dictionnaire, avec chaque sous-dictionnaire associant des fréquences à une lettre.

Comme précédament, la constitution d'un tel dictionnaire passe par une lecture du texte lettre par lettre: pour chaque position, les lettres précédant cette position sont lues, et constituent le préfixe. Le dictionnaire est ouvert à la position de ce préfixe, et la fréquence de la lettre à la position choisie est ajoutée dans le sous-dictionnaire de ce préfixe. Si cette lettre est déjà présente dans le sous-dictionnaire, sa fréquence est augmentée.

Pour le texte "Cocorico !", et des préfixes de 2 lettres:

"Cocorico !"                                 (1)
 ‾‾^
{
      > "Co": { c: 1 }
}
"Cocorico !"                                 (2)
  ‾‾^
{
        "Co": { 'c': 1 }
      > "oc": { 'o': 1 }
}
"Cocorico !"                                 (3)
   ‾‾^
{
        "Co": { 'c': 1 }
        "oc": { 'o': 1 }
      > "co": { 'r': 1 }
}
"Cocorico !"                                 (4)
    ‾‾^
{
        "Co": { 'c': 1 }
        "oc": { 'o': 1 }
        "co": { 'r': 1 }
      > "or": { 'i': 1 }
}
"Cocorico !"                                 (5)
     ‾‾^
{
        "Co": { 'c': 1 }
        "oc": { 'o': 1 }
        "co": { 'r': 1 }
        "or": { 'i': 1 }
      > "ri": { 'c': 1 }
}
"Cocorico !"                                 (6)
      ‾‾^
{
        "Co": { 'c': 1 }
        "oc": { 'o': 1 }
        "co": { 'r': 1 }
        "or": { 'i': 1 }
        "ri": { 'c': 1 }
      > "ic": { 'o': 1 }
}
"Cocorico !"                                 (7)
       ‾‾^
{
        "Co": { 'c': 1 }
        "oc": { 'o': 1 }
      > "co": { 'r': 1; ' ': 1}
        "or": { 'i': 1 }
        "ri": { 'c': 1 }
        "ic": { 'o': 1 }
}
"Cocorico !"                                 (8)
        ‾‾^
{
        "Co": { 'c': 1 }
        "oc": { 'o': 1 }
        "co": { 'r': 1; ' ':1 }
        "or": { 'i': 1 }
        "ri": { 'c': 1 }
        "ic": { 'o': 1 }
      > "o ": { '!': 1 }
}

On retrouve la structure en dictionnaire lettre-effectif de l'approche précédente: les mêmes raisonnements s'appliquent et les fonctions pourront être réutilisées. Ainsi sont convertis les dictionnaires d'effectifs en dictionnaires de fréquences cumulées croissantes, pour chaque préfixe.

2.2 Génération d'un texte aléatoire

On dispose alors d'un arbre à deux niveaux, le premier pour les préfixes, le secont pour les lettres suivant ce préfixe. En ayant généré un début de texte, les dernières lettres de ce texte pourront correspondre à un préfixe dans le dictionnaire. Il sera alors possible de choisir la lettre suivante dans le sous-dictionnaire correspondant, et d'ainsi compléter le texte, avec une lettre en plus. En répétant l'opération sur le nouveau texte produit, il est alors possible d'ajouter des lettres supplémentaires:

"Co_"   "Coc_"   "Coco_"   "Coco _"   "Coco !_"
 ‾‾^      ‾‾^       ‾‾^        ‾‾^         ‾‾^
   1        2         3          4           5

On obtient ainsi un texte différent de l'original, comportant uniquement les séquences de 2 lettres présentes dans le texte précédent, généré aléatoirement d'après les fréquences du texte analysé.

Reste encore le besoin d'une amorce: un premier préfixe à choisir, à partir duquel continuer la génération du texte. La seule restriction est qu'il doit constituer un préfixe présent dans le dicionnaire: Un préfixe est choisit au hasard parmi celui-ci. Le choix aurait également pu tenir compte de la fréquence d'apparition des préfixes, et se limiter aux préfixes commençant par une majuscule.

L'algorithme est complet.

Étude du texte généré

Les textes sont choisit depuis le projet Guttemberg [1] de manière à disposer des corpus longs et dans de nombreuses langues.

Pour tout les textes qui ne sont pas anglais, l'encodage en UTF-8 qui supporte tout les caractères est adapté: Les codes de caractères trop longs pour être contenus par un octet sont répartis sur plusieurs octets. Celà est géré nativement par le language python, ce qui garanti qu'il n'y ait pas de caractère sectionné.

Les ouvrages choisits au hasard sont:

1. Longueur des préfixes

Dans l'exemple ci-dessus, le préfixe est de taille 2. La fidélité au texte originale est influencée par la longueur du préfixe.

1.1. Limite inférieure: faible cohérence

Si le préfixe est de taille très faible le texte

En ignorant le préfixe entièrement, seule la fréquence des lettres dans le texte est prise en compte, ce qui revient à un tirage aléatoire des lettres, sans information de contexte, et le résultat n'est pas interprétable:

Anglais sans préfixe

Apparition de cohérences, tel que un point précédé d'une lettre et suivi d'un espace, mais également d'incohérences, et pas de structure apparente.

ddm. t helufrtevlpeystri ymdnaunld,o te 'ths ei t ,e cseee ogd -y roc mrtos h h,ynwdr fi,gusnsf p ve ohocsh riH, oelnsiesdproqgpc,o,pdwyeee t,
Français sans préfixe

Des différences notables de par la présence des accents, mais pas de structure proche de la langue française non-plus.

hrérbtgt ru bpui e cé èoisrdan s lrisiuuétsattdsnrnuarbsl eifs m rs tapfin 1 g.sr tmoet' npst.eetes svl énh a saa8 scn
Japonais sans préfixe

Pas de sens d'après une pratiquante de la langue, et caractères ASCII apparents au milieu Kanjis et Hiragana.

のぎれ rなき。うつに 學。v。と戀しがもつ人か るのl分見nつeゐud分り鶴はのるる力い目は もV
Anglais préfixe de longueur 1

Des mots courts sont reconaissables, et pas d'erreur de ponctuation. Les phonèmes sont tous communs en anglais

ine, th to Ellin asint of to exed andurs ce he the videthal; beepted, of Lyeturs, wored her new sheyesse lis a fackne paid, anot assawrear thered I not bovienat dit
Français préfixe de longueur 1

Des groupes de quelques mots courts (2 à 3 lettres) apparaissent en cohérence entre eux, mais la aucun dépassant 4 lettres.

C'es coproin, tout s'ilive vent décommangticathé, auqui fee resse Sactre, semmes des prits de treur pourdu mons quisous tud lent, je brule soci, à l'a vil, pouslis d'on gés calici pe of tort de arancerce sala que de le lute
Japonais préfixe de longueur 1

Le sens est présent dans les deux premières lignes, mais à partir de "のこと" en fin de troisième ligne, la phrase perds toute cohérence. On constate également que les guillemets ne sont pas appariés: "』『".

然を試みることも思へるべき日だと思ふ時も母 程夢中で庭を夢で死ぬだらう』 『もしやしなかつたのみ立つたと未練をのこと を耻とすれば自分のことを夫婦になつてゐる が
Anglais préfixe de longueur 2

La plupart des mots courts sont correctes, et mieux agencés. Les mots plus longs paraissent une combinaison de deux autres mots, tel que "produlogize" par "produce" et "apologize".

Projectroport!--It was in of up mysted shed that shew to his sily be confling thateve most hardent me,' he somethis the produlogize, if and what I she door by
Français préfixe de longueur 2

De même que pour l'anglais, des mots nouveaux apparaissent, et des mots courts sont existants.

maître que Lyonsi de langest marqui à septe avec unlevant lui nous appriment fait lus n'ennes avait parécis. Delages qu'ille, cepteureveugles oisellesque le du pièce un les pense

1.2. Lien entre longueur des préfixes et cohérence

On remarque que plus la longueur des préfixe est importante, plus l'apparition d'incohérence dans le sens a lieu tard dans un passage, et pour des ensembles plus importants.

On remarque que pour une longueur de préfixe de taille donnée, chaque séquence de même taille dans texte produit est issu du texte d'origine, et ne peut pas comporter d'incohérence en interne. C'est dans l'agencement de ces séquences que les incohérences, ainsi que création de passages nouveaux apparaissent.

Lorsque la taille du préfixe est plus petite qu'un mot, des mots cohérents ainsi qu'incohérents apparaissent, et les phrases sont dans l'ensemble incohérentes. Lorsque la taille du préfixe est plus grande qu'un mot, les incohérences et création de nouveaux passages se font au sein d'une phrase.

La création de nouveau texte a ainsi lieu à une échelle au delà de celle comprise par la taille d'un préfixe. Les éléments qui structurent le texte -- phonèmes, mots, phrases, paragraphes -- sont conservées lorsque la taille des préfixe est plus grande.

1.3. Limite supérieure: répétition du texte à l'identique

Pour obtenir un texte très cohérent, il faudrait ainsi des préfixes très longs. Cependant, lorsque la longueur est trop importante, le texte étudié finit par ne plus avoir plusieurs possibilité de lettres suivant un préfixe, mais une seule. Le texte produit est alors une copie d'un passage entiers du texte d'origine.

Pour éviter cette limite, et pour grandement enrichir la diversité du texte produit, il est possible de choisir un texte à analyser qui soit bien plus long qu'un livre, tel que l'ensemble des articles de Wikipédia. Il sera alors possible de générer un texte bien différent de chacun des passages, tout en préservant une grande cohérence grâce à un long préfixe.

2. Nature de la source

2.2. Différences entre les langues

Parmi les langues testées, celles basées sur un alphabet forment des phrases et mots déstructurées lorsque le préfixe est court, et la structure se reforme progressivement lorsque le préfixe s'allonge.

Pour la langue japonaise basée sur un systèmes d'écriture par idéogrammes, les mots sont encodés par un seul caractère la plupart du temps, et ne peuvent pas être scindés. La présence d'un préfixe augmente ainsi immédiatement la structure du texte, qui devient vite cohérent.

2.1. Autres sources que du texte

L'utilisation pour d'autres types de données que le texte est possible, mais reste limité, et nécessite une prise en charge plus spécifique.

Code source du programme

La source du programme même est testée en tant que texte à analyser. L'utilisation des caractères de tabulation ("\t", caractère 9) constitue une barrière: si le préfixe est plus court que 3, à chaque ligne comportant 3 tabulations, le préfixe de 3 tabulations fait perdre tout contexte. De plus, la syntaxe du programme s'établit également à une échelle plus grande que la phrase, et malgré quelques constructions valides, le code source ne peut pas être exécuté.

Fichier image

Grâce au format FarbFeld [4], il est possible d'exécuter le programme sur un fichier image, ligne par ligne comme s'il était du texte. Les images sont en deux dimensions, mais l'analyse n'a lieu qu'en une seule dimension.

Le résultat est différent à du bruit aléatoire, mais également très loin de l'image d'origine. Le résultat semble biaisé, et l'implémentation en python n'est pas recommandée pour une utilisation autre que le texte.

Le détail de la conversion de l'image, la source, et les résultats sont disponibles dans le dossier source du projet.

3. Longueur du texte généré

Le programme comporte un paramètre permettant de choisir la taille du texte à générer. Le texte généré peut être plus long que le texte original, et il est possible que le texte généré ne soit pas aussi long que prévu.

3.1. Apparition de boucles dans le texte

Lorsque le texte original comporte des répétitions, il est possible que le texte étudié en comporte aussi, et lorsque la séquence d'un passage répété apparaît dans le texte généré, il y aura alors plusieurs lettres disponibles pour ce même préfixe. Le texte pourra alors suivre plusieurs fois la même séquence, et former des boucles:

orico_
   ‾‾^

Depuis le premier préfixe jusqu'à ce point, une seule séquence était possible, mais pour le préfixe co, plusieurs solutions s'ouvrent:

oricoc > oricoco_    De nouveau le préfixe, avec
              ‾‾^    une boucle de "co" à "co"
oricoc > oricorico_
                ‾‾^
orico  > orico !    Aucune boucle: fin du texte.

En alternant plusieurs boucles, il est ainsi possible de former un texte plus long que l'original, en comportant de nombreuses répétitions. La génération d'un texte se réalise donc uniquement en certains points, où il y a plusieurs possibilités par préfixe, le reste n'étant que suivre la séquence du texte original.

3.2. Cas de l'occurence de la fin du texte

Pour le dernier préfixe du texte, il n'y a aucune lettre qui suit. Si le texte généré parvient à ce préfixe, si la situation n'est pas gérée, le programme reporte une erreur.

Dans cette situation, il est possible de choisir d'interrompre la génération, ou de reprendre un autre préfixe parmi le texte.

Il est également possible d'éviter cette situation, en expoîtant les boucles: exclure toutes les séquences ne conduisant qu'à la fin du texte si celà conduit à une fin prématurée. La séquence du texte continuera alors d'emprunter des boucles jusqu'à ce que la longueur espérée puisse être atteinte.

Cependant, celà peut altérer la probabilité d'atteindre des lettres et séquences du texte, puisqu'une partie est exclue.

Conclusion

La théorie de l'information donne une nouvelle approche permettant de quantifier une information. Une information qui paraît trop peu formelle tel que le language naturel peut malgré tout être étudiée de manière formelle. Celà permet des applications tel que la génération de texte aléatoire.

L'expérimentation sur des textes en prose indiquent que le système d'écriture a une grande influence sur le maintient de la structure dans le texte généré. Dans un même système d'écriture, la langue a en revanche moins d'importance.

La longueur du préfixe choisit détermine le niveau de structuration du texte produit. La création de nouveau texte, ainsi que l'apparition d'abérrations linguistiques a en effet lieu pour des structures plus grandes que le préfixe.

Il est délicat de parler de création de sens nouveau, car bien qu'il y ait création de texte nouveau, aucune analyse de sens n'a eu lieu, et le texte produit est le fruit du hasard (random.random() en python).

Des lois empiriques régissant le texte d'alphabet latin, tel que l'alternance voyelle-consonne, la loi de Zipf [5] pour les fréquences d'utilisation des lettres, ainsi que des mots entiers sont retrouvés dans le texte produit, même pour un préfixe de faible taille.

Enfin, l'analyse peut être élargie à des sujets qui ne sont pas de la prose, tel que du code source ou des images, mais le mécanisme se devra être adapté à chaque média.


  1. Project Guttemberg - guttemberg.org - GNU Free Documentation License 1.2
  2. 0.30000000000000004.com - Erik Wiffin
  3. Leucauge decorata - Kaeng Krachan National Park, Thailand Photo by Rushenb - License CC BY-SA
  4. FarbFeld - Suckless - License ISC
  5. Applications and explanations of Zipf's law - David M W