Необходимо сжать N 256-байтных отсортированных (неважно как: по убыванию, возрастанию или ещё как) последовательностей.
элементы последовательностей представляют собой значения в диапазоне [0-255].
интересует возможность, сжать до размера ~12,5% от исходного материала.

Отсортированную последовательность можно сопоставить неупорядоченному множнеству. Можно составить список из присутствующих элементов с указанием их количества (частотный словарь).  В нем будет не более 22 различных значений частоты,   поэтому частотные значения можно проиндексировать 5-битными (или меньше) ссылками. 
Степень сжатия оказывается в общем случае около 70 процентов и уменьшить ее (в общем случае) не удастся.

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

Добавлено @ 11:15 

а как восстановить на приёмном конце таблицу индексирования?

Ее придется включать в архивированные данные.

Добавлено @ 11:27 

Что-то не совсем понял идею, почему рассматриваются перестановки, если речь идет об отсортированных последовательностях (читай, о неупорядоченных множествах)?
(кстати, log2(256!) ~ 1684)

два вопроса:
1. какой у неё будет размер
2. её нужно будет отдельно дописывать для каждой последовательности?


пример на последовательности из двух элементов (разных):
1,2
мы можем передать её двумя вариантами:
(1,2) и (2,1)
в любом случае на приёмном конце знают, что её надо отсортировать по возрастанию и из обоих вариантов передачи последовательность будет восстановлена правильно
выбирая один из этих вариантов можно передать 1 бит информации. в общем случае  log2(n!) (меньше при наличии повторений)

Добавлено @ 11:42 
кстати, ещё одна идея: просто взять разности соседних элементов и передавать их
т.к. мы знаем, что число > 128 может встретиться не более одного раза, то можно спокойно записать его позицию (или маркер, что такого нету) в отдельный байт, а при передаче самих разностей обрезать старший бит (т.к. и так уже достаточно информации для его восстановления)
передаваемая информация станет короче на (256-8) бит, что даёт 12.1%
проще некуда 

если надо сильнее сжать - можно эту же идею распространить на значения > 64
но чем дальше, тем процент сжатия будет расти медленнее...

Вот какой алгоритм был у меня.

для элементов массива от 0 до 255
{
 если элемент присутствует
 {
   записать бит 1 
   записывать бит 1 пока есть повторения элемента
   записать бит 0
 }
 иначе
  записать бит 0
}

Пример (здесь рассматривается сортировка по возрастанию):

Исходная посл.: 11244456...
Результат: 011010011101010...

Конечный результат ровно 512 бит (64 байта), что не есть нужный результат. (Степень сжатия гарантированно 75%).

В идеале нужен размер 32 + (2|3) байт.

P.S. Может есть какие-нибудь ссылки где можно почитать по этой теме?

Это сообщение отредактировал(а) Lived - 19.10.2006, 12:36

1. До 22 байтов.
2. Да. Вопрос о сжатии N последовательностей я вообще не рассматривал.

[QUOTE=maxim1000,19.10.2006,  11:37]
Почему разных??? Мне кажется постановка задачи можно прочитать, например, так: 
передаются упорядоченные по возрастанию последовательности...

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

[QUOTE=maxim1000,19.10.2006,  11:37]
Да, вот только картину портит то, что элементы могут повторяться по многу раз (если я правильно понял задачу). Что будем делать если вся последовательность состоит, скажем, из одних пятерок?

Добавлено @ 12:34 
Lived, Ваш алгоритм очень хорош.

В такой постановке, задача в общем виде не решается. Ибо всегда найдутся данные которые не сожмуться.

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


но передать её можно N! способами:
изменить упорядочивание перед передачей на одно из N! возможных, а при приёме восстановить его (при этом запомнив, какой порядок использовался)


тогда их разности будут нулевые...

Добавлено @ 14:26 

ну почему же?
есть ограничение - упорядоченность последовательности
т.е. мы кодируем не одну из 256^256 возможных последовательностей, а из значительно меньшего множества...

Я тут поразмышлял...  

256^256 - множество всех последовательностей(П.).

X - кол-во П. из этого множества, удовлетворяющих некоторому условию (например, каждый a(i+1) >= a(i), т.е. элементы отсортированы по возрастанию).

Алгоритм предложенный мной несколькими сообщениями выше, сопоставляет любой такой П. число из диапазона 2^512.

...

Значит если знать X, то можно представить его в виде 2^N,
где N и будет кол-во бит затрачиваемых на кодирование одной такой П.

Есть ли способы найти X? (простой перебор не приемлем)

P.S. Да, в алгоритме не учитывается что таких П. N-ное кол-во. Подозреваю что это тоже можно как-нибудь использовать. Но пока не знаю как.

кстати, тот подход, который я предложил, использует похожее представление:
мы передаём всё-таки одну из 256^256 последовательностей, но избыток информации, появляющийся из-за того, что X<256^256, используем сразу для передачи следующей последовательности


если они независимы, то много пользы от этого не получится
ну разве что иногда немного "размазывать" информацию по времени бывает удобнее, но не более того...

можно ещё посмотреть такой вариант:
берём разности соседних элементов
и используем что-то типа Хаффманна или арифметического кодирования
основная проблема в этом подходе - распределение вероятностей
можно использовать реальное: как показал nostromo, его можно передать довольно-таки сжато
а можно найти какую-то глобальную аппроксимацию, которая, конечно, не даст оптимального результата, но не потребует передачи самого распределения
то, что я показал с выделением разности, большей 128, - небольшое приближение
в принципе, может быть, получится найти такое распределение, которое будет давать достаточный _гарантированный_ результат...

Добавлено @ 15:37 
касательно нахождения X
можно попробовать так:
f(n,m) - количество неубывающих последовательностей из n элементов, каждый из которых принадлежит [0..m-1]
тогда X=f(256,255)
дальше можно сделать рекурсивный подсчёт этой функции:
f(1,m)=m
f(n+1,m)=сумма[i=0..m-1] f(n,m-i)
(не исключено, что что-то где-то потерял, но смысл такой)

Это сообщение отредактировал(а) maxim1000 - 19.10.2006, 15:32

Тут можно использовать два бита 0-элемента нет, 1-элемент есть,  2- элемент повторяет предидущий. но тут конечно 1/4 (если не считать, что полученную строку Хаффманом можно пройти)

проверил - похоже на правду
только можно упростить:
f(n+1,m)=f(n+1,m)+f(n,m-1)
(кстати, где-то я подобное встречал, но не помню где)
промоделировал в excel для случая 16^16: 3*10^8
количество бит для оптимального запоминания - 28
при прямом методе (тупо всё записать) - 64
для 32^32: 60/160
динамика выглядит оптимистично: степень компрессии растёт с увеличением n
решил для 256 excel не нагружать (да и растягивать так далеко неудобно  )

Проанализируем одну последовательность

ее исходный размер 256*8=2048 б.


Возрастающих последовательностей порядка 256^256/256!
Если их пронумеровать то потребуется  365 б.


сжали в 17%