3/09/2013

Generateur de chaines


                                                       

1 Introduction


                  On a parfois besoin de générer aléatoirement des chaines de caractères, soit pour jouer à DES MOTS ET DES LETTRES, soit pour attribuer des mots de passe, ou encore un tas d’autres raisons. Mais la plupart du temps on préfère que les mots générés soient le plus uniques possible. Donc dans cet article nous allons etudier certaines methodes pour parvenir à ces fins. 


 

2 Definitions de bases


- Caractère :
           " Un caractère d’un point de vue informatique est ” à la fois un type de donnée et une notion abstraite. Comme en typographie, un caractère informatique peut représenter une lettre minuscule, une lettre majuscule, un chiffre ou un signe de ponctuation, mais aussi une espace typographique, une tabulation, un retour à la ligne et quelques autres opérations spéciales ” (source wikipedia )
- Chaine de caractères
                       " En informatique, ”une chaîne de caractères est à la fois conceptuellement une suite ordonnée de caractères et physiquement une suite ordonnée d’unité de code (code unit). La chaîne de caractères est un type de donnée dans de nombreux langages informatiques ”. (source wikipedia)
       Bien entendu selon le besoin spécifié, vous prendrez le soin de bien choisir les caractères en  question. 

3 Prerequis



Générer une chaine de carcatère suppose 

  - Disposer d’un ensemble bien défini(en fonction des besoins) de caractères.
  - Choisir aléatoirement au sein de l’ensemble, et dans un ordre bien precis, un certain nombre de caractères. 

Pour l’ensemble des choix on dispose de:

  •   L’alphabet ( miniscule et majuscule)
  •   Les chiffres ( de 0 à 9)
  •   Les caractères spéciaux (—, !,”,£,%,&......etc)
Pour l’alea on devra mettre au point un système de generation aleatoire ou pseudo-aleatoire
qui dans une certaine mesure sera capable de choisir un caractère dams l’ensemble prédéfini. 

4 Choix aléatoire



Une façon simple de mettre au point choix aleatoire est la suivante. 

- Disposer d’un ensemle de choix.
- Disposer d’un generateur aleatoire ou pseudo aleatoire de nombre
- Choisir un certain intervalle en generale 100, 1000, 10000, ou n pour faire simple. 
- Diviser l’intervalle par n, n etant la cardinalité de votre ensemble,
   c’est-à-dire le nombre d’éléments  dans l’ensemble.
- Génerer un nombre aléatoire auquel on fera correspondre un caratère,
   en fonction de l’intervalle auquel  il appartient. 

5 Algorithme


          T[N] = {’a1’,’a2’,’a3’,..........,’an’} un tableau de n caractères.

         aleatoire(): Fonction qui genere un entier compris entre 1 et n.

            W[M]  : un tableau qui contiendra le mot généré.

           Pour i allant de 1 à m

                  k = aleatoire()

                  W[i] = T[k]


           Fin
     

6 Implementation en java


     Avant tout, mettre au point notre fonction aleatoire().
Nous n’allons pas réecrire un generateur aleatoire de nombres , mais utiliser un qui existe déjà.

     En effet Java dispose d’une fonction random() dans la classe java.lang.Math. Le seul ennui c’est qu’il génère uniquement des nombres entre 0 et 1 , 0 et 1 exclus.

      Donc tout ce que nous avons à faire c’est de multiplier ce nombre par une grandeur donnée pour qu’il soit entre 1 et n.
Et si x est compris entre 0 et 1,  alors 26x est compris entre 0 et 26.

    Ensuite puisque c’est un nombre entier qu’on cherche on peut faire un arrondi à l’entier superieur le plus proche ou à l’entier inferieur le plus proche.

Et pour cela Java dispose des methodes :
- ceil() qui renvoit l’entier inferieur le plus proche.
- floor()     qui renvoit l’entier inferieur le plus proche.
Dans notre cas ce qu’il nous faut c ’est ceil() , pour exlure le 0 et inclure 26. Et l'algorithme est le suivant: 

           public int aleatoire(){  
                int k = (int)ceil(Math.random()*n) 
                return k; 
           }
       

