Dans ce billet, nous allons implémenter l'algorithme du "radoteur", un algorithme attribué à Roland Moreno. Cet algorithme a pour but de générer, à partir d'un texte descriptif d'un produit, un nom susceptible d'être utilisé comme marque pour ce produit. L'intérêt conceptuel de l'algorithme est de produire une suite de caractères qui peut être vue comme la somme des mots qui le décrivent.
Ce billet se base sur l'explication de l'algorithme trouvée ici.
Pour fonctionner, l'algorithme a besoin de données d'entrée, c'est-à-dire une série de mots à partir de laquelle on veut en générer de nouveaux. Dans notre post nous utiliserons la chaîne de caractères suivante (tirée du document cité en introduction) :
SOIENT CINQUANTE MOTS D’ANGLAIS PRIS AU HASARD, SHANNON POSTULE L’EXISTENCE D’UNE LOI DE COMPOSITION DE CE SOUS-ENSEMBLE DE LA LANGUE, NON NEUTRE, ENTIÈREMENT DÉTERMINÉ, ET VA S’ATTACHER À DEMONTRER LA RIGUEUR DE CETTE LOI.
Ensuite, l'algorithme procède de la manière suivante :
On définit tout d'abord la chaîne de caractères avec laquelle on travaille :
input_string = "SOIENT CINQUANTE MOTS D’ANGLAIS PRIS AU HASARD, SHANNON POSTULE L’EXISTENCE D’UNE LOI DE COMPOSITION DE CE SOUS-ENSEMBLE DE LA LANGUE, NON NEUTRE, ENTIÈREMENT DÉTERMINÉ, ET VA S’ATTACHER À DEMONTRER LA RIGUEUR DE CETTE LOI."
Ensuite, on choisit l'un des mots présents pour démarrer notre algorithme.
words = input_string.split(' ')
from random import randint
words[randint(0, len(words) - 1)]
'CETTE'
On peut résumer ces étapes sous la forme d'une fonction :
def init_chain(input_string):
"""Retourne le caractère de départ et la position dans la chaîne,
choisis au hasard."""
words = input_string.split(' ')
r = randint(0, len(words) - 1)
start_char = words[r][0]
position = 0 + r + sum([len(w) for w in words[:r]])
return start_char, position
On vérifie le fonctionnement de la fonction :
init_chain(input_string)
('S', 48)
input_string[48]
'S'
Comme on le voit, la lettre et la position se correspondent.
init_chain(input_string)
('C', 7)
input_string[7]
'C'
On peut maintenant implémenter la recherche du prochain caractère. Il suffit pour cela de démarrer la recherche de la prochaine occurence de la lettre courante à partir de la position actuelle.
start_char = 'C'
position = 7
while input_string[position + 1] != start_char:
position = (position + 1) % len(input_string)
position
72
input_string[73]
'C'
Maintenant que les bases sont posées, nous pouvons résumer ceci sous forme d'une fonction :
def build_chain(input_string, start_char, position):
"""Construit une chaîne selon l'algorithme du radoteur."""
chain = start_char
while chain[-1] not in (' ', ',', '.') and len(chain) < 30:
while input_string[(position + 1) % len(input_string)] != chain[-1]:
position = (position + 1) % len(input_string)
chain += input_string[(position + 2) % len(input_string)]
position = (position + 2) % len(input_string)
return chain
Testons :
build_chain(input_string, 'S', 48)
'STE '
input_string[48:]
'SHANNON POSTULE L’EXISTENCE D’UNE LOI DE COMPOSITION DE CE SOUS-ENSEMBLE DE LA LANGUE, NON NEUTRE, ENTIÈREMENT DÉTERMINÉ, ET VA S’ATTACHER À DEMONTRER LA RIGUEUR DE CETTE LOI.'
On s'attend effectivement à la sortie 'STE' pour ces caractères de départ. L'algorithme est donc bien implémenté. A noter que l'on a ici utilisé deux subtilités dans le code :
On peut maintenant générer pleins de mots de cette manière :
set([build_chain(input_string, *init_chain(input_string)) for i in range(5000)])
{'ASHEMONCOSONE,', 'CE ', 'CENGURISIOUEUE ', 'CHARENTETTR ', 'CIS ', 'D,', 'DE ', 'DE,', 'DERI.', 'DETENQU ', 'DÉ,', 'D’ENE ', 'EMIGLEXI ', 'EREUANN ', 'HA ', 'LA ', 'LANGUTINTT ', 'LAUL’USE ', 'LE ', 'LOINTS ', 'LOMBLANONTE ', 'MPRD’ACE ', 'N ', 'NT ', 'POITRENÉT ', 'PONS’AISANOSTIÈRMOIE ', 'R ', 'S ', 'S-EMER ', 'SOTUN ', 'STE ', 'VATA ', 'À '}
On peut appliquer cette technique à d'autres ensemble. Par exemple pour trouver des noms de marques (comme on peut le lire sur la notice wikipédia de son inventeur). Imaginons que l'on cherche à créer un produit avec la description suivante :
Parfum capiteux, doux, subtil, idéal pour les soirées en ville.
On peut lui appliquer notre algorithme :
input_string = 'Parfum capiteux, doux, subtil, idéal pour les soirées en ville.'.upper()
set([build_chain(input_string, *init_chain(input_string)) for i in range(5000)])
{'CALESURÉAR ', 'DÉEN ', 'E.', 'IRFUX,', 'LL,', 'PAPOILEUX,', 'PIL ', 'S ', 'VITIDOUM '}
Parmi ces propositions, on pourrait garder le Vitidoum, le Papoileux ou encore l'Irfux.
Nous avons implémenté l'algorithme du radoteur. Les résultats sont intéressants, mais pas forcéments tous valides. Je pense que ceci explique pourquoi cet algorithme ne peut fournir que des candidats qu'il faut ensuite trier manuellement pour retenir ceux qui sont pertinents.