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

Форум для предварительного обсуждения тем.
Прежде чем организовать обсуждение в отдельном форуме, полезно убедиться, что четко понимаешь о чем говоришь.
Lex
Posts: 1862
Joined: Thu Aug 26, 2004 8:12 pm

Post by Lex » Fri Jun 06, 2008 2:30 pm

Preobragenskiy wrote: и это кстате косвенно доказывает любой архиватор который умудряется сжать любой достаточно большой блок "случайных" данных, пускай на долю процента. Значит закономерность всеже есть, за счет чего и сжимаются данные
Не один архиватор не возьмет последовательность от полинома Галуа и уж темболее не возьмет белый шум. В последовательности Галуа нет ни одного повторяющегося числа.

Все архиваторы которые могу сжить на 0.0001% белый шум достигают этого за счет автоматной декомпозиции. Это всегда частный случай.
Абсолютный белый шум это бесконечное количество закономерностей ?

В точку.
весь мир, бензин и спички ;)

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

Post by Lex » Fri Jun 06, 2008 2:52 pm

DS wrote:А если мне дадут непериодичеки покрытую плоскость, то я смогу сказать только, что элементы бывают стольки-то типов, стыкуются те-то с теми-то и каждый тип в покрытии встречается с такой-то частотой. Все. Это не сложно.
Это бесконечная плоскость покрытая точками двух цетов. В конечномерном случае это сводимо к бесконечной последовательности чисел. Потеря в точности при переходе к конечномерному пространсву дает невероятную сложность скрытых в этой последовательности гармоник.
весь мир, бензин и спички ;)

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

Post by Preobragenskiy » Fri Jun 06, 2008 3:12 pm

Lex wrote: Не один архиватор не возьмет последовательность от полинома Галуа
Если Галуа - это белый шум.
Lex wrote: и уж темболее не возьмет белый шум.
Согласен, там где нет закономерностей, а распределение абсолютно ровное, там ему делать нечего :)
Lex wrote: В последовательности Галуа нет ни одного повторяющегося числа.
У него есть период, пусть и очень большой, а это означает что сжатие возможно. Конечно может быть не Раром или Зипом, но тем не менее.
Lex wrote: Все архиваторы которые могу сжить на 0.0001% белый шум достигают этого за счет автоматной декомпозиции. Это всегда частный случай.
Этого не понял. Если архиватору удалось поиметь пускай даже 0.0001%, это уже означает что в простейшем случае одинаковые блоки отличные от одного байта встречаются настолько часто, что мы выигрываем в сжатии даже если к файлу допишем таблицу часто встречающихся комбинаций.
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

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

Post by Inex » Sat Jun 07, 2008 8:25 am

Preobragenskiy wrote:У него есть период, пусть и очень большой, а это означает что сжатие возможно. Конечно может быть не Раром или Зипом, но тем не менее.
а сжатие знаков числа пи? у него нет периода...
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

DS
Posts: 949
Joined: Tue Jan 06, 2004 6:17 am

Post by DS » Sat Jun 07, 2008 2:00 pm

Lex wrote:Это бесконечная плоскость покрытая точками двух цетов. В конечномерном случае это сводимо к бесконечной последовательности чисел. Потеря в точности при переходе к конечномерному пространсву дает невероятную сложность скрытых в этой последовательности гармоник.
Я бы даже сказал немыслимую сложность. Т.е. субъективно отсутствующую, не принимаемую во внимание. Потому как делать-то с ней что? А вот "мыслимая" сложность, т.е. собственно сложность, это когда вы сталкиваетесь с явлением и видите, что протекает оно по каким-то законам, и сознаете, что понять их будет нелегко, но все-таки возможно.
Мне вот как-то гипотетический робот ищущий разетку по памяти, по каким-то косвенным признакам, и вынужденно прибегающий к полностью случайному поиску в отсутствие таковых, кажется все же посложнее робота, который ищет всегда случайно. Я об этом.

зы. белый шум - это когда отсчеты случайной величины во времени некоррелированы между собой. При этом сама случайная величина может иметь любое распределение, например нормальное. Т.е. все должно жаться кодом Хаффмана на ура. Есть одно исключение, когда распределение равномерное. Это не жмется никак. Называется равномерный шум.

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

Post by Preobragenskiy » Sat Jun 07, 2008 3:42 pm

