powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Дисперсия длины архива?
25 сообщений из 146, страница 1 из 6
Дисперсия длины архива?
    #39576305
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если взять некоторый набор независимых (друг от друга) последовательностей битов длины N, упаковать их все каким нибудь архиватором (например, zip) и посчитать среднее значение (S) длины получившихся архивов и дисперсию (D) длин архивов, то ...

1. каким (по порядку величины хотя бы) будет отношение D/S?

2. у какого из известных архиваторов (наряду с zip) это отношение будет "заметно" бОльшим ( чем у остальных)?

3. Кстати, будет ли само распределение длин таких архивов (для конкретного архиватора) нормальным ... то есть, типа, что там -- Гаус или Пуассон?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576312
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS,
1. Надо брать не дисперсию, а корень из нее. Его отношение к среднему будет называться коэффициентом вариации и безразмерным.
2. Экспериментальная проверка займет минут 10.
3. Скорее всего, ничего похожего на "правильное" распределение не будет.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576318
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS1. каким (по порядку величины хотя бы) будет отношение D/S?
Это бессмысленный показатель, у числителя и знаменателя разные размерности.

А вообще - вопрос сам по себе тоже бессмысленен. Архивация как процесс опирается на тот факт, что реальные данные обладают внутренней структурой и существенно неслучайны. Попытка проверить что-то на каком-то случайном наборе бит приведёт лишь к ответу на вопрос "какой архиватор дописывает меньше хрени к несжимаемым данным".
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576364
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
О! Никогда не проверял, давным баловался меотдами сжатия, кажется теоретический предел сжатия ~2/3 (для текстов ~ 1/4). Можно на примере ехе-файла. Избыточность рулит.
а) Предполагаю, что так и будет.
б) Дополню Соколинского. Да, типовая мера = М/СКО, а не на Д. Т.е, скоко СКО умещается в М.
в) Такой широкий рынок архиваторов? В Пуассона/Релея как-то по смыслу больше верится: сильных алгоритмов мало, слабых - больше, а плохие никто не использует. Типа так ожидается. Правда это для чисто сжатия ( не для файла)
г) Следует помнить, что в сжатых архивах некое кол-во идёт на инфу, и даже потом пустой архив может оказаться не нулевым.

А вообще, это всё было о-о-очень давно...
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576475
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А если к опискам не цепляться (конечно, корень из D, а не D), а по содержанию что-нибудь сказать попробовать? Не?
______________
softwarer, я разве сказал "случайный набор"?
________________
И да, вопрос мог бы быть сформулирован так:

1. как выглядит статистика коэффициента сжатия (для "типичных" архиваторов)?

2. у каких архиваторов статистика коэффициента сжатия имеет бОльшую (по сравнению с другими "типичными" архиваторами) дисперсию?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576479
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот тут что-то было.

http://www.compression.ru/arctest/act/act-calg.htm
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576525
WebSharper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98О! Никогда не проверял, давным баловался меотдами сжатия, кажется теоретический предел сжатия ~2/3

Мне кажется теоретического предела сжатия нет. Например однотерабайтный файл из одних нулей можно сжать до словосочетания "терабайт нулей".
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576546
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
WebSharper, ну это тоже из области придирок. Тогда уж и тексты можно сжимать до одной ссылки на глобальный корпус текстов. Говорят о статистическом теоретическом пределе в общем случае. Жипег взять - он не сожмётся, потому как там уже Хафман порылся. А возьми равномернорасределённую послед-сть ... А ещё помню, что английский сжимается больше русского, т.к. там язык для "лиц с ограниченными способностями". Наверняка есть сжималки, специализированные под конкретику.
И вопрос ТС я интерпретировал именно как для случайных выборок.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576625
WebSharper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98WebSharper, ну это тоже из области придирок. Тогда уж и тексты можно сжимать до одной ссылки на глобальный корпус текстов.


Именно так.

Говорят о статистическом теоретическом пределе в общем случае.


Не могли бы вы дать определение этого?

т.к. там язык для "лиц с ограниченными способностями".


Задорнов жив!

И вопрос ТС я интерпретировал именно как для случайных выборок.

Случайные выборки их чего?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39576669
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
WebSharperСлучайные выборки их чего? их мн-ва {0;1} согласно ТСу
Сейчас посмотрел ехешки - раньше и ехешки были другими, менее сжимаемыми.
Кто такой этот ваш Задорнов? Я сам придумал!! Могу ещё: вставьте пипюру в пипюроприёмник
Об остальном - ну его нафиr ...
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577036
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98Говорят о статистическом теоретическом пределе

