Nouvelle algorithme de compression Résolu/Fermé

Question

Bonjour, 

Je vien de creer en java un outil de compression et je souhaite avoir votre avis sur ses performances (non en vitesse mais en puissance de compression) pour l'instant l'engin est tres lent et peut compresser 800 Ko en quelques secondes, il n'y a pas de gestion du multi Thread. Voici le lien vers les sources : https://github.com/LaPatate64/Compressor 

Configuration: Windows 7 / Chrome 24.0.1312.57

KX · Answer

Quand on regarde ta classe ByteBuffer, on voit immédiatement pourquoi tes performances sont mauvaises, le dimensionnement de ton byte[] data est trop strict, sauf erreur, tu as toujours data.length==stackSize, ce qui signifie que tu fais sans arrêt des opérations de copier/coller des données (regarde push, pop, et remove)

Pour améliorer la vitesse, il faut que tu limites le nombre de ces copier-coller, en t'autorisant d'avoir data.length>stackSize, et augmenter de manière importante la taille du buffer (x2 par exemple) lorsque tu le redimensionnes, afin d'éviter d'avoir à l'agrandir trop souvent. De plus, quand tu enlèveras des données, ne changes pas de tableau, ça ne sert à rien.

Par exemple tu peux faire une fonction ensureCapacity qui augmentera ton tableau en taille si nécessaire. Idéalement, c'est la seule méthode qui devrait modifier la taille du tableau, les autres méthodes devrait l'appeler pour augmenter la mémoire. Au passage, il serait plus performant d'utiliser les méthodes de Arrays plutôt que de réimplémenter à la main les copies. Enfin, quelques constructeurs seraient les bienvenus, en particulier pour initialiser le ByteBuffer avec une capacité donnée.

Il faudrait passer en revue toutes tes méthodes pour les optimiser avec les modifications, je t'en donne juste quelques unes pour voir comment ça marche :

private byte[] data;
private int stackSize;
private int stackCapacity;

public ByteBuffer()
{
    stackSize = 0;
    stackCapacity = 128;
    data = new byte[128];
}

public ByteBuffer(int capacity)
{
    stackSize = 0;
    stackCapacity = capacity;
    data = new byte[capacity];
}

public ByteBuffer(byte[] value)
{
    stackCapacity = stackSize = value.length;
    data = Arrays.copyOf(value, stackCapacity);
}

private void ensureCapacity(int minimalCapacity)
{
    if (stackCapacity < minimalCapacity)
    {
        do stackCapacity *= 2;
        while (stackCapacity < minimalCapacity);
        
        data = Arrays.copyOf(data, stackCapacity);
    }
}

public void clear()
{
    stackSize = 0;
}

public void push(byte number) 
{
    ensureCapacity(stackSize+1);
    data[stackSize]=number;
    stackSize++;
}

public void push(byte[] number)
{
    ensureCapacity(stackSize+number.length);
            
    for (int a=stackSize, b=0; b != number.length; a++, b++)
        data[a] = number[b];
    
    stackSize += number.length;
}
Pour ton algorithme de compression, quelques explications de ta méthode serait plus qu'utile pour faire des remarques objectives. Sinon, on pourra juste optimiser le programme mais pas la compression en elle même.

nicocorico · Answer

Oui je vois, tu sembles vouloir exploiter l'idée que les octets à compresser n'utilisent qu'une petite partie des 256 valeurs possibles...ou du moins je crois, car tu dis que ton dictionnaire peut s'étendre jusqu'à 256 valeurs, mais dans ce cas il contiendrait simplement les valeurs de 0 à 255, à quoi servirait-il?  
Et il faut pas se leurrer, il n'y a aucune chance que la fourchette de valeurs soit si limité, ou bien dans ce cas il faut les compresser dès l'origine plutôt que d'utiliser un principe de compression plus universel... 
Et c'est très bien de chercher par soi-même et il faut que tu continues dans cette voie, cependant il faut aussi savoir s'inspirer de ce qui existe déjà...tu penses bien que nombreux sont ceux qui ont réfléchi à ce sujet, et le fait de bien étudier les algorithmes que d'autres ont imaginé te permettra de comprendre les pièges, les limites et les possibilités de la compression de données. Je te propose de creuser le lien que je t'ai passé, tu y apprendra directement le principe que tu vas finir par obtenir en cherchant dans la voie que tu as empruntée! 
  
Le chêne aussi était un gland, avant d'être un chêne

nicocorico · Answer

