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:

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:

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:

$$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!