Transformée Burrows Wheeler

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche

La transformée de Burrows-Wheeler (aussi appelé BWT) est la seconde étape, mais pas des moindres, de l'algorithme de compression bzip2. C'est d'ailleurs l'un des deux principaux rouages de l'algorithme d'après son auteur :

bzip2 compresses files using the Burrows-Wheeler block sorting text compression algorithm, and Huffman coding.

- Julian Seward

Vous pouvez essayer cette transformée ici ! Mon code est disponible sur github.

Utilisation

Cette transformée est utilisée pour faire apparaître des motifs redondants dans une séquence de lettres ou d'octets, ce qui aide à la compression avec l'encoding d'Huffman.

Elle est aussi utilisée dans le domaine de la génétique, pour chercher une sous-chaîne (une séquence) dans un génome humain de plusieurs gigaoctets.

Principe de fonctionnement

La transformée

La transformé de Burrows-Wheeler se construit à partir d'une matrice de permutations des lettres du mot (ou d'une séquence d'octet de façon générale).

Prenons le mot ABRACADABRA. Voici les étapes à suivre :

1. On créer la matrice des rotations

Il y a autant de rotations que de lettres/octets

A B R A C A D A B R A
B R A C A D A B R A A
R A C A D A B R A A B
A C A D A B R A A B R
C A D A B R A A B R A
A D A B R A A B R A C
D A B R A A B R A C A
A B R A A B R A C A D
B R A A B R A C A D A
R A A B R A C A D A B
A A B R A C A D A B R

2. On trie les lignes suivant un ordre choisi, qu'il faudra respecter pour l'inverse de la transformée. Ici, je choisis l'ordre alphabétique

A A B R A C A D A B R
A B R A A B R A C A D
A B R A C A D A B R A
A C A D A B R A A B R
A D A B R A A B R A C
B R A A B R A C A D A
B R A C A D A B R A A
C A D A B R A A B R A
D A B R A A B R A C A
R A A B R A C A D A B
R A C A D A B R A A B

3. On trouve la ligne contenant le mot initial, et on retiens sont indice I

A A B R A C A D A B R
A B R A A B R A C A D
A B R A C A D A B R A  I=3
A C A D A B R A A B R
A D A B R A A B R A C
B R A A B R A C A D A
B R A C A D A B R A A
C A D A B R A A B R A
D A B R A A B R A C A
R A A B R A C A D A B
R A C A D A B R A A B

4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière colonne de la matrice :

A A B R A C A D A B R
A B R A A B R A C A D
A B R A C A D A B R A  I=3
A C A D A B R A A B R
A D A B R A A B R A C
B R A A B R A C A D A
B R A C A D A B R A A
C A D A B R A A B R A
D A B R A A B R A C A
R A A B R A C A D A B
R A C A D A B R A A B

Le résultat est donc 3RDARCAAAABB. On voit que dans cet exemple, quatre A se suivent ainsi que deux B. Il est facile d'imaginer que sur des séquences beaucoup plus grande, il y aura suffisamment de motifs redondants pour que la compression soit bonne.

L'inverse de la transformée

Pour reconstruire la séquence d'origine, il faut répéter deux étapes, jusqu'à avoir une matrice carrée :

  1. On insert la séquence en première colonne
  2. On tri les lignes par ordre alphabétique

Une fois que nous avons la matrice carré reconstruite, on prend la ligne correspondant à l'indice.

Partons de 3BNENAA. L'indice est de 3 et la séquence est BNENAA.

