Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
Привет друзья.

Дима-Т, Сова, Илья, Иван-ФХ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 кодить!

Теоретики - курят в сторонке.
11 янв 18, 23:33    [21099367]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
В продолжение топиков 210891852109314621093146
11 янв 18, 23:42    [21099384]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
Dima T
Member

Откуда:
Сообщений: 11891
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

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

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

PS Собственных экзотических идей по данному вопросу у меня нет.
12 янв 18, 11:31    [21100619]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
exp98
Member

Откуда:
Сообщений: 1281
mayton
архиваторами
2) Визуализация.
кодить

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

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

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

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

На кртинке просто фрагмент теоремы, что м.ож. одинаково распределённых случ.величин имеет норм.распр-е. Всю жизнь верил теории, недавно взял, да и посмотрел кусочек.
12 янв 18, 12:15    [21100855]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
exp98
Member

Откуда:
Сообщений: 1281
К вопросу о приложениях ГЧ.
Ещё давнее вспомнил. Была, не мною, предложена модель в целях локации моделировать пересечённую местность вариантом итеративной 2-мерной корелляционной модели с параметрами, на основе ГПСЧ. Там интересные картинки рисовывались, всевозможные площадные регионы типа овалов, рукавов, амёб и т.д., каждый регион со своими корелл. характеристиками. В каком-то случае возник "треуг-к Серпинского". Ну и как подзадача было облагородить сишный ГЧ.
Надо сказать, как и в случае с натуральными фракталами, под заданную картинку модель надо было подбирать (читай перебором).
За ради модели и исходников надо долго и физически рыться, если сохранилось.
12 янв 18, 13:10    [21101093]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 17109
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия.
Угу...
Очень давно, когда архиваторы были слабыми, а я совсем зелёным, у меня зарождалась аналогичная идея. Но её убил простой эксперимент. Взял я файл (большой текст), обмял его архиватором (ДОСовым RAR) с максимальными настройками, потом отXORил его рандомом (помнится, сделал аж 100 копий, каждая обработана со своим seed) и попытался обжать тем же архиватором с теми же настройками... посмотрел на результат - и зарёкся плодить дурные идеи.
12 янв 18, 13:19    [21101146]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
Иван FXS
Member

Откуда:
Сообщений: 1655
Akina,

а осталась в вашей памяти что-то более конкретное про результат того эксперимента: типа -- ни одна из 100 копий не сжалась ни на один бит? Мы ведь обсуждаем вопрос "можно ли случайную строку сжать", а не "можно ли её сжать на десятки процентов" ...
12 янв 18, 14:48    [21101746]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 17109
Иван FXS
а осталась в вашей памяти что-то более конкретное про результат того эксперимента: типа -- ни одна из 100 копий не сжалась ни на один бит?

Исходный файл - форматированный ASCII-текст размером порядка 1 Мбайт, в сжатом виде порядка 80 кбайт.
Среда программирования (и ГСЧ) - Borland Turbo BASIC 1.0.
Максимальное дополнительное сжатие - порядка 1.6% (на одном файле).
Количество файлов, размер которых уменьшился - порядка 70%.
Среднее уменьшение размера файла, по всему массиву - порядка 0,2%.
Среднее уменьшение размера файла, только по дополнительно сжатым - порядка 0,3%.
12 янв 18, 15:23    [21101900]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
д0kХ
Guest
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

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

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

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

+1

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

+1

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

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

Если очень глубоко копать, тему, то точка перехода качества сжатия,
в качество востанновленной информации
находится где то по этой методике.
И нужно будет минимум 2 прохода по всему объему информации ,
что бы поймать фрактальные зависимости.
12 янв 18, 19:27    [21102879]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
д0kХ
Guest
Если стоит вопрос масимального сжатия без потерь,
то это другая область математики - многомерные пространства.
Тут еще больше украдено до нас.

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

Усидеть одновременно на 2 стульях если и получится,
то код никакого фундаметального и
практического интереса представлять не будет.
12 янв 18, 19:37    [21102902]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
д0kХ
Если стоит вопрос масимального сжатия без потерь,
то это другая область математики - многомерные пространства.
Тут еще больше украдено до нас.

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

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

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

