Compressão de dados

Question

Eu tenho uma tarefa para comprimir a dados do mercado de ações de alguma forma ... os dados estão em um arquivo onde o valor das ações para cada dia é dado em uma linha e assim por diante ... por isso é realmente um grande arquivo.

Por exemplo,
123.45
234.75
345.678
889.56
.....

Agora, a questão é como comprimir os dados (aka reduzir a redundância) usando algoritmos padrão como Huffman ou aritmética de codificação ou LZ codificação ... que a codificação é mais preferível para este tipo de dados ?? ...

Tenho notado que se eu tomar os primeiros dados e, em seguida, considerar a diferença entre cada um dos dados consecutivos, há muita repetição nos valores de diferença ... isso me faz pensar se primeiro tomar essas diferenças, encontrar a sua frequência e, portanto, probalility e em seguida, usando codificação seria uma maneira ?? ...

Huffman

estou certo? ... Alguém pode me dar algumas sugestões.

Answer 1

Eu acho que o problema é mais complexo do que simplesmente subtraindo os preços das ações. Você também precisa armazenar a data (a menos que você tem um período de tempo consistente que pode ser inferida a partir do nome do arquivo).

A quantidade de dados não é muito grande, no entanto. Mesmo se você tiver dados a cada segundo para cada dia para cada ano durante os últimos 30 anos para 300 stockd, você ainda pode gerenciar para armazenar tudo isso em um computador superior fim casa (digamos, um MAC Pro), como Isso equivale a 5TB UNCOMPRESSED .

Eu escrevi um script rápido e sujo que irá perseguir o estoque IBM no Yahoo para todos os dias, e armazená-lo "normalmente" (apenas o próximo ajustado) e usando o "método da diferença" que você menciona, em seguida, compactá-los usando gzip. Você faz obter poupanças: 16K vs 10K. O problema é que eu não armazenar a data, e eu não sei o valor corresponde ao que data, você teria que incluir isso, é claro.

Boa sorte.

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()

Agora, compare o "dados brutos" (raw.dat) versus o "formato comprimido" você propõe (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

Muitas ferramentas de compressão nos dias de hoje usam uma combinação dessas técnicas para dar boas relações em uma variedade de dados. Pode valer a pena começar com algo bastante geral e moderno, como bzip2 que usa Huffman codificação combinado com vários truques que embaralhar os dados de volta para trazer vários tipos de redundância (página contém links para várias implementações mais abaixo).

Answer 3

Executar comprimento codificação poderia ser mais adequado? Confira aqui . Para dar um exemplo extremo simples de como ele funciona, aqui está uma linha de dados em código ASCII ... 30 bytes de comprimento

HHHHHHHHEEEEEEELLLLLLLLOOOOOO

Aplicar RLE a ele e você terá isso em 8 bytes:

9H7E8L6O

• O Nine H
• O Sete E
• Oito L's
• O Six O

Uma redução de cerca de 27% como resultado (taxa de compressão para o exemplo da linha é 8/30)

O que você acha?

Espero que isso ajude, Cumprimentos, Tom.

Answer 4

caculate a diferença de dados consecutivos, e em seguida utilizar Run Length Encoding (RLE) .

E você também precisa converter os dados para número inteiro e, em seguida, caculate a diferença.

Answer 5

o que seria melhor seria uma compressão diferencial adaptativa (i esquecer o nome correto). Onde não só você tomar apenas as diferenças de cada dia, você pode calcular um preditor e realmente fazer a sua diferenciação fora dessa. Tipicamente supera preditores lineares normais.

Se você quiser começar a fantasia que você poderia fazer é adapative cruz, em que o mercado de ações tem em geral a sua própria tendência que a cana ser usado para escolher melhores preditores para a compressão.

Answer 6

Eu sugiro que você quebrar o arquivo principal em um segmentado formato bloqueado então segmentos individuais compressa separadamente; isto deveria resultar em compressão máxima optimizado. No lado do descompressão terá de descomprimir esses segmentos individuais separadamente e depois reconstruir o arquivo de texto original.