Feuilles de root

Logiciels libres, programmation et économie

Accueil » Programmation » Programmation Scheme » Génération aléatoire de noms

Génération aléatoire de noms

De Olite aux chaînes de Markov

Cet article s'intéresse aux techniques de génération aléatoire de noms et à une d'entre elles en particulier : les chaînes de Markov.

Il est basé sur l'article Génération aléatoire de noms, De Elite aux chaînes de Markov. Cette version propose des exemples en Scheme (Kawa).

Fonctions utilitaires

string-replace remplace un caractère par un autre dans une chaîne :

(define (string-replace search replace subject)
    (let
        ((ll (string->list subject)))
        (list->string
            (map (lambda (x) (if (equal? x search) replace x)) ll)
            )
        )
    )

random génère un nombre aléatoire compris entre 0 et 1 :

(define (random)
    (java.lang.Math:random))

Oolite

Oolite est une réécriture sous licence libre du de commerce et de combat spatial Elite sorti en 1984. Il utilise le principe des nombres pseudo aléatoires pour générer les noms des étoiles et des planètes. Voici une implémentation en Scheme :

(define (rand-name-elite)
    (let* (
            (pairs (string-append
                    "..lexegezacebiso"
                    "usesarmaindirea."
                    "eratenberalaveti"
                    "edorquanteisrion"
                    ))
            (pair1 (* (floor (* (random) (/ (string-length pairs) 2)))))
            (pair2 (* (floor (* (random) (/ (string-length pairs) 2)))))
            (pair3 (* (floor (* (random) (/ (string-length pairs) 2)))))
            (pair4 (* (floor (* (random) (/ (string-length pairs) 2)))))
            )
            (string-replace #\. #\null (string-append (substring pairs pair1 (+ pair1 2)) (substring pairs pair2 (+ pair2 2)) (substring pairs pair3 (+ pair3 2)) (substring pairs pair4 (+ pair4 2))))
        )
    )

Voici quelques exemples de noms générés : seesreea earelere ezcesoce arusndma reezoua

Chaînes de Markov

Principes

Un processus de Markov est un processus stochastique dans lequel l'état suivant du processus ne dépend que de l'état présent.

Implémentation

Nous allons utiliser les tables de hachage comme tableau associatif. Une autre solution aurait été d'utiliser les listes associatives (assoc).

(import (rnrs hashtables))

On cherche à calculer et à stocker les probabilités de transition d'une lettre à une autre.

La fonction suivante permet de compter les occurrences de toutes les paires de lettres présentes dans une liste donnée en paramètre.

(define (compute-transitions database)
    (let ((transitions (make-eqv-hashtable)))
        (for-each
            (lambda (word)
                (let
                     ((previous "^")(next ""))
                     (for-each
                         (lambda (letter)
                             (set! next letter)
                             (let ((key (string-append previous next)))
                                     (hashtable-set! transitions key (+ (hashtable-ref transitions key 0) 1))
                                 )
                             (set! previous next)
                             )
                         (map string (string->list word))
                         )
                     (hashtable-set! transitions (string-append previous "$") 1)
                    )
                )
            database
            )
        transitions
        )
    )

(define (make-state-frequency next-state cum-frequency)
    (cons next-state cum-frequency))

(define (next-state o)
    (car o))

(define (cum-frequency o)
    (cdr o))

(define (markov state transitions)
    (define cum-dist '())
    (define sum 0)
    (for-each
        (lambda (key)
            (when
                (equal? state (substring key 0 (string-length state)))
                (set! sum (+ sum (hashtable-ref transitions key 0)))
                (set! cum-dist (append cum-dist (list (make-state-frequency (substring key (string-length state) (+ 1 (string-length state))) sum))))
                )
            )
        (vector->list (hashtable-keys transitions))
        )

    (define random-value (floor (* (random) sum)))

    (let loop ((i 0))
        (if (and (< i (length cum-dist)) (< random-value (cum-frequency (list-ref cum-dist i))))
            (next-state (list-ref cum-dist i))
            (string-append "" (loop (+ i 1)))
            )
        )
    )

Une chaîne de Markov étant donnée, l'algorithme pour générer aléatoirement une suite de lettres est assez intuitif et pourrait ressembler à ceci :

(define (random-name-markov transitions)
    (let
        ((state "^")(result ""))
        (while (not (equal? state "$"))
            (let ((newletter (markov state transitions)))
                (set! result (string-append result newletter))
                (set! state newletter)
                )
            )
        (substring result 0 (- (string-length result) 1))
        )
    )