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

Télécharger le projet
Commenter

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
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (psycho81)