Rastell Toull Site web consacrée à la Bretagne, à l'Afrique du nord à la chanson française, à la recherche scientifique, et à bien d'autres sujets ...

La numération monoalpha-multinumérique : une numération compatible avec l'ordre lexicographique et la concaténation par Jacques-Deric Rouault Article original

Page publique Page opérationnelle Version 4.1 du 4 mai 2012 Table thématique Table chronologique Administrateur du site

Dans la seconde solution avancée ici, nous proposons de préfixer le nombre décimal par un premier chiffre qui code le nombre de chiffres qui composent le nombre décimal. Pour faciliter la lecture et limiter les confusions, le premier chiffre est pris dans l'alphabet latin avec la convention A=1, B=2, C=3, ..., Z=26. Ce chiffre peut être a priori  indifféremment écrit en caractères majuscules ou minuscules, mais pour éviter certains problèmes avec les systèmes d'exploitation qui différentient les minuscules des majuscules (comme UNIX), l'usage des majuscules est fortement recommandé.

Cette numération monoalpha-multidécimale s'écrit comme suit : A0, A1, A2, ..., A9, B10, B11, ..., B99, C100, C101, ..., C999, D1000, D1001, etc ...

La compatibilité avec l'ordre alphanumérique est parfaite (propriété que n'a pas la numération décimale), et la compacité est optimale puisqu'on a ajouté un seul chiffre à l'écriture décimale classique.

La plus grande valeur exprimable dans cette numération est 10²⁶-1, ce qui suffit en général pour toutes les applications courantes.

On connait déjà plusieurs numérations alphadécimales : la numération hexadécimale ou de base 16 basée sur les 10 chiffres arabes 0-9 et les 6 premières lettres majuscules de l'alphabet latin A-F,  les numérations hexatridécimale, sexatrigésimale, hexatrigésiale ou de base 36, basée sur les 10 chiffres arabes 0-9 et les 26 lettres de l'alphabet  latin A-Z, ou d'autres numérations de base 64.  Dans la numération monoalpha-multidécimale proposée ici, qui différe des numérations alphadécimales citées ci-dessus, les chiffres arabes et les caractères romains se placent à des endroits précis du nombre. C'est pourquoi, et pour éviter toute ambiguité, nous la qualifion de numération monoalpha-multidécimale afin de bien préciser que les nombres sont formés d'une lettre latine suivie d'un ou plusieurs chiffres arabes.

Coder des nombres à l'aide de lettres était une pratique assez courante dans l'antiquité, en particulier dans les civilisations grecque et hébraïque (Ifrah 1981). Cependant, dans ces alphabets, si les 9 premières lettres codaient les unité, les 10 suivantes codaient les dizaines et les dernières lettres les premières centaines. Il existe cependant un système archaique de numération basé sur les 24 lettres de l'alphabet grec, daté du VIe siècle avant JC, et analogue à celui décrit ici. Ce système, qui ne dépasse pas 24, est en particulier utilisé pour numéroter les 24 livres de l'Illyade et de l'Odyssée (Reinach, 1885). 

Pour accroître la lisibilité des grands nombres entiers, il est d'usage d'intercaler régulièrement (tous les trois chiffres) un symbole séparateur : blanc, point (en français), virgule (en anglais). Cet usage demeure compatible avec la numération monoalpha-multidécimale, sous la réserve qu’ils soient appliqués à tous les nombres de la série. Pour des raisons de compatibilité avec les différents systèmes d'exploitation des ordinateurs, le choix du caractère blanc souligné (ASCII 95) retenu dans le langage ADA (Taft & Duff, 1997) sera très fortement conseillé.

Pour coder des nombres supérieurs à 26 chiffres, on codera alors la longueur sur deux caractères alphabétiques, ce qui autorise les nombres jusqu'à 10^26*26 soit 10⁶⁷⁶. On parlera alors de numération dialpha-multidécimale. Et ainsi de suite …

Cette méthode de préfixage par un chiffre alphabétique peut également être étendue aux numérations binaires, hexadécimales, etc ...

La concaténation directe de deux ou plusieurs nombres entiers peut être lue comme un seul entier ou plusieurs entiers écrits suivant un format fixe. Par exemple le nombre 20080611 peut être également comme le 11e jour du 6e mois de l'année 2008 dans le format fixe AAAAMMJJ. Pour lever cette ambiguité, l'écriture D2008A6B11 indique clairement que le nombre figuré résulte de la concaténation de trois nombres entiers. Comme dans la table ASCII les chiffres (codes 48 à 57) sont codés avant les lettres majuscules (codes 65 à 90) et les caractères minuscules (codes 97 à 122), la concaténation des nombres monoalpha-multidécimale est totalement compatible avec l'ordre lexicographique. A1B12 se range avant B12A1 car A est avant B, A1C124 se range avant A1D1308 car C se range avant D.

Dans un arbre, le nom d'une branche est formé par la concénation du nom de la branche qui arrive au noeud et du nom représentant le rang de la branche au noeud. L'utilisation de la numération monoalpha-multidécimale offre une façon naturelle de nommer toutes les branches de l'arbre dans un ordre compatible avec l'ordre lexicographique (Figure 1)

Figure 1 : Dénomination des branches d'un arbre par concaténation de nombres monoalpha-multidecimaux.

    Dans l'arbre de la figure 1, les noms des 46 branches sont automatiquement rangées par l'ordre lexicographique : A1, A1A1, A1A1A1, A1A1A2, A1A1A2A1, A1A1A2A2, A1A1A2A3, A1A1A2A4, A1A1A3, A1A2, A1A3, A1A3A1, A1A3A1A1, A1A3A2, A1A4, A1A4A1, A2, A2A1, A2A1A1, A2A1A1A1, A2A1A1A2, A2A1A2, A2A1A3, A2A1A3A1, A2A2, A3, A3A1, A3A1A1, A3A1A2, A3A1A3, A3A1A4, A3A1A5, A3A1A6, A3A1A7, A3A1A8, A3A1A9, A3A1B10, A3A1B11, A3A1B12, A3A1B13, A3A1B14, A3A2, A3A3, A3A3A1, A3A3A2, A4. L'ordre lexicographique décrit l'arbre en prenant à chaque noeud le branche la plus à gauche. Même pour une branche située au 4e niveau, son nom (par exemple A2A1A3A1) reste très lisible.

La numération monoalpha-multinumérique a été développé dans le contexte particulier de la constitution d'une base de données consacrée au recensement exhaustif des éléments transposables. Il s'agit de séquences relativement courtes d'ADN plus ou moins hautement répétées dans les génomes des différentes espèces vivantes. Un même élément transposable peut être retrouvé dans différents organismes et se trouve alors identifié sous des noms différents dans les différentes bases de données disponibles. Partant du fait que deux éléments transposables de longueurs différentes sont nécessairement différents, les éléments transposables recensés sont alors codés par la concaténation de deux nombres monoalpha-multidécimaux : le premier donne le nombre de paires de bases et le second second nombre qui donne son rang d'identification ;  par exemple C451B48. La comparaison d'un nouvel élément à ceux déjà recensés est alors très fortement accélérée suivant un processus classique de tri rapide, puisqu'il suffit de le comparer uniquement à ceux de longueur identique, dont le nom traduit le premier des deux nombres.