ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Об одном парадоксе информационной энтропии
23 сообщений из 48, страница 2 из 2
  2  все
Об одном парадоксе информационной энтропии
    #39582064
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Иван FXS задачка в том, как при таком перекодировании обойтись без "словаря перевода", либо с таким словарём, который не перекрыл бы (своей длиной) весь эффект сжатия. ИМХО, никак.


Иван FXS чувствуете подвох: получается, что абсолютно случайная последовательность битов не сжимается (хотя лично всё ещё тлеет надежда) из-за того, что в ней предельно много информации! Так и есть.
В абсолютно случайной последовательности ни один элемент не сводится к остальным, поэтому информация там максимальна.
...
Рейтинг: 0 / 0
10.01.2018, 20:29
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582141
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSИ есть хорошие шансы надеяться, что “выигрыш” (в числе битов) от этого сжатия будет больше, чем длина в битах записи числа Х. И даже (возможно, особенно если N велико) больше, чем длина в битах алгоритма нашего ДПСЧ, записанного на каком-то “экономном” байт-коде...

Можно, наконец, явно произнести, что, зная только Х, мы всегда можем повторно сгенерировать строку Z и, вычтя её из R, получить исходную S.
Скорее всего нет. Потому-что для достижения такой точности мы должны будем параметризировать наш ДПСЧ
очень точно. Считайте что калибровка начального параметра seed будет стоить столь-же дорого как и вся
ваша сжимаемая последовательность.
...
Рейтинг: 0 / 0
10.01.2018, 23:53
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582142
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
BarloneНикакой архиватор случайную последовательность не сожмет.
сжать произвольную (в т.ч. "случайную") строку S можно (попробовать), например, так:

1. найти в ней 2 (прописью: две ) одинаковых подстроки Zi (Z1 и Z2), желательно подлиннее;

2. в выходной поток записать сначала три числа: длину Zi, адрес Z1, адрес Z2. Потом - саму подстроку Zi. Потом -- строку S', представляющую собой S, из которой выброшены Z1 и Z2.

Как вы считаете, это очень редкая ситуация и трудная задача? Для достаточно длинной и достаточно случайной строки S -- очень ли велика вероятность, что в ней не удастся найти Z1 и Z2 такие, что длина Zi больше длины, необходимой, чтобы разместить три числа?
...
Рейтинг: 0 / 0
10.01.2018, 23:56
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582147
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSА префиксное кодирование, например, специально занимается тем, что выравнивает (как можно лучше) частоты слов. С учётом длин, конечно: все слова длиной 8 бит должны иметь частоты, в идеале, равные 1/256; а слова длиной 10 бит -- равные 1/1024 ...
Префиксное кодирование достаточно грубое. Особенно на частых значениях (там где префисное дерево
сворачивает в листики на коротких ветвях). Если взять английский текст (где уже посчитана
плотность сжатия в 2 бита на символ) и применить к нему хаффмена или шеннона-фано
то вы ожидаемых 25% не получите.

В идеале для частотного сжатия используют арифметический кодер (как в Winrar) но я подозреваю
что подкапотом у хорошего текстового архиватора стоит целый конвейер методов. И арифметика
это просто часть этого стека которая слегка улучшает энтропию.
...
Рейтинг: 0 / 0
11.01.2018, 00:04
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582150
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
mayton,

что такое "точность параметризации" ДПСЧ? И что такое калибровка начального параметра seed?

Разве мы говорим про ДСЧ на основании "теплового шума" (какого-нибудь кристалла), а не про алгоритмический ДПСЧ (который абсолютно детерминирован, ибо суть алгоритм)?
...
Рейтинг: 0 / 0
11.01.2018, 00:06
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582154
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSКак вы считаете, это очень редкая ситуация и трудная задача? Для достаточно длинной и достаточно случайной строки S -- очень ли велика вероятность, что в ней не удастся найти Z1 и Z2 такие, что длина Zi больше длины, необходимой, чтобы разместить три числа?
(Я прошу прощения. Я отвечаю по топику и снизу одновременно).

Я думаю что тут задача похожа на транспортную. Возможно мы будем стоять в условии выбора.
Мы нашли 3 последовательности по 5 бит. И 5 последовательностей по 3 бита. И вообще...
Мы не в состоянии спрогнозировать как будет выглядеть исходная последовательность
ПОСЛЕ того как мы уже поджали ее. Возможно появятся цепочки бит которые снова
можно поджать и т.д. А возможно стоит рекурсивно вернуться назад и взять 2 бита по 7. И еще
раз...

Вобщем это задача оуенно трудная. И что обидно - пока без перспективы выйти на какой-то
гарантированный результат.