-- меня интересует не предел, а дисперсия сжимаемости.

Хорошо, открою карты: меня интересует, есть ли возможность в системах типа блокчейна PoW реализовать в форме PoC (Proof of Compression). Так понятней?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577083
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дык здесь и говорят: Сигму не знаем, надо изучать.
Для простых случаев понятно лишь только на пальцах. Шифрованные данные практически не сжимаемы, потому как равномерны.
Популярные сжималки могут комбинировать набор методов в завис-и от файла или от цели: время/объём. Уверен, что тот же зип два одинаковых файла сожмёт каждый из них как новый - это уже фреймворк применения. Для чистых же методов, не знающих формата данных, могу только навскидку M/S сильно больше 1.
Короче, это личная карма вопрошающего .

Я технологию чейнов не знаю, однако был реализован в железе проект, давно закрытый, как идея только.
Фирма была что-то типа Peribit / PerEbit. Сжатие трафика на лету (на сетевом где-то уровне, ниже уровня приложений), типа через глобальный частично пополняемый словарь. Девайс корпорации не приняли, поскольку на VPN никакого сжатия. А то было бы как я выше писал: пересылается ссылка на глобальную БД (+обновление).
Примерно в те же времена в своей конторе мы договорились с Главным Аналитиком на нечто похожее, но в софт-варианте и на уровне приложений, но, увы, он скоропостижно слёг с онкологией, а потом и контора - хлоп.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577085
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98Шифрованные данные практически не сжимаемы

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

-- то только (и именно) тогда признавать манера выполнившим норматив по PoW (оно же, в этом случае, PoC -- Proof of Compression) ...
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577089
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
"... майнеру удаётся на этом своём блоке достичь ..."
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577176
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98WebSharper, ну это тоже из области придирок. Тогда уж и тексты можно сжимать до одной ссылки на глобальный корпус текстов. Говорят о статистическом теоретическом пределе в общем случае. Жипег взять - он не сожмётся, потому как там уже Хафман порылся. А возьми равномернорасределённую послед-сть ... А ещё помню, что английский сжимается больше русского, т.к. там язык для "лиц с ограниченными способностями". Наверняка есть сжималки, специализированные под конкретику.
И вопрос ТС я интерпретировал именно как для случайных выборок.
Мне почему-то вспоминается криптография и анализ криптостойкости.
По сути - поиск закономерностей. Слабых. Еле уловимых на уровне авто-корреляций.

ИМХО если таковые есть в тексте для сжатия - то можем сжимать дальше.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577396
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS,
без надувания щёк, я не в теме от слова совсем.
К "сжатию" есть интерес академический, да, а слазил в инет на тему pow&poc и понял, чтобы в это вникнуть, нужно время. Это целый фреймворк, спец.мат.теория, коллективные вычисления, теория игр ... Это не моё, и думаю, Вам нужна специализированная тусовка, копать спец.журналы и т.п.

У меня в последнее время более прозаично: как внедрить один контрол в другой штатным способом без документации и т.п. - вот это действительно проблема, и вроде есть кто знает, но не объясняют, потому что все усвоили, что информация правит балл.

Из инета 1 грошик:
Вьюгин, Колмлгоровская сложность и алгоритмическая случайность, 2012.
Что-то к теме Статистические испытания ( nrjetix_com /fileadmin/doc/publications/Lectures_security/Lecture2_pdf).
Что-то к сравнению архиваторов (ict_nsc_ru /ws/YM2007/12817/paper_html).
Ещё вот дома книжка, Мир, 1988 ~ Информация неопределённость сложность (ну да, по обложке это Трауб). Правда она нудная, у них там так водится, не вдохновила тогда.
Везде в конце Литература.

З.Ы,
У Колмогорова опред. кол-ва инфы, адекватнее энтропии по Шеннону, и чем-то напоминает условную вероятность. В нём уже не вынести за скобки объём централизованного репозитария. Но оно неудобно для реализации.

