Lex об архиваторах

Форум для предварительного обсуждения тем.
Прежде чем организовать обсуждение в отдельном форуме, полезно убедиться, что четко понимаешь о чем говоришь.
Dmitry_Milk
Posts: 396
Joined: Sat Apr 15, 2006 5:59 am
Location: Казань
Contact:

Post by Dmitry_Milk » Sat Jun 07, 2008 7:49 pm

Да, и еще. Получается, что в ващем эксперименте RAR откровенно схалтурил. Даже если не заморачиваться с дробным количеством бит на каждый 9-значный кусок и не учитывать не ровно 50% вероятность 3-го слева бита в 32-битном числе, то все равно видно невооруженным глазом, что два самых старших бита в каждом 32-битном кусочке всегда нулевые. То есть можно даже просто было брать из каждого такого 32-битного кусочка только по 30 бит, сэкономив при этом по 2 бита на каждый 9-значный кусок. То есть, файл из 444 444 байт должен был превратиться в 416666.

Хотя, возможно, в оставшемся рар положил информацию о закономерностях, тогда мои извинения рару :)

Preobragenskiy
Posts: 1030
Joined: Sun Sep 05, 2004 11:45 am
Location: Киев

Post by Preobragenskiy » Sat Jun 07, 2008 10:31 pm

Dmitry_Milk wrote:
Preobragenskiy wrote:Вод код конверта текстового файла в бинарный.
(16 ти ричное число пи представлено бинарном формате)
Очень странный у вас конвертор. Это же не перевод десятичной дроби в двоичную. Вы просто разбили дробь на куски по 9 цифр и каждый кусок заменили 32-битным числом, независимо от других кусков. А этим вы опять внесли избыточность, ведь информационная емкость 9-значного десятичного числа - 3,32192809488736234787031942948939 * 9 = 29,8973528539862611308328748654045 бит. Накаждый такой кусок по 9 десятичных цифр вы недоиспользовали по 2,10264714601373886916712513459549 бит, а на всю последовательность вы растранжирили 233627,460668193207685236126066165 бита (почти 29 килобайт).
Есть такое :) Можете попробовать переписать, у меня нашлось только пятнадцать минут на эту задачу :wink:
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

Dmitry_Milk
Posts: 396
Joined: Sat Apr 15, 2006 5:59 am
Location: Казань
Contact:

Post by Dmitry_Milk » Sun Jun 08, 2008 1:16 pm

Ну уж нееет :) Реализовывать трехмилионобитную арифметику, да еще с операцией деления, а потом еще и ждать, пока на этом выполнится миллион делений и сложений - увольте. Я и так верю, что пи - самый шумный шум :)

Lex
Posts: 1862
Joined: Thu Aug 26, 2004 8:12 pm

Post by Lex » Sun Jun 08, 2008 2:15 pm

2 egg

Да нет особого смысла писать. Для белого шума можно посчитать теоретический предел сжатия. Правда считать долго )) я прикинул и понял что за час не сделать.
весь мир, бензин и спички ;)

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Mon Jun 09, 2008 1:42 am

Preobragenskiy wrote:
Inex wrote: а сжатие знаков числа пи? у него нет периода...
[читать инфу - принципы сжатия архиватором]
это ты себе пометку сделал? :P
могу сразу сказать, что ни один существующий архиватор не сожмет (разве что на уровне неравномерности цифр в числе пи, если такая неравномерность имеется)
Last edited by Inex on Mon Jun 09, 2008 1:53 am, edited 1 time in total.
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Mon Jun 09, 2008 1:46 am

Shuklin wrote: Однако есть небольшая вероятность что архиватор будет архи продвинут, догадается что ему подсунули Пи с N-го по M-ый знак, так и запишет, Число Пи с N-ой по M-ую позиции ))
Ну а при деархивировании пересчитает все заново.

Еще более продвинутый архиватор сможет сжать даже последовательность знаков Пи, содержащей небольшое число браков. В качестве предсказанной последовательности возьмет правильное значение Пи, а браки будут учтены арифметиком.
нету щас таких архиваторов и с большой вероятностью не появятся
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Mon Jun 09, 2008 1:52 am

