Compression de données

Question

J'ai pour tâche de compresser les données boursières d'une manière ou d'une autre ... les données se trouvent dans un fichier où la valeur boursière de chaque jour est indiquée sur une ligne, etc. ... il s'agit donc d'un fichier vraiment volumineux.

Par exemple,
123.45
234.75
345.678
889.56
.....

maintenant la question est de savoir comment compresser les données (réduire la redondance) en utilisant des algorithmes standard tels que le codage de Huffman ou Arithmetic ou le codage LZ ... quel codage est le plus préférable pour ce type de données? ...

J'ai remarqué que si je prends les premières données et considère ensuite 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, en prenant d'abord ces différences, en trouvant leur fréquence et par conséquent probalility et ensuite en utilisant le codage de Huffman serait un moyen ?? ...

Ai-je raison? ... quelqu'un peut-il me faire des suggestions?

Answer 1

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

Cependant, la quantité de données n’est pas très grande. Même si vous avez des données toutes les secondes, tous les jours et tous les ans au cours des 30 dernières années pour 300 stocks, vous pouvez tout de même stocker tout cela dans un ordinateur domestique haut de gamme (par exemple, un MAC Pro), ce qui représente une valeur de 5 To. .

J'ai écrit un script rapide et sale qui va chasser chaque jour le titre IBM dans Yahoo et le stocker "normalement". (uniquement la clôture ajustée) et en utilisant la "méthode de la différence" vous mentionnez, puis les compresser en utilisant gzip. Vous obtenez des économies: 16K vs 10K. Le problème est que je n’ai pas enregistré la date et que je ne sais pas quelle valeur correspond à quelle date, il faudrait bien sûr l’inclure.

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

Comparez maintenant les " données brutes " (raw.dat) versus le "format compressé" vous proposez (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 diverses données. Cela vaut peut-être la peine de commencer avec quelque chose d'assez général et moderne comme bzip2 qui utilise le codage de Huffman combiné à divers 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 longueur d’exécution pourrait convenir? Découvrez-la ici . Pour donner un exemple extrêmement simple de son fonctionnement, voici une ligne de données en code ASCII ... 30 octets de long

HHHHHHHHEEEEEEELLLLLLLLOOOOOO

Appliquez-le RLE et vous obtenez cela en 8 octets:

9H7E8L6O

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

Il en résulte une réduction d’environ 27% (le taux de compression de la ligne exemple est de 8/30)

Qu'en pensez-vous?

J'espère que ça aide, Meilleures salutations, Tom.

Answer 4

Calculez la différence entre les données consécutives, puis utilisez le codage de la longueur de la longueur (RLE) .

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

Answer 5

Le meilleur serait une compression différentielle adaptative (j'oublie le nom correct). Où non seulement vous prenez les différences chaque jour, vous pouvez calculer un prédicteur et faire votre différence en dehors de cela. Généralement supérieur aux prédicteurs linéaires normaux.

si vous voulez avoir l’imagination, vous pouvez utiliser une combinaison croisée, dans laquelle le marché boursier a sa propre tendance qui peut être utilisée pour sélectionner de meilleurs prédicteurs pour la compression.

Answer 6

Je vous conseillerais de décomposer le fichier principal en un format bloqué segmenté, puis de compresser chaque segment séparément; Cela devrait aboutir à une compression optimisée maximale. Du côté de la décompression, vous devrez décompresser ces segments séparément, puis reconstruire le fichier texte original.