Если ещё раз вернуться к сигме (п.2 в первом посте). Типовые методы "энтропийные", уменьшают среднюю энтропию, и в такой методе очевидно есть предел. Это "шенноновский" подход. Поэтому кажется, что безусловного лидера во всех тестах вряд ли найти. А к примеру вынос централизованного репозитария из компрессора во вне - это уже фреймворк, но к pow это вроде не подходит.
У сжималок может ещё оказаться фича втягивать файл целиком, если предвидится, что метаданные првысят эффект от сжатия.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577424
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS-- я танцую, как от печки, от того, что сейчас биткойновые майнеры совершают какой-то невообразимый объем совершенно бессмысленной -- сама по себе -- вычислительной работы. Почему бы не предложить им вместо этого пустого перебора хэшей позаниматься сжатием того же самого блока (который этот самый майнер готовится предложить в блокчейн). И если этому майнеру удаётся этом своём блоке достичь выдающегося показателя сжатия (лучше некоторого "порога сжатия", который и будет играть роль параметра "сложности"), потому что одна из характеристик денег, или эквивалента денег - это трудность добывания.
Сравните скажем, золото и воду. Первого на земле мало, и его трудно добывать. вода - ее много и ее добыть гораздо легче. теперь сравните цены на золото и воду (килограмм).

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


Иван FXS-- то только (и именно) тогда признавать манера выполнившим норматив по PoW (оно же, в этом случае, PoC -- Proof of Compression) ...зачем к блоку, который прошел стандартный тест, добавлять еще какой-то тест?
или вы предлагаете не делать первый тест, а только ваш?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577486
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
S.G.потому что одна из характеристик денег, или эквивалента денег - это трудность добывания

-- если разобраться, то дело не в трудности добывания. Килограмм золота добыть довольно трудно (трудоёмко), а миллиграмм -- миллион раз менее трудоёмко. А килограмм (натурального) шёлка и килограмм, скажем, сушёных комаров добыть, пожалуй, примерно также трудоёмко, как килограмм золота ...

S.G.если сделать простой тест, то первый же майнер получит все биткоины

-- "если сделать простой тест", то произойдёт другое: система потонет в потоке создаваемых всеми узлами блоков.

Собственно, поэтому в неё и зашит параметр "сложность", который авторегулирует скорость создания блоков. Иными словами, протокол Биткойна создан таким, что "сделать простой тест" в нём просто невозможно.

S.G.вы предлагаете не делать первый тест, а только ваш

-- да, я предлагаю заменить "трудную задачу" поиска "красивого" хэша -- "трудной задачей" очень сильного сжатия.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577768
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И почему бы им не поискать ферзевые расстановки для 30х30 и выше. И им польза, и нам здесь тоже пригодится))
Всех с НГ-2018
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577877
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

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

И вас с НГ.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577921
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXSS.G.потому что одна из характеристик денег, или эквивалента денег - это трудность добывания

-- если разобраться, то дело не в трудности добывания. Килограмм золота добыть довольно трудно (трудоёмко), а миллиграмм -- миллион раз менее трудоёмко. А килограмм (натурального) шёлка и килограмм, скажем, сушёных комаров добыть, пожалуй, примерно также трудоёмко, как килограмм золота ... Во-первых, сравнивать надо не килограмм с миллиграмом одного и того же, а килограмм с килограммом разных сущностей. :)
Если действительно разобраться, то вы неправ, трудность добывания напрямую связана с ценой. Можно накидать кучу примеров - например аллюминий, который был жутко дорогим, когда его добывалось трудно и мало, и сильно подешевел, когда придумали как добывать много и легко. ну и пример с шелком, который был дорогим, когда только Китай знал как добывать, а сегодня он не очень дорог.
А насчет шелка и комаров.. если внимательно прочитать мой текст, можно прочитать "трудность.. одна из характеристик". Чтобы что-то стало деньгами, оно должно иметь и другие характеристики.
Оставлю вам самому сообразить почему шелк и комары не годятся в качестве денег.

Иван FXSS.G.если сделать простой тест, то первый же майнер получит все биткоины

-- "если сделать простой тест", то произойдёт другое: система потонет в потоке создаваемых всеми узлами блоков. возможно, система и потонет, возможно и не потонет, но во всяком случае произойдет то, что я сказал.

Иван FXS Собственно, поэтому в неё и зашит параметр "сложность", который авторегулирует скорость создания блоков. Иными словами, протокол Биткойна создан таким, что "сделать простой тест" в нём просто невозможно. Прекрасно, значит вы уже понимаете, что сложность не бессмысленная, (тут 21067973 ) а она специально такая, со смыслом?

Иван FXS S.G.вы предлагаете не делать первый тест, а только ваш

