COMPRESSION BINAIRE - BWT (BURROWS-WHEELER TRANSFORM) MFT (MOVE TO FRONT) QUICKSORT

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