Compression de données

Question

J'ai pour tâche de compresser des données boursières ... les données se trouvent dans un fichier où la valeur du stock pour chaque jour est donnée sur une ligne et ainsi de suite ... donc c'est un très gros fichier.

Par exemple,
123,45
234,75
345,678
889,56
.....

maintenant la question est de savoir comment compresser les données (alias réduire la redondance) en utilisant des algorithmes standards comme Huffman ou codage arithmétique ou codage LZ ... quel codage est le plus préférable pour ce genre de données? ...

J'ai remarqué que si je prends les premières données puis Considérer la différence entre chaque donnée consécutive, il y a beaucoup de répétition dans les valeurs de différence ... cela me fait me demander si d'abord prendre ces différences, trouver leur fréquence et donc la probalité, puis utiliser le codage huffman serait un moyen?

Ai-je raison? ... quelqu'un peut-il me donner quelques suggestions.

Answer 1

Je pense que votre problème est plus complexe que de simplement soustraire les cours boursiers. Vous devez également stocker la date (sauf si vous disposez d'une période cohérente pouvant être déduite du nom de fichier).

La quantité de données n'est cependant pas très importante.Même si vous avez des données chaque seconde pour chaque jour pour chaque année pour les 30 dernières années pour 300 stockd, vous pouvez toujours stocker tout cela dans un ordinateur à domicile haut de gamme (disons, un MAC Pro), car cela équivaut à 5 To . J'ai écrit un script rapide et sale qui va suivre le stock d'IBM dans Yahoo pour chaque jour, et le stocker "normalement" (seulement la fermeture ajustée) et en utilisant la "méthode de différence" que vous mentionnez, puis en les compressant en utilisant gzip . Vous obtenez des économies: 16K vs 10K. Le problème est que je n'ai pas stocké la date, et je ne sais pas quelle valeur correspond à quelle date, vous auriez à inclure cela, bien sûr.

Bonne chance.

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

Maintenant, comparez les "données brutes" (de raw.dat) par rapport à la vous proposes "format compressé" (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

De nos jours, de nombreux outils de compression utilisent une combinaison de ces techniques pour obtenir de bons rapports sur une variété de données. Il pourrait être utile de commencer avec quelque chose de très général et moderne comme bzip2 qui utilise le codage Huffman combiné avec diverses astuces qui mélangent les données pour faire ressortir différents types de redondance (la page contient des liens vers diverses implémentations plus bas).

Answer 3

Le codage de la longueur d'exécution peut convenir? Vérifiez-le here. Pour donner un exemple simple extrême de la façon dont cela fonctionne, voici une ligne de données dans le code ascii ... 30 octets

 
HHHHHHHHEEEEEEELLLLLLLLOOOOOO 

Appliquer RLE à et vous obtenez ceci dans 8 octets:

 
9H7E8L6O 

• Neuf H de
• Seven E de
• Huit L'
de
• Six O de

Une réduction d'environ 27% en raison (taux de compression pour la ligne exemple est 8/30)

Que pensez-vous?

Espérons que cela aide, Cordialement, Tom.

Answer 4

Caculez la différence des données consécutives, puis utilisez Encodage de longueur d'exécution (RLE).

Et vous devez également convertir les données en nombre entier, puis calculer la différence.

Answer 5

ce qui serait le mieux serait une compression différentielle adaptative (j'ai oublié le nom correct). Où non seulement vous prenez les différences chaque jour, vous pouvez calculer un prédicteur et faire votre différenciation hors de cela. Surpasse généralement les prédicteurs linéaires normaux. Si vous voulez avoir envie de ce que vous pourriez faire, c'est de l'adaptabilité croisée, dans laquelle le marché boursier dans son ensemble a sa propre tendance qui peut être utilisée pour choisir de meilleurs prédicteurs pour la compression.

Answer 6

Je vous suggère de décomposer le fichier principal en un format segmenté bloqué puis de compresser des segments individuels séparément; cela devrait aboutir à une compression optimisée maximale. Au niveau de la décompression, vous devrez décompresser séparément ces segments individuels, puis reconstituer le fichier texte d'origine.