Сжатие данных - PullRequest
       34

Сжатие данных

1 голос
/ 30 ноября 2009

У меня есть задача каким-то образом сжать данные фондового рынка ... данные находятся в файле, где стоимость акций для каждого дня указывается в одной строке и так далее ... так что это действительно большой файл.

Например,
123,45
234,75
345,678
889,56
.....

Теперь вопрос заключается в том, как сжать данные (или уменьшить избыточность), используя стандартные алгоритмы, такие как кодирование Хаффмана, арифметическое или LZ-кодирование ... какое кодирование наиболее предпочтительно для данных такого типа ?? ...

Я заметил, что если я беру первые данные, а затем рассматриваю разницу между каждыми последовательными данными, существует много повторений в значениях разности ... это заставляет меня задуматься, если сначала взять эти различия, найти их частоту и, следовательно, способность и затем использование кодирования Хаффмана было бы способом ?? ...

Я прав? ... может кто-нибудь дать мне несколько советов.

Ответы [ 6 ]

2 голосов
/ 30 ноября 2009

Я думаю, что ваша проблема сложнее, чем просто вычитать цены на акции. Вам также необходимо сохранить дату (если у вас нет согласованного промежутка времени, который может быть выведен из имени файла).

Однако объем данных не очень велик. Даже если у вас есть данные каждую секунду за каждый день за каждый год в течение последних 30 лет на 300 складах, вы все равно можете хранить все это на домашнем компьютере более высокого уровня (скажем, MAC Pro), поскольку это составляет 5 ТБ UNCOMPRESSED .

Я написал быстрый и грязный скрипт, который будет преследовать акции IBM в Yahoo каждый день, и сохранять их «нормально» (только скорректированное закрытие), используя упомянутый «разностный метод», а затем сжимать их с помощью gzip. Вы получаете экономию: 16K против 10K. Проблема в том, что я не сохранил дату, и я не знаю, какое значение соответствует какой дате, вы, конечно, должны были бы включить это.

Удачи.

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

Теперь сравните «необработанные данные» (raw.dat) с «сжатым форматом», который вы предлагаете (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
2 голосов
/ 30 ноября 2009

В наши дни многие инструменты сжатия используют комбинацию этих методов, чтобы получить хорошие соотношения для различных данных. Возможно, стоит начать с чего-то довольно общего и современного, такого как bzip2 , в котором используется кодирование Хаффмана в сочетании с различными приемами, которые перемешивают данные, чтобы выявить различные виды избыточности (страница содержит ссылки на различные реализации ниже).

0 голосов
/ 12 января 2012

Я бы предложил вам разбить основной файл на сегментированный заблокированный формат, а затем сжать отдельные сегменты отдельно; это должно привести к максимально оптимизированному сжатию. На стороне декомпрессии вам придется отдельно распаковать эти отдельные сегменты, а затем восстановить исходный текстовый файл.

0 голосов
/ 26 мая 2011

что было бы лучше всего - адаптивное дифференциальное сжатие (я забыл правильное имя). Если вы не только ежедневно учитываете разницу, вы можете вычислить предиктор и фактически отойти от этого. Обычно превосходит нормальные линейные предикторы.

Если вы хотите получить фантазию, то вы можете сделать это кросс-адаптивно, в котором фондовый рынок в целом имеет свою собственную тенденцию, которую можно использовать для выбора лучших предикторов сжатия.

0 голосов
/ 30 ноября 2009

Вычислить разницу последовательных данных, а затем использовать кодирование длины выполнения (RLE) .

И вам также необходимо преобразовать данные в целое число, а затем рассчитать разницу.

0 голосов
/ 30 ноября 2009

Может быть подходящей кодировка длины пробега? Проверьте это здесь . Чтобы дать предельно простой пример того, как это работает, вот строка данных в коде ascii ... 30 байт

HHHHHHHHEEEEEEELLLLLLLLOOOOOO

Примените RLE к нему, и вы получите это в 8 байтах:

9H7E8L6O
  • Девять H
  • Семь Э
  • Восемь L
  • Шесть О

В результате сокращение составило приблизительно 27% (степень сжатия для примерной строки составляет 8/30)

Что вы думаете?

Надеюсь, это поможет, С наилучшими пожеланиями, Том.

...