Compression binaire - bwt (burrows-wheeler transform) mft (move to front) quicksort

Soyez le premier à donner votre avis sur cette source.

Vue 16 174 fois - Téléchargée 309 fois

Description

Ce code (non fini pour l'instant) sert (et servira) à réorganiser des données avec la méthode BWT (Burrows-Wheeler Transform). Puis de le traiter avec le Move-To-Front afin de le passer dans un compresseur réel arithmétique (ou autre suivant les possibilités). Le code actuel fait le BWT et le MFT (tout ca en test). Je dépose cette source afin que la communauté de vbfrance puisse amener à ce projet des propos vis à vis de la performance à améliorer pour ce traitement (qui est très lourd dans son utilisation théorique). Bien sur, je suis persuadé que beaucoup diront qu'il serai préférable le faire en C ou en assembleur. Je n'en suis pas encore à cette conception mais celà suivra. Je souhaite pour le moment savoir si des optimisations sympas pouvait être effectuées.

Voili voilou

Je vous file pas le projet car il est en vb2005 et je sens que je vais récupérer quelques plaintes de non compatibilités et donc ... d'abandon de curiosité. Je vous donne donc seulment la classe. Vous pouvez m'écrire pour de plus amples informations, je suis avide de conseils et critiques "constructives". Evitez, s'il vous plait les "Ce code est nul, apprends à programmer" sans apporter de solutions. Merci et bonne prog !

je tiens à signaler que j'aimerai pouvoir prendre un bloc d'octet le plus important possible suivant la mémoire, toute proposition allant dans ce sens est la bienvenue !

Pour des informations sur BWT et MTF voici un cours sommaire
http://fr.wikipedia.org/wiki/Transformation_de_Burrows-Wheeler mais qui ne travaille pas en binaire (je n'ai d'ailleur trouvé aucune source BWT en binaire !)

http://fr.wikipedia.org/wiki/Mtf

et le quicksort binaire (qui est lui aussi introuvable sous cette forme pourtant ... utile car il n'y a plus la notion de pivot)

Source / Exemple :


Public Class ClsBwt

    Private ReadOnly bin(255, 7) As Integer

    Public Sub New()

        Dim i As Integer
        Dim j As Integer

        ' Construction du tableau binaire qui permet d'économiser quelques calculs

        For i = 0 To 255
            For j = 0 To 7
                bin(i, j) = (i >> (7 - j)) And 1
            Next
            'Console.WriteLine(i & vbTab & bin(i, 0) & bin(i, 1) & bin(i, 2) & bin(i, 3) & bin(i, 4) & bin(i, 5) & bin(i, 6) & bin(i, 7))
        Next
        j = Nothing
        i = Nothing

    End Sub

    Public Sub bwt(ByRef str As String)
        bwt(System.Text.ASCIIEncoding.Default.GetBytes(str))
    End Sub

    Public Sub bwt(ByRef b() As Byte)

        Console.WriteLine("BWT generator")

        Dim lim As Integer = UBound(b)
        Dim blim As Integer = ((lim + 1) << 3) - 1

        Dim blims = CType(blim >> 1, Integer)
        Dim blim2 = blim + 1

        Dim i As Integer
        Dim j As Integer
        Dim k As Integer

        Dim ptr(blim) As Integer

        Dim change As Integer = 0

        'Console.WriteLine("Initialisation des pointeurs")

        For i = 0 To blim
            ptr(i) = i
        Next

        Console.WriteLine("Chaine origine (binaire)")
        For i = 0 To blim
            j = ptr(i) - 1
            If j < 0 Then
                j = blim
            End If
            Console.Write(bin(b(j >> 3), (j And 7)))
        Next
        Console.WriteLine("")

        Dim lev As Integer = 0
        Dim cpt(blim, 3) As Integer
        cpt(lev, 0) = 0
        cpt(lev, 2) = blim
        cpt(lev, 3) = -1

        'view(ptr, b, lev, cpt)

TriLev:
        'Console.WriteLine(spa(lev) & "Tri du level " & lev & " de " & cpt(lev, 0) & " à " & cpt(lev, 2))

        'view(ptr, b, lev, cpt)

        If cpt(lev, 3) = -1 Then
            'Console.WriteLine(spa(lev) & "Tri du level " & lev & " de " & cpt(lev, 0) & " à " & cpt(lev, 2))
            cpt(lev, 3) = 0

            i = cpt(lev, 0)
            j = cpt(lev, 2)

            cpt(lev, 1) = -1

Cherche1:

            k = ptr(i) + lev
            If k >= blim2 Then
                k -= blim2
            End If
            If bin(b(k >> 3), k And 7) = 0 Then
                i += 1
                If i <= j Then
                    GoTo Cherche1
                Else
                    GoTo EndSearch
                End If
                'Else
                'Console.WriteLine(spa(lev) & "On a un 1")
            End If
            cpt(lev, 1) = i
Cherche0:

            k = ptr(j) + lev
            If k >= blim2 Then
                k -= blim2
            End If
            If bin(b(k >> 3), k And 7) = 1 Then
                j -= 1
                If i < j Then
                    GoTo Cherche0
                Else
                    GoTo EndSearch
                End If
                'Else
                'Console.WriteLine(spa(lev) & "On a un 0")
            End If

            If i < j Then
                'Console.WriteLine(spa(lev) & "Echange [" & i & "-" & j & "]")
                change += 1
                k = ptr(i)
                ptr(i) = ptr(j)
                ptr(j) = k
                cpt(lev, 1) = j
                i += 1
                j -= 1
                GoTo Cherche1
            End If

EndSearch:
            'Console.WriteLine(spa(lev) & "FIN Premier 1 : " & cpt(lev, 1))

            If cpt(lev, 1) <> -1 Then
                'Ya des 1

                k = cpt(lev, 1) - 1
                If k > cpt(lev, 0) Then
                    'Console.WriteLine(spa(lev) & "Relancement de la boucle sous tri 0 de " & cpt(lev, 0) & " à " & k)
                    If cpt(lev, 1) < cpt(lev, 2) Then
                        cpt(lev, 3) = 1
                    Else
                        cpt(lev, 3) = 2
                    End If

                    i = lev + 1
                    If i <= blim Then
                        cpt(i, 0) = cpt(lev, 0)
                        cpt(i, 2) = k
                        cpt(i, 3) = -1
                        lev += 1
                    End If

                    GoTo TriLev
                End If

                If cpt(lev, 1) < cpt(lev, 2) Then
                    'Console.WriteLine(spa(lev) & "Relancement de la boucle sous tri 1 de " & cpt(lev, 1) & " à " & cpt(lev, 2))
                    cpt(lev, 3) = 2
                    i = lev + 1
                    If i <= blim Then
                        cpt(i, 0) = cpt(lev, 1)
                        cpt(i, 2) = cpt(lev, 2)
                        cpt(i, 3) = -1
                        lev += 1
                    End If
                    GoTo TriLev
                End If
                'Console.WriteLine(spa(lev) & "Fin du tri du level " & lev)
                lev -= 1
                GoTo TriLev

            Else

                ' Ya pas de 1

                'Console.WriteLine(spa(lev) & "Relancement de la boucle sous tri 0 de " & cpt(lev, 0) & " à " & cpt(lev, 2))
                cpt(lev, 3) = 2
                i = lev + 1
                If i <= blim Then
                    cpt(i, 0) = cpt(lev, 0)
                    cpt(i, 2) = cpt(lev, 2)
                    cpt(i, 3) = -1
                    lev += 1
                End If

                GoTo TriLev

            End If

        End If

        If cpt(lev, 3) = 1 Then
            'Console.WriteLine(spa(lev) & "***** Lancement du sous tri 1 du level " & lev & " de " & cpt(lev, 1) & " à " & cpt(lev, 2))
            cpt(lev, 3) = 2
            i = lev + 1
            If i <= blim Then
                cpt(i, 0) = cpt(lev, 1)
                cpt(i, 2) = cpt(lev, 2)
                cpt(i, 3) = -1
                lev += 1
            End If

            GoTo TriLev
        End If

        If cpt(lev, 3) = 2 Then
            'Console.WriteLine(spa(lev) & "Fin du tri du level " & lev & " de " & cpt(lev, 0) & " à " & cpt(lev, 2))
            lev -= 1
            If lev >= 0 Then
                GoTo TriLev
            End If
        End If

        'view(ptr, b, 0, cpt)

        Console.WriteLine(change & " changement(s)")

        Console.WriteLine("Transformée de Burrows-Wheeler")

        For i = 0 To blim
            j = ptr(i) - 1
            If j < 0 Then
                j = blim
            End If
            Console.Write(bin(b(j >> 3), (j And 7)))
        Next
        Console.WriteLine("")

        Console.WriteLine("MoveToFront")

        k = 0
        For i = 0 To blim
            j = ptr(i) - 1
            If j < 0 Then
                j = blim
            End If
            If bin(b(j >> 3), (j And 7)) = k Then
                Console.Write("0")
            Else
                k = bin(b(j >> 3), (j And 7))
                Console.Write("1")
            End If
        Next

        lev = Nothing
        ptr = Nothing

        k = Nothing
        j = Nothing
        i = Nothing

        blim = Nothing
        lim = Nothing
    End Sub

    Private Sub view(ByRef ptr() As Integer, ByRef b() As Byte, ByVal lev As Integer, ByRef cpt(,) As Integer)
        Dim lim As Integer = UBound(ptr)
        Dim lim2 As Integer = lim + 1
        Dim k As Integer
        Dim i As Integer
        Dim j As Integer

        Dim str As New System.Text.StringBuilder

        For i = 0 To lim
            str.Append(spa(lev))
            For j = 0 To lim
                k = ptr(i) + j
                If k >= lim2 Then
                    k -= lim2

                End If
                str.Append(bin(b(k >> 3), (k And 7)))
            Next
            str.Append(vbTab)

            For j = 0 To 3
                k = cpt(i, j)
                str.Append(cpt(i, j) & vbTab)
            Next

            str.Append(vbCrLf)
        Next

        Console.WriteLine(str.ToString)
        Console.ReadLine()

        j = Nothing
        i = Nothing
    End Sub

    Private Function spa(ByVal nb As Integer) As String
        Return New String(" ", nb)
    End Function

    Protected Overrides Sub Finalize()
        MyBase.Finalize()
    End Sub

End Class

Conclusion :


L'appel se fait de cette manière

Dim MonBwt as ClsBwt

MonBwt.bwt(TableauDeBytes) ' ou
MonBwt.bwt("aaa") ' ou

Pour les tests ... Ne prenez pas de trop grandes chaines au début ... Certaines optimisations ne sont pas encore développées.

Je sais, il reste beaucoup de ligne de test, ca sert a tracer un peu la progression du programme

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

psycho81
Messages postés
88
Date d'inscription
mardi 4 mai 2004
Statut
Membre
Dernière intervention
17 février 2008
-
Petite information en passant :

La méthode de base de réorganisation BWT a été mise au point en 1994. Depuis, les meilleurs taux de compression réalisés sont souvent à base de cette méthode de réorganisation. Il est à prévoir que de nouvelle méthode post BWT, similaire à l'algorhytme JPEG verront le jour. Pour l'instant les possiblités offertes par cet algorhytme n'ont pas encore été totalement exploités (à l'inverse de Hufmann par exemple dont on a défini une certaine limite). BWT est donc très récent et est donc succeptible de provoquer une véritable révolution dans les méthodes de compression (une autre ...). Bientot dans le zip, je mettrai une documentation sur BWT et MTF, un recueil de texte glané ci et là sur le net.

Bonne prog !
psycho81
Messages postés
88
Date d'inscription
mardi 4 mai 2004
Statut
Membre
Dernière intervention
17 février 2008
-
Doodoo256,

L'efficacité de cette méthode est ... dans ce cas précis nulle vu qu'elle ne fait que réorganiser les données vers une forme plus ... facilement compressible. Il allourdit meme le packet de la référence de ligne qui permettra de retrouver la chaine originelle. Cependant, la réorganisation effectué permet de dégager un très grand nombre de zéro dans la chaine binaire (vu que le move to front remplace 1111100000 par 1000010000). Pour ce qui est de l'implémentation de cet algorhytme, bzip2 l'utilise ainsi que compressia et ... bien d'autre je pense (au fait Doodoo256 j'ai une version beta de compressia en ligne de commande qui devrait t'interesser, pour que je te le fasse aprvenir contacte moi à rebel_thc AroBaBase yahoo point afrreux -Super ce mail non ? :p)

Pour répondre à la compression qui sera utilisé par la suite, vu le très grand nombre de zéro que nous pourrons trouver, j'ai opté pour une compression arithmétiqe binaire pas au point encore pour le moment( us_30 Huffman serait un acte inutile dans ce cas la vuq ue je travaille en binaire et donc le gain serait nul sous cette forme vu qu'il faudrai au moins 1 bit pour coder 1 bit alors que la compression aritmétique permet de coder n bit avec un seul bit ! je suis arrivé chez moi à n = 1236 bits sans forcer soit un gain considérable !).

