Compresión de datos

Question

Tengo la tarea de comprimir los datos del mercado de valores de alguna manera ... los datos están en un archivo donde el valor de las acciones para cada día se da en una línea y así sucesivamente ... así que es un archivo realmente grande.

Por ejemplo,
123,45
234,75
345.678
889.56
.....

ahora la pregunta es cómo comprimir los datos (también conocido como reducir la redundancia) utilizando algoritmos estándar como la codificación Huffman o Arithmetic o la codificación LZ ... ¿qué codificación es más preferible para este tipo de datos ?? ...

He notado que si tomo los primeros datos y luego considero la diferencia entre cada dato consecutivo, hay mucha repetición en los valores de diferencia ... esto me hace preguntarme si primero tomo estas diferencias, encuentro su frecuencia y, por lo tanto, la probalidad y luego usar la codificación huffman sería una forma ?? ...

¿Estoy en lo cierto? ... alguien puede darme algunas sugerencias.

Answer 1

Creo que su problema es más complejo que simplemente restar los precios de las acciones. También debe almacenar la fecha (a menos que tenga un período de tiempo constante que se pueda inferir del nombre del archivo).

Sin embargo, la cantidad de datos no es muy grande. Incluso si tiene datos cada segundo por cada día de cada año durante los últimos 30 años para 300 existencias, aún podría lograr almacenar todo eso en una computadora doméstica de gama alta (por ejemplo, un MAC Pro), ya que eso equivale a 5 TB sin comprimir .

Escribí una secuencia de comandos rápida y sucia que perseguirá las acciones de IBM en Yahoo todos los días, y la almacenará "normalmente". (solo el cierre ajustado) y utilizando el " método de diferencia " mencionas, luego comprimiéndolos usando gzip. Obtendrá ahorros: 16K frente a 10K. El problema es que no almacené la fecha, y no sé qué valor corresponde a qué fecha, tendría que incluir esto, por supuesto.

Buena suerte.

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

Ahora compare los "datos brutos" (raw.dat) versus el "formato comprimido" usted propone (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

Muchas herramientas de compresión en estos días usan una combinación de estas técnicas para dar buenas relaciones en una variedad de datos. Puede valer la pena comenzar con algo bastante general y moderno como bzip2 que usa la codificación Huffman combinada con varios trucos que barajan los datos para mostrar varios tipos de redundancia (la página contiene enlaces a varias implementaciones más abajo).

Answer 3

¿La codificación de longitud de ejecución puede ser adecuada? Compruébelo aquí . Para dar un ejemplo extremadamente simple de cómo funciona, aquí hay una línea de datos en código ASCII ... 30 bytes de largo

HHHHHHHHEEEEEEELLLLLLLLOOOOOO

Aplíquele RLE y obtendrá esto en 8 bytes:

9H7E8L6O

• Nueve H
• Siete E
• Ocho L's
• Seis O

Una reducción de aproximadamente el 27% como resultado (la relación de compresión para la línea de ejemplo es 8/30)

¿Qué opinas?

Espero que esto ayude, Atentamente, Tom.

Answer 4

Calcule la diferencia de datos consecutivos, y luego use Run Length Encoding (RLE) .

Y también necesita convertir los datos a entero y luego calcular la diferencia.

Answer 5

lo que sería mejor sería una compresión diferencial adaptativa (olvido el nombre correcto). Donde no solo tomas las diferencias cada día, puedes calcular un predictor y realmente hacer tu diferenciación de eso. Normalmente supera a los predictores lineales normales.

si quieres ponerte elegante, lo que puedes hacer es una adaptación cruzada, en la cual el mercado de valores en general tiene su propia tendencia de que la caña se use para elegir mejores predictores para la compresión.

Answer 6

Sugeriría que descomponga el archivo principal en un formato bloqueado segmentado y luego comprima segmentos individuales por separado; Esto debería dar como resultado una compresión máxima optimizada. En el lado de descompresión, tendrá que descomprimir estos segmentos individuales por separado y luego reconstruir el archivo de texto original.