Quante volte può un file di essere compresso?

https://stackoverflow.com/questions/1166385

19-09-2019
|

Domanda

Stavo pensando a compressione, e sembra che ci dovrebbe essere una sorta di limite alla compressione che potrebbe essere applicato ad esso, altrimenti sarebbe un singolo byte.

Quindi la mia domanda è: quante volte posso comprimere un file prima:

Non c'è niente di più piccolo?
Il file viene danneggiato?

Sono questi due punti uguali o diversi?

Da dove viene il punto dei rendimenti decrescenti appaiono?

Come possono questi punti si trovano?

Non sto parlando di qualsiasi algoritmo specifico o file particolare, proprio in generale.

Soluzione

Per la compressione senza perdita di dati, l'unico modo è possibile sapere quante volte si può guadagnare da ricomprimere un file è da provare. Sta andando a dipendere l'algoritmo di compressione e il file che si sta comprimendo.

Due file possono mai comprimere alla stessa uscita, quindi non si può scendere a un byte. Come potrebbe un byte rappresentare tutti i file che si potrebbe decomprimere, da?

La ragione per cui la seconda compressione a volte funziona è che un algoritmo di compressione non può fare onnisciente compressione perfetta. C'è un trade-off tra il lavoro che ha a che fare e il tempo necessario per farlo. Il file è cambiato da tutti i dati ad una combinazione di dati circa i dati e i dati stessi.

Esempio

Prendere run-length encoding (probabilmente il più semplice compressione utile) come esempio.

04 04 04 04 43 43 43 43 51 52 11 byte

Tale serie di byte potrebbe essere compresso come:

[4] 04 [4] 43 [-2] 51 52 7 byte (sto mettendo i metadati tra parentesi)

Se il numero positivo tra parentesi è un numero di ripetizioni e il numero negativo tra parentesi è un comando per emettere i prossimi personaggi -n come si trovano.

In questo caso potremmo provare ancora una compressione:

[3] 04 [-4] 43 fe 51 52 7 byte (Fe è la tua -2 visti come due di dati complemento)

Abbiamo guadagnato nulla, e inizieremo crescente sulla prossima iterazione:

[- 7] 03 04 ao 43 fe 51 52 8 byte

Ci crescere da un byte per l'iterazione per un po ', ma sarà effettivamente peggiorare. Un byte può contenere solo numeri negativi a -128. Si comincerà in crescita di due byte quando il file sorpassa 128 byte di lunghezza. La crescita otterrà ancora peggio, come il file diventa più grande.

C'è un vento contrario che soffia contro il programma di compressione - i meta-dati. E anche, per reali compressori, l'intestazione appiccicato al all'inizio del file. Ciò significa che alla fine il file inizierà a crescere con ogni compressione aggiuntiva.

RLE è un punto di partenza. Se volete saperne di più, guarda LZ77 (che guarda indietro nel file per trovare i modelli) e LZ78 (che costruisce un dizionario). Compressori come zip spesso cercano più algoritmi e utilizzare la migliore.

Qui ci sono alcuni casi mi vengono in mente in cui la compressione multipla ha funzionato.

