L'algoritmo di compressione perfetta
Una storia dai tempi del college.
Mi hanno fatto irruzione in pieno con entusiasmo alla stanza di due miei amici. Avevo trovato l'algoritmo di compressione perfetto.
"Ho trovato un algoritmo di compressione che può ridurre la dimensione di qualsiasi file!"
"Questo è impossibile. Qual è il tuo algoritmo? "
"Non posso condividere l'algoritmo di adesso, ma ti dirò una volta che scrivo un programma per comprimere i file".
"Non sai che è impossibile scrivere un algoritmo per comprimere tutti i file?"
"Sì, ma ... ora ho questo algoritmo!"
Così che cosa è stato il mio algoritmo?
1. Consideriamo il testo da comprimere come un numero di grandi dimensioni.
2. Trova la radice quadrata intera del numero.
3. La radice quadrata e la forma di errore del testo compresso.
Per esempio, cerchiamo di comprimere il numero 98653784578.
Integer radice quadrata di 314.092 = 98653784578
Errore = 114 (cioè 98653784578-314.092 2)
314.092 e 114 formano il testo compresso. Abbiamo appena salvato 2 personaggi usando il nostro algoritmo!
Se il numero originale è di lunghezza n, allora la radice quadrata e l'errore sarà di lunghezza massima n / 2 ciascuno. Quindi questo significa che il testo compresso finale sarà di una lunghezza n massimo e forse anche più piccoli.
Riesci a trovare il difetto nella logica?
Sembra che non ero l'unico che ha inventato un algoritmo di compressione perfetta. Almeno non ho speso 12 anni per capire che la compressione perfetta non è possibile e non mi sono umiliato pubblicamente (e non fino a questo post, ma chi sta leggendo questo comunque 
). Ci sono diverse prove di compressione perfetto perché non può essere raggiunto.
Penso che si dovrà affrontare il seguente problema con questa logica. Per distinguere tra le diverse coppie integrante di errore, è possibile seguire due approcci.
1. È possibile inserire un separatore tra la parte integrale e l'errore. Inoltre è necessario un separatore tra due coppie diverse. Ora il problema è che il separatore deve essere unico e non deve essere confuso come parte del parte integrante o l'errore. Per questo il separatore deve avere una larghezza minima di n / 2 +1.
2. È possibile impostare una larghezza fissa per entrambi parte integrante e di errore. In tal caso, entrambe integrante ed errore richiede una lunghezza minima di n / 2.
Io pensavo allo stesso modo. Invece stavo pensando alla combinazione di memorizzare il numero di sequenza (che sarà superiore al numero stesso, se il numero è maggiore di 21). Infine mio fratello mi ha aiutato a capire il concetto. Se avete bisogno di memorizzare 1 bit di informazione, è necessario 1 bit. Non c'è altro modo.
mi corregga se sbaglio, ma a me il difetto sembra essere in questa dichiarazione:
"Se il numero originale è di lunghezza n, allora la radice quadrata e l'errore sarà la lunghezza massima di n / 2 ciascuno"
per i numeri dove n è dispari, la lunghezza massima di radice quadrata e di errore sono (n +1) / 2. Lo stesso algoritmo del numero 10.200:
int_sqrt (10.200) = 100
errore = 10.200 - 100 ^ 2 = 200
I nostri numeri risultanti sono sei cifre insieme, uno più lungo rispetto al numero originario.
1. Qualche lunghezza n / 2 non è né corretto né per l'utente root di errore. Si consideri il numero 7, ha bisogno di 3 bit per memorizzare. Root è 2, bisogno di 2 bit per memorizzare. Errore è di 3 bisogno di un altro 2 bit. Totale di 4 bit.
2. seconda sfida è dove memorizzare la lunghezza della radice e l'errore.
Questo non funziona per tutti gli ingressi. Non è possibile comprimere ingresso singolo bit.
Beh, non in piazza ma penso che ci sia un modo per salvare alcuni bit se si sapesse qualche informazione additionaly logico.
ad esempio in singola precisione in virgola mobile significando (mantissa) è 23-bit-bit, ma la precisione è di 24 bit, perché si sa che il significando iniziano sempre con 1. Quello è il modo in cui dovrebbe andare.
Abbiamo bisogno di informazioni logiche che non devono essere scritte, dovremmo sapere in anticipo. Io in realtà non so come, deve essere inventato, ma l'ho immagine in quel modo -> comprimere un file nel miglior modo possibile, di invertire ogni secondo byte e comprimere nuovamente. Quindi non abbiamo bisogno di salvare le informazioni circa byte-inversione, dobbiamo solo lo sa.
(Invertendo i byte è facile, avrei voluto conosceva la strada a destra)
Penso che ciò che devi fare è usare la teoria delle stringhe per comprimere i dati in un'altra dimensione. Dal momento che i dati vengono compressi in un'altra dimensione e non esiste nella tua dimensione il suo zero byte ... ma c'è un problema ... come si fa a recuperare i dati quando ne avete bisogno? Hai bisogno di memorizzare qualcosa su cui è stato immagazzinato e quale dimensione.
Quindi, quello che fai è riporlo una dimensione più nello stesso posto dentro il disco stesso. Poi si può sempre recuperare. Il problema è che inevitabilmente qualche altra dimensione si tenta di utilizzare il vostro HD per memorizzare qualche tipo di informazioni inutili su di esso. Pertanto è necessario assicurarsi che la HD è adeguatamente schermato da inter-dimensionale-data-dirottamento.
Ci si va ... compressione zero byte. Così semplice.
hohums, vedo che hai guardato troppo a lungo il film come matrice o-one.
Ma ho una notizia per voi, la terra è un globo!
Chi ha preso 12 anni per capirlo? Non sono sicuro se quella persona stava lavorando la stessa dimensione.
Penso che come Ali ha detto, si può avere guardato troppo matrix o roba fiction scienza. Forse questa è la svolta, ma non ho ancora la conferma che si tratta. Neat concetto però.