Bon j'y reviens un peu! J'ai pensé à une technique toute simple et relativement rapide permettant de déterminer toutes les répétitions de suites d'octets d'un fichier. En fait il suffit de répertorier les suites déjà rencontrées sous forme d'arbre, et pour chaque nouvelle recherche on trouve la meilleure chaine existante, puis on détermine le nombre d'octets en commun au-delà des bornes de la meilleure chaine initiale... Chaque chaine ajoute donc un ou plusieurs octets à sa chaine parente, sa taille s'arrêtant au premier octet différent, donc pour chaque chaine on détermine bel et bien la plus longue chaine lui correspondant dans le fichier. Et on fait ça à chaque octet ajouté, donc on créé autant de chaine qu'il y a d'octets. Grâce à ce résultat, on peut donc savoir quelles sont les chaines les plus rentables pour la compression... d'autant plus qu'on a accès à l'ensemble des descendants d'une chaine donnée, ce qui permet de déterminer tous les endroits où l'on trouve la même base, pour limiter la diversité des chaines. Donc il devient possible de partir d'une chaine et de dire partout où on la trouve comme tu en avais l'idée... là on a le choix entre le «où» et le «quoi»! Voilà, c'est une bonne base de travail! Je mets ici le programme en pascal (delphi), programme n'étant qu'une base pour expérimentation, il ne fait rien d'autre que de calculer la table pour l'exemple. unit Tri; interface uses Windows, Messages, SysUtils; implementation Type PDatasT = ^DatasT; DatasT = Array[0..$7FFFFFF] of Byte; PPAlpha_Def = ^PAlpha_Def; PAlpha_Def = ^Alpha_Def; Alpha_Def = Packed Object FFrere : PAlpha_Def; // Chaine suivante ayant la même chaine-base FFils : PAlpha_Def; // Pointeur sur le premier descendant FParent : PAlpha_Def; // Parent FSize : Integer; // Taille totale de la chaine FFirstCode : PDatasT; // Pointeur sur le début spécifique de cette chaine end; Var AlphaPtr : Array of Alpha_Def; // Recueil des chaines Procedure Extract(Src: PDatasT; Size: Integer); Var Fils_ : PAlpha_Def; PredFils_ : PPAlpha_Def; ChaineBase : PAlpha_Def; NewParent : PAlpha_Def; NewSize : Integer; Alpha_Size : DWord; begin ChaineBase:= @AlphaPtr[0]; Alpha_Size:= 256; Repeat If ChaineBase.FSize > 0 then begin DWord(NewParent):= DWord(ChaineBase) + SizeOf(Alpha_Def); While NewParent.FSize >= ChaineBase.FSize do NewParent:= NewParent.FParent; end else NewParent:= @AlphaPtr[Src[0]]; NewSize:= NewParent.FSize+01; Repeat If NewParent.FFirstCode <> nil then While (NewParent.FFirstCode[NewSize] = Src[NewSize]) and (NewSize < Size) do Inc(NewSize); PredFils_:= @NewParent.FFils; Fils_ := NewParent.FFils; While (Fils_ <> nil) and ((Fils_.FSize < NewSize) or ((Fils_.FSize = NewSize) and (Fils_.FFirstCode[NewSize] < Src[NewSize]))) do begin PredFils_:= @Fils_.FFrere; Fils_ := Fils_.FFrere; end; If (Fils_ = nil) or (Fils_.FSize <> NewSize) or (Fils_.FFirstCode[NewSize] <> Src[NewSize]) then Break; NewParent:= Fils_; Inc(NewSize); until (NewSize >= Size); With AlphaPtr[Alpha_Size] do begin FParent := NewParent; FFirstCode := Src; // Pointe sur le début de la chaine FSize := NewSize; FFrere := PredFils_^; PredFils_^ := @AlphaPtr[Alpha_Size]; end; ChaineBase:= NewParent; Inc(Alpha_Size); Inc(DWord(Src)); Dec(Size); Until Size < 0; end; Var Source : array of Byte; F : Integer; PtrBuf : Pointer; FileSize : Integer; begin F:= FileOpen('nom du fichier', fmopenread); FileSize:= FileSeek(F, 00, 2); FileSeek(F, 0, 0); SetLength(Source, FileSize+1000); SetLength(AlphaPtr, FileSize+1000); PtrBuf := @Source[0]; FileSize:= FileRead(F, Pointer(PtrBuf^), FileSize); FileClose(F); FillChar(Pointer(AlphaPtr)^, Length(AlphaPtr) - 01, 0); Extract(Source, FileSize); end.

Nouvelle algorithme de compression

3 réponses

Discussions similaires