ho lavorato presso una rivista Amiga fornito con un disco. Naturalmente, abbiamo preparato il disco alle branchie. Uno degli strumenti che abbiamo usato consentono di confezionare un file eseguibile in modo che quando è stato eseguito, decompresso e si mise a correre. Poiché l'algoritmo di decompressione doveva essere in ogni eseguibile, doveva essere piccolo e semplice. Spesso ottenuto guadagni aggiuntivi comprimendo due volte. La decompressione è stato fatto in RAM. Dal momento che la lettura di un floppy era lento, abbiamo spesso avuto un aumento di velocità, come pure!
Microsoft supportato compressione RLE sui file bmp. Inoltre, molti word processor fatto codifica RLE. file RLE sono quasi sempre in modo significativo comprimibile da un compressore migliore.
Un sacco di giochi ho lavorato usato un piccolo, decompressore LZ77 veloce. Se si comprime un grande rettangolo di pixel (soprattutto se si ha un sacco di colore di sfondo, o se si tratta di un'animazione), è possibile comprimere molto spesso due volte con buoni risultati. (Il motivo? Hai solo tante bit per specificare la distanza lookback e la lunghezza, quindi un unico grande modello ripetuto è codificato in diversi pezzi, e quei pezzi sono altamente comprimibile.)

Altri suggerimenti

In genere il limite è una compressione. Alcuni algoritmi risultati in un rapporto di compressione più elevato, e utilizzando un algoritmo povero seguita da un buon algoritmo spesso provocare miglioramenti. Ma usando il buon algoritmo, in primo luogo è la cosa giusta da fare.

C'è un limite teorico per quanto un dato insieme di dati può essere compresso. Per saperne di più su questo si dovrà studiare teoria dell'informazione .

In generale, per maggior parte degli algoritmi, comprimendo più di una volta non è utile. C'è un caso particolare però.

Se si dispone di un gran numero di file duplicati, il formato zip zip verrà ciascuno indipendentemente, e si può quindi comprimere il primo file zip per rimuovere le informazioni zip duplicato. In particolare, per 7 file di Excel identici dimensione di 108KB, li zippare con risultati 7-zip in un archivio 120KB. Zippare di nuovo si traduce in un archivio 18kb. Andando passato che si ottiene rendimenti decrescenti.

Supponiamo di avere un file di N bit lunga, e noi vogliamo comprimere senza perdita di qualità, in modo da poter recuperare il file originale. Ci sono 2 ^ n possibili file N bit a lungo, e quindi il nostro algoritmo di compressione deve cambiare uno di questi file in uno dei 2 ^ N possibili altri. Tuttavia, non possiamo esprimere 2 ^ N file diversi in meno di N bit.

Quindi, se siamo in grado di prendere alcuni file e comprimerli, dobbiamo avere alcuni file che la lunghezza in compressione, per bilanciare quelle che accorciano.

Ciò significa che un algoritmo di compressione in grado di comprimere solo determinati file, e in realtà ha per allungare un po '. Ciò significa che, in media, la compressione di un file casuale non può accorciare, ma potrebbe allungarla.

algoritmi di compressione pratiche funzionano perché di solito non usiamo i file casuali. La maggior parte dei file che usiamo avere una sorta di struttura o altre proprietà, se sono eseguibili di testo o di programma o immagini significative. Utilizzando un algoritmo di compressione buona, siamo in grado di ridurre drasticamente i file dei tipi normalmente usiamo.

Tuttavia, il file compresso, non è uno di quei tipi. Se l'algoritmo di compressione è buona, la maggior parte della struttura e la ridondanza sono stati spremuto fuori, e quello che è rimasto assomiglia molto casualità.

No algoritmo di compressione, come abbiamo visto, in grado di comprimere in modo efficace un file casuale, e che si applica a un file casuale dall'aspetto anche. Pertanto, cercando di ri-comprimere un file compresso non sarà accorciare in modo significativo, e potrebbe anche allungare un po '.

Quindi, il numero normale di volte che un algoritmo di compressione può essere eseguito con profitto è uno.

La corruzione si verifica solo quando si parla di compressione lossy. Ad esempio, non si può necessariamente recuperare un'immagine con precisione da un file JPEG. Ciò significa che un compressore JPEG può accorciare in modo affidabile un file di immagine, ma solo a costo di non essere in grado di recuperare esattamente. Noi siamo spesso disposti a fare questo per le immagini, ma non per il testo e file particolare non eseguibili.

In questo caso, non c'è stadio in cui ha inizio la corruzione. Si inizia quando si inizia a comprimerlo, e peggiora come si comprime più. È per questo che i buoni programmi di elaborazione delle immagini consentono di specificare la quantità di compressione che si vuole quando si effettua una JPEG: in modo da poter bilanciare qualità dell'immagine contro dimensione del file. A trovare il punto di arresto considerando il costo delle dimensioni del file (che è più importante per connessioni di rete di stoccaggio, in generale) rispetto al costo di una ridotta qualità. Non esiste una risposta ovvia a destra.

Di solito la compressione di una volta è abbastanza buono se l'algoritmo è buono.
_{Infatti, comprimendo più volte potrebbe portare ad un aumento delle dimensioni}

I tuoi due punti sono diversi.

Compression fatto ripetutamente e raggiungere alcun miglioramento nella riduzione della dimensione
è una condizione teorico previsto
compressione ripetuta corruzione causando
è probabile che sia un errore nella realizzazione (o forse lo stesso algoritmo)

Vediamo ora alcune eccezioni o variazioni,

Codifica può essere applicato più volte , senza riduzione delle dimensioni
(Infatti a volte aumentare di dimensioni) al fine di una maggiore sicurezza
file audio Immagine, video o
sempre più compressa perderà dati (effettivamente essere 'corrotti' in un certo senso)

È possibile comprimere un file tutte le volte che vuoi. Ma per la maggior parte algoritmi di compressione la compressione risultante dalla seconda volta in poi sarà trascurabile.

Compression (sto pensando lossless) sostanzialmente significa che esprime qualcosa di più conciso. Ad esempio

111111111111111

potrebbe essere più consisely espresso come

15 X '1'

Questa è chiamata codifica run-length. Un altro metodo che un computer può utilizzare è quello di trovare un modello che viene regolarmente ripetuto in un file.

Esiste chiaramente un limite a quanto possono essere utilizzate queste tecniche, ad esempio run-length encoding non sarà effetto

15 X '1'

dal momento che non ci sono motivi ripetuti. Analogamente, se i metodi di sostituzione modello converte modelli lunghi di 3 quelli char, riapplicare avrà scarso effetto, poiché i modelli ripetuti solo rimanenti saranno 3-lunghezza o più corta. In generale l'applicazione di compressione per un file già compressi lo rende leggermente più grande, a causa di varie spese generali. L'applicazione di una buona compressione di un file mal compresso è di solito meno efficace di applicare solo la buona compressione.

Quante volte posso comprimere un file prima che non c'è niente di più piccolo?

In generale, nemmeno un . Qualunque sia algoritmo di compressione utilizzato, ci deve sempre esiste un file che non viene affatto compressa, altrimenti si potrebbe sempre comprimere più volte fino a raggiungere 1 byte, dal vostro stesso argomento .

Quante volte posso comprimere un file prima che diventi corrotto?

Se il programma che si utilizza per comprimere il file fa il suo lavoro, il file non sarà mai corrotto (naturalmente sto pensando di senza perdita di dati di compressione).

È possibile comprimere infinite volte. Tuttavia, la seconda e ulteriori compressioni solito produrranno solo un file più grande di quello precedente. Quindi non v'è alcun punto in compressione più di una volta.

Ecco l'algoritmo di compressione massimo (in Python) che per uso ripetuto comprimere qualsiasi stringa di cifre a dimensioni 0 (è lasciato come esercizio al lettore come applicare questo per una stringa di byte).


def compress(digitString):
    if digitString=="":
        raise "already as small as possible"
    currentLen=len(digitString)
    if digitString=="0"*currentLen:
        return "9"*(currentLen-1)
    n=str(long(digitString)-1); #convert to number and decrement
    newLen=len(n);
    return ("0"*(currentLen-newLen))+n; # add zeros to keep same length

#test it
x="12";
while not x=="":
    print x;
    x=compress(x)

Il programma stampa 10 09 12 11 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0 stringa quindi vuota. Non comprime la stringa ad ogni passaggio ma sarà sufficiente con passaggi comprimere qualsiasi stringa di cifre fino a una stringa di lunghezza zero. Assicurati di annotare quante volte lo si invia attraverso il compressore altrimenti non sarà in grado di tornare indietro.

E 'una domanda molto buona. È possibile visualizzare in un file da diversi punti di vista. Forse si sa a priori che questo file contiene serie aritmetica. Lascia la fine di esso come flusso di dati di "byte", "simboli", o "campioni".

Alcune risposte possono dare a voi "teoria dell'informazione" e "statistiche matematiche" Si prega di verificare monografia di quei ricercatori per comprendere a pieno profonda:

Uno dei concetto principale nella teoria dell'informazione è entropia . Se si dispone di un flusso di "byte" .... L'entropia di quel byte non dipendere da valori della vostra "byte", o "campioni" ... Se è stato definito solo dalle frequenze con cui i byte retrive valori diversi. Massima entropia deve essere posto per la piena flusso di dati casuali. entropia minima, che pari a zero, deve essere posto per il caso in cui il vostro "byte" ha un valore identico.

Non c'è niente di più piccolo?

Quindi l'entropia è il numero minimo di bit per il vostro "byte", che è necessario utilizzare quando si scrive le informazioni sul disco. Naturalmente è quindi se si utilizza l'algoritmo di Dio. La vita reale compressione senza perdita algoritmi euristici non sono così.

Il file viene danneggiato?

Non capisco il senso della questione. È possibile scrivere nessun bit al disco e si scriverà un file danneggiato sul disco con dimensioni pari a 0 bit. Naturalmente è danneggiato, ma la sua dimensione è zero bit.

Esempio di una tecnica più avanzata compressione utilizzando una "doppia tabella o matrice croce" elimiates anche i simboli unnessacry extrenous in algoritmo

[ESEMPIO PRECEDENTE] Prendere run-length encoding (probabilmente il più semplice compressione utile) come esempio.

04 04 04 04 43 43 43 43 51 52 11 byte

Tale serie di byte potrebbe essere compresso come:

[4] 04 [4] 43 [-2] 51 52 7 byte (sto mettendo i metadati tra parentesi)

[si trasforma in] 04.43.51.52 VALORI . 4.4 ** - 2 COMPRESSIONE

ulteriore compressione con simboli Additonal come valori sostitutivi

Valori 04.A.B.C . 4.4 ** - 2 COMPRESSIONE

In teoria, non lo sapremo mai, è una cosa senza fine:

In informatica e matematica, il termine piena teorema occupazione è stato utilizzato per riferirsi a un teorema che mostra che nessun algoritmo può eseguire in modo ottimale un determinato compito fatto da qualche classe di professionisti. Il nome deriva dal fatto che tale teorema garantisce che v'è la possibilità infinita di tenere scoperta di nuove tecniche per migliorare la il modo in cui almeno un po 'compito specifico è fatto. Ad esempio, il pieno Teorema di lavoro per gli scrittori del compilatore afferma che non esiste cosa come un perfetto dimostrabilmente compilatore size-ottimizzazione, come tale prova per il compilatore avrebbe dovuto rilevare calcoli non fatale e ridurli ad una sola istruzione ciclo infinito. In tal modo, l'esistenza di un provably perfetta compilatore size-ottimizzazione implicherebbe una soluzione a il problema della terminazione, che non può esistere , rendendo la prova di per sé un problema indecidibile.

(fonte)

Tutto dipende l'algoritmo. In altre parole, la questione può essere quante volte un file può essere compresso utilizzando questo algoritmo prima, allora questo uno accanto ...

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow