Сжатие данных
У меня есть задача каким-то образом сжать данные фондового рынка... данные находятся в файле, где стоимость акций для каждого дня указывается в одной строке и так далее... так что это действительно большой файл.
Например,
123,45
234,75
345,678
889,56
.....
Теперь вопрос заключается в том, как сжать данные (или уменьшить избыточность), используя стандартные алгоритмы, такие как кодирование Хаффмана или арифметическое кодирование или кодирование LZ... какое кодирование является наиболее предпочтительным для данных такого типа??...
Я заметил, что если я возьму первые данные, а затем рассмотрю разницу между каждыми последовательными данными, будет много повторений в значениях разности... это заставляет задуматься, если сначала взять эти различия, найти их частоту и, следовательно, вероятности, а затем использование кодирования Хаффмана было бы способом??...
Я прав?... может кто-нибудь дать мне несколько советов.
6 ответов
Я думаю, что ваша проблема сложнее, чем просто вычитать цены на акции. Вам также необходимо сохранить дату (если только у вас нет согласованного промежутка времени, который может быть выведен из имени файла).
Количество данных не очень большое, хотя. Даже если у вас есть данные каждую секунду для каждого дня за каждый год за последние 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
В наши дни многие инструменты сжатия используют комбинацию этих методов, чтобы получить хорошие соотношения для различных данных. Возможно, стоит начать с чего-то достаточно общего и современного, такого как bzip2, в котором используется кодирование Хаффмана в сочетании с различными приемами, которые перемешивают данные, чтобы выявить различные виды избыточности (страница содержит ссылки на различные реализации ниже).
Может быть подходящей кодировка длины пробега? Проверьте это здесь. Чтобы дать предельно простой пример того, как это работает, вот строка данных в коде ascii...30 байт
HHHHHHHHEEEEEEELLLLLLLLOOOOOO
Примените RLE к нему, и вы получите это в 8 байтах:
9H7E8L6O
- Девять Н
- Семь Э
- Восемь L
- Шесть О
В результате сокращение составило около 27% (степень сжатия для примерной линии составляет 8/30).
Как вы думаете?
Надеюсь, это поможет, С наилучшими пожеланиями, Том.
То, что было бы лучше всего, было бы адаптивным дифференциальным сжатием (я забыл правильное имя). Если вы не только ежедневно учитываете разницу, вы можете вычислить предиктор и фактически отойти от этого. Обычно превосходит нормальные линейные предикторы.
если вы хотите придумать, что вы могли бы сделать, это кросс-адаптивность, в которой фондовый рынок в целом имеет свою собственную тенденцию, которую можно использовать для выбора лучших предикторов для сжатия.
Вычислите разницу между последовательными данными, а затем используйте кодирование длины выполнения (RLE).
И вам также необходимо преобразовать данные в целое число, а затем рассчитать разницу.
Я бы посоветовал вам разбить основной файл на сегментированный заблокированный формат, а затем сжать отдельные сегменты отдельно; это должно привести к максимально оптимизированному сжатию. На стороне декомпрессии вам придется отдельно распаковать эти отдельные сегменты, а затем восстановить исходный текстовый файл.