Doodoo256, l'avantage de cette méthode est qu'il n'est pas nécessaire d'avoir un tableau (n,n) donc exponentielle mais plutot du genre (3 ou 4,n) donc linéaire ce qui permet d'avoir une montée de mémoire moindre suivant la taille du bloc (le BWT expliqué est toujours de la forme (n,n)). Donc pour conclure... plus la mémoire est grande, plus grand est le buffer, et ... plus la réorganisation des données est efficiente.

Le fait de travailler sous forme binaire permet de trouver des cycles de répétitions plus précis que par octects par exemple ab n'a aucun cycle alors que 0110000101100010 (ab en binaire) contient des cycles ici 011000 01 011000 10

La taille du buffer optimale serait donc de la forme Total mémoire / NombreDeBitsDuBloc*BitsUtilisésPourTraitementDunBit

Bientot la suite ...

Bonne prog
us_30
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
8 -
Salut,

Je découvre cet algo, que je cherchais depuis des années dans ma pauvre tête... Pour comprendre, faut mieux lire l'adresse donné sur wikipedia ... Désolé psycho81. Bon, je me pencherai dessus, et si j'ai une bonne remarque, je te tiendrai au courant. Le .NET , c'est pas ma spécialité, mais on le comprend assez bien, en connaissant VB...

