Programmer's Blood Bath ([info]314159265) wrote,
@ 2007-09-12 10:40:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Ммм... Где-бы почитать про алгоритмы сжатия гомогенных данных, например сжимаем только последовательности строк длиной 6 символов, состоящих из алфавита a-z, или только 64bit какие-нибудь numeric'и... А если бы они были бы адаптивными по отношению к накопленным данным, было бы вообще замечательно. Или я много хочу?

(Post a new comment)


[info]fenikso
2007-09-12 09:09 am UTC (link)
мне кажется, что обычные алгоритмы будут вполне применимы, просто в середине будет вставляться враппер alpha_char[6] -> really_big_byte :) остальные-то идеи никуда не денутся..

(Reply to this) (Thread)

[info]314159265
2007-09-12 09:19 am UTC (link)
Безусловно применимы. Однако хочется оптимального.

(Reply to this) (Parent)(Thread)

[info]abbra
2007-09-12 09:47 am UTC (link)
Huffman code не подойдет?

(Reply to this) (Parent)(Thread)

[info]thesz
2007-09-12 10:06 am UTC (link)
Он не оптимален.

(Reply to this) (Parent)

[info]thesz
2007-09-12 10:05 am UTC (link)
PPM*? (Prediction by PArtial Matchind)

Вместе с арифметическим кодированием практически идеальны. Современные PPM* жмут английский текст так, что от прдсказателя человека отличются сотыми битов на символ.

(Reply to this) (Thread)

[info]314159265
2007-09-12 10:18 am UTC (link)
Точно, это оно. Благодарю.

(Reply to this) (Parent)(Thread)

[info]thesz
2007-09-12 10:20 am UTC (link)
Надеюсь, опечатки не помешали найти. ;)

(Reply to this) (Parent)

[info]some41
2007-09-12 10:57 am UTC (link)
не совсем понятна постановка задачи. для текста (точнее для последовательностей элементов, хорошо описываемых марковским процессом) хорошо подходит ppm (правда ppm - это не один алгоритм, а общий принцип). для чисел не уверен.

(Reply to this) (Thread)

[info]314159265
2007-09-12 11:10 am UTC (link)
Более точно сформулировать не могу. Строки в моем случае неважно описываются марковским процессом, хотя в качестве отправной точки - подходит. Вот это более точно описывает задачу.

(Reply to this) (Parent)(Thread)

[info]some41
2007-09-12 11:26 am UTC (link)
то есть сжимать нужно колонки базы данных? тогда, если только это не offline процесс, ppm + arithmetic coder подходят так себе - они довольно медленные + ppm ест много памяти. возможно будут лучше lz или block sorting. что касается качества сжатия, то ppm, думаю, с текстовыми колонками справится прилично (если только там текст на шифрован по RSA :). с числами за один проход не зная распределения, мне кажется, бороться трудно.

(Reply to this) (Parent)(Thread)

[info]314159265
2007-09-12 11:35 am UTC (link)
Не база, но принцип очень похож. lzo нормально работает, хочется бОльшего. Скорость сжатия не критична, важна скорость восстановления. Про числа, кроме того что n_{i} < n_{i+1}, ничего не известно.

(Reply to this) (Parent)(Thread)

[info]some41
2007-09-12 12:47 pm UTC (link)
ppm и bwt симметричны, так что скорость компрессии и декомпрессии почти не отличаются. lzo - это очень экстремальный вариант, можно что-то типа lzx попробовать. возрастание - это уже не мало. можно, например, хранить дельты считая распределение убывающим (бОльшие дельты встречаются реже) адаптивно подбирая конкретную форму. например, если совсем тупо, использовать rice codes с динамически меняющимся m.

(Reply to this) (Parent)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…