From: "Kharitonov A. Dmitry" <kharpost@rambler.ru>
To: ALT Linux Team development discussions <devel@lists.altlinux.org>
Subject: Re: [devel] вопрос про числа
Date: Mon, 09 Nov 2009 15:48:06 +0300
Message-ID: <4AF80F86.8020609@rambler.ru> (raw)
In-Reply-To: <20091108204538.GA17792@imap.altlinux.org>
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 намного эффективней.
А чем он собсвенно не подходит? хороший потоковый упаковщик с
динамической кодовой книгой те требует не много памяти.
next prev parent reply other threads:[~2009-11-09 12:48 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-11-07 19:34 Alexey Tourbin
2009-11-07 19:54 ` Денис Смирнов
2009-11-07 20:09 ` Dmitry V. Levin
2009-11-07 20:39 ` Vladislav Zavjalov
2009-11-07 21:35 ` Vladislav Zavjalov
2009-11-07 22:34 ` Alexey Tourbin
2009-11-08 0:18 ` Денис Смирнов
2009-11-08 4:02 ` Vladislav Zavjalov
2009-11-09 12:31 ` Kharitonov A. Dmitry
2009-11-09 13:06 ` Vladislav Zavjalov
2009-11-09 13:48 ` Kharitonov A. Dmitry
2009-11-08 20:45 ` Vladislav Zavjalov
2009-11-09 12:48 ` Kharitonov A. Dmitry [this message]
2009-11-09 13:04 ` Vladislav Zavjalov
2009-11-12 18:35 ` Michael Shigorin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4AF80F86.8020609@rambler.ru \
--to=kharpost@rambler.ru \
--cc=devel@lists.altlinux.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
ALT Linux Team development discussions
This inbox may be cloned and mirrored by anyone:
git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
public-inbox-index devel
Example config snippet for mirrors.
Newsgroup available over NNTP:
nntp://lore.altlinux.org/org.altlinux.lists.devel
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git