Дело в том что мы тут занимаем свою нишу. И занимаемся не математическими
открытиями а инженерией алгоритмов. Подобно конструктору Lego, мы собираем
из примитивов нечто. Это не наука. Это приспособление. Мы "приспосабливам"
для себя осколки знаний just for fun. Эволюционный путь. Отбор. Итеративный
подход. Best practices. Scrum/Agile. Это все разные названия этого процесса.

Мы не претендуем даже на строгое доказательство верности нашего пути.
Здесь нет формул. Просто скопление практик.

И я как и все другие мемберы тоже нахожусь здесь for fun. Помимо этого
я решаю параллельно еще 3-4 других задачи которые я не озвучил но они
перемежаются с обсуждаемыми хеш-тегами и рано или поздно я ими поделюсь.

Вот как то в таком вот аспекте.
12 янв 18, 23:11    [21103549]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

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

Я не собираюсь "ломать об колено" архиватор с ГПСЧ. Он вполне себе
может существовать как "концепт" для сравнения его с другими.
Я-бы поставил другую задачу. Не опровергнуть тезисы Ивана а скорее
дать ему новые идеи и тезисы. Опять-же. На практике.
12 янв 18, 23:14    [21103558]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
exp98
Надо сказать, как и в случае с натуральными фракталами, под заданную картинку модель надо было подбирать (читай перебором).За ради модели и исходников надо долго и физически рыться, если сохранилось.

Скриншоты сохранились?
12 янв 18, 23:17    [21103561]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
д0кХ
Guest
mayton
д0kХ
Если стоит вопрос масимального сжатия без потерь,
то это другая область математики - многомерные пространства.
Тут еще больше украдено до нас.

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

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

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

Дело в том что мы тут занимаем свою нишу. И занимаемся не математическими
открытиями а инженерией алгоритмов. Подобно конструктору Lego, мы собираем
из примитивов нечто. Это не наука. Это приспособление. Мы "приспосабливам"
для себя осколки знаний just for fun. Эволюционный путь. Отбор. Итеративный
подход. Best practices. Scrum/Agile. Это все разные названия этого процесса.

Мы не претендуем даже на строгое доказательство верности нашего пути.
Здесь нет формул. Просто скопление практик.

И я как и все другие мемберы тоже нахожусь здесь for fun. Помимо этого
я решаю параллельно еще 3-4 других задачи которые я не озвучил но они
перемежаются с обсуждаемыми хеш-тегами и рано или поздно я ими поделюсь.

Вот как то в таком вот аспекте.

Я как бы о том, что мало смысла пытаться собрать пазлы брутфорсом.
Даже ради лулзов.
Универсальная Алгоритмы сжатия с потерями имеет огромный практический смысл.
Это базовая алгоритмика абстрактного и образного мышления искуственного интеллекта.
Поэтому я бы подвинул приоритет задачи в эту сторону.
12 янв 18, 23:24    [21103578]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
д0кХ
Я как бы о том, что мало смысла пытаться собрать пазлы брутфорсом.
Даже ради лулзов.
Универсальная Алгоритмы сжатия с потерями имеет огромный практический смысл.
Это базовая алгоритмика абстрактного и образного мышления искуственного интеллекта.
Поэтому я бы подвинул приоритет задачи в эту сторону.

Давай через пару недель. Подниму тему с lossy compression. У меня там идей еще больше...
12 янв 18, 23:27    [21103586]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
д0кХ
Guest
mayton, я бы не ввязывался в эту дискуссию ,
если бы не считал нужным лайнуть посты Dima T и exp98
дополнить их мысли мну ИМХО .
Они дело говорят , обрати внинмание на выделенное мной их постах.


Они тоже уже переросли этот топик.
12 янв 18, 23:35    [21103595]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
Я-ж говорю. Каждый здесь находит своё.
12 янв 18, 23:45    [21103608]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 5484
mayton
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

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

Я не собираюсь "ломать об колено" архиватор с ГПСЧ. Он вполне себе
может существовать как "концепт" для сравнения его с другими.
Я-бы поставил другую задачу. Не опровергнуть тезисы Ивана а скорее
дать ему новые идеи и тезисы. Опять -же. На практике.

один дурак задаст столько вопросов.... (с)

уже отвечено 21082855
12 янв 18, 23:55    [21103629]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
д0кХ
Guest
mayton
Dima T
Идея архиватора с ГПСЧ не рабочая, не будет сжатия. Писал тут 21093742 и тут 21094323

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

