Quali sono alcune buone strategie per determinare la dimensione del blocco in un algoritmo di deflazione?

Question

Sto scrivendo una libreria di compressione come un piccolo progetto laterale e sono abbastanza avanti (La mia libreria può estrarre qualsiasi file gzip standard, oltre a produrre output gzip conforme (ma certamente non ancora ottimale)) che è tempo di capire una strategia di terminazione del blocco significativa. Attualmente, ho appena tagliato i blocchi dopo ogni 32k di input (dimensione della finestra LZ77) perché era comodo e rapido da implementare - ora torno indietro e sto cercando di migliorare effettivamente l'efficienza di compressione.

Deflate spec ha solo questo da dire al riguardo: " Il compressore termina un blocco quando determina che l'avvio di un nuovo blocco con alberi freschi sarebbe utile o quando la dimensione del blocco riempie il buffer di blocco del compressore " ;, che non è poi così utile.

Ho ordinato il codice SharpZipLib (come immaginavo sarebbe l'implementazione open source più facilmente leggibile) e ho scoperto che termina un blocco ogni 16k letterali di output, ignorando l'input. Questo è abbastanza facile da implementare, ma sembra che ci debba essere un approccio più mirato, specialmente dato il linguaggio nella specifica & Quot; determina che l'avvio di un nuovo blocco con alberi freschi sarebbe utile & Quot;.

Quindi qualcuno ha qualche idea per nuove strategie o esempi di quelli esistenti?

Grazie in anticipo!

Answer 1

Come suggerimento per iniziare.

Uno sguardo speculativo al futuro con un buffer di dimensioni sufficienti affinché l'indicazione di una compressione superiore valga la pena cambiare

Ciò modifica il comportamento dello streaming (è necessario immettere più dati prima che si verifichi l'output) e complica in modo significativo operazioni come flush. È anche un notevole carico aggiuntivo nella posta in gioco.

Nel caso generale sarebbe possibile garantire che ciò abbia prodotto l'output ottimale semplicemente ramificandosi in ciascun punto in cui è possibile avviare un nuovo blocco, facendo ricorrere entrambi i rami se necessario fino a quando non vengono prese tutte le rotte. Vince il percorso che ha avuto il comportamento del nido. Questo non sarà probabilmente fattibile su dimensioni di input non banali poiché la scelta di quando avviare un nuovo blocco è così aperta.

Semplicemente limitandolo a un minimo di 8 K letterali di output ma prevenendo più di 32 K letterali in un blocco si otterrebbe una base relativamente trattabile per provare algoritmi speculativi. chiama 8K un sottoblocco.

Il più semplice dei quali sarebbe (pseudo codice):

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 è una costante per tenere conto del costo del passaggio da un blocco all'altro

Questo è approssimativo e potrebbe probabilmente essere migliorato, ma è un inizio per l'analisi se non altro. Strumentare il codice per informazioni su ciò che provoca un interruttore, utilizzarlo per determinare una buona euristica secondo cui una modifica potrebbe essere utile (forse che il rapporto di compressione è sceso in modo significativo).

Ciò potrebbe portare alla costruzione di specChange solo quando l'euristica lo considera ragionevole. Se l'euristica si rivela essere un indicatore forte, puoi eliminare la natura speculativa e decidere semplicemente di scambiarti in quel punto, non importa quale.

Answer 2

Hmm, mi piace l'idea di alcune analisi euristiche per provare a trovare alcune " regole " perché quando si termina il blocco potrebbe essere utile. Stasera esaminerò il tuo approccio suggerito e vedrò cosa potrei farci.

Nel frattempo, mi viene in mente che per fare una scelta pienamente informata sulla questione, ho bisogno di un quadro mentale migliore dei pro e dei contro delle decisioni sulla dimensione del blocco. Davvero rapidamente capisco che i blocchi più piccoli ti consentono di avere un alfabeto di simboli potenzialmente meglio mirati, a costo di un maggiore sovraccarico derivante dalla definizione degli alberi più spesso. I blocchi più grandi contrastano il loro alfabeto di simboli più generale con efficienza di scala (solo un albero per archiviare e decodificare per molti dati codificati).

Dalla parte superiore della mia testa, non è chiaro se la distribuzione relativa dei codici litterici rispetto alla lunghezza, i codici di distanza avrebbe un impatto specifico sulla dimensione ottimale del blocco. Buon cibo per pensare però.