Le codage de Fibonacci et Python

codage fibonacci python

Le codage de Fibonacci et Python

Le codage de Fibonacci et Python : mais c’est quoi ce codage ?

Nous allons avant tout parler mathématiques, puis nous allons implémenter tout ça en Python.

Le codage de Fibonacci et Python: approche mathématique

Codage de Fibonacci d’un caractère

Un caractère est représenté en ASCII par un nombre. Par exemple, le caractère “A” est représenté par le nombre “65”. Bien sûr, “65” peut être représenté en binaire…

Du décimal au binaire

Pour convertir un nombre décimal au binaire, il suffit de décomposer le nombre décimal en somme de puissances de 2.$$\begin{align}65&=64+1\\&=2^6+1\\&=\small 0 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0\end{align}$$

On peut représenter cette décomposition à l’aide du tableau suivant:

\(2^7\)\(2^6\)\(2^5\)\(2^4\)\(2^3\)\(2^2\)\(2^1\)\(2^0\)
01000001

Ainsi, le nombre décimal 65 peut être codé en binaire sur un octet (8 bits) par 01000001.

Du décimal au “fibonaire”

Ne cherchez pas la définition du “fibonaire”, c’est un mot que j’ai inventé 🙂

Nous allons suivre le même principe que précédemment, mais au lieu de décomposer en somme de puissances de 2, nous allons le faire en somme de termes de la suite de Fibonacci.

Suite de Fibonacci

Cette suite, souvent notée \( (F_n) \) est définie par ses deux premiers termes \(F_0=F_1=1\) et par la relation de récurrence:$$\forall\ n\in\mathbb{N},\quad F_{n+2} = F_{n+1} + F_n.$$ Ses premiers termes sont donc :

  • \(F_2 = F_0+F_1=1+1=2\)
  • \(F_3=F_1+F_2=1+2=3\)
  • \(F_4=F_2+F_3=2+3=5\)
  • \(F_5=F_3+F_4=3+5=8\)

Théorème de Zeckendorf

Le théorème de Zeckendorf stipule que tout entier naturel n peut s’écrire sous la forme:$$n = \sum_{i=1}^k\alpha_i F_i$$où:

  • \(\alpha_i \in \{0;1\}\)
  • \(\alpha_i \times \alpha_{i+1} = 0\)
  • \(F_i\) est le i-ème terme de la suite de Fibonacci.

Par exemple, $$65 = 2+8+55$, que l’on peut représenter sous forme de tableau:

1235813213455
010010001

Codage et décodage de Fibonacci

Pour coder le caractère “A”, il suffit d’ajouter un “1” à droite de la décomposition. On obtient alors :

“A” devient 0100100011

Le théorème de Zeckendorf nous assure que le codage ne peut pas comporter deux “1” côte-à-côte sauf à la fin, ce qui s’avère utile pour coder un message.

En effet, si l’on doit décoder le message :

1010100011000100011101010000110001001001110010010011001010110100010001100001000011100101000111001010001101010010011010010000110010010001100000010011000010000110000001001110010010011001010110100100001110101000011001010110010001001101010010011101010000110010101110010100011000100011100000100110000001001100101011010000100111010100001101010010011100100100110010101100000100011000010000110010010001110100010011101010000110010101110101011

il suffit de repérer les deux “1” pour savoir où découper. Ici, on aura donc:

  • 1010100011,
  • puis 000100011 (quand il y a 3 “1”, il faut ne prendre que les deux premiers – qui indiquent la fin du codage d’un caractère – car l’autre 1 correspond au premier chiffre du codage du caractère suivant),
  • puis 10101000011,
  • etc.

Une fois la découpe faite, il suffit, pour chaque paquet, de supprimer le “1” final et de faire le chemin inverse du codage. Par exemple, ici, le premier paquet est 1010100011; on enlève le “1” final et on met le résultat dans le tableau:

1235813213455
101010001

$$1+3+8+55=67$$donc le premier paquet est le codage de 67, qui correspond au caractère “C”.

