Quelles sont les bonnes stratégies pour déterminer la taille de bloc dans un algorithme de dégonflage?

Question

J'écris une bibliothèque de compression sous la forme d'un petit projet parallèle, et j'en suis assez loin (ma bibliothèque peut extraire n'importe quel fichier gzip standard, ainsi que produire une sortie gzip conforme (mais pas encore optimale)). le temps de comprendre une stratégie significative de terminaison de bloc. Actuellement, je viens de couper les blocs après chaque entrée de 32 000 (taille de la fenêtre LZ77) car elle était pratique et rapide à mettre en œuvre. Maintenant, je vais essayer d’améliorer réellement l’efficacité de la compression.

La spécification Deflate a seulement ceci à dire: & "Le compresseur termine un bloc lorsqu'il détermine qu'il serait utile de commencer un nouveau bloc avec de nouvelles arborescences, ou lorsque la taille du bloc remplit la mémoire tampon du compresseur &"; ce qui n'est pas très utile.

J'ai trié le code SharpZipLib (comme je l'avais imaginé, ce serait l'implémentation open source le plus lisible) et constaté qu'il terminait un bloc tous les 16 000 littéraux de sortie, en ignorant l'entrée. Ceci est assez facile à mettre en œuvre, mais il semble qu'il faille une approche plus ciblée, en particulier étant donné le langage utilisé dans la spécification & "; Détermine que le démarrage d'un nouveau bloc avec des arbres frais serait utile &";. / p>

Quelqu'un a-t-il des idées de nouvelles stratégies ou des exemples de stratégies existantes?

Merci d'avance!

Answer 1

À titre de suggestion pour vous lancer.

Un regard spéculatif sur l'avenir avec un tampon de taille suffisante pour que l'indication d'une compression supérieure vaille la peine d'être modifiée.

Ceci modifie le comportement de transmission en continu (plus de données doivent être entrées avant que la sortie ne se produise) et complique considérablement les opérations telles que le vidage. C'est également une charge supplémentaire considérable dans les enjeux de la compression.

Dans l’ensemble, il serait possible de s’assurer que cela produirait la sortie optimale simplement en créant des branches à chaque point où il est possible de commencer un nouveau bloc, les deux branches étant récursives si nécessaire jusqu’à ce que toutes les routes soient empruntées. Le chemin qui a eu le comportement de nid gagne. Cela n’est probablement pas faisable avec des tailles d’entrée non négligeables, car le choix du moment pour commencer un nouveau bloc est tellement ouvert.

Le simple fait de le limiter à un minimum de 8 000 littéraux de sortie tout en empêchant plus de 32 000 littéraux dans un bloc constituerait une base relativement souple pour l’essai d’algorithmes spéculatifs. appeler 8K un sous-bloc.

Le plus simple serait (pseudo-code):

create empty sub block called definite
create empty sub block called specChange
create empty sub block called specKeep
target = definite
While (incomingData)
{
  compress data into target(s)    
  if (definite.length % SUB_BLOCK_SIZ) == 0)
  {
    if (targets is definite)
    {
      targets becomes 
        specChange assuming new block 
        specKeep assuming same block as definite
    }        
    else
    {
      if (compression specChange - OVERHEAD better than specKeep)
      {
        flush definite as a block.
        definite = specChange
        specKeep,specChange = empty
        // target remains specKeep,specChange as before 
        but update the meta data associated with specChange to be fresh
      }
      else 
      {
        definite += specKeep
        specKeep,specChange = empty
        // again update the block meta data
        if (definite is MAX_BLOCK_SIZE)
        {
          flush definite
          target becomes definite 
        }
      }
    }
  }
}
take best of specChange/specKeep if non empty and append to definite
flush definite.

OVERHEAD est une constante pour prendre en compte le coût de la commutation de blocs

Ceci est approximatif et pourrait probablement être amélioré, mais constitue un début d'analyse, pour rien d'autre. Instrumentez le code pour obtenir des informations sur les causes d'un commutateur. Utilisez-le pour déterminer si une modification heuristique peut être bénéfique (le taux de compression a peut-être chuté de manière significative).

Cela pourrait conduire à la construction de specChange uniquement lorsque l'heuristique le jugerait raisonnable. Si l'heuristique s'avère être un indicateur fort, vous pouvez alors vous passer de la nature spéculative et simplement décider d'échanger votre point de vue, peu importe les circonstances.

Answer 2

Hmm, j'aime bien l'idée d'une analyse heuristique pour essayer de trouver des & règles " pour quand finir le bloc pourrait être bénéfique. Je vais examiner votre approche suggérée ce soir et voir ce que je pourrais en faire.

Entre-temps, il m'est apparu que pour pouvoir prendre une décision éclairée sur la question, il me fallait une meilleure image mentale des avantages et des inconvénients des décisions relatives à la taille d'un bloc. Très rapidement, j'ai compris que des blocs plus petits vous permettaient d'avoir un alphabet de symboles potentiellement mieux ciblé, au prix d'une surcharge de temps liée à la définition plus fréquente d'arbres. Les blocs plus grands contrent leur alphabet de symboles plus général avec une efficacité d’échelle (un seul arbre à stocker et décoder pour beaucoup de données codées).

De mémoire, il n’est pas évident de savoir si la distribution relative des codes littéraux par rapport à la longueur, les codes de distance aurait un impact spécifique sur la taille optimale des blocs. Bonne nourriture pour la pensée cependant.