Datenkompression

Question

Ich habe die Aufgabe, Börsendaten irgendwie zu komprimieren. Die Daten befinden sich in einer Datei, in der der Aktienwert für jeden Tag in einer Zeile usw. angegeben ist. Es handelt sich also um eine wirklich große Datei.

Z.B,
123.45
234.75
345.678
889.56
.....

Jetzt stellt sich die Frage, wie man die Daten mithilfe von Standardalgorithmen wie Huffman oder arithmetischer Codierung oder LZ-Codierung komprimiert (also die Redundanz reduziert). Welche Codierung ist für diese Art von Daten am besten?

Mir ist aufgefallen, dass es, wenn ich die ersten Daten nehme und dann die Differenz zwischen den einzelnen aufeinanderfolgenden Daten betrachte, viele Wiederholungen in den Differenzwerten gibt ... Da frage ich mich, ob ich zuerst diese Differenzen nehme, ihre Häufigkeit und damit ihre Wahrscheinlichkeit finde und dann Die Verwendung von Huffman-Codierung wäre eine Möglichkeit?

Habe ich recht?...kann mir jemand ein paar Vorschläge machen?

Answer 1

Ich denke, Ihr Problem ist komplexer als nur das Subtrahieren der Aktienkurse.Sie müssen auch das Datum speichern (es sei denn, Sie haben eine konsistente Zeitspanne, die aus dem Dateinamen abgeleitet werden kann).

Allerdings ist die Datenmenge nicht sehr groß.Selbst wenn Sie in den letzten 30 Jahren jede Sekunde, jeden Tag, jedes Jahr Daten für 300 Stockd haben, könnten Sie es dennoch schaffen, all diese auf einem Heimcomputer der höheren Preisklasse (z. B. einem MAC Pro) zu speichern, da dies 5 TB UNKOMPRIMIERT entspricht .

Ich habe ein schnelles und schmutziges Skript geschrieben, das jeden Tag die IBM-Aktien in Yahoo durchsucht, sie „normal“ speichert (nur den angepassten Abschluss) und die von Ihnen erwähnte „Differenzmethode“ verwendet und sie dann mit gzip komprimiert.Sie erzielen Einsparungen:16.000 vs. 10.000.Das Problem ist, dass ich das Datum nicht gespeichert habe und ich nicht weiß, welcher Wert welchem ​​Datum entspricht, das müsste man natürlich mit einbeziehen.

Viel Glück.

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

Vergleichen Sie nun die „Rohdaten“ (raw.dat) mit dem von Ihnen vorgeschlagenen „komprimierten Format“ (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

Viele Komprimierungstools in diesen Tagen verwenden eine Kombination dieser Techniken gute Verhältnisse auf einer Vielzahl von Daten zu geben. Könnte mit etwas ziemlich allgemein und modern ausgehend wert sein wie bzip2 , die mit verschiedenen kombinierten Huffman verwendet Codierung Tricks, die die Daten um zu bringen, verschiedene Arten von Redundanz (Seite enthält Links zu verschiedenen Implementierungen weiter unten).

mischen

Answer 3

Run Length Encoding könnte geeignet sein? Check it out hier. Um ein extremes einfaches Beispiel zu geben, wie es funktioniert, ist hier eine Zeile von Daten im ASCII-Code ... 30 Byte lang

HHHHHHHHEEEEEEELLLLLLLLOOOOOO

Übernehmen, um es RLE und Sie erhalten diese in 8 Bytes:

9H7E8L6O

• Nine H
• Seven E ist
• Acht L's
• Sechs O

Eine Reduzierung von ca. 27% als Ergebnis (Verdichtungsverhältnis für das Beispiel Linie 8/30)

Was denken Sie?

Hope, das hilft, Freundliche Grüße, Tom.

Answer 4

caculate die Differenz von aufeinanderfolgenden Daten, und dann Run Length Encoding (RLE) .

Und Sie müssen auch die Daten konvertieren in Integer und dann die Differenz caculate.

Answer 5

, was am besten wäre wäre eine adaptive Differenzbildkompression (i die richtigen Namen vergessen). Wo nicht nur nehmen Sie nur jeden Tag die Unterschiede, können Sie einen Prädiktor berechnen und tatsächlich tun Ihr differenzier ab davon. Typischerweise übertrifft normale lineare Prädiktoren.

Wenn Sie Lust zu bekommen, was Sie tun können, ist Quer adapative, in denen der Aktienmarkt insgesamt hat es eigenen Trend ist das Zuckerrohr verwendet werden, um bessere Prädiktoren für die Kompression zu wählen.

Answer 6

Ich würde Ihnen vorschlagen, die Hauptdatei in brechen, um eine segmentierte blockiert Format dann separat einzelne Segmente komprimieren; dies sollte in maximal optimierte Kompression führen. Bei der Dekomprimierung Seite sehen Sie diese einzelnen Segmente separat dekomprimieren müssen und dann die ursprüngliche Textdatei zu rekonstruieren.