P.S. маленькие но по три рубля
большие по пять рублей
(с) Роман Карцев
...
Рейтинг: 0 / 0
11.01.2018, 00:14
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582155
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSmayton,

что такое "точность параметризации" ДПСЧ? И что такое калибровка начального параметра seed?

Разве мы говорим про ДСЧ на основании "теплового шума" (какого-нибудь кристалла), а не про алгоритмический ДПСЧ (который абсолютно детерминирован, ибо суть алгоритм)?
Все верно. Я имею в виду псевдо-случайный ГСЧ.
...
Рейтинг: 0 / 0
11.01.2018, 00:15
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582159
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
maytonМы не в состоянии спрогнозировать как будет выглядеть исходная последовательность
ПОСЛЕ того как мы уже поджали ее.
почему "не в состоянии спрогнозировать", если мы производим с ней формальные операции?

Может, нужен пример? Вот "случайная" последовательность (слегка подшаманенная, да):

JHDBCEBVJEGGB ABCD KJFDBNCDKMNEJLLCMVPW ABCD ELHLMAKSHFIHJKDPPWL

вот она же "сжатая":

4 К1 К2 ABCD JHDBCEBVJEGGB KJFDBNCDKMNEJLLCMVPW ELHLMAKSHFIHJKDPPWL

maytonВозможно мы будем стоять в условии выбора.
Мы нашли 3 последовательности по 5 бит. И 5 последовательностей по 3 бита.
можем посчитать, что нам выгоднее, а можем, не заморачиваясь, взять "по 5". И для демонстрации принципиальной возможности сжатия достаточно однократного повторов подстроки.
...
Рейтинг: 0 / 0
11.01.2018, 00:31
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582162
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИван FXS, я вот что подумал: если ты прав, т.е. твоя идея рабочая, то можно жать что угодно до бесконечности. Ну хотя бы в десятки раз. Например дистрибутив виндовса сжать до 1 Мб, пусть даже 100 Мб, думаю ради этого MS запустил бы перебор на пару месяцев.

Вывод: если бы это работало, то этим бы уже пользовались.
Я над этим давно думал. И пришел к концепции своего идеального архиватора текста.
Я рассмотрел три уровня.

Уровень символов (арифметика, хаффмен, PPM) уже все изпахано вдоль и поперек.
Уровень слогов (LZW), слов, (Dictionaries). Тоже исследовано. Архиватор-справочник уже вошел в
луркмоар и хабр как анекдот.
Уровень предложений (sentences). Здесь - неизвестно. Никто не знает как они строятся.
Вернее есть набор рулов. Но как описать творческий полёт пейсателя? Я подумал. А и не надо.
Sentences даже в русском языке строятся по определенному шаблону. Мне достаточно
проанализировать тексты одного автора. И построить по ним марковские модели (ММ). Грубо...
это выглядит как FSM у которого переходы имеют вероятности. При этом выходом ММ является
генерация шаблона sentences с привязкой к предыдущему sentence.

Я утверждаю что для генерации текста по моей модели мне достаточно делать сигналы управления
для данной ММ. При этом сигналы будут сжаты в силу заведомо известной мне энтропии.

Еще вопрос который я для себя не решил - каков размер будет самого описания ММ вместе
с структурой переходов.

Другие уровни. Стили. Части. Главы. . Модель должна рекурсивно включать в себя другие модели.
Например любое повествование содержит переходы от одного литературного стиля к другому.
...
Рейтинг: 0 / 0
11.01.2018, 00:35
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582164
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSпочему "не в состоянии спрогнозировать", если мы производим с ней формальные операции?

Может, нужен пример? Вот "случайная" последовательность (слегка подшаманенная, да):

JHDBCEBVJEGGB ABCD KJFDBNCDKMNEJLLCMVPW ABCD ELHLMAKSHFIHJKDPPWL

вот она же "сжатая":

4 К1 К2 ABCD JHDBCEBVJEGGB KJFDBNCDKMNEJLLCMVPW ELHLMAKSHFIHJKDPPWL

Это не есть прогноз. Во первых вы - искусственно упростили исходные данные. Вместо битов - символы.
Во вторых - вы подгадали алфавитную последовательность. Дайте мне биты и белый шум.

Но давайте отвлечемся. В смежном топике два "перца" уже 2 месяца спорят о задаче расстановки 8 ферзей.
Я даже потерял нить их диалога и не знаю о чем это. Фракталы, немцы какие-то конгрессы... Ну да бох с ним.

