Четверговый архивариус

mayton
Дата: 11.01.2018 23:33:37
Привет друзья.

Дима-Т, Сова, Илья, Иван-ФХC, ПТР-128, Эхп98, Барлон, Зяма и прочие простите кого забыл.

В продолжение топиков:

Я задаю тему.

Эксперименты с ГПСЧ, Системами счисления, кодеками и архиваторами. Макеты. Proo-of-conept. Работающее
приложение. Здесь мы будем обкатывать наши идеи в виде реализации.

Некоторые поинты.

1) Базовый тип. Для формального доказательства наших гипотез, нам не нужны биты.
Нам хватит строк. std::string, String, e.t.c. Пример:
string s="00101010010101010";

Любой сможет на них легко делать булевы
операции и что главное - конкатенации и обрезку. Памяти нам хватит. Оверхед составит
порядка 8-16 раз ну и пофиг.

А биты пойдут потом. Когда гипотеза взлетит.

2) Визуализация.. Я - большой фанат научной графики и визуализации идей. Зачастую
бывает что данные представленные картинкой несут больше ценных сведений чем куча
умных словесных тезисов. Поэтому черно-белая (bi-tonal) картинка придаст больше
наглядности для энтропии и преобладания каких-то свойств в бинарном файле.

Для тех, кому лень кодить графические кодеки - берите формат PPM. Это матрица пикселов в тексте.
Или рисуйте в браузере на канвасе. Примеры - тривиальны.

3) Язык. Любой из популярных. Можно даже JavaScript, главное чтоб мы смогли хотть как-то протестить.

4) Сорцы.. Как всегда я поднимаю репку. Комитте сюда.
https://sourceforge.net/p/psevdo-random-arc/code/HEAD/tree/

5) Сторонние библиотеки. Желательно чтоб были сорцы чтоб понять идею.


Go-go кодить!

Теоретики - курят в сторонке.
mayton
Дата: 11.01.2018 23:42:59
В продолжение топиков 210891852109314621093146
Dima T
Дата: 12.01.2018 11:31:02
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

Если кратко: длина подстроки исходных данных, которая совпадет с последовательностью из ГПСЧ вероятнее всего будет меньше или равна длине инфы требуемой для инициализации ГПСЧ. Т.е. меняем M бит на M бит.

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

PS Собственных экзотических идей по данному вопросу у меня нет.
exp98
Дата: 12.01.2018 12:15:13
mayton
архиваторами
2) Визуализация.
кодить

Простите за немного не в тему.
Насчёт последнего - каждый занимается тем, чего ему нехватает)

Архивация, п.2):
Внезапно вспомнил давно уопробированные варианты. К началу 90-х (640К оперативка, 10М диск либо ваще только флоппи) ГУИшные проги делали с внешним хэлп-файлом (он же и ресурсный файл). Ради экономии места и/или защиты от самостоятельного пополнения использовался простейший вариант сжатия по повторяющимся частям слов. Просто видно было, как по мере листания файла вначале шли боле-мене узнававемые чуть не целые слова, затем превращаясь в разноообразные куски букв. Вот и вся визуализация.

Реализация примитивная, сжатие сильное, однако отнюдь не максимальное. Надеюсь с идеей всё ясно, исходники, извините, далече.
-----------

ГПСЧ в эксэле: щас найду картинку ...
Раздел "МС Офис"
тема generator-sluchaynyh-chisel-v-excel
сообщение 20570120

