Teoria: algoritmo di compressione che rende alcuni file più piccoli, ma nessuno più grande?

Question

mi sono imbattuto in questa domanda;

"Un algoritmo di compressione senza perdita di dati pretende di garantire per rendere alcuni file più piccoli e nessun file più grandi.
È questo;

  

a) Impossible

     

b) Possibile, ma può essere eseguito per un importo di tempo indeterminato,

     

c) Eventuale per il fattore di compressione 2 o meno,

     

d) possibile per qualsiasi fattore di compressione? "

Sono sporgendosi verso (a), ma non sono riuscito a dare una spiegazione solida del perché. (Ti elenco i pensieri un amico e mi si avvicinò con come una possibile risposta)

Answer 1

Per il principio piccione buche, data una stringa di 10 bit si ha 1024 ingressi possibili, e necessario mappare a 9 bit o meno, quindi non ci sono <1024 uscite.

Questo garantisce sia l'algoritmo ha collisioni (lossy) o ad un certo punto choses per restituire l'ingresso non modificato come uscita.

In quest'ultimo caso, non è possibile determinare come decomprimere una stringa di bit arbitraria. (Potrebbe essere un ingresso non modificato o un'uscita compresso da una stringa di bit più grande).

-> Impossibile.

Answer 2

Basta un leggero chiarimento del post di RJFalconer ...

Devi solo avere alcuni file di diventare più piccolo, in modo l'affermazione che una stringa di 10 bit deve mappare a 9 bit o meno non è giusto. In particolare, se qualcuno ha proposto un tale meccanismo di compressione è potrebbe mappa tutte le stringhe di 10 bit o meno esattamente la stessa uscita (cioè una trasformazione di identità).

Tuttavia, ci viene detto che non v'è almeno un file che non diventano più piccoli. Senza perdita di generalità, si consideri che iniziare con x bit e finire come y bit, dove y è strettamente minore di x.

Ora consideriamo il dominio dei "file con bit Y o meno", che dispone di 2 ^{y + 1 stringhe} -1 bit (compreso il vuoto). Affinché nessuno di quelli di provocare un file più grande, ognuno ha per mappare una stringa di bit nello stesso dominio, vale a dire 2 ^{y + 1} -1 file compressi. Tuttavia, sappiamo già che la stringa iniziale di x bit di lunghezza comprime ad uno di questi valori -. Lasciando solo 2 ^{y + 1 valori} -2 possibili

Al questo puntare il principio dei cassetti è disponibile in - chiaramente non si può mappare 2 ^{y + 1} -1 ingressi a 2 ^{y + 1} -2 uscite senza ripetere un'uscita, che viola la reversibilità di compressione.

Answer 3

a) impossibile

Se si dispone di un file che non può essere compresso ulteriormente, si devono ancora aggiungere le informazioni se è stato compresso o no, quindi in questo caso il file dovrebbe crescere.

Answer 4

So che Sono un po 'in ritardo, ma ho trovato questo tramite Google e qualcun altro potrebbe fare lo stesso, quindi mi inviare la mia risposta: la soluzione più ovvia è a) impossible, così ha sottolineato da Jon Skeet (e btw ci sono un sacco di prove tutti su Internet). Non sto mettendo in dubbio l'impossibilità di comprimere i dati casuali, tanto per essere chiari fin dall'inizio; Ho capito la teoria che sta dietro di esso, e -se si chiede me- mi fido la matematica. : D

Ma, se c'è permesso a pensare lateralmente , potremmo assolutamente approfittare del fatto che la questione non è ben definita, il che significa che non dà una definizione rigorosa di "algoritmo di compressione" e delle proprietà che dovrebbe avere (ma per ridurre alcuni file senza espansione chiunque altro) .

Inoltre, non mette alcuna condizione sui file da comprimere, l'unica cosa che gli interessa è "per fare alcuni file più piccoli e nessun file più grandi" .

Detto questo, abbiamo subito almeno due modi per mostrare che, di fatto, non esiste un tale algoritmo:

1. Possiamo sfruttare il nome del file per memorizzare alcune delle informazioni del file (o addirittura l'intero file, se il file system permette, riducendo così ogni file a 0 bit). Banalmente, si potrebbe semplicemente decidere lasciare intatta ogni file, ma uno, riducendolo a 0 bit e rinominare con un nome predefinito. Sono d'accordo che questo potrebbe essere considerato barare, ma poi di nuovo, non ci sono restrizioni nella domanda iniziale e questo algoritmo potrebbe effettivamente raggiungere lo scopo (a patto che non si rinomina il file, è per questo che questa sarebbe una scelta di design molto povero oltre essendo inutile).

2. Possiamo limitare il numero di file da comprimere, ad esempio, a quelle lunghe almeno bit X. Ancora una volta, una soluzione banale sarebbe quella di lasciare ogni file intatti, ma uno, che possiamo ridurre facendola corrispondere a un file più piccolo di bit X. Ora facciamo avere un algoritmo che, citando testualmente, rende alcuni file più piccoli e nessun file più grandi; tuttavia, esegue una restrizione tutte le sue possibili ingressi (cioè esso non può elaborare tutti i file).

A coloro che sostengono che questo non avrebbe alcuna utilità pratica, io dico che sono d'accordo con te ... ma hey, questa è la teoria, e questo era solo una dissertazione teorica. ;)

Ovviamente, se dovessi fare un test e affrontare questa domanda, avevo messo una X in grassetto sul a), e poi basta andare avanti senza pensare troppo su di esso.

Tuttavia, è perfettamente possibile dimostrare che, dal momento che il linguaggio naturale è intrinsecamente ambigua e la questione non è formalmente espresso, ciascuna delle altre possibili risposte non è necessariamente sbagliato: ponendo le giuste condizioni ed eventualmente specificare con maggiore chiarezza cosa si intende da certi concetti, potremmo legalmente in grado di soddisfare l'obiettivo di una qualsiasi delle altre opzioni elencate, facendo una sorta di inganno e costringendo il programma per ottenere il comportamento desiderato.

Answer 5

  

e) Eventuale

... con alcune restrizioni.

Recentemente ho incontrato Shoco , una libreria di compressione stringa per stringhe di piccole dimensioni. Mi sono ricordato di questa domanda durante la lettura di questa affermazione:

  

... il più notevole proprietà di shoco è che la dimensione compressa non potrà mai superare la dimensione della stringa di input, a condizione che sia ASCII.

     

Se si è certi che i dati di input è ASCII, il buffer per solo bisogno di essere grande come la stringa di input

http: //ed-von-schleck.github. io / shoco / # how-da-opere

Answer 6

possibile

to make some files smaller and no files larger

se detto algoritmo di compressione rende il file più grande, basta che restituire il file originale.