extreme compression

grinder:workspace zeph$ python try.py
original_size:150516
divisor_size:15052
135464 / 1 120412 / 1 105361 / 1 90309 / 1 75258 / 1 60206 / 1 45155 / 1 30103 / 1 15052 / 1 iterations:9
reconstructing . . . . . . . . . . reconstructed_size:150516

source code: python tryout for compression fibonacci generator [warning! it might damage your pc…🙂 ]

basically… was a lot of time I had to make a demo on this… keeping the result of a division, and the module, we can compress a file infinite times…

    res = src
    while res > pip:
        res = src / pip
        mod = src % pip
        saving.append(mod)
        src = res

every file is a string of ones and zeros, right? so, it is a number

we can recursively apply this algorithm till we reach the size we want

it is extremely time consuming, so, better use it only for log files and ISO images

the target is to use a divisor as much as big as the “number” to divide… this is easy to achieve using a standard math serie like Fibonacci… 1*10^6 number of fibonacci is pretty big… 1*10^9 HUGE!

at the end you only need to keep, this string “1*10^9” (6 digits!) + the number of iterations (1 or 2 digits?) + the last result of the division and the last result of the module

        while True:
            mod = saving.pop()
            back =  back * pip + mod

comments?🙂

in the sample I went down from 150k to 15k … not bad, ah?
(k, I used an array as support datastructure, but the tryout is to show that it is possible)

I already imagine storage of logs of ISPs, with a FPGA implementation of this trick…

7 thoughts on “extreme compression

  1. C’e’ qualcosa che non ho capito.
    L’idea e’ di concepire un file come un numero e di comprimerlo rappresentandolo come divisione intera piu’ un resto di un numero grande quasi quanto l’originale.
    Il problema e’ che se il resto e’ lungo quasi quanto il numero originale non ci si guadagna molto.
    Quindi il problema dell’ algoritmo e’ quello di trovare il giusto divisore per ogni file da comprimere, in modo da minimizzare il resto.
    O forse sto sbagliando qualcosa?

  2. Ovviamente non sta in piedi.
    Usi numeri a precisione arbitraria e on li salvi.
    Chiaramente il resto e` dello stesso ordine di grandezza del divisore.
    Ma a te non serve l’ultimo resto: servono tutti.
    Nell’esempio fatto hai un divisore da 15k-cifre, e il resto e` 15k-cifre.
    Ogni iterazione togli 15k-cifre dal file.
    Ma lo stato rimane in “saving”. Il tuo “saving” e` lungo come quanto manca al file.
    E` facile comprimere e decomprimere nello stesso programma. Ti tieni lo stato nel programma stesso…
    Cosi` ti comprimo anche a zero: “read(file); unlink(file); print(“scomparso”); write(file); print(“rieccolo”);
    So che vali di piu` e ti voglio bene lo stesso. Si vede che non sei ne` un matematico ne` un ingengere, ma i migliori non si laureano (e dopo qualche anno si vede…)

  3. Sorrt for the previous comment. It’s clear you are making fun of your reader, and I just got tricked by it. You are _definitely_ smarter than this…

  4. ciao Ale, a dire il vero il saving e’ di 1 byte per ogni iterazione, hai letto bene il mio proof-of-concept?

    se vuoi ne faccio uno che lavora su file… visto che questo potrebbe non convincere a sufficienza

    che dici?

  5. appena uscito dalla doccia , devo scappare al lavoro…
    pubblico la mail appena mandata a “rubi”
    (@Fabio: spero cio’ risponda anche ai tuoi quesiti):
    +++++++++++++++++++++++++++++++++++++++++++++++++++++++
    devo scappare al lavoro, ma ho le tue risposte

    mi sono espresso male

    concordiamo che:

    un numero diviso per se stesso da 1 e resto 0?

    un numero diviso 1 da risultato se stesso e resto 0?

    un numero diviso per la sua base numerica e’ una stronzata perche’ lo shifti solo a destra e a sinistra?

    un numero diviso un altro numero molto vicino a se stesso, da un risultato tendenzialmente vicino a 1 e un resto che “non sappiamo”, ma che facilmente possiamo ritenere NOTEVOLMENTE inferiore al valore del numero di partenza ?

    ora, tutto casino non e’ per dimostrare la divisione ma…

    se tu applichi come divisore, un numero ottenuto da una serie numerica, puoi mappare su un altro piano di riferimento quel divisore tramite il suo numero di occorrenza nella serie… giusto? e in questo caso puoi mappare blocchi enormi di un numero a stringhe di pochi byte

    il tutto sta nel cercare numeri di serie (ad esempio numeri di fibonacci) tali che il risultato della divisione sia tendente a 1

    piu’ il numero da dividere e’ grosso, piu’ la differenza tra la serie e l’occorrenza nella serie e’ enorme… piu’ sara’ la tua possibilita’ di mappare blocchi ottenuti tramite la divisione a numeri riferenti alla serie decisamente inferiori al numero di partenza

    ora ti e’ chiaro?

    ovvio che per numeri piccoli, come volevi fare tu, sta cosa si perde, proprio perche’ non guadagni gran che con la serie numerica

    cheers,
    G.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s