Непятничная задачка

← →
palva © (2005-02-14 16:41) [0]

Непятничная задачка.

Требуется хранить в файле большой массив, состоящий из перестановок чисел 0..255. В несжатом виде перестановка - это некий массив из 256 байтов с неповторяющимися значениями. Ясно, что в таком массиве имеется информационная избыточность. Скажем, последний байт массива можно не хранить, он вычисляется по значениям остальных байтов. Пока я придумал способ хранения, который требует 224 байта (вместо 256). Теоретическое минимальное значение log_2 256! / 8 байтов, что приближенно равно 210.4995. Как видите резерв имеется, но чтоб использовать этот резерв придется, наверно, придумывать алгоритмы, требующие существенно большего количества ресурсов.

У кого какие соображения? Попробуйте догадаться хотя бы, как сделать 224 байта.

← →
MBo © (2005-02-14 16:45) [1]

А есть ли необходимость действительно хранить сами эти перестановки? Понятно, что быстрее прочитать готовый массивчик, но не устроит ли генерация перестановки по ее номеру?

← →
Sandman25 © (2005-02-14 16:47) [2]

palva © (14.02.05 16:41)

128*8+64*7+32*6...+2*2+1=224 байта с копейками (битами)

---
к

← →
palva © (2005-02-14 16:48) [3]

> генерация перестановки по ее номеру?

Это идеальный вариант. Номер из диапазона 1..256! Только не могу предположить, какой может быть алгоритм генерации.

← →
wal © (2005-02-14 16:49) [4]

Хранить номер перестановки
256!=8,5781777534284265411908227168123e+506
Log2(256!)~=1684(бит)~=211(байт).

С уважением.

← →
palva © (2005-02-14 16:51) [5]

Sandman25 © (14.02.05 16:47) [2]
> 224 байта с копейками (битами)

По моим расчетам 223.5 Может я и ошибся...

← →
wal © (2005-02-14 16:52) [6]

Есть не очень сложный алгоритм, который создает "отсортированные" перестановки (каждая последующая "больше" предыдущей).

С уважением.

← →
MBo © (2005-02-14 17:30) [7]

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

← →
default © (2005-02-14 18:03) [8]

перестановок по 2 элемента всего 256*255=65280
двумя байтами можно закодировать 2^16=65536 состояний
первые 65280 из них кодируют нужную перестановку из двух элементов
остаётся 65536 - 65280 = 256
то есть как раз достаточно для кодирования следующего элемента! таким образом 2 байтами кодируем 3 элемента перестановки!256/3=85.33...то есть экономим 85 байт!
итого 256-85=171 байт для кодирования...
рулёз!

← →
Sha © (2005-02-14 18:13) [9]

> default © (14.02.05 18:03) [8]

Можно подробнее, как именно двумя байтами кодируются 3 элемента?

← →
default © (2005-02-14 18:23) [10]

Sha © (14.02.05 18:13) [9]
два байта дают 65536 состояний
первыми 65280 кодируются два элемента всей перестановки
(путём указания её номера, таких номеров 65280)
посредством оставшихся 256 состояний кодируем следующий элемент перестановки после указанных двух
то есть кодируем тройками
я думаю этим алгоритмом далеко не ограничивается всё пространство решений этой задачи...есть думаю и эффективнее...
даже в этом алгоритме есть избыточность
поскольку после наступления какой-то перестановки она уже встретиться не может, но число бит под номер перестановки постоянно

← →
Sha © (2005-02-14 18:35) [11]

> default © (14.02.05 18:23) [10]

Не понял. Нельзя ли привести пример кодирования/декодирования?

← →
default © (2005-02-14 18:37) [12]

Sha © (14.02.05 18:35) [11]
если брать перестановки по 4 элемента и ещё маленькие нюансы можно сжать аж до 64 байт...
тут надо уже искать компросисс эффективности сжатия и скорости шифрации/дешифрации

← →
raidan © (2005-02-14 18:40) [13]

А если брать по 16 элементов?

← →
Sha © (2005-02-14 18:43) [14]

> default © (14.02.05 18:37) [12]

Опять не понял. Нельзя ли, наконец, привести пример кодирования/декодирования?

← →
raidan © (2005-02-14 18:45) [15]

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

← →
raidan © (2005-02-14 18:46) [16]

>palva © (14.02.05 16:41)
Кстати, что по этому поводу говорит winrar?
На сколько сжимает?

← →
Юрий Зотов © (2005-02-14 18:48) [17]

Или я чего-то не так понял, или Set of byte требует 32 байтов.

← →
default © (2005-02-14 18:49) [18]

возьму на примере меньшего числа элементов
пусть элементами перестановки будут числа 1,2,3,4
число перестановок по два элемента будет 4*3=12
пусть они занумерованы так:
1 1,2
2 1,3
3 1,4
4 2,1
5 2,3
6 2,4
7 3,1
8 3,2
9 3,4
10 4,1
11 4,2
12 4,3
нужно нам закодировать перестановку 1,3,2,4
1,3 - это перестановка двух элементов имеет номер 2
следующий элемент перестановки это 2, нумерация же кодирования третьего элемента тройки обычная: 1..4 в этом случае
значит первая тройка кодируется как 22 и тд по тройкам
понятно что мы не кодировали бы перестановки из 4 элементов так, но я на этом примере хотел пояснить кодирование при 256 элементах
но ка я говорил можно и эффективней кодировать тут уже надо искать приемлемую скорость декодирования