Dmitry_Milk wrote:Ну уж нееет :) Реализовывать трехмилионобитную арифметику, да еще с операцией деления, а потом еще и ждать, пока на этом выполнится миллион делений и сложений - увольте.
можно поступить проще: выкинуть из пи все циферки 8 и 9, а с 0 по 7 закодировать 3 битами
Это, конечно, уже будет не совсем пи, но для простоты сгодится...
а можно просто построить гистограммы распределений цифр и пар цифр числа пи (кстати, действительно интересно, насколько оно равномерное)
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Preobragenskiy
Posts: 1030
Joined: Sun Sep 05, 2004 11:45 am
Location: Киев

Post by Preobragenskiy » Mon Jun 09, 2008 3:21 am

Inex wrote:
Preobragenskiy wrote:
Inex wrote: а сжатие знаков числа пи? у него нет периода...
[читать инфу - принципы сжатия архиватором]
это ты себе пометку сделал? :P
могу сразу сказать, что ни один существующий архиватор не сожмет (разве что на уровне неравномерности цифр в числе пи, если такая неравномерность имеется)
на вотетом "разве что" и построены все архиваторы :)

А неравномерность безусловно в числе Пи имеется :)
Вот если Пи сжать архиватором одним, потом полученный архив другим, потом третем и четвертым ... тогда, возможно, число пи будет куда более равномерной случайной величиной :wink:

(Кстате повторно архив мне сжать не удалось, естественно. 0%) :)
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

Preobragenskiy
Posts: 1030
Joined: Sun Sep 05, 2004 11:45 am
Location: Киев

Post by Preobragenskiy » Mon Jun 09, 2008 3:26 am

Inex wrote:
Dmitry_Milk wrote:Ну уж нееет :) Реализовывать трехмилионобитную арифметику, да еще с операцией деления, а потом еще и ждать, пока на этом выполнится миллион делений и сложений - увольте.
можно поступить проще: выкинуть из пи все циферки 8 и 9, а с 0 по 7 закодировать 3 битами
Это, конечно, уже будет не совсем пи, но для простоты сгодится...
а можно просто построить гистограммы распределений цифр и пар цифр числа пи (кстати, действительно интересно, насколько оно равномерное)
кстате это интересная задача для программиста, подозреваю перевод числа из миллиона разрядов всеже имеет довольно компактное решение :D
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Mon Jun 09, 2008 9:59 am

Preobragenskiy wrote: на вотетом "разве что" и построены все архиваторы :)
ну речь-то идет о том, чтобы сжать выше этой элементарной избыточности... сложность числа пи составляет всего сотню байт, поэтому идеальный архиватор мог бы сжать 1е+6 знаков пи до этой сотни байт, а вовсе не до полумегабайта...
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Lex
Posts: 1862
Joined: Thu Aug 26, 2004 8:12 pm

Post by Lex » Tue Jun 10, 2008 7:22 am

Inex wrote:числа пи составляет всего сотню байт, поэтому идеальный архиватор мог бы сжать 1е+6 знаков пи до этой сотни байт, а вовсе не до полумегабайта...
Там сложность в сотню байт при условии что вы владеете математикой на уровне Архемеда. Тут есть эффект декомпозиции и как следствие сокращение объемов. Если нет понимая (модели объекта), то придется жать как поток битов.
весь мир, бензин и спички ;)

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Tue Jun 10, 2008 9:44 am

Lex wrote: Там сложность в сотню байт при условии что вы владеете математикой на уровне Архемеда.
там сложность в сотню байт, если вы сишный компилятор
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Lex
Posts: 1862
Joined: Thu Aug 26, 2004 8:12 pm

Post by Lex » Tue Jun 10, 2008 10:02 am

Как варант, но сути это не меняет. Нужно что то еще для декомпозиции. Некое внешне знание ( система).
весь мир, бензин и спички ;)

Locked

Who is online

Users browsing this forum: No registered users and 2 guests