Insertion Tri Insertion Tri Insertion Tri Insertion Tri Insertion Tri Insertion Tri
B
N
E
N
A
A
A
A
B
E
N
N
BA
NA
EB
NE
AN
AN
AN
AN
BA
EB
NA
NE
BAN
NAN
EBA
NEB
ANA
ANE
ANA
ANE
BAN
EBA
NAN
NEB
BANA
NANE
EBAN
NEBA
ANAN
ANEB
ANAN
ANEB
BANA
EBAN
NANE
NEBA
BANAN
NANEB
EBANA
NEBAN
ANANE
ANEBA
ANANE
ANEBA
BANAN
EBANA
NANEB
NEBAN
BANANE
NANEBA
EBANAN
NEBANA
ANANEB
ANEBAN
ANANEB  1
ANEBAN  2
BANANE  3
EBANAN  4
NANEBA  5
NEBANA  6

Le mot d'origine est donc BANANE.

Algorithmes

À partir du document de référence, on peut établir plusieurs versions d'implémentations de la transformée de Burrows-Wheeler. Une première "naïve", en appliquant la transformée sans se poser de question. La seconde en se basant sur la partie 4 An efficient implémentation de l'article officiel.

Implémentation naïve

Algorithmes Python

Application :

def BTW(word: str) -> Tuple[int, str]:
    """Applique la transformée de Burrows-Wheeler sur `word`"""

    # On construit la matrice de rotation en utilisant les listes en compréhension
    matrice = [word[i:] + word[:i] for i in range(len(word))]

    # On trie (ici, en suivant l'ordre de la table ASCII)
    matrice = sorted(matrice)

    # On récupère l'indice de la chaine de départ 
    index = matrice.index(word)

    # On renvoie l'indice et la dernière colonne de la matrice
    return index, "".join([row[-1] for row in matrice])

Application inverse :

def invert_BTW(index: int, transformed: str) -> str:
    """Applique l'inverse de la transformée de Burrows-Wheeler en fonction de `index` et `transformed`"""

    # On initialise la matrice avec 'nombre de lignes = len(transformed)'
    matrice = [ [] for _ in range(len(transformed))]

    # Pour chaque caractère (ou colonne)
    for _ in range(len(matrice)):

        # On insère le mot `transformed` dans la première colonne
        for i,row in enumerate(matrice):
            row.insert(0, word[i])

        # Et on trie les lignes avec la même fonction que précédemment
        matrice = sorted(matrice, key=lambda row: "".join(row))

    # On renvoie la ligne de la matrice qui nous intéresse, grâce à l'indice de départ
    return "".join(matrice[index])

Limitations

Le problème de cet algorithme, c'est qu'à chaque fois nous construisons une matrice de taille , avec taille des données passées à la transformée (e.g. : ABRACADABRA -> Matrice 11,11). Cela n'est pas un problème pour des mots, mais pour des fichiers de plusieurs gigaoctets cela prendrait trop de place mémoire en plus d'être complètement inefficace, dû au grand nombre d'itérations sur la matrice.

Implémentation avancée

Pour palier le problème de la mémoire, on stocke le mot/fichier dans une variable (dans la réalité, on traitera des fichiers par block, et non pas directement tout le fichier). Chaque "ligne" de la matrice ne peut en faite contenir que deux informations : une référence à la chaîne de caractère et l'indice de position de la première lettre de la rotation.

Puisque nous voulons trier ces lignes, nous devons pouvoir les comparer (inférieur, supérieur, égale...).

On peut donc créer une classe Rotation qui réponde à ces critères :

