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

Маленькая энтропия означает, в частности, что если мы нарежем рассматриваемую строку S на последовательные “слова” одинаковой длины М и составим частотный словарь этих слов, то не только всё множество возможных “слов” длины М будет присутствовать в этом словаре, но и разброс частот этих слов будет минимальным. То есть -- существенно меньшим, чем разброс частот в аналогично препарированной случайной строке битов той же длин N.

Можно сказать, что частоты “слов” в S “хорошо выровнены”.

Возьмём теперь датчик случайных чисел (ДПСЧ), выберем произвольное начальное значение Х (не слишком длинное в битовой записи) и создадим на основании последовательности значений, возвращаемых этим ДПСЧ -- начиная с ДПСЧ(Х)
-- (псевдо-)случайную строку Z той же самой длины N.

Сложим побитово S и Z. Получившаяся строка R будет, вообще говоря, столь же (псевдо-)случайна, как и строка Z. То есть частоты входящих в неё “слов” совершенно не будут выровнены. А это значит, что, прогнав её (Z) через тот же самый хороший архиватор, мы сможем дополнительно её сжать. И есть хорошие шансы надеяться, что “выигрыш” (в числе битов) от этого сжатия будет больше, чем длина в битах записи числа Х. И даже (возможно, особенно если N велико) больше, чем длина в битах алгоритма нашего ДПСЧ, записанного на каком-то “экономном” байт-коде...

Можно, наконец, явно произнести, что, зная только Х, мы всегда можем повторно сгенерировать строку Z и, вычтя её из R, получить исходную S.
...
Рейтинг: 0 / 0
10.01.2018, 13:16
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581797
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Что-то не так. Хорошо сжатая последовательность как раз максимально похожа на случайную.
...
Рейтинг: 0 / 0
10.01.2018, 15:19
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581802
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Вот сразу заявлю: не вижу paradoxa -- надеяться только можно.
Вообще, оно конечно, если на серии опытов существует плотность распред F( S AND Y), то она м.б. весьма разнообразна и не связана с индивидуальными плотностями (умозрительно говоря).

С другой стороны, давно уже было такое:
Строим словарь С1 из "текста", нарезая его на кусочки ограниченной в целом длины (аналог ЛЗВ).
Строим текст из ссылок на С1
Строим словарь С2 из текста.
Строим текст из ссылок на С2
......
На первых итерациях имеем квазикомбинаторный взрыв.
В дальнейшем - сужаемость, похожая на треугольник. Его высота и полнота зависит от начальной "энтропийности" "текста". Чем "белее шум", тем тр-к брюхастее и выше, а чем больше повторяемость - тем ниже и менее беременный.

Последний "текст"= единственная ссылка. Вот и сжатие. А есть ли paradox, хрз.
Писал "текст" - т.к. в компе всё можно свести к послед-сти {0,1}
...
Рейтинг: 0 / 0
10.01.2018, 15:26
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581808
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Barlone,

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

А префиксное кодирование, например, специально занимается тем, что выравнивает (как можно лучше) частоты слов. С учётом длин, конечно: все слова длиной 8 бит должны иметь частоты, в идеале, равные 1/256; а слова длиной 10 бит -- равные 1/1024 ...
...
Рейтинг: 0 / 0
10.01.2018, 15:32
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581835
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Иван FXS. “Хорошее сжатие” означает, что информационная энтропия распределения битов в этой строке сильно минимизирована наоборот, максимизирована.

Иван, вы бы почитали что-нибудь про все это, наконец.
...
Рейтинг: 0 / 0
10.01.2018, 15:52
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581854
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
S.G.,

да, спасибо. Внимание всем: "энтропия минимизирована" читать (выше) как "энтропия максимизирована".
...
Рейтинг: 0 / 0
10.01.2018, 16:13
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581858
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
S.G.,

