[devel] вопрос про числа

[devel] вопрос про числа

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 1066 bytes --]

Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
по возрастанию.  Для примера m=32, n порядка 10^3.

Вычислить энтропию и предложить оптимальную процедуру кодирования
(сжатия) последовательности.  Сколько битов на число можно получить?


(Вопрос связан с тем, что нам нужно придумать компактное представление
"множества строк".  Например каждую строку можно представить в виде её
m-битного хеша.  Соответственно множество n строк можно представить
в виде n*m битов.  Но всё-таки битов получается очень много, и их можно
неплохо сжать.  Неплохо наварить на этом можно, вот что.  Осталось только
придумать процедуру сжатия.

Иначе же существует эквивалентное представление в алфавите {0,1} с
постоянными вероятностями.  А именно, каждое число из диапазона 0..2^m-1
можно рассматривать как номер бита в битмапе из 2^m битов.  Тогда
последовательность чисел можно перевести в битмап и сжать битмап
побитово.  Проблема только в том что при побитовом кодировании/
декодировании получается очень большой битмап и очень большой цикл.)

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] вопрос про числа

[Денис Смирнов]

[-- Attachment #1: Type: text/plain, Size: 1060 bytes --]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Алексей Турбин wrote:
AT> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
AT> по возрастанию.  Для примера m=32, n порядка 10^3.
AT> Вычислить энтропию и предложить оптимальную процедуру кодирования
AT> (сжатия) последовательности.  Сколько битов на число можно получить?

1. Попробовать для начала представить это в виде последовательности
разностей соседних чисел? (сжимаем диапазон)

2. При кодировании результата разделяем на два потока значение количества
нулевых битов перед первым значащим битом в конечном числе и собственно
значение. Второе, я так понимаю, сжать невозможно, а первое должно
сжиматься неплохо -- во-первых для кодирования нужно не более чем log2 m
(в нашем случае 5) бит. Во вторых распределение вероятностей будет
неравномерным, и тут можно воспользоваться каким-нибудь арифметическим
кодером.

Как отправная точка сойдет?

-- 
С уважением, Денис

http://freesource.info
----------------------------------------------------------------------------

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] вопрос про числа

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 1232 bytes --]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
> по возрастанию.  Для примера m=32, n порядка 10^3.
> 
> Вычислить энтропию и предложить оптимальную процедуру кодирования
> (сжатия) последовательности.  Сколько битов на число можно получить?
> 
> (Вопрос связан с тем, что нам нужно придумать компактное представление
> "множества строк".  Например каждую строку можно представить в виде её
> m-битного хеша.  Соответственно множество n строк можно представить
> в виде n*m битов.  Но всё-таки битов получается очень много, и их можно
> неплохо сжать.  Неплохо наварить на этом можно, вот что.  Осталось только
> придумать процедуру сжатия.
> 
> Иначе же существует эквивалентное представление в алфавите {0,1} с
> постоянными вероятностями.  А именно, каждое число из диапазона 0..2^m-1
> можно рассматривать как номер бита в битмапе из 2^m битов.  Тогда
> последовательность чисел можно перевести в битмап и сжать битмап
> побитово.  Проблема только в том что при побитовом кодировании/
> декодировании получается очень большой битмап и очень большой цикл.)

s/последовательность/неупорядоченное множество/


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] вопрос про числа

[Vladislav Zavjalov]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
> по возрастанию.  Для примера m=32, n порядка 10^3.
> 
> Вычислить энтропию и предложить оптимальную процедуру кодирования
> (сжатия) последовательности.  Сколько битов на число можно получить?

То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
находится среди них. Хранить хочется меньше, чем n*m бит.

Я бы попробовал посмотреть паковку на такую тему:
Делим весь диапазон пополам, сохраняем два бита: попадание чисел из
множества в каждую половину.
Для тех половин, где числа есть - повторяем процедуру.

Но это так, первая идея без обоснования :)

Слава

Re: [devel] вопрос про числа

[Vladislav Zavjalov]

> То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
> находится среди них. Хранить хочется меньше, чем n*m бит.
> 
> Я бы попробовал посмотреть паковку на такую тему:

Эх, только вот эксперимент показывает, что такая паковка эффективна
только при достаточно больших n. При n=1000 и m=32 коэффициент паковки у меня
получился 1.38... Так что я неправильно подумал...

Слава

Re: [devel] вопрос про числа

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 958 bytes --]

On Sun, Nov 08, 2009 at 12:35:51AM +0300, Vladislav Zavjalov wrote:
> > То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
> > находится среди них. Хранить хочется меньше, чем n*m бит.
> > 
> > Я бы попробовал посмотреть паковку на такую тему:
> 
> Эх, только вот эксперимент показывает, что такая паковка эффективна
> только при достаточно больших n. При n=1000 и m=32 коэффициент паковки у меня
> получился 1.38... Так что я неправильно подумал...

Что-то у Вас слишком хороший коэффициент получился.  У меня получается
энтропия 23.477 бита супротив 32 то максимально возможный коэффициент
сжатия по идее должен быть 1.36.