Maintenant que nous avons notre algorithme aleatoire(), passons au code proprement dit :
Notre ensemble de choix sera l’aphabet, donc un ensemble de 26 elements.

   package ric;

   /**
   *
   * @author geeklord
   */
   public class Genere {
       /**
       * Tableau des lettres
       */
       char tab[] = {’a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’l’,’m’,’n’,’o’,’p’,
       ’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’};


       /**
       * Genere un tableau de char de n lettres
       */

       public char[] genereString(int n){
    char word[]= new char[n];
    int k;
    for(int i=0; i<n; i++){
      k = aleatoire();
      word[i] = tab[k];
    }
    return word;
       }

       /**
       * Choisit une lettre dans le tableau des lettres en fonction de
       * leurs chances respectives
       */

       private char aleatoire(){
    int t = ceil(Math.random()*tab.length);
    return t;
       }

   }

       

                Cette classe par exemple permet de generer un mot aleatoire, avec l’alphabet simple.
 Mais pour générer des mots de passe par exemple, on pourra ajouter à l’ensemble des choix les lettres majuscules et meme des chiffres. 

7 Pour aller plus loin


            Pour satisfaire certaines conditions, on aura parfois peut-etre besoin que certains caractères apparaissent au moins une fois ou apparaissent plus de fois que d’autres. Dans ce cas l’algorithme devra etre modifié de façon a augmenter les chances d’apparition des caracactères en question. 

7.1 Details


               Le choix des caractères est basé sur un generateur de nombre uniforme, c’est-à-dire qui donne les memes chances d’apparition à tout le monde. En nous basant sur cette uniformité, tout ce qui reste à faire est d’augmenter l’ntervalle associé au caractère en question. S’il y a n caractères, et qu’on divise l’intervalle totale par n, tout le monde a la meme chance d’apparraitre.
               Mais si on divise l’intervalle total par 2n, et qu’on attribue n de ces petits intervalles à un seul caractère , il a donc 50 pour cent de chances d’apparaitre. Autrement dit, sur un mot de mille lettres, il apparait environ 500 fois.

7.2 Algorithme de choix pondéré


                 Ce genre de choix est appelé choix pondéré, autrement dit chaque caractère possède un coefficient qui determine ses chances d’apparition, plus le coefficient est elevé mieux c’est. Il existe plusieurs algorithmes pour le faire et nous pouvons nous meme en implementer un, mais le plus efficace est celui de Walker
          Mais le principe général d’un algorithme de choix pondere est celui ci.
  •   Disposer d’un tableau de caractères
  •  Affecter un coefficient positif à chaque nombre, ce coefficient represente  la chance ou   probabilité d’apparition du nombre.
  •  Disposer d’un tableau contenant les chances cumulées des caractères.
  •  Generer un nombre aleatoire uniforme et le multiplier par la somme des coefficients
  •  Choisir le caractère dont l’intervalle associé, contient ce nombre.

7.3 Exemple d’implementation d’un choix pondéré



  /*
   * To change this template, choose Tools | Templates
   * and open the template in the editor.
   */
   package ric;

   /**
   *
   * @author geekLord
   */
   public class PonderateGenere {

       /**
       * Tableau des lettres
       */
       char tab[] = {’a’,’b’,’c’,’R’,’S’,’T’,’U’,’V’,’W’,
                         ’X’,’2’,’3’,’4’,’5’,’6’};

      /**
       * Tableau des coefficients associés a chaque lettres.
       *  Les coefficients sont arbitraires.
       * Plus le coefficient est élevé, plus les chances sont
       * grandes
       */

     
double chances[] = {2.0,12.0,17.0,22.0,11.0,5.0,7.0,9.0,
        22.0,30.0,1.0,13.0,8.0,25.0,30.0} ;

       public PonderateGenere(){

       }



       public String genere(int n){
           if(chances.length == tab.length){
                initChances();
           }
           return String.valueOf( genereString(n));
       }
       /**
       * Genere un tableau de char de n lettres
       */

       private char[] genereString(int n){
          char word[]= new char[n];
          for(int i=0; i<n; i++){
             word[i] = randomChar();
          }
          return word;
       }
       /**
       * Choisit une lettre dans le tableau des lettres en fonction de
       * leurs chances respectives
       */
       private char randomChar(){
           double t = (Math.random());
           for(int i=0; i<tab.length;i++){
             if(t< chances[i]){
               return tab[i];
             }else {
               continue;
             }
           }
           return ’-’;
       }


       /**
        * Methode qui normalise les chances respectives de chaque
        * caratère de sorte qie la somme soit egale à 1.
        * En fait on divise chaque coefficient par la somme des
        * coefficient.
       */

     private void initChances(){
          double som = chances[0] + 0.0;
          for(int i=1; i< tab.length; i++){
            som = som + chances[i];
            chances[i] += chances[i-1];
          }

          for (int i = 0; i < tab.length; i++) {
            chances[i] = chances[i] / som;
          }

       }


   }
     

8 Ressources


2 commentaires:

Ajouter un commentaire

HTML5::: La géolocalisation

1- Introduction            Le but de cet article est d'apprendre à implémenter la geolocalisation sur votre site web, en se se...