Public Class bwt Private ReadOnly bin(255, 7) As Integer Public Sub New() Dim i As Integer Dim j As Integer 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 Function bwt(ByRef str As String) Return bwt(System.Text.ASCIIEncoding.Default.GetBytes(str)) End Function Public Function bwt(ByRef b() As Byte) 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") Dim oct As Byte = 0 Dim pos As Integer = 0 Dim posout As Integer = 0 Dim out(UBound(b)) As Byte 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 k = bin(b(j >> 3), (j And 7)) oct = oct Or (1 << (7 - pos)) 'Console.Write(oct) End If If pos = 7 Then out(posout) = oct posout += 1 pos = 0 oct = 0 Else pos += 1 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 Return out lev = Nothing ptr = Nothing k = Nothing j = Nothing i = Nothing blim = Nothing lim = Nothing End Function 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