$ perl -le 'sub log2{log($_[0])/log(2)}; sub H{my$p=shift;-$p*log2($p)-(1-$p)*log2(1-$p)}; $n=1000;$m=32; $bits_per_hash=(1<<$m)/$n; print H(1/$bits_per_hash)*$bits_per_hash'
23.4769105882751
$

Я правда не уверен что это правильная энтропия получается (через
эквивалентность по битмапу).

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] вопрос про числа

[Денис Смирнов]

[-- Attachment #1: Type: text/plain, Size: 813 bytes --]

On Sun, Nov 08, 2009 at 01:34:21AM +0300, Алексей Турбин wrote:

AT> Что-то у Вас слишком хороший коэффициент получился.  У меня получается
AT> энтропия 23.477 бита супротив 32 то максимально возможный коэффициент
AT> сжатия по идее должен быть 1.36.
AT> $ perl -le 'sub log2{log($_[0])/log(2)}; sub H{my$p=shift;-$p*log2($p)-(1-$p)*log2(1-$p)}; $n=1000;$m=32; $bits_per_hash=(1<<$m)/$n; print H(1/$bits_per_hash)*$bits_per_hash'
AT> 23.4769105882751
AT> $
AT> Я правда не уверен что это правильная энтропия получается (через
AT> эквивалентность по битмапу).

С моим методом на той тестовой выборке что у меня сгенерировалось у меня
экономия в полтора раза получается.

-- 
С уважением, Денис

http://freesource.info
----------------------------------------------------------------------------

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] вопрос про числа

[Vladislav Zavjalov]

On Sun, Nov 08, 2009 at 01:34:21AM +0300, Alexey Tourbin wrote:
> On Sun, Nov 08, 2009 at 12:35:51AM +0300, Vladislav Zavjalov wrote:
> > > То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
> > > находится среди них. Хранить хочется меньше, чем n*m бит.
> > > 
> > > Я бы попробовал посмотреть паковку на такую тему:
> > 
> > Эх, только вот эксперимент показывает, что такая паковка эффективна
> > только при достаточно больших n. При n=1000 и m=32 коэффициент паковки у меня
> > получился 1.38... Так что я неправильно подумал...
> 
> Что-то у Вас слишком хороший коэффициент получился.  У меня получается
> энтропия 23.477 бита супротив 32 то максимально возможный коэффициент
> сжатия по идее должен быть 1.36.
> 
> $ perl -le 'sub log2{log($_[0])/log(2)}; sub H{my$p=shift;-$p*log2($p)-(1-$p)*log2(1-$p)}; $n=1000;$m=32; $bits_per_hash=(1<<$m)/$n; print H(1/$bits_per_hash)*$bits_per_hash'
> 23.4769105882751
> $
> 
> Я правда не уверен что это правильная энтропия получается (через
> эквивалентность по битмапу).

Я плохо выразился, при небольших n у меня оказалось все совсем плохо, происходит не сжатие, а расширение :)

Слава

Re: [devel] вопрос про числа

[Vladislav Zavjalov]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
> по возрастанию.  Для примера m=32, n порядка 10^3.
> 
> Вычислить энтропию и предложить оптимальную процедуру кодирования
> (сжатия) последовательности.  Сколько битов на число можно получить?

А вот еще одна идея, наоборот, для малых n.

Если у нас два числа, можно использовать 2m-1 бита для их хранения,
выиграть один бит, так как порядок чисел не важен.
Достигается это легко: если считать все по модулю 2^m, то у нас есть два
числа и два непрерывных диапазона остальных чисел.
Один из этих диапазонов меньше чем (2^m)/2.
То число, перед которым пустой диапазон больше, запишем явно, m битами.
Кроме того, запишем расстояние от него до второго числа, m-1 битами.

Если чисел n, будем действовать похоже: Выберем максимальное расстояние
между соседними числами (оно больше чем (m^2)/n). Запишем число, стоящее
после этого максимального пустого диапазона.
Оставшихся вне максимального диапазона чисел меньше чем (2^m)(1-1/n).
Повторим для них ту же процедуру, считая числа от начала этого нового
диапазона по модулю (2^n)(1-1/n).
Получим последовательную запись всех наших n чисел, причем ограничения
на их размер будут такими:

(2^m)
(2^m)(1 - 1/n)
(2^m)(1 - 1/n)(1 - 1/(n-1))
...
(2^m)(1 - 1/n)(1 - 1/(n-1)) ... ( 1 - 1/2)

Если я не ошибаюсь, энтропия такого набора:
m*n + \sum_{i=1}^{n-1} [ (n-i) \log (1 - 1/(n-i+1)) ]
Для n=1000 и m=32 это 30.6 бит на число...

Слава

Re: [devel] вопрос про числа

[Kharitonov A. Dmitry]