Вобщем... Эту задачу еще решал Гаусс. Он искал аналитическое (формульное) решение которое бы дало сразу
(мгновенно) ответ. По сути он хотел O(1) формулу. А ее нет. Дело в том что все комбинаторные задачи
и шахматы в том числе не имеют формульного решения. Они рекурсивны по своей природе и мы не можем
сделать оценку позиции пока не сделаем оценку позиции .... пока ... и так далее до шаха и мата.

Я считаю что данная задача (а именно оценка эффективности сжатия после применения замен) - рекурсивна.
...
Рейтинг: 0 / 0
11.01.2018, 00:46
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582165
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
maytonместо битов - символывсе, что есть в компе, суть биты.

maytonДайте мне ... белый шум. где ж я его возьму - вынь да положь?!

maytonискусственно упростили исходные данные Вообще, я сейчас полемизировал с утверждением: "никакой архиватор случайную последовательность не сожмет", причём даже его я слегка подшаманил -- до "никакой архиватор никакую случайную последовательность никогда никак не сожмет". И показал, что вполне тривиальный архиватор может иногда как-то сжимать некоторые случайные последовательности.
...
Рейтинг: 0 / 0
11.01.2018, 00:59
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582168
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSвсе, что есть в компе, суть биты.
Ох хитрец...

maytonгде ж я его возьму - вынь да положь?!
Linux есть? На сях кодишь?
...
Рейтинг: 0 / 0
11.01.2018, 01:06
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582238
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Еще подкину арихиватор над которым я думал. Если взять битовую последовательность длиной N
и циклически сдвинуть ее на 1 бит и сложнить по модулю два с оригинальной то
мы получим карту разностей.

Если мы будем продолжать циклическое вращение N раз то мы получим N вариантов разностей.
И если выберем ту разность где количество нулевых битов будет максимально - то скорее
всего мы нашли большую битовую под-последовательность которая несколько раз встречается
в оригинальной. Самоподобие или фрактал.

Далее - дело техники. Выделяем самые длинные последовательности нулей в разности и решаем,
добавлять их в справочник архиватора или нет.
...
Рейтинг: 0 / 0
11.01.2018, 09:20
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582240
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Иван FXSBarloneНикакой архиватор случайную последовательность не сожмет.
сжать произвольную (в т.ч. "случайную") строку S можно (попробовать), например, так:

1. найти в ней 2 (прописью: две ) одинаковых подстроки Zi (Z1 и Z2), желательно подлиннее;

2. в выходной поток записать сначала три числа: длину Zi, адрес Z1, адрес Z2. Потом - саму подстроку Zi. Потом -- строку S', представляющую собой S, из которой выброшены Z1 и Z2.

Как вы считаете, это очень редкая ситуация и трудная задача? Для достаточно длинной и достаточно случайной строки S -- очень ли велика вероятность, что в ней не удастся найти Z1 и Z2 такие, что длина Zi больше длины, необходимой, чтобы разместить три числа?Ну архиваторы примерно так и работают. Так что просто проверьте. Вот вам 16Мб случайная последовательность, сжимайте.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
#include <stdio.h>
#include <stdlib.h>
int main() {
 int i;
 unsigned char n;
 FILE *f;
 f = fopen("rand.dat","wb");

 for(i=0;i<16777216;++i)
 {
    n=rand()>>7;
    fwrite(&n,1,1,f);
 }
 fclose(f);
 return 0;
}
...
Рейтинг: 0 / 0
11.01.2018, 09:24
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582243
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Иван FXS Вообще, я сейчас полемизировал с утверждением: "никакой архиватор случайную последовательность не сожмет", причём даже его я слегка подшаманил -- до "никакой архиватор никакую случайную последовательность никогда никак не сожмет". И показал, что вполне тривиальный архиватор может иногда как-то сжимать некоторые случайные последовательности.Ну так-то можно случайность по разному понимать. Конечно случайная последовательность может совершенно случайно начаться с пары сотен нулевых битов.
или так https://xkcd.com/221/
...
Рейтинг: 0 / 0
11.01.2018, 09:33
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582249
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот из нашего CardRaytracer. Линейный конгруэнтный.
Константы M, J не единственные.
Кастинг в double можно выбросить вобщем.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
    
    static final int M = 1_048_576; // 2^20
    static final int J = 2_045;
    int oldI = 12357;

    double Random() {
        oldI = (oldI * J + 1) % M;
        return (double) oldI / M;
    }
...
Рейтинг: 0 / 0
11.01.2018, 09:44
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582279
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
BarloneКонечно случайная последовательность может совершенно случайно начаться с пары сотен нулевых битов.да, поэтому вопрос "сожмет ли архиватор случайную последовательность?" нужно понимать либо как

