From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Sun, 8 Nov 2009 23:45:38 +0300 From: Vladislav Zavjalov To: ALT Linux Team development discussions Message-ID: <20091108204538.GA17792@imap.altlinux.org> References: <20091107193402.GD10659@altlinux.org> Mime-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20091107193402.GD10659@altlinux.org> User-Agent: Mutt/1.4.2.3i 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: Sun, 08 Nov 2009 20:45:38 -0000 Archived-At: List-Archive: List-Post: 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 бит на число... Слава