Ho scritto i 500 byte e funziona perfettamente, bisognerebbe inventare una libreria per zippare le innumerevoli parole lunghe e ripetute codificandole in qualche modo, si potrebbe risparmiare un 25-30% di mem
Se parliamo di parole ripetute spesso, puoi già farlo con una semplice tabella di sostituzione.
Ad esempio, se nei messaggi o nel testo che devi memorizzare compaiono spesso parole come "errore", "riprova", "inserisci", "dati", "lettura", ecc... puoi crearti un array in cui metti questi termini e da cui richiami con un semplice indice.
Ad esempio. Mettiamo che hai la stringa "errore dati. riprova", e che hai un array contenente nelle prime 4 celle:
errore
dati
riprova
inserisci
basta stamapare (o inviare) termini[0]+termini[1]+termini[2]. Se poi devi scrivere "inserisci dati", basta inviare termini[3]+termini[1].
Se però parliamo di un vero e proprio algoritmo di compressione, la vedo dura sfruttare questo sistema per salvare i dati in pochi kB di dati, come ha detto Uwe le tabelle per decomprimere i dati porterebbero anch'esse via dello spazio per cui alla fine il guadagno dello spazio recuperato sarebbe pareggiato dal costo per il setup iniziale.
Piuttosto se i dati non sono moltissimi puoi usare direttamente la Flash con PROGMEM oppure, soluzione alternativa e forse più economica, una comune SD che è proprio la soluzione adottata dallo shield Ethernet: le schede SD altro non sono che Flash di grosse dimensioni formattabili con un filesystem di modo che è possibile salvare un file direttamente.