"сожмет ли архиватор любую случайную последовательность хотя бы на 1 бит?"

либо как

"какое математическое ожидание величины сжатия архиватором случайной последовательности (с пониманием того, что некоторые он вообще не сожмёт)?"

Ибо математические прикидки показывают, что, да, танки летают, но низенько-низенько ...
...
Рейтинг: 0 / 0
11.01.2018, 10:27
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582351
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Иван FXSда, поэтому вопрос "сожмет ли архиватор случайную последовательность?" нужно понимать либо как

"сожмет ли архиватор любую случайную последовательность хотя бы на 1 бит?"

либо как

"какое математическое ожидание величины сжатия архиватором случайной последовательности (с пониманием того, что некоторые он вообще не сожмёт)?"

Ибо математические прикидки показывают, что, да, танки летают, но низенько-низенько ...
Ну если учесть, что в случае неудачи сжатия архиватору надо будет добавить минимум 1 бит - признак "не сжато", для идеального архиватора матожидание величины сжатия будет нулевым, а для неидеального - отрицательным.
...
Рейтинг: 0 / 0
11.01.2018, 11:32
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582482
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneВот вам 16Мб случайная последовательность, сжимайте. ...
Может сжаться
https://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел#Недостатки_ГПСЧ Длина циклов ГПСЧ зависит от самого генератора и составляет около 2^(n/2) , хотя линейные конгруэнтные и РСЛОС-генераторы обладают максимальными циклами порядка 2^n , где n — размер внутреннего состояния в битах
Никто не знает какой цикл у этого ГПСЧ получится. Для 32-бит цикл от 65536 может быть.
...
Рейтинг: 0 / 0
11.01.2018, 13:38
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582684
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Иван FXSА как связана "фреймворковость" с обсуждением сравнительной сжимаемости (податливости сжатию) строк (сообщений) типа приведённого вами Иван , не придирайтесь, у меня привычка отвечать на смежные вопросы, тем более, что Вы тоже жонглируете, случается, терминами "с лёгкостью необыкновенной".

Связана, чтобы это запомнилось или вызвало обсуждение. Сообщение предположительно кодировало ровно один бит информации, предназначенной для Потребителя (true). Искажённая фраза в результате "раскодировки" даст по-нашему NULL, те неопределеность, т.е. отсутствие ожидаемой инфы для Потребителя, и придётся повторить передачу. И там, и там кодировался 1 бит, а длины файлов, ушедших в эфир, разные. Идея примера была в этом. Согласен, что сравнивавемые строки не очень показательны.

Информация для Потребителя - в этом заключалась моя фреймворковость. В отличие от информации для канала связи, по сути - от длины передаваемого файла. И, кстати, если подписать ЭЦП'ю, строка ведь удлиняется? (допустим, я подписал просто из прынцыпа, а не для того, чтобы удостоверить себя)

Повторяю, разговоры про пардокс - пока это всё гипостазирование.
...
Рейтинг: 0 / 0
11.01.2018, 16:53
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582698
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
exp98,

всё-таки я вижу некоторую разницу между ситуацией, когда у отправителя стоит пакующий (сжимающий) алгоритм, а у получателя -- соответствующий ему (пакующему алгоритму) распаковывающий алгоритм; и отправляются, вообще говоря, произвольные сообщения ...

и ситуацией, когда отправитель целенаправленно строит свои сообщения как цитаты (абзацы) из литературных классиков, а сообщения посылает в виде (имя автора; номер тома; страница; номер абзаца).
...
Рейтинг: 0 / 0
11.01.2018, 17:33
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39583043
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TBarloneВот вам 16Мб случайная последовательность, сжимайте. ...
Может сжаться
https://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел#Недостатки_ГПСЧ Длина циклов ГПСЧ зависит от самого генератора и составляет около 2^(n/2) , хотя линейные конгруэнтные и РСЛОС-генераторы обладают максимальными циклами порядка 2^n , где n — размер внутреннего состояния в битах
Никто не знает какой цикл у этого ГПСЧ получится. Для 32-бит цикл от 65536 может быть.Да, по-хорошему конечно надо "правильный" ГПСЧ использовать. А так от реализации в компиляторе зависит.
...
Рейтинг: 0 / 0
12.01.2018, 09:54
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39583186
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima TНикто не знает какой цикл у этого ГПСЧ получится. Для 32-бит цикл от 65536 может быть. -- "для конкретного значения seed" следует добавлять.
...
Рейтинг: 0 / 0
12.01.2018, 11:46
| Ответить | Цитировать | Написать  
23 сообщений из 48, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Об одном парадоксе информационной энтропии
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]