Compressione dati

Question

Ho il compito di comprimere i dati di un mercato azionario in qualche modo ... i dati sono in un file in cui il valore di borsa per ogni giorno è dato in una riga e così via ... quindi è un file davvero grande.

Ad esempio,
123,45
234,75
345.678
889.56
.....

ora la domanda è come comprimere i dati (ovvero ridurre la ridondanza) usando algoritmi standard come Huffman o codifica aritmetica o codifica LZ ... quale codifica è preferibile per questo tipo di dati ?? ...

Ho notato che se prendo i primi dati e poi considero la differenza tra ogni dato consecutivo, c'è molta ripetizione nei valori delle differenze ... questo mi fa chiedermi se prima di prendere queste differenze, trovarne la frequenza e quindi la propensione e quindi l'uso della codifica huffman sarebbe un modo ?? ...

Ho ragione? ... qualcuno può darmi qualche suggerimento.

Answer 1

Penso che il tuo problema sia più complesso della semplice sottrazione dei prezzi delle azioni. È inoltre necessario memorizzare la data (a meno che non si abbia un intervallo di tempo coerente che può essere dedotto dal nome del file).

Tuttavia, la quantità di dati non è molto grande. Anche se hai dati ogni secondo per ogni giorno per ogni anno negli ultimi 30 anni per 300 stockd, potresti comunque riuscire a archiviare tutto ciò in un computer domestico di fascia alta (diciamo, un MAC Pro), dato che ammonta a 5 TB NON COMPRESSO .

Ho scritto uno script veloce e sporco che inseguirà lo stock IBM in Yahoo per tutti i giorni e lo memorizzerà "normalmente". (solo la chiusura rettificata) e utilizzando il metodo "differenza" citi, quindi comprimili usando gzip. Ottieni un risparmio: 16K contro 10K. Il problema è che non ho memorizzato la data e non so quale valore corrisponda a quale data, ovviamente dovresti includerla.

Buona fortuna.

import urllib as ul
import binascii as ba

# root URL
url = 'http://ichart.finance.yahoo.com/table.csv?%s'

# dictionary of options appended to URL (encoded)
opt = ul.urlencode({
    's':'IBM',       # Stock symbol or ticker; IBM
    'a':'00',        # Month January; index starts at zero
    'b':'2',         # Day 2
    'c':'1978',      # Year 2009
    'd':'10',        # Month November; index starts at zero
    'e':'30',        # Day 30
    'f':'2009',      # Year 2009
    'g':'d',         # Get daily prices
    'ignore':'.csv', # CSV format
    })

# get the data
data = ul.urlopen(url % opt)

# get only the "Adjusted Close" (last column of every row; the 7th)

close = []

for entry in data:
    close.append(entry.strip().split(',')[6])

# get rid of the first element (it is only the string 'Adj Close') 
close.pop(0)

# write to file
f1 = open('raw.dat','w')
for element in close:
    f1.write(element+'\n')
f1.close()

# simple function to convert string to scaled number
def scale(x):
    return int(float(x)*100)

# apply the previously defined function to the list
close = map(scale,close)

# it is important to store the first element (it is the base scale)
base = close[0]

# normalize all data (difference from nom)
close = [ close[k+1] - close[k] for k in range(len(close)-1)]

# introduce the base to the data
close.insert(0,base)



# define a simple function to convert the list to a single string
def l2str(list):
    out = ''
    for item in list:
        if item>=0:
            out += '+'+str(item)
        else:
            out += str(item)
    return out

# convert the list to a string
close = l2str(close)

f2 = open('comp.dat','w')
f2.write(close)
f2.close()

Ora confronta i "dati non elaborati" (raw.dat) rispetto al "formato compresso" proponi (comp.dat)

:sandbox jarrieta$ ls -lh
total 152
-rw-r--r--  1 jarrieta  staff    23K Nov 30 09:28 comp.dat
-rw-r--r--  1 jarrieta  staff    47K Nov 30 09:28 raw.dat
-rw-r--r--  1 jarrieta  staff   1.7K Nov 30 09:13 stock.py
:sandbox jarrieta$ gzip --best *.dat
:sandbox jarrieta$ ls -lh
total 64
-rw-r--r--  1 jarrieta  staff    10K Nov 30 09:28 comp.dat.gz
-rw-r--r--  1 jarrieta  staff    16K Nov 30 09:28 raw.dat.gz
-rw-r--r--  1 jarrieta  staff   1.7K Nov 30 09:13 stock.py

Answer 2

Molti strumenti di compressione oggigiorno usano una combinazione di queste tecniche per fornire buoni rapporti su una varietà di dati. Potrebbe valere la pena iniziare con qualcosa di abbastanza generale e moderno come bzip2 che utilizza la codifica Huffman combinata con vari trucchi che rimescolano i dati per far emergere vari tipi di ridondanza (la pagina contiene collegamenti a varie implementazioni più avanti).

Answer 3

La codifica della lunghezza della corsa potrebbe essere adatta? Dai un'occhiata qui . Per dare un esempio estremamente semplice di come funziona, ecco una riga di dati nel codice ascii ... lunga 30 byte

HHHHHHHHEEEEEEELLLLLLLLOOOOOO

Applica RLE ad esso e ottieni questo in 8 byte:

9H7E8L6O

• Nove H
• Sette E
• Otto L
• Sei O

Di conseguenza una riduzione di circa il 27% (il rapporto di compressione per la riga di esempio è 8/30)

Cosa ne pensi?

Spero che questo aiuti, I migliori saluti, Tom.

Answer 4

Calcola la differenza di dati consecutivi, quindi utilizza la codifica lunghezza di esecuzione (RLE) .

E devi anche convertire i dati in numeri interi e quindi calcolare la differenza.

Answer 5

ciò che sarebbe meglio sarebbe una compressione differenziale adattativa (dimentico il nome corretto). Laddove non solo prendi semplicemente le differenze ogni giorno, puoi calcolare un predittore e in realtà fare la tua differenza. Supera in genere i normali predittori lineari.

se vuoi immaginarti che cosa potresti fare è l'adattamento incrociato, in cui il mercato azionario in generale ha la sua tendenza a usare canna per scegliere predittori migliori per la compressione.

Answer 6

Vorrei suggerire di suddividere il file principale in un formato bloccato segmentato, quindi comprimere i singoli segmenti separatamente; questo dovrebbe comportare la massima compressione ottimizzata. Dal lato della decompressione dovrai decomprimere questi singoli segmenti separatamente e quindi ricostruire il file di testo originale.