trovare le definizioni di token ottimali per la compressione

Question

trovare le definizioni di token ottimali per la compressione

#1 da (2 voti)
#2 da (0 voti)

5

Ho una collezione di stringhe che hanno molte sottostringhe comuni, e sto cercando di trovare un buon modo per definire i token per comprimerli.

Ad esempio, se le mie stringhe sono:

s1 = "String"
s2 = "Bool"
s3 = "String -> Bool"
s4 = "String -> String"
s5 = "(String -> String) -> String -> [Bool]"

quindi potrei voler usare i token:

$1 = "String"
$2 = "Bool"
$3 = "$1 -> $1"

in modo che le stringhe possano essere definite come:

s1 = "$1"
s2 = "$2"
s3 = "$1 -> $2"
s4 = "$3"
s5 = "($3) -> $1 -> [$2]"

(In effetti, ora è chiaro che la definizione $4 = " -> " potrebbe essere buona da aggiungere.)

Sto cercando un modo buono (forse il migliore?) per scegliere il definizioni di token. Sono interessato a ridurre al minimo la lunghezza totale delle definizioni token + le definizioni stringa risultanti.

Qualche idea?

Aggiorna

È un po 'correlato a questa domanda SO: codifica Huffman con simboli di lunghezza variabile

algorithms strings compression huffman-encoding

posta ErikR 26.05.2016 - 16:39

fonte

2 risposte

Leggi altre domande sui tag algorithms strings compression huffman-encoding

Come progettare un modello di repository in grado di gestire il caricamento dei dati relazionali caso per uso? Come strutturare la logica del livello aziendale (app con logica del livello aziendale molto complessa, calcoli, ecc.)

score 2 · Answer 1

Il termine generico per ciò che stai cercando di fare è compressione basata sulla grammatica . In particolare, sembra che tu stia cercando di risolvere il problema grammaticale più piccolo .

Vedi per es. Charikar, Lehman, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, Shelat (2005). Il più piccolo problema di grammatica . Transazioni IEEE sulla teoria dell'informazione 51 (7): 2554-2576

score 0 · Answer 2

Lempel-Ziv stile compressione fa il tipo di cosa che sei cercando.

Per la tua applicazione, sembra che tu voglia un "dizionario di stringhe" fisso (la rappresentazione interna di LZ delle definizioni di token), piuttosto che quella dinamica utilizzata dai programmi di compressione standard di streaming come gzip o compress . Lo schema generale di Lempel-Ziv è facilmente adattabile a questo tipo di cose.

Se non altro, tieni presente che le tecniche in stile Lempel-Ziv possono naturalmente aiutare a comprimere i dati di definizione del token stesso.