class Rotation:
    """
        Provide convenient operations on rotated iterables.
        `Rotation(s, i)` represent something like `s[i:]`
    """


    def __init__(self, string, index):
        """string : methode getitem et lt
            string : iterable object passed as reference, implementing standard operators (>,<, ==...)
            index : index of first value
        """

        self.string = string
        self.index = index


    def __str__(self):
        return str(self.string[self.index:] + self.string[:self.index])


    def __repr__(self):
        return 'Rot(' + str(self.string[self.index:] + self.string[:self.index]) + ')'


    def __getitem__(self, index):
        return self.string[(self.index + index)%len(self.string)]


    def __len__(self):
        return len(self.string) - self.index


    def __eq__(self, other):
        return self.string == other.string and self.index == other.index


    def __lt__(self, other):
        """ Lower Than `<` operator 
            usage : Rotation(s, index2) < Rotation (s, index2)
            other : Roration
        """ 
        for i in range(min(len(self), len(other))):
           if self[i] < other[i]:
               return True
           elif self[i] > other[i]:
               return False
        return len(self) < len(other)


    def __le__(self, other):
        """ Lower Than `<=` operator 
            usage : Rotation(s, index2) <= Rotation (s, index2)
            other : Roration
        """ 
        if self[0] <= other[0]:
           return True
        else:
           return False


    def __gt__(self, other):
        """ Lower Than `>` operator 
            usage : Rotation(s, index2) > Rotation (s, index2)
            other : Roration
        """
        for i in range(min(len(self), len(other))):
           if self[i] > other[i]:
               return True
           elif self[i] < other[i]:
               return False
        return False


    def __ge__(self, other):
        """ Lower Than `>=` operator 
            usage : Rotation(s, index2) >= Rotation (s, index2)
            other : Roration
        """ 
        if self[0] >= other[0]:
           return True
        else:
           return False

Avec cette classe, l'implémentation est plutôt simple :

def lastCol(rotation_table):
    """Renvoie la dernière colonne d'une matrice sous la forme List<List>"""

    return [rotation[-1] for rotation in rotation_table]


def BTW(iterable):
    """Effectue la transformée de Burrows-Wheeler sur un itérable avec la classe Rotation"""

    # On crée une liste des rotations
    rotation_table = list(map(lambda i: Rotation(iterable, i), range(len(iterable))))

    # On la trie
    rotation_table = sorted(rotation_table)

    index = None

    # On cherche l'indice de la chaine de départ
    for i, rotation in enumerate(rotation_table):

        if rotation.index == 0:
            index = i
            break

    return index, lastCol(rotation_table)

Seulement pour l'inverse de la transformée, la classe Rotation n'est pas d'une grande utilité. Il faut suivre la partie qui traite les optimisations de l'algorithme dans le document officiel.

def invert_BTW(index, lastCol):
    """ Effectue l'inverse de la transformée de Burrows-Wheeler.

        Notation du document offciel :
        lastCol = L
        len(lastCol) = N
        index = I
        precedingChars = C, même taille que l'alphabet
        P = P, même taille que la colonne
    """

    # On cherche à construire T, une liste qui à un numéro de ligne de la matrice M associe une ligne de la matrice M' (M' étant une matrice dont chaque ligne a été décalée de 1)

    P = [] # i -> Nombre d'instances du caracère lastCol[i] dans le préfix lastCol[:i] (L[0,...,i-1])
    freq = {}

    for i, char in enumerate(lastCol):
        freqChar = freq.get(char, 0)
        P.append(freqChar)
        freq[char] = freqChar+1

    precedingChars = {}
    tmp = 0
    for c in sorted(freq.keys()):
        precedingChars[c] = tmp
        tmp += freq[c]

    del freq


    T = [] # La liste que nous voulions
    for i, char in enumerate(lastCol):
        T.append(P[i] + precedingChars[char])

    del precedingChars, P

    
    # Explication  de la notation du document officiel :
    # T^2 = T[T[I]
    # T^3 = T[T^2[I] = T[T[T[I]

    word = []
    tmp = index # Représente le résultat de T^x
    for i in range(len(lastCol)):
        word.append(lastCol[tmp])
        tmp = T[tmp]

    word.reverse() # On remet le mot à l'endroit
    word = "".join(word)

    return word

L'avantage de cet algorithme, c'est qu'il utilise en mémoire moins de ressources qu'une matrice de rotations. Il utilise un dictionnaire de la taille de "l'alphabet" de la séquence (un texte français -> 26 lettres *2 (majuscule et minuscule) + les caractères spéciaux) et le texte en question.

Sources