я просто физик по исходному. А там -- в термодинамике -- энтропия возрастает самопроизвольно, а чтобы её уменьшить, нужно специально усилия прикладывать.
...
Рейтинг: 0 / 0
10.01.2018, 16:16
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581863
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Иван FXSв случайной последовательности частоты "слов" распределены по какому-нибудь Пуассону (на вскидку)Да с чего бы? Равномерно.
...
Рейтинг: 0 / 0
10.01.2018, 16:18
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581864
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
в смысле "равномерно" это как?
...
Рейтинг: 0 / 0
10.01.2018, 16:19
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581869
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
https://ru.wikipedia.org/wiki/Дискретное_равномерное_распределение
...
Рейтинг: 0 / 0
10.01.2018, 16:28
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581879
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Barlone,
Сами слова - равномерно. А их частота (сиречь количество одинаковых в выборке) - таки да, по Пуассону.
...
Рейтинг: 0 / 0
10.01.2018, 16:34
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581881
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Иван FXSВнимание всем: "энтропия минимизирована" читать (выше) как "энтропия максимизирована". После прочтения "парадокс" совсем пропал.
...
Рейтинг: 0 / 0
10.01.2018, 16:35
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581888
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Соколинский Борис,

так можно слова длиной 15 с частотами из правого крыла Пуассона (их, 15-буквенного Пуассона) перекодировать словами длины 14 с частотами из левого крыла Пуассона (их, 14-буквенного Пуассона).

И наоборот, то есть взаимно?
...
Рейтинг: 0 / 0
10.01.2018, 16:43
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581889
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
читать:Иван FXS(их, 14-буквенного Пуассона) ?
...
Рейтинг: 0 / 0
10.01.2018, 16:45
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581934
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Кстати пользуюсь мнемоникой: возрастание Э интерпретируется как возрастание хаоса, что и ведёт к побелению шума. Всякая же структуризация ведёт к уменьшению Э.

Ваще я полагаю, что выравнивание Э-й как самоцель нужно только для шифрования, а для сжатия нужна суммарная. Просто это не будет означать криптостойкость сжатого кода. Не помню, в Хаффмане вроде как раз тлько суммарность используется.
...
Рейтинг: 0 / 0
10.01.2018, 17:31
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581947
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Ну и собственно к paradoxu. Он - в головах. Т.к. Ш-н относил всё к оптимальной "передаче инфы" на уровне канала связи. Да ещё наверное подразумевая, что передавать алгоритм вместе с кодом не требуется и что наверное этот алгоритм - вещь статическая.

Мы же давно имеем глобальные сети + сетевой стек + возможность фреймворкать. Давно уже не надо на Ш как на икону смотреть.
Т.е. оптимальность всегда д.б. относительно конретного фреймворка.
...
Рейтинг: 0 / 0
10.01.2018, 17:43
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581964
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Кстати, в тему максимизации/минимизации энтропии: из двух сообщений одинаковой длины лучше будет сжиматься ("хорошим" архиватором) то, в котором больше информации? Или, наоборот, то, в котором меньше информации?
...
Рейтинг: 0 / 0
10.01.2018, 18:04
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39581995
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
В Э-ном смысле я полагаю, что в целом там, где удельная инфа выше.
Если же фреймворкать, то скоко инфы в известной фразе?
"Не верьте тому, кто пугает вас плохой погодой в Швейцарии. Здесь очень солнечно и тепло."
А в исковерканной?
"...в Лимпопо. Там ооооооооооооооооочень ХооооЛоооооооДНооооооо."
...
Рейтинг: 0 / 0
10.01.2018, 18:34
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582008
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
exp98, лучше будет сжиматься то сообщение, в котором удельная ("на единицу длины") инфа выше, -- я правильно вас понял?

