Qual è il modo migliore per comprimere un elenco di stringhe simili ma non identiche?

Question

Dì, ho un numero di stringhe che sono abbastanza simili ma non assolutamente identiche.

Possono differire più o meno, ma la somiglianza può essere vista dall'occhio nudo.

Tutte le lunghezze sono uguali, ognuna è di 256 byte. Il numero totale di stringhe è inferiore a 2 ^ 16.

Quale sarebbe il miglior metodo di compressione per tale caso?

Aggiornamento ( Formato dati ):

Non posso condividere i dati ma posso descriverlo abbastanza vicino alla realtà:

Immagina la notazione (come la lingua del logo) che è la sequenza dei comandi per un dispositivo per spostarsi e disegnare sul piano. Come:

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

.

E così via.

L'intero vocabolario di questa lingua non supera la dimensione dell'alfabeto inglese.

La stringa quindi descrive un'intera immagine: "U12C6P1L74D74R74U74P0 ....".

Immagina ora la classe di diecimila bambini che hanno detto di disegnare un'immagine molto specifica con l'aiuto di questa lingua: come la bandiera del loro paese. Otterremo 10k di stringhe che sono tutte diverse e tutte allo stesso tempo.

Il nostro compito è comprimere l'intero grappolo di stringhe nel modo più buono possibile.

Il mio sospetto Ecco che c'è un modo per sfruttare questa somiglianza e lunghezza comune delle corde, mentre, Huffman E.G. Non usarlo esplicitamente.

Answer 1

Potresti dirci quali sono i dati?Forse come una sequenza di DNA?Come

.

AGCTGTGCGGAGAGAGAGCGGTGGG ...

GGCTGTGCGGAGGGAGAGCGGTGGGGGGGGGGG ...

CGCTGTGAGGAGNGAGAGCGGTGGG ...

NGCTGTGCGGAGAGAGAGCGGTGGG ...

ggctgtgcgagtgagagcggtggg ...

... ...

? Forse o no.Ad ogni modo qui è due livelli o due modi per pensare:

.

1. Huffman Codifica: rif.Wikipedia da solo

2. Stringology: Ref. http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9ndohjxtiyyc

   Penso che sia facile risolvere il tuo problema ma difficile scegliere il modo migliore.È possibile progettare diversi metodi per confrontare usando http://en.wikipedia.org/wiki/data_compressione e più strumenti.

Answer 2

Dal momento che hai una larghezza fissa di 256 byte ed è una potenza di 2 proverei una trasformazione della tana-wheeler o un algoritmo di movimento davanti con quella dimensione o forse il doppio di quella dimensione.Quindi puoi provare un codice Huffman.Forse puoi provare una curva Hilbert su 256 byte e poi un BWT e MFT?

Answer 3

"Il numero totale di stringhe è inferiore a 2 ^ 16."Questo è un numero piccolo e limitato, che rende il tuo lavoro molto facile: perché non tieni una tabella di ricerca (Tabella hash) di tutte le stringhe precedenti in precedenza.È quindi possibile convertire ogni linea di 256 byte in un indice a due byte in questa tabella di ricerca.

Hai quindi una sequenza di numeri interi a 16 bit.Questi numeri interi contiene modelli come "Dopo che la penna è scesa, c'è una probabilità del 90% che il prossimo comando è iniziare a disegnare".Se i dati contiene modelli come questo, PPM è la tua scelta.7-zip ha un'implementazione PPM di alta qualità.Puoi sceglierlo usando la GUI o la linea cmd.