Vladislav Zavjalov wrote:
> On Sun, Nov 08, 2009 at 01:34:21AM +0300, Alexey Tourbin wrote:
>   
>> On Sun, Nov 08, 2009 at 12:35:51AM +0300, Vladislav Zavjalov wrote:
>>     
>>>> То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
>>>> находится среди них. Хранить хочется меньше, чем n*m бит.
>>>>
>>>> Я бы попробовал посмотреть паковку на такую тему:
>>>>         
>>> Эх, только вот эксперимент показывает, что такая паковка эффективна
>>> только при достаточно больших n. При n=1000 и m=32 коэффициент паковки у меня
>>> получился 1.38... Так что я неправильно подумал...
>>>       
>> Что-то у Вас слишком хороший коэффициент получился.  У меня получается
>> энтропия 23.477 бита супротив 32 то максимально возможный коэффициент
>> сжатия по идее должен быть 1.36.
>>
>> $ perl -le 'sub log2{log($_[0])/log(2)}; sub H{my$p=shift;-$p*log2($p)-(1-$p)*log2(1-$p)}; $n=1000;$m=32; $bits_per_hash=(1<<$m)/$n; print H(1/$bits_per_hash)*$bits_per_hash'
>> 23.4769105882751
>> $
>>
>> Я правда не уверен что это правильная энтропия получается (через
>> эквивалентность по битмапу).
>>     
>
> Я плохо выразился, при небольших n у меня оказалось все совсем плохо, происходит не сжатие, а расширение :)
>   
Вообще-то у вас получается не паковка, а сортировка.

Re: [devel] вопрос про числа

[Kharitonov A. Dmitry]

Vladislav Zavjalov wrote:
> On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
>   
>> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
>> по возрастанию.  Для примера m=32, n порядка 10^3.
>>
>> Вычислить энтропию и предложить оптимальную процедуру кодирования
>> (сжатия) последовательности.  Сколько битов на число можно получить?
>>     
>
> А вот еще одна идея, наоборот, для малых n.
>
> Если у нас два числа, можно использовать 2m-1 бита для их хранения,
> выиграть один бит, так как порядок чисел не важен.
> Достигается это легко: если считать все по модулю 2^m, то у нас есть два
> числа и два непрерывных диапазона остальных чисел.
> Один из этих диапазонов меньше чем (2^m)/2.
> То число, перед которым пустой диапазон больше, запишем явно, m битами.
> Кроме того, запишем расстояние от него до второго числа, m-1 битами.
>
> Если чисел n, будем действовать похоже: Выберем максимальное расстояние
> между соседними числами (оно больше чем (m^2)/n). Запишем число, стоящее
> после этого максимального пустого диапазона.
> Оставшихся вне максимального диапазона чисел меньше чем (2^m)(1-1/n).
> Повторим для них ту же процедуру, считая числа от начала этого нового
> диапазона по модулю (2^n)(1-1/n).
> Получим последовательную запись всех наших n чисел, причем ограничения
> на их размер будут такими:
>
> (2^m)
> (2^m)(1 - 1/n)
> (2^m)(1 - 1/n)(1 - 1/(n-1))
> ...
> (2^m)(1 - 1/n)(1 - 1/(n-1)) ... ( 1 - 1/2)
>
> Если я не ошибаюсь, энтропия такого набора:
> m*n + \sum_{i=1}^{n-1} [ (n-i) \log (1 - 1/(n-i+1)) ]
> Для n=1000 и m=32 это 30.6 бит на число...
>   
Тот же LZMA намного эффективней.
А чем он собсвенно не подходит? хороший потоковый упаковщик с 
динамической кодовой книгой те требует не много памяти.

Re: [devel] вопрос про числа

[Vladislav Zavjalov]

On 11/09/09 15:48, Kharitonov A. Dmitry wrote
> Тот же LZMA намного эффективней.
> А чем он собсвенно не подходит? хороший потоковый упаковщик с
> динамической кодовой книгой те требует не много памяти.

Но интересно же попридумывать. :) А реальную программу, мне кажется, 
вряд ли украсит суровая самодельная паковка ради 20% экономии памяти...

Слава

Re: [devel] вопрос про числа

[Vladislav Zavjalov]

>> Я плохо выразился, при небольших n у меня оказалось все совсем плохо,
>> происходит не сжатие, а расширение :)
> Вообще-то у вас получается не паковка, а сортировка.

Ну да, скорее сортировка. Но во-первых тут это может быть даже более 
ценно, а во-вторых, для бОльших n этот алгоритм-таки сжимает.

Слава

Re: [devel] вопрос про числа

[Kharitonov A. Dmitry]

Vladislav Zavjalov wrote:
>>> Я плохо выразился, при небольших n у меня оказалось все совсем плохо,
>>> происходит не сжатие, а расширение :)
>> Вообще-то у вас получается не паковка, а сортировка.
>
> Ну да, скорее сортировка. Но во-первых тут это может быть даже более 
> ценно, а во-вторых, для бОльших n этот алгоритм-таки сжимает.
Большой объём кодовой книги всё портит
Эффект сжатия в основном достигается за счёт повторяемости данных, для 
хеша это вообще не актуально.

Re: [devel] вопрос про числа

[Michael Shigorin]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
> Вычислить энтропию и предложить оптимальную процедуру кодирования
> (сжатия) последовательности.  Сколько битов на число можно получить?

Почитай fingerprint theory на daylight.com -- возможно,
и какой-то код дадут (если окажется не привязанным к специфике
SMILES).

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/