Le codage de Fibonacci en Python

Regardons pas à pas comment implémenter un codage de Fibonacci en Python.

Construction d’une table contenant les termes de la suite de Fibonacci

def suite(n):
    table = [1,1]
    k = 1
    while max(table) <= n:
        table.append( table[k-1] + table[k] )
        k += 1
    table.pop()
    
    return table[1:]

L’idée est ici d’écrire une fonction suite(n) qui retourne tous les termes de \(F_1\) à \(F_k\), où \(F_k\leqslant n\).

La fonction de codage

On va d’abord commencer par coder un caractère:

def codage_car(c): # codage d'un caractère
    s = 0
    coef = []
    F = suite( ord(c) )
    for i in range( 1 , len(F)+1 ):
        if s + F[-i] <= ord(c):
            coef.append(1)
            s += F[-i]
        else:
            coef.append(0)
    coef.reverse()
            
    return ''.join([str(_) for _ in coef]) + '1'

Ensuite, on implémente une fonction qui code tout un message:

def codage(message):
    r = ''
    for l in message:
        r += codage_car(l)
        
    return r
>>> codage("C'est génial!")
1010100011000100011101010000110001001001110010010011001010111000010001100000000000110000001001100100100011000010000111001010001110101011

La fonction de décodage

On commence par la fonction qui décode un paquet:

def decodage_car(c):
    C = list(c[:-1])
    F = [1,1]
    for i in range( len(C)-1 ):
        F.append( F[i] + F[i+1] )
    
    G = F[1:]
    s = 0
    
    for i in range( len(C) ):
        s += G[i]*int(C[i])
        
    return chr(s)

puis celle qui décode le message entier:

def decode(message):
    r = ''
    while len(message) !=0 :
        p = message.find('11')
        r += decodage_car(message[:(p+2)])
        message = message[(p+2):]
        
    return r
>>> decodage('1010100011000100011101010000110001001001110010010011001010111000010001100000000000110000001001100100100011000010000111001010001110101011')
C'est génial!

Stéphane Pasquet
Stéphane Pasquet

1 réflexion au sujet de « Le codage de Fibonacci et Python »

Nicolas PatroisPublié le  8:22 - Juil 26, 2021

J’aime bien l’idée, ça me rappelle un autre codage (pseudo unaire), avec deux touches sur le clavier : l’espace et une autre, par exemple 0.
Par exemple, le caractère A a pour code binaire 01000001 (65 en décimal). Vous l’encodez 0 0 00 0 0 00000 00 0. Pour r, 01110010 est codé 0 0 00 000 0 00 00 0 0 0. Je vous laisse trouver comment ça marche.

Je me suis amusé à recoder les quatre fonctions de la page. Comme les caractères en utf8 vont jusqu’à 0x1000C7=1048775, on peut se contenter des 40 premiers termes de la suite de Fibonacci. La fonction la plus longue est la première, les trois autres se font en une ligne.
La première utilise encore map (qui renvoie un itérateur sur les images des éléments de l’itérable par la fonction).
J’ai utilisé la fonction zip qui renvoie ici un itérateur sur les paires successives de deux itérables (le plus long est automatiquement tronqué à la longueur du plus court).
Pour découper le message codé, j’ai utilisé la méthode split mais ça fait perdre le séparateur et ajoute un caractère vide à la fin.

fibo=[0,1]
for _ in range(40):
  fibo.append(sum(fibo[-2:]))
del fibo[:2]

def codagec(c):
  o=ord(c)
  i=-1
  m=""
  while True:
    try:
      if fibo[i]<=o:
        m="1"+m
        o-=fibo[i]
      elif m:
        m="0"+m
      i-=1
    except:
      break
  return m+"1"

def codage(m):
  return "".join(map(codagec,m))

def décodagec(m):
  return chr(sum(f*int(c) for f,c in zip(fibo,m[:-1])))

def décodage(m):
  return "".join(décodagec(c+"11") for c in m.split("11")[:-1])

Laissez votre message