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)
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
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
- Bwt wikipedia
- Compression binaire - Meilleures réponses
- Bwt move - Meilleures réponses
- C / C++ / C++.NET : Bwt burrows-wheeler transform - CodeS SourceS - Guide
- C / C++ / C++.NET : Algorithme move to front (mtf) - CodeS SourceS - Guide
- ListView Move to next and previous records ✓ - Forum - Visual Basic 6
- Visual Basic / VB.NET : Transformer un caractère en code binaire et le remettre en caract&egr - Guide
- Transformateur, hexa, binaire, string - Codes sources - IRC (AddOns)
Commentaires
- Messages postés
- 88
- Date d'inscription
- mardi 4 mai 2004
- Statut
- Membre
- Dernière intervention
- 17 février 2008
-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 !
- Messages postés
- 88
- Date d'inscription
- mardi 4 mai 2004
- Statut
- Membre
- Dernière intervention
- 17 février 2008
-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
- Messages postés
- 2065
- Date d'inscription
- lundi 11 avril 2005
- Statut
- Membre
- Dernière intervention
- 14 mars 2016
8 -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.
- Messages postés
- 5
- Date d'inscription
- mardi 15 avril 2003
- Statut
- Membre
- Dernière intervention
- 11 novembre 2005
-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 ?
- Messages postés
- 5
- Date d'inscription
- mardi 15 avril 2003
- Statut
- Membre
- Dernière intervention
- 11 novembre 2005
-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.