На кртинке просто фрагмент теоремы, что м.ож. одинаково распределённых случ.величин имеет норм.распр-е. Всю жизнь верил теории, недавно взял, да и посмотрел кусочек.
exp98
Дата: 12.01.2018 13:10:33
К вопросу о приложениях ГЧ.
Ещё давнее вспомнил. Была, не мною, предложена модель в целях локации моделировать пересечённую местность вариантом итеративной 2-мерной корелляционной модели с параметрами, на основе ГПСЧ. Там интересные картинки рисовывались, всевозможные площадные регионы типа овалов, рукавов, амёб и т.д., каждый регион со своими корелл. характеристиками. В каком-то случае возник "треуг-к Серпинского". Ну и как подзадача было облагородить сишный ГЧ.
Надо сказать, как и в случае с натуральными фракталами, под заданную картинку модель надо было подбирать (читай перебором).
За ради модели и исходников надо долго и физически рыться, если сохранилось.
Akina
Дата: 12.01.2018 13:19:59
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия.
Угу...
Очень давно, когда архиваторы были слабыми, а я совсем зелёным, у меня зарождалась аналогичная идея. Но её убил простой эксперимент. Взял я файл (большой текст), обмял его архиватором (ДОСовым RAR) с максимальными настройками, потом отXORил его рандомом (помнится, сделал аж 100 копий, каждая обработана со своим seed) и попытался обжать тем же архиватором с теми же настройками... посмотрел на результат - и зарёкся плодить дурные идеи.
Иван FXS
Дата: 12.01.2018 14:48:57
Akina,

а осталась в вашей памяти что-то более конкретное про результат того эксперимента: типа -- ни одна из 100 копий не сжалась ни на один бит? Мы ведь обсуждаем вопрос "можно ли случайную строку сжать", а не "можно ли её сжать на десятки процентов" ...
Akina
Дата: 12.01.2018 15:23:17
Иван FXS
а осталась в вашей памяти что-то более конкретное про результат того эксперимента: типа -- ни одна из 100 копий не сжалась ни на один бит?

Исходный файл - форматированный ASCII-текст размером порядка 1 Мбайт, в сжатом виде порядка 80 кбайт.
Среда программирования (и ГСЧ) - Borland Turbo BASIC 1.0.
Максимальное дополнительное сжатие - порядка 1.6% (на одном файле).
Количество файлов, размер которых уменьшился - порядка 70%.
Среднее уменьшение размера файла, по всему массиву - порядка 0,2%.
Среднее уменьшение размера файла, только по дополнительно сжатым - порядка 0,3%.
д0kХ
Дата: 12.01.2018 19:27:48
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

Если кратко: длина подстроки исходных данных, которая совпадет с последовательностью из ГПСЧ вероятнее всего будет меньше или равна длине инфы требуемой для инициализации ГПСЧ. Т.е. меняем M бит на M бит.

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

PS Собственных экзотических идей по данному вопросу у меня нет.

+1

exp98
К вопросу о приложениях ГЧ.
Ещё давнее вспомнил. Была, не мною, предложена модель в целях локации моделировать пересечённую местность вариантом итеративной 2-мерной корелляционной модели с параметрами, на основе ГПСЧ. Там интересные картинки рисовывались, всевозможные площадные регионы типа овалов, рукавов, амёб и т.д., каждый регион со своими корелл. характеристиками. В каком-то случае возник "треуг-к Серпинского". Ну и как подзадача было облагородить сишный ГЧ.
Надо сказать, как и в случае с натуральными фракталами, под заданную картинку модель надо было подбирать (читай перебором).
За ради модели и исходников надо долго и физически рыться, если сохранилось.

+1

Извини mayton, но задача-идея писать на эту тему код - попытка
поставить телегу впереди лошади.

Фундаментально математически нужно с другой стороны подходить, смотреть
на универсальные алгоритмы сжатия
не теряющее сути информации, но снижающие детализацию без возможности восстановления.

Если очень глубоко копать, тему, то точка перехода качества сжатия,
в качество востанновленной информации
находится где то по этой методике.
И нужно будет минимум 2 прохода по всему объему информации ,
что бы поймать фрактальные зависимости.
д0kХ
Дата: 12.01.2018 19:37:07
Если стоит вопрос масимального сжатия без потерь,
то это другая область математики - многомерные пространства.
Тут еще больше украдено до нас.

Ищи мат выкладки по алгоритма ADSL и прочие алгоритмы укладки
шаров в многомерных пространствах.

Усидеть одновременно на 2 стульях если и получится,
то код никакого фундаметального и
практического интереса представлять не будет.