Я не собираюсь "ломать об колено" архиватор с ГПСЧ. Он вполне себе
может существовать как "концепт" для сравнения его с другими.
Я-бы поставил другую задачу. Не опровергнуть тезисы Ивана а скорее
дать ему новые идеи и тезисы. Опять-же. На практике.

Имхо Иван пытается откопать и обсмаковать Гавно мамонта протухшие лулзы



+ квота для жерв информационного геноцида


Подам отличную идею — уже сейчас делить разные числа одно на другое, конвертить остатки в avi и смотреть еще не вышедшие фильмы :)

»
— Результат обсуждения Бабушкинского алгоритма сжатия на хабре.
Сам молодой гений описывает своё изобретение так:

Алгоритм™ архивации таков: любой файл представляет собой HEX-последовательность символов, переводим этот HEX в DEC, получаем неебически-большое число, дописываем перед этим число 0, — получаем число в диапазоне от 0 до 1 с огромным числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Беда в подборе чисел, которое может идти и 2 часа, а может идти и 2 недели. Есть опытные образцы и работающая программа, и всё это работает.

Сжатый фильм «Клик» (Файл удалён). Тест алгоритма архивации Бабушкина.

2 марта 2013 г. поциент Вконтакте выложил ссылку на статью Криса Касперски «Могущество кодов Рида-Соломона или информация, воскресшая из пепла», прочитав которую, можно понять, что даже «придуманный» им алгоритм архивации заимствован из полушутливого раздела статьи про инопланетян.

На основе принципа работы архиватора был разработан алгоритм "Сортировка Бабушкина", имеющий уникальное время работы О(n). Главное - подобрать числа, которые при делении дадут число Бабушкина, за время, меньшее времени тепловой смерти Вселенной.

12 янв 18, 23:58    [21103636]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
exp98
Member

Откуда:
Сообщений: 1281
mayton
Скриншоты сохранились?
надо долго и физически рыться, если сохранилось. Как только так и ... ну 95-й, о чём-то говорит? Хотя в отчёте 2-3 конечно были, только это было заказное исследование ) А так, визуально помнится как выше описано. Итеративность - ключевой момент был, в принципе и своё воссоздать можно.

И да, сжатие изображений "фрактальными" методами, похоже что преимуществ по Ксж пред жпг не особо. Во всяк, в сравнимое время. Хотя идея подбираться к "неподвижной точке сжимающего отображения" в полном Банаховом пространстве очень вдохновляла в первое время. Это намёк.
13 янв 18, 19:18    [21104702]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
exp98
Member

Откуда:
Сообщений: 1281
д0кХ, пусть Иван сам делает выводы с учётом или без наших мнений. Учиться не поздно никогда и никому. К тому же его идея не в архиваторе, а в применении оного.
13 янв 18, 19:24    [21104715]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
mayton
Member

Откуда: loopback
Сообщений: 36186
Попробовал на "бумаге" систему счисления с весами Фибоначчи. Забавно. У нее есть
возможность восстанавливать трафик после сбоя. Тоесть даже если было повреждение
то имеется возможность "поймать синхроизацию" трафика как сетевых протоколах и телевидении.

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

Если пойти на хитрость и прибавить +2 то последний артефакт устраняется.
14 янв 18, 21:57    [21106023]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 52110
Блог
mayton
К сожалению имеются изначально трудности с кодированием отрицательных чисел, нуля и единицы.

Множество целых чисел гомеоморфно множеству натуральных. Всегда можно воспользоваться.
15 янв 18, 13:27    [21107479]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
exp98
Member

Откуда:
Сообщений: 1281
softwarer
Множество целых чисел гомеоморфно множеству натуральных. Всегда можно воспользоваться.
Плз, аккуратнее с общепринятыми мат.терминами! Лишь одинаковая мощность, что говорит только о БИЕКТИВНОСТИ. Даже "изо-" требует "операции", не говоря о "гомео-".
Ну или операцию тогда надо определить (весьма экзотическим способом).
15 янв 18, 13:43    [21107599]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый архивариус  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 52110
Блог
exp98,

операция определяется легко и просто на первом курсе. Например,

НатуральноеЦелое
10
21
3-1
42
5-2
63
......


А в целом ок, принимается.
15 янв 18, 14:28    [21107823]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить