From: "Денис Смирнов" <mithraen@altlinux.ru> To: ALT Linux Team development discussions <devel@lists.altlinux.org> Subject: Re: [devel] вопрос про числа Date: Sat, 7 Nov 2009 22:54:36 +0300 Message-ID: <20091107195436.GA16968@mw.office.seiros.ru> (raw) In-Reply-To: <20091107193402.GD10659@altlinux.org> [-- 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 --]
next prev parent reply other threads:[~2009-11-07 19:54 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 ` Денис Смирнов [this message] 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 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=20091107195436.GA16968@mw.office.seiros.ru \ --to=mithraen@altlinux.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