Devo trovare un insieme di simboli gerarchici che possano rappresentare i dati binari di input in uno spazio quasi ottimale. Quali algoritmi posso esaminare? [chiuso]

2

Ho un flusso di dati binari. Non presupporre conoscenze preliminari sul modello previsto nei dati di input.

I simboli possono rappresentare dati binari o altri simboli, quindi gerarchici.

L'output dovrebbe minimizzare lo spazio, ma non deve essere ottimale. Ma l'algoritmo deve essere online - cioè, con più input, la rappresentazione deve adattarsi. L'approssimazione è consentita e molto desiderabile se può essere controllata con alcuni parametri che possono decidere di compromettere l'accuratezza della rappresentazione con il runtime di aggiornamento e l'utilizzo dello spazio.

Esempio: 00011100110011 = > ABCDCDC = > ABEEC

000 = > A

111 = > B

00 = > C

11 = > D

CD = > E

    
posta Quark 15.03.2017 - 23:32
fonte

1 risposta

2

Supponendo che la codifica lossless sia quello che vuoi, questo sembra un buon caso per la codifica di Huffman: link

La codifica di Huffman è un codice di prefisso quasi ottimale. Usa schemi bit più brevi per simboli più comuni, riducendo al minimo la quantità di spazio richiesta. Ovviamente, devi trasmettere l'albero di Huffman separatamente, quindi la codifica di Huffman non comprime sempre i tuoi dati.

Se vuoi ottenere guadagni minori rispetto a ciò che può ottenere la codifica di Huffman, puoi usare il codice aritmetico ( link ) ma Non credo davvero che i guadagni minori valgano la complessità extra.

Per la codifica con perdita, rispondere alla domanda sarebbe praticamente impossibile visto che CandiedOrange ha notato in un commento.

    
risposta data 16.03.2017 - 14:25
fonte

Leggi altre domande sui tag