← →
palva © (2005-02-14 18:49) [19]

wal © (14.02.05 16:52) [6]
> Есть не очень сложный алгоритм, который создает "отсортированные" перестановки (каждая последующая "больше" предыдущей).

Да, помнится в учебнике Куроша по общей алгебре такой алгоритм излагался. Каждая перестановка получалась из предыдущей обменом двух соседних чисел. Надо вечером дома посмотреть.

← →
Sha © (2005-02-14 18:50) [20]

> Юрий Зотов © (14.02.05 18:48) [17]

Set - неупорядоченное множество,
Перестановка - упорядоченное.

← →
default © (2005-02-14 18:50) [21]

Юрий Зотов © (14.02.05 18:48) [17]
там сочетания, а не перестановки

← →
Sha © (2005-02-14 18:54) [22]

> default © (14.02.05 18:49) [18]
> значит первая тройка кодируется как 22 и тд по тройкам

Нет не как 22, а как 022 - всего 3 байта.

← →
default © (2005-02-14 19:07) [23]

Sha © (14.02.05 18:54) [22]
там принцип пояснён...
при 256 элементах тройка кодируется 2 байтами
вообщем работают алгоритмы такого рода...

← →
default © (2005-02-14 19:26) [24]

Sha © (14.02.05 18:54) [22]
да действительно, я ступил
считал состояния независимыми...

← →
palva © (2005-02-14 22:01) [25]

Пока ехал домой, придумал практический алгоритм, который позволяет использовать меньше 240 байтов.

Берем перестановку и кодируем по два байта. Первые два байта остаются без изменения. Следующие два байта заменяем на их номер среди тех байтов, которые еще не были закодированы. И так далее кодируем по два байта. Для примера рассмотрим начало перестановки
1, 2, 3, 4, 200, 12, ... - это исходная перестановка 1, 2, 1, 2, 196, 8, ... - это ее код (промежуточный)
Сразу можно сказать что если 2*n байтов уже закодировано, то следующие два кода не будут превышать 256-2*n. Следовательно для их записи потребуется уже не 8 битов, а вообще говоря меньше. Мы уже исследовали этот способ записи и определили, что он требует 240 байтов. Будем считать, что очередные два кода - запись некоторого числа в позиционной системе по основанию 256-2*n. Это число вначале потребует для своей записи 16 битов, потом, начиная с некоторого места 15 битов и т. д. Вот эти биты и будем накапливать как результат кодирования. Такой метод вырабатывает 1753 бита или 220 байтов. С раскодированием проблем не будет, поскольку местА, где число битов уменьшается на единицу могут быть вычислены заранее и фиксированы для данного алгоритма. Можно пойти дальше и кодировать не по 2 байта а по 4. Вычисления при кодировании здесь будут уже существенные - много умножений, но результат улучшится - 1698 битов 213 байтов. Наверно, можно кодировать и по 8 байтов - я не смотрел, будет лучше в этом случае или нет.

Выкладываю программу, считающую число битов при кодировании по 4.
{$APPTYPE CONSOLE} var i: Cardinal; sumofbits, max_number: Cardinal; function log2(n: Cardinal): Cardinal; var i, r: Cardinal; begin r := 0; for i := 1 to 32 do begin if Odd(n) then r := i; n := n shr 1; end; Result := r; end; begin sumofbits := 0; max_number := 256; for i := 0 to 63 do begin sumofbits := sumofbits + log2(max_number * max_number * max_number * max_number); max_number := max_number - 4; end; WriteLn(sumofbits, " ", (sumofbits + 7) div 8) // 1698 213 end.

← →
default © (2005-02-14 22:48) [26]

palva © (14.02.05 22:01) [25]
метод 224 байт допускает удобную практическую реализацию
всё зависит от интерпретации
выгодная интерпретация это понимать этот метод как постановку элемента 1 на одно из 256, далее 2 на одно из 255 мест и тд
ливидирую избыточность получим затраты [2]

← →
palva © (2005-02-14 23:05) [27]

default © (14.02.05 22:48) [26]
Да, вы совершенно правы, 224 легко достижимо. В своем последнем посте я ошибся и вместо 224 писал везде 240, т.е.

> ...который позволяет использовать меньше 240 байтов

> Мы уже исследовали этот способ записи и определили, что он требует 240 байтов.

Везде надо читать 224. Но сути это не меняет.

Первоначально задача и ставилась так, чтобы предложить практический способ сделать размер меньше чем 224. В моем последнем посте и предлагается алгоритм, дающий 220 и 213 байтов.

← →
default © (2005-02-14 23:08) [28]

объясните как вы получили 196, 8 из 200, 12(

уже не надо

palva © (14.02.05 22:01) [25]
"Следовательно для их записи потребуется уже не 8 битов, а вообще говоря меньше."
вы тут неверно сказали, надо было сказать - начиная с некоторого n
"Наверно, можно кодировать и по 8 байтов - я не смотрел, будет лучше в этом случае или нет."
странно что вы говорите НАВЕРНО если вы понимаете суть алгоритма вами же придуманного, конечно, будет!

математически можно суть пояснить так(это не для вас, а тем кто захочет понять откуда берётся избыточность и как это работает:)):
есть две двоичные записи чисел a и b прилегающие друг к другу, одна пусть кодируется na битами, другая - nb
причём оба числа не максимальны и вдобавок имеют ещё границу m - свою на каждом шаге алгоритма - она на каждом шаге в данном случае будет уменьшаться на 2
то есть: a<=m-1<2^na-1 и b<=m-1<2^nb-1
(m-1 используется поскольку считаем с 0)
(по сути своей это и есть условие избыточности!
не было бы его не было бы и алгоритма palva!тут возникает своеобразная битовая разрозненность, мы уплотнением и достигнем сжимаемости!)
число m определяется шагом алгоритма как уже говорилось - это число max_number в алгоритме
ясно что на оба числа расходуется na + nb бит в этом случае
но исходя из условия избыточности битами na и nb реальнобудут задаваться только m^2 чисел, а не 2^na*2^nb=2^(na+nb) если бы на a и b не были бы наложены условия избыточности
для m^2 чисел требуется лишь Log2(m^2) бит, а для
2^(na+nb) - na+nb
ясно отсюда что поскольку при каждом шаге алгоритма m уменьшается(при постоянстве na и nb) значит будет и уменьшаться Log2(m^2)
это приведёт к тому что начиная с некоторого шага алгоритма
m настолько уменьшится что мы будем иметь возможность получить экономию бит

Любую комбинацию 256 чисел можно представить в виде перестановок. Такое ощущение, что должно быть достаточно 32 байт.

← →
palva1 (2005-02-15 10:09) [34]

default © (15.02.05 01:06) [30]
Я написал наверно по следующей причине. Из кодируемой группы байтов только первый действительно может достигать верхней границы, а второй и следующие - нет. Здесь возникает некоторая избыточность, поскольку интерпретация этой группы, как записи числа в позиционной системе позволяет кодировать некоторые недопустимые наборы байтов. Эта избыточность тем больше, чем больше байтов в группе, причем растет довольно быстро (навскидку - по экспоненте). Поэтому я так осторожничаю с числом 8. Но на самом деле это недолго проверить - изменить в выложенной программе несколько строк и запустить. Может быть я сегодня днем попробую это сделать и выложить результат. Сейчас - недосуг.

> palva1 (15.02.05 10:09) [34]
> Поэтому я так осторожничаю с числом 8.

Можно смело разбивать на группы с любым количеством элементов, если немного подправить веса разрядов.
Например, для четверок можно использовать такие веса:

i*(i+1)*(i+2)*a[i+3]+i*(i+1)*a[i+2]+i*a[i+1]+a[i]

Здесь для удобства элементы нумеруются в обратном порядке,
так, что 1<=a[i]<=i, (первый элемент имеет номер 256).

Поправка:
Здесь для удобства элементы нумеруются в обратном порядке,
так, что 0<=a[i]<i, (первый элемент имеет номер 255).

palva1 (15.02.05 10:09) [34]
увеличение качества сжимаемости при увеличении численности группы кодировки почти очевидно
в пределе когда группа равна 256 мы как раз и получим теорграницу в 211 байт при остальных же группах затраты будут стремиться к этой границе при увеличении численности группы
почему очевидно?
да очень просто(можно это и математически доказать)
возьмём кодирование 6 элементов перестановки по 2 и по 3 элемента в группе
1 2|3 4|5 6 кодирование по 2
мы уплотнили код элементов 1,2; 3,4; 5,6
уплотнения же между элементами 2,3 и 4,5 НЕТ!
1 2 3|4 5 6 кодирование по 3
мы уплотнили элементы 1,2,3 и 4,5,6
но уплотнения элементов 3,4 НЕТ!
но тут нет одного уплотнения, а в предыдущем случае двух - отсюда и стремление к теоргранице при возрастании численности групп

← →
SergP. (2005-02-15 12:28) [38]

ИМХО максимум что можно выжать:

кол. байт = (log_2(256!))/8

Сколько это будет - х/з, не считал...

> palva © (14.02.05 22:01) [25]

В программе имеется неточность: аргумент при первом вызове Log2 равен 256^4=0. После исправления

sumofbits := sumofbits + log2(max_number * (max_number-1) * max_number * max_number);

получаем результат 1724/216.

Предложенное в [34] усовершенствование позволяет сэкономить
еще одит байт (1713/215).

> default © (15.02.05 12:10) [37]
> отсюда и стремление к теоргранице при возрастании численности групп

Все не так просто. Общая тенденция, конечно, имеется. Но не факт, что всегда для больших групп результат будет лучше, чем для меньших.

Непятничная задачка Найти похожие ветки