From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on sa.int.altlinux.org X-Spam-Level: X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00,SPF_PASS autolearn=ham version=3.2.5 Message-ID: <4AF80F86.8020609@rambler.ru> Date: Mon, 09 Nov 2009 15:48:06 +0300 From: "Kharitonov A. Dmitry" User-Agent: Thunderbird 2.0.0.21 (X11/20090323) MIME-Version: 1.0 To: ALT Linux Team development discussions References: <20091107193402.GD10659@altlinux.org> <20091108204538.GA17792@imap.altlinux.org> In-Reply-To: <20091108204538.GA17792@imap.altlinux.org> Content-Type: text/plain; charset=KOI8-R; format=flowed Content-Transfer-Encoding: 8bit Subject: Re: [devel] =?koi8-r?b?18/Q0s/TINDSzyDeydPMwQ==?= X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 09 Nov 2009 12:44:08 -0000 Archived-At: List-Archive: List-Post: 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 намного эффективней. А чем он собсвенно не подходит? хороший потоковый упаковщик с динамической кодовой книгой те требует не много памяти.