Inex wrote:
Preobragenskiy wrote:У него есть период, пусть и очень большой, а это означает что сжатие возможно. Конечно может быть не Раром или Зипом, но тем не менее.
а сжатие знаков числа пи? у него нет периода...
[читать инфу - принципы сжатия архиватором]

а вообще можно попробовать :)

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

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

Post by Preobragenskiy » Sat Jun 07, 2008 3:47 pm

eveandersson.com/pi/digits/1000000.txt

нашел до миллионного знака, теперь его нужно перевести из текстового в бинарный файл ( текстовый файл сам по себе жмется хорошо из-за того что использует только 30-35 символов из 256 мощности на байт ). В текстовом формате степень сжатия Раром составила >50%
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

Shuklin
Posts: 339
Joined: Thu Jun 16, 2005 3:41 pm
Location: Харьков
Contact:

Post by Shuklin » Sat Jun 07, 2008 4:10 pm

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

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

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

Post by Preobragenskiy » Sat Jun 07, 2008 4:36 pm

Рар версии 3.0, поимел 3 319 байт, что составляет почти 1% :wink:


Точнее 444,444 bytes -> 441,125 bytes

Вод код конверта текстового файла в бинарный.
(16 ти ричное число пи представлено бинарном формате)

Code: Select all

private void button1_Click(object sender, EventArgs e)
        {
            System.IO.StreamReader sr = new System.IO.StreamReader("D:\\DriversXP\\1000000.txt");
            System.Collections.ArrayList s = ToHex(sr.ReadToEnd());
            sr.Close();

            System.IO.FileStream sw = new System.IO.FileStream("D:\\DriversXP\\hex.txt", System.IO.FileMode.CreateNew);
            foreach(int i in s)
                foreach(byte b in BitConverter.GetBytes(i))
                sw.WriteByte(b);
            sw.Close();

        }

        public static System.Collections.ArrayList ToHex(string plainText)
        {
            plainText = plainText.Replace("\n", "");

            System.Collections.ArrayList al = new System.Collections.ArrayList();
            char[] charArray = plainText.ToCharArray();

            string output = "";

            for (int i = 0; i < plainText.Length - 9; i+=9)
            {
                int num = Convert.ToInt32(plainText.Substring(i, 9));
                al.Add(num);
            }

            return al;
        }
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

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

Post by Preobragenskiy » Sat Jun 07, 2008 4:45 pm

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

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

Egg
Posts: 2693
Joined: Fri Jan 02, 2004 9:13 pm
Location: Boulder, CO
Contact:

Post by Egg » Sat Jun 07, 2008 5:26 pm

давайте лучше проводем внутренний конкурс на архиватор "белого" шума или просто ПСЧ последовательности...
с одной стороны померяемся различными частями тела, а с другой стороны - получим эксперимтальный материал для анализа...
Давайте уже отделять котят от котлет!

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

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

Egg wrote:давайте лучше проводем внутренний конкурс на архиватор "белого" шума или просто ПСЧ последовательности...
с одной стороны померяемся различными частями тела, а с другой стороны - получим эксперимтальный материал для анализа...
Чтобы ставить опыты нужно иметь какойто набор вопросов, на которые предполагается получить ответ :wink:
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

Egg
Posts: 2693
Joined: Fri Jan 02, 2004 9:13 pm
Location: Boulder, CO
Contact:

Post by Egg » Sat Jun 07, 2008 5:46 pm

Preobragenskiy wrote:Чтобы ставить опыты нужно иметь какойто набор вопросов, на которые предполагается получить ответ
ну например, можно ли ужать белый шум не менее, чем на 2%... :)
Давайте уже отделять котят от котлет!

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

Post by Preobragenskiy » Sat Jun 07, 2008 6:28 pm

Egg wrote:
Preobragenskiy wrote:Чтобы ставить опыты нужно иметь какойто набор вопросов, на которые предполагается получить ответ
ну например, можно ли ужать белый шум не менее, чем на 2%... :)
результаты опыта - идеальный белый шум сжать не удалось, все что удалось - не идеальный белый шум :wink:
"Зачем пытаться искуственно выращивать людей, если каждая баба может нарожать их без всякой медицины?"
прф. Преображенский из к/ф "Собачье сердце"

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

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

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

Locked

Who is online

Users browsing this forum: No registered users and 1 guest