-- да, я предлагаю заменить "трудную задачу" поиска "красивого" хэша -- "трудной задачей" очень сильного сжатия. ок, и сжимать чего именно?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39577976
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
S.G.но во всяком случае произойдет то, что я сказал
если у вас есть волшебная палочка, которая позволяет ПО ВАШЕМУ желанию, заставить Биткойн работать, "если сделать простой тест", -- при том, согласно регламента работы Биткойна никто не в праве произвольно "делать простой тест" в нём ... То, конечно, эта волшебная палочка поможет вам сделать так, чтобы "первый же майнер получит все биткоины". Я только отказываюсь признавать этот цирк "биткойном".

S.G.сложность не бессмысленная, (тут 21067973 ) а она специально такая, со смыслом?
да, сложность со смыслом: смысл сложности в том, чтобы быть сложной.

S.G.ок, и сжимать чего именно?
сжимать тот самый блок, который создал майнер, которому предлагается сжимать. Извините за повтор того, что уже было написано #27 дек 17, 19:24#.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39578046
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXSS.G.но во всяком случае произойдет то, что я сказал
если у вас есть волшебная палочка, которая позволяет ПО ВАШЕМУ желанию, заставить Биткойн работать, "если сделать простой тест", -- при том, согласно регламента работы Биткойна никто не в праве произвольно "делать простой тест" в нём ... То, конечно, эта волшебная палочка поможет вам сделать так, чтобы "первый же майнер получит все биткоины". Я только отказываюсь признавать этот цирк "биткойном".

S.G.сложность не бессмысленная, (тут 21067973 ) а она специально такая, со смыслом?
да, сложность со смыслом: смысл сложности в том, чтобы быть сложной. По-моему, вы теряете нить разговора.
Мы начали с того, что вы возмущались бессмысленной сложностью расчетов для блока. Я показал вам, что большая сложность имеет смысл, (она делает биткоин похожим на деньги или золото) и что если сложность будет небольшой, то ничего хорошего не получится.
Ок, кажется вы согласились со мной.


Иван FXS S.G.ок, и сжимать чего именно?
сжимать тот самый блок, который создал майнер, которому предлагается сжимать. Извините за повтор того, что уже было написано #27 дек 17, 19:24#.вот пример биткоин блока:

автор
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
Block #138849
BlockHash 00000000000001c21dbf4715d5da1a288061faa21e950dd8df6ae25c8b55d868
Summary
Number Of Transactions 	184
Height 	138849 (Mainchain)
Block Reward 	50 BTC
Timestamp 	Jul 31, 2011 12:37:14 AM
Mined by 	
Merkle Root 	
98c5d975bf556f0344770eee7ab31688a1c108223c14cea908ff99b0ab8fe947
Previous Block 	138848
Difficulty 	1690895.80305239
Bits 	1a09ec04
Size (bytes) 	58913
Version 	1
Nonce 	3723473450
Next Block 	138850


Что именно в нем предлагаете сжимать? весь блок в виде текста? Только хеш в виде текста? Только хеш в числовом (байтовом) виде?
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39578050
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
S.G.,

я возмущаюсь тем, что САМИ ПО СЕБЕ вычисления, производимые (в Биткойне) для выполнения "норматива сложности", бесполезны. И предлагаю заменить их полезными САМИ ПО СЕБЕ вычислениями, состоящими в сильном сжатии блока.

Сжимать предлагается то битовое представление блока, в котором он (блок) распространяется по сети интернет.
...
Рейтинг: 0 / 0
Дисперсия длины архива?
    #39578054
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXSя возмущаюсь тем, что САМИ ПО СЕБЕ вычисления, производимые (в Биткойне) для выполнения "норматива сложности", бесполезны. И предлагаю заменить их полезными САМИ ПО СЕБЕ вычислениями, состоящими в сильном сжатии блока.
В чем разница? Можно просто посчитать хэш, а можно считать хэш до посинения, выискивая более красивый. Точно так же можно просто пожать, а можно жать всяко-всяческими способами выкраивая единицы байт. Итого не меняется, надо потратить кучу времени на поиск лучшего решения.

Иван FXSСжимать предлагается то битовое представление блока, в котором он (блок) распространяется по сети интернет.
Тут GZIP/DEFLATE лучше использовать. Пусть жмут не идеально, но очень быстро и в итоге общее время минимальное получается.
...
Рейтинг: 0 / 0
25 сообщений из 146, страница 1 из 6
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Дисперсия длины архива?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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