Как упаковать массив чисел не кратных двойке?

← →
uses1 (2007-07-31 01:28) [0]

Есть массив чисел из области от 0 до N. Где N - не кратно двум, например 129.

Как можно упаковать такой массив, чтобы цифры были поплотнее?

То есть если отводить вместо 129, 8 бит (0-255), то будет не оптимально, так как цифры от 130 до 255 не встречаются.

← →
DrPass © (2007-07-31 01:31) [1]

> То есть если отводить вместо 129, 8 бит (0-255), то будет
> не оптимально

отведи 7 с половиной бит. Тебе как раз хватит

← →
ferr © (2007-07-31 01:39) [2]

Например чтобы упоковать 5 чисел в диапазоне [0, 10). Достаточно выделить одно число 10^5, тогда у чисел будут следующие позиции:

1. a mod 10
2. a mod 100 div 10
3. a mod 1000 div 100
...

В итоге получим обычное представления числа в 10-ой системе ;-)

Аналогично можно работать из другими системами счисления.

P.S. Ни в коем случае не приминять.

← →
TUser © (2007-07-31 01:39) [3]

> Есть массив чисел из области от 0 до N. Где N - не кратно
> двум, например 129.
>
> Как можно упаковать такой массив, чтобы цифры были поплотнее?
>

А если у тебя файл, размером 129 байт, то знаешь как, да?

Телепатор говрит, что тебе надо хранить половинки, например, Chisla[i] div 2.

← →
uses1 (2007-07-31 01:43) [4]

Биты не делятся.

← →
uses1 (2007-07-31 01:46) [5]

> ferr © (31.07.07 01:39) [2]
>
> Например чтобы упоковать 5 чисел в диапазоне [0, 10). Достаточно
> выделить одно число 10^5

А если 1000 чисел?

← →
ferr © (2007-07-31 01:51) [6]

> > ferr © (31.07.07 01:39) [2]
> >
> > Например чтобы упоковать 5 чисел в диапазоне [0, 10).
> Достаточно
> > выделить одно число 10^5
>
>
> А если 1000 чисел?

Это чисто математический приём, пользоваться им бессмысленно. Ну если надо например хранить 1000 чисел в диапазоне [0,3) то надо работать с числом 3 ^ 1000.

Я это всё к тому что твоя задача либо имеет чисто теоретический интерес, либо не имеет лучшего практического решения чем в [0].

← →
uses1 (2007-07-31 02:00) [7]

> ferr © (31.07.07 01:51) [6]
> Это чисто математический приём, пользоваться им бессмысленно.
> Ну если надо например хранить 1000 чисел в диапазоне [0,
> 3) то надо работать с числом 3 ^ 1000.

В том то и дело.

> Я это всё к тому что твоя задача либо имеет чисто теоретический
> интерес, либо не имеет лучшего практического решения чем
> в [0].

Интерес практический.

Даже тройки хотя бы упаковать. Значения от 0 до 2.

3*3 = 9
3*9 = 27
3*27 = 81
Сколько не группируй, а кратное двойке не получишь.

← →
ferr © (2007-07-31 02:04) [8]

> 3*3 = 9
> 3*9 = 27
> 3*27 = 81
> Сколько не группируй, а кратное двойке не получишь.

это должно быть очевидно =) Ну там 243 близко к 255.

← →
uses1 (2007-07-31 02:14) [9]

> ferr © (31.07.07 02:04) [8]
>
> > 3*3 = 9
> > 3*9 = 27
> > 3*27 = 81
> > Сколько не группируй, а кратное двойке не получишь.
>
> это должно быть очевидно =) Ну там 243 близко к 255.

А 3 близко к 4 и что?

← →
ferr © (2007-07-31 02:17) [10]

3/4 = 0.75 vs 243/256 ~= 0.95

← →
uses1 (2007-07-31 02:30) [11]

> ferr © (31.07.07 02:17) [10]
>
> 3/4 = 0.75 vs 243/256 ~= 0.95

А если файл на мегабайт, то можно найти и ещё лучшее соотношение.

Вопрос был как это не чуть-чуть, на калькуляторы и т. п. улучшуть. А как нормально и полностью упаковать.

← →
ferr © (2007-07-31 02:38) [12]

> Вопрос был как это не чуть-чуть, на калькуляторы и т. п.
> улучшуть. А как нормально и полностью упаковать.

Ответ был -- никак.

← →
Альберт_ (2007-07-31 03:57) [13]

сортируй массив в порядке возрастания и находи остаток при делении на 8, например. если следующий элемент массива меньше текущего, то начинается новый отрезок = 8.

← →
SlymRO © (2007-07-31 05:42) [14]

схема кодирования Хафмана

← →
shlst (2007-07-31 09:39) [15]

биты ещё как делятся!
Пакуй числом, это как десятичные цифры паковать 1,2,3 = 123
Пример - пакуем в 129:
120
1
34
8

(120*129^3)+(1*129^2)+(34*129)+(8)=257623715

← →
БарЛог © (2007-07-31 09:46) [16]

zip

← →
palva © (2007-07-31 10:15) [17]

> ferr © (31.07.07 01:39) [2]
> Аналогично можно работать из другими системами счисления.
> P.S. Ни в коем случае не приминять.

Ну а почему не применять? Скажем, у нас числа 0..5 требуют 3 бита. Первое и второе число (a1, a2) будем хранить как a1*5 + a2. Это число не более 30, а значит потребует пять битов вместо шести, которые понадобились бы, если числа a1 и a2 хранить в исходном виде. На следующей паре чисел a3 a4 сэкономим еще один бит и т. д.

← →
shlst (2007-07-31 10:27) [18]

[15]
257623715 = для хранения надо 28 бит, а если хранить каждое число 8-ю битами, то будет 32 бита. Чем больше чисел таким образом упаковать(как в [15], тем будет ближе к log2(основание системы, у нас 129)*n = 7,0112*n
Можно использовать "длинные числа"

← →
StriderMan © (2007-07-31 10:38) [19]

> Как можно упаковать такой массив, чтобы цифры были поплотнее?

шрифт помельче, межсимвольный интервал = 0

← →
partizan (2007-07-31 15:52) [20]

> Биты не делятся.
>

В некотором смысле делятся: http://algolist.manual.ru/compress/standard/arithm.php

← →
partizan (2007-07-31 16:02) [21]

А вообще, если так хочется сжать - коды Хаффмана.
Выделяется не фиксированное кол-во бит на одно число, а разное кол-во бит на каждое число. На те числа, что встречаются чаще - меньше бит, что реже - больше.

В случае чисел от 1 до 129 (если не известно, какие встретятся чаще, а какие реже) - можно выделить по 7 бит на 1..127, и 8 бит на числа 128 и 129.
Всреднем получится (7*127+2*8)/129 = 7,015... бит на число

← →
Kerk © (2007-07-31 16:09) [22]

[21] partizan (31.07.07 16:02)
> В случае чисел от 1 до 129 (если не известно, какие встретятся
> чаще, а какие реже) - можно выделить по 7 бит на 1..127,
> и 8 бит на числа 128 и 129.

Не выйдет.

← →
partizan (2007-07-31 16:13) [23]

> Не выйдет

Почему нет?

1 => 0000000 2 => 0000001 3 => 0000010 .... 127 => 1111110 128 => 11111110 129 => 11111111

Числа 1..127 состоят из 7 бит, и не в одном не встречается последовательность из 7 единиц => если на каком-то шаге при декодировании получено 7 единиц - значит это 128 либо 129, а если 7 бит, из которых не все единици - это число от 1 до 127

Ошибка у тебя

1 => 0000000 2 => 0000001 3 => 0000010 .... 126 => 111110 127 => 1111111 128 => 11111110 129 => 11111111
И теперь попробуй отличи 127 от 128 и 129

+ еще ноль потерял

← →
partizan (2007-07-31 16:17) [26]

попробуй посмотреть внимательно на мои посты. Там числа от 1 до 129, нуля нет!

Поэтому 126 => 1111101 (125 в двоичной), 127 => 1111110 (126 в двоичной)

← →
partizan (2007-07-31 16:19) [27]

А если с нулем нужно (0..129) - тогда по 7 бит на 0..126 (двоичное представления, как есть), на 127 - 8 бит: 11111110, на 128 и 129 - по 9 бит (111111110 и 111111111)

[26] partizan (31.07.07 16:17)
> попробуй посмотреть внимательно на мои посты. Там числа
> от 1 до 129, нуля нет!

Тогда и кодированием извращаться не нужно. 128 разных чисел в 7 бит и так влезает.

> А вообще, если так хочется сжать - коды Хаффмана.
> Выделяется не фиксированное кол-во бит на одно число, а
> разное кол-во бит на каждое число. На те числа, что встречаются
> чаще - меньше бит, что реже - больше.
>
Коды хаффмана лишь раздуют при случайном распределении.

> В случае чисел от 1 до 129 (если не известно, какие встретятся
> чаще, а какие реже) - можно выделить по 7 бит на 1..127,
> и 8 бит на числа 128 и 129.
> Всреднем получится (7*127+2*8)/129 = 7,015... бит на число

Закодировать то можно, я бы посмотрел как ты декодировать будешь..

← →
partizan (2007-07-31 16:20) [30]

> Тогда и кодированием извращаться не нужно. 128 разных чисел
> в 7 бит и так влезает.

От 1 до 129 их 129 а не 128

[27] partizan (31.07.07 16:19)
> на 128 и 129 - по 9 бит

Так не бывает :) Иначе бы сабж не возник

Если уж извращаться с кодами Хаффмана, то нужно действительно частоту учитывать. Тогда может на некоторые цифры и по три бита придется. Но к сабже это мало отношения имеет.

← →
partizan (2007-07-31 16:27) [33]

Так это частный случай Хаффмана, когда у чисел 0..129 частота одинаковая, а у чисел 130..255 - нулевая.

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

Как упаковать массив чисел не кратных двойке? Найти похожие ветки