Par contre, pour avancer un peu sur le débat, je me pose qlq questions.
- Pourquoi choisir la forme binaire plutôt que par octet directement.
- Ce qui me semble évident, pour répondre à DooDoo, c'est de découper par bloc. Si on pense à des fichiers de plusieurs Méga, voir Giga, on rendrait fou le PC sans bloc ! Mais il reste une question. Y a-t-il une taille optimum... (surement, si on tient compte des déclarations des variables)
- Ensuite, après transformation, je ne vois pas l'intérêt d'utiliser Huffman. Le plus direct serait comme pour le PCX d'antant, non ? (surtout si la taille traitée est assez conséquente)

Amicalement,
Us.
Doodoo256
Messages postés
5
Date d'inscription
mardi 15 avril 2003
Statut
Membre
Dernière intervention
11 novembre 2005
-
Ok, un petit tour sur Google m'a ouvert les yeux..

Le site de Compressia est mort on dirait.

En tout cas, quel algo de compression as-tu l'intention d'appliquer après BWT ?
Question bête :

Si on applique BTW sur un fichier binaire d'environ 500 Ko, il faut une grosse bécane pour faire les rotations ou alors découper en blocs c'est ça ?
Doodoo256
Messages postés
5
Date d'inscription
mardi 15 avril 2003
Statut
Membre
Dernière intervention
11 novembre 2005
-
Bonsoir,

je viens de faire un petit tour dans les sources et je tombe là dessus...
Je vais suivre avec intérêt tes travaux ça m'a l'air révolutionnaire malgré la complexité de l'algo.

Où se situe l'efficacité de cette méthode par rapport à du 7z, LZW et Huffman par exemple ?

L'algo a déjà été implémenté ? Dans quel soft ?

a++ ;

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.