А как связана "фреймворковость" с обсуждением сравнительной сжимаемости (податливости сжатию) строк (сообщений) типа приведённого вами: " Там ооооооооооооооооочень ХооооЛоооооооДНооооооо " -- против " Там очень ХоЛоДНо ", например?
...
Рейтинг: 0 / 0
10.01.2018, 18:43
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582012
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Соколинский БорисBarlone,
Сами слова - равномерно. А их частота (сиречь количество одинаковых в выборке) - таки да, по Пуассону.А, ну действительно.
Только это не поможет. Никакой архиватор случайную последовательность не сожмет.
...
Рейтинг: 0 / 0
10.01.2018, 18:53
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582021
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSВозьмём теперь датчик случайных чисел (ДПСЧ), выберем произвольное начальное значение Х (не слишком длинное в битовой записи) и создадим на основании последовательности значений, возвращаемых этим ДПСЧ -- начиная с ДПСЧ(Х)
-- (псевдо-)случайную строку Z той же самой длины N.

Сложим побитово S и Z. Получившаяся строка R будет, вообще говоря, столь же (псевдо-)случайна, как и строка Z. То есть частоты входящих в неё “слов” совершенно не будут выровнены. А это значит, что, прогнав её (Z) через тот же самый хороший архиватор, мы сможем дополнительно её сжать. И есть хорошие шансы надеяться, что “выигрыш” (в числе битов) от этого сжатия будет больше, чем длина в битах записи числа Х. И даже (возможно, особенно если N велико) больше, чем длина в битах алгоритма нашего ДПСЧ, записанного на каком-то “экономном” байт-коде...
ИМХО не сожмется. Результат тоже будет близок к случайному набору.

Можешь затестить, в отличии от других твоих алгоритмов этот прост в реализации:
1. Взял какой-нибудь сжатый файл. i = 0
2. Инициализировал ГПСЧ значением i.
3. Поксорил файл с ГПСЧ
4. Пожал (например в ZIP)
5. Если результат размером меньше идеального (ранее найденного), то запомнил результат как идеальный.
6. Если i < ... то i++ и п.2

Думаю найдутся решения чуть поменьше исходного, но уменьшение будет в пределах 1%.
...
Рейтинг: 0 / 0
10.01.2018, 19:05
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582025
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Иван FXSтак можно слова длиной 15 с частотами из правого крыла Пуассона (их, 15-буквенного Пуассона) перекодировать словами длины 14 с частотами из левого крыла Пуассона (их, 14-буквенного Пуассона).

Это все равно что повторно архивировать.

Иван FXSКстати, в тему максимизации/минимизации энтропии: из двух сообщений одинаковой длины лучше будет сжиматься ("хорошим" архиватором) то, в котором больше информации? Или, наоборот, то, в котором меньше информации? Информация - многозначный термин.
...
Рейтинг: 0 / 0
10.01.2018, 19:16
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582046
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXS, я вот что подумал: если ты прав, т.е. твоя идея рабочая, то можно жать что угодно до бесконечности. Ну хотя бы в десятки раз. Например дистрибутив виндовса сжать до 1 Мб, пусть даже 100 Мб, думаю ради этого MS запустил бы перебор на пару месяцев.

Вывод: если бы это работало, то этим бы уже пользовались.
...
Рейтинг: 0 / 0
10.01.2018, 19:48
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582055
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

потому и "парадокс".
...
Рейтинг: 0 / 0
10.01.2018, 20:05
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #39582056
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Соколинский БорисИван FXSтак можно слова длиной 15 с частотами из правого крыла Пуассона (их, 15-буквенного Пуассона) перекодировать словами длины 14 с частотами из левого крыла Пуассона (их, 14-буквенного Пуассона).

Это все равно что повторно архивировать.
задачка в том, как при таком перекодировании обойтись без "словаря перевода", либо с таким словарём, который не перекрыл бы (своей длиной) весь эффект сжатия.

Соколинский БорисИнформация - многозначный термин.
чувствуете подвох: получается, что абсолютно случайная последовательность битов не сжимается (хотя лично всё ещё тлеет надежда) из-за того, что в ней предельно много информации!
...
Рейтинг: 0 / 0
10.01.2018, 20:13
| Ответить | Цитировать | Написать  
Об одном парадоксе информационной энтропии
    #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
| Ответить | Цитировать | Написать  
48 сообщений из 48, показаны все 2 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Об одном парадоксе информационной энтропии
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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