Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6   вперед  Ctrl      все
 Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
Если взять некоторый набор независимых (друг от друга) последовательностей битов длины N, упаковать их все каким нибудь архиватором (например, zip) и посчитать среднее значение (S) длины получившихся архивов и дисперсию (D) длин архивов, то ...

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

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

3. Кстати, будет ли само распределение длин таких архивов (для конкретного архиватора) нормальным ... то есть, типа, что там -- Гаус или Пуассон?
26 дек 17, 17:19    [21064190]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 6982
Иван FXS,
1. Надо брать не дисперсию, а корень из нее. Его отношение к среднему будет называться коэффициентом вариации и безразмерным.
2. Экспериментальная проверка займет минут 10.
3. Скорее всего, ничего похожего на "правильное" распределение не будет.
26 дек 17, 17:29    [21064219]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 51621
Блог
Иван FXS
1. каким (по порядку величины хотя бы) будет отношение D/S?

Это бессмысленный показатель, у числителя и знаменателя разные размерности.

А вообще - вопрос сам по себе тоже бессмысленен. Архивация как процесс опирается на тот факт, что реальные данные обладают внутренней структурой и существенно неслучайны. Попытка проверить что-то на каком-то случайном наборе бит приведёт лишь к ответу на вопрос "какой архиватор дописывает меньше хрени к несжимаемым данным".
26 дек 17, 17:33    [21064236]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
exp98
Member

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

А вообще, это всё было о-о-очень давно...
26 дек 17, 18:34    [21064465]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
А если к опискам не цепляться (конечно, корень из D, а не D), а по содержанию что-нибудь сказать попробовать? Не?
______________
softwarer, я разве сказал "случайный набор"?
________________
И да, вопрос мог бы быть сформулирован так:

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

2. у каких архиваторов статистика коэффициента сжатия имеет бОльшую (по сравнению с другими "типичными" архиваторами) дисперсию?
27 дек 17, 00:55    [21065238]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
mayton
Member

Откуда: loopback
Сообщений: 35893
Вот тут что-то было.

http://www.compression.ru/arctest/act/act-calg.htm
27 дек 17, 01:03    [21065248]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
WebSharper
Member

Откуда:
Сообщений: 201
exp98
О! Никогда не проверял, давным баловался меотдами сжатия, кажется теоретический предел сжатия ~2/3


Мне кажется теоретического предела сжатия нет. Например однотерабайтный файл из одних нулей можно сжать до словосочетания "терабайт нулей".
27 дек 17, 09:01    [21065482]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
exp98
Member

Откуда:
Сообщений: 1224
WebSharper, ну это тоже из области придирок. Тогда уж и тексты можно сжимать до одной ссылки на глобальный корпус текстов. Говорят о статистическом теоретическом пределе в общем случае. Жипег взять - он не сожмётся, потому как там уже Хафман порылся. А возьми равномернорасределённую послед-сть ... А ещё помню, что английский сжимается больше русского, т.к. там язык для "лиц с ограниченными способностями". Наверняка есть сжималки, специализированные под конкретику.
И вопрос ТС я интерпретировал именно как для случайных выборок.
27 дек 17, 09:35    [21065553]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
WebSharper
Member

Откуда:
Сообщений: 201
exp98
WebSharper, ну это тоже из области придирок. Тогда уж и тексты можно сжимать до одной ссылки на глобальный корпус текстов.


Именно так.

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


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

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


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

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


Случайные выборки их чего?
27 дек 17, 10:59    [21065810]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
exp98
Member

Откуда:
Сообщений: 1224
WebSharper
Случайные выборки их чего?
их мн-ва {0;1} согласно ТСу
Сейчас посмотрел ехешки - раньше и ехешки были другими, менее сжимаемыми.
Кто такой этот ваш Задорнов? Я сам придумал!! Могу ещё: вставьте пипюру в пипюроприёмник
Об остальном - ну его нафиr ...
27 дек 17, 11:40    [21066001]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
exp98
Говорят о статистическом теоретическом пределе


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

Хорошо, открою карты: меня интересует, есть ли возможность в системах типа блокчейна PoW реализовать в форме PoC (Proof of Compression). Так понятней?
27 дек 17, 17:34    [21067672]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
exp98
Member

Откуда:
Сообщений: 1224
Дык здесь и говорят: Сигму не знаем, надо изучать.
Для простых случаев понятно лишь только на пальцах. Шифрованные данные практически не сжимаемы, потому как равномерны.
Популярные сжималки могут комбинировать набор методов в завис-и от файла или от цели: время/объём. Уверен, что тот же зип два одинаковых файла сожмёт каждый из них как новый - это уже фреймворк применения. Для чистых же методов, не знающих формата данных, могу только навскидку M/S сильно больше 1.
Короче, это личная карма вопрошающего.

Я технологию чейнов не знаю, однако был реализован в железе проект, давно закрытый, как идея только.
+
Фирма была что-то типа Peribit / PerEbit. Сжатие трафика на лету (на сетевом где-то уровне, ниже уровня приложений), типа через глобальный частично пополняемый словарь. Девайс корпорации не приняли, поскольку на VPN никакого сжатия. А то было бы как я выше писал: пересылается ссылка на глобальную БД (+обновление).
Примерно в те же времена в своей конторе мы договорились с Главным Аналитиком на нечто похожее, но в софт-варианте и на уровне приложений, но, увы, он скоропостижно слёг с онкологией, а потом и контора - хлоп.
27 дек 17, 19:01    [21067943]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
exp98
Шифрованные данные практически не сжимаемы


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

-- то только (и именно) тогда признавать манера выполнившим норматив по PoW (оно же, в этом случае, PoC -- Proof of Compression) ...
27 дек 17, 19:24    [21067973]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
"... майнеру удаётся на этом своём блоке достичь ..."
27 дек 17, 19:25    [21067979]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
mayton
Member

Откуда: loopback
Сообщений: 35893
exp98
WebSharper, ну это тоже из области придирок. Тогда уж и тексты можно сжимать до одной ссылки на глобальный корпус текстов. Говорят о статистическом теоретическом пределе в общем случае. Жипег взять - он не сожмётся, потому как там уже Хафман порылся. А возьми равномернорасределённую послед-сть ... А ещё помню, что английский сжимается больше русского, т.к. там язык для "лиц с ограниченными способностями". Наверняка есть сжималки, специализированные под конкретику.
И вопрос ТС я интерпретировал именно как для случайных выборок.

Мне почему-то вспоминается криптография и анализ криптостойкости.
По сути - поиск закономерностей. Слабых. Еле уловимых на уровне авто-корреляций.

ИМХО если таковые есть в тексте для сжатия - то можем сжимать дальше.
28 дек 17, 00:31    [21068514]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
exp98
Member

Откуда:
Сообщений: 1224
Иван 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 это вроде не подходит.
У сжималок может ещё оказаться фича втягивать файл целиком, если предвидится, что метаданные првысят эффект от сжатия.
28 дек 17, 13:31    [21069702]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
S.G.
Member

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

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


Иван FXS
-- то только (и именно) тогда признавать манера выполнившим норматив по PoW (оно же, в этом случае, PoC -- Proof of Compression) ...
зачем к блоку, который прошел стандартный тест, добавлять еще какой-то тест?
или вы предлагаете не делать первый тест, а только ваш?
28 дек 17, 14:51    [21069953]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
S.G.
потому что одна из характеристик денег, или эквивалента денег - это трудность добывания


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

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


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

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

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


-- да, я предлагаю заменить "трудную задачу" поиска "красивого" хэша -- "трудной задачей" очень сильного сжатия.
28 дек 17, 17:17    [21070422]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
exp98
Member

Откуда:
Сообщений: 1224
И почему бы им не поискать ферзевые расстановки для 30х30 и выше. И им польза, и нам здесь тоже пригодится))
Всех с НГ-2018
29 дек 17, 11:16    [21072039]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

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

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

И вас с НГ.
29 дек 17, 13:34    [21072647]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 28056
Иван FXS
S.G.
потому что одна из характеристик денег, или эквивалента денег - это трудность добывания


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

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


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

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

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


-- да, я предлагаю заменить "трудную задачу" поиска "красивого" хэша -- "трудной задачей" очень сильного сжатия.
ок, и сжимать чего именно?
29 дек 17, 14:20    [21072808]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
S.G.
но во всяком случае произойдет то, что я сказал

если у вас есть волшебная палочка, которая позволяет ПО ВАШЕМУ желанию, заставить Биткойн работать, "если сделать простой тест", -- при том, согласно регламента работы Биткойна никто не в праве произвольно "делать простой тест" в нём ... То, конечно, эта волшебная палочка поможет вам сделать так, чтобы "первый же майнер получит все биткоины". Я только отказываюсь признавать этот цирк "биткойном".

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

да, сложность со смыслом: смысл сложности в том, чтобы быть сложной.

S.G.
ок, и сжимать чего именно?

сжимать тот самый блок, который создал майнер, которому предлагается сжимать. Извините за повтор того, что уже было написано #27 дек 17, 19:24#.
29 дек 17, 16:05    [21073068]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 28056
Иван FXS
S.G.
но во всяком случае произойдет то, что я сказал

если у вас есть волшебная палочка, которая позволяет ПО ВАШЕМУ желанию, заставить Биткойн работать, "если сделать простой тест", -- при том, согласно регламента работы Биткойна никто не в праве произвольно "делать простой тест" в нём ... То, конечно, эта волшебная палочка поможет вам сделать так, чтобы "первый же майнер получит все биткоины". Я только отказываюсь признавать этот цирк "биткойном".

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

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


Иван FXS
S.G.
ок, и сжимать чего именно?

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

автор
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


Что именно в нем предлагаете сжимать? весь блок в виде текста? Только хеш в виде текста? Только хеш в числовом (байтовом) виде?
29 дек 17, 18:26    [21073322]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Иван FXS
Member

Откуда:
Сообщений: 1647
S.G.,

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

Сжимать предлагается то битовое представление блока, в котором он (блок) распространяется по сети интернет.
29 дек 17, 19:03    [21073386]     Ответить | Цитировать Сообщить модератору
 Re: Дисперсия длины архива?  [new]
Dima T
Member

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

В чем разница? Можно просто посчитать хэш, а можно считать хэш до посинения, выискивая более красивый. Точно так же можно просто пожать, а можно жать всяко-всяческими способами выкраивая единицы байт. Итого не меняется, надо потратить кучу времени на поиск лучшего решения.

Иван FXS
Сжимать предлагается то битовое представление блока, в котором он (блок) распространяется по сети интернет.

Тут GZIP/DEFLATE лучше использовать. Пусть жмут не идеально, но очень быстро и в итоге общее время минимальное получается.
29 дек 17, 19:13    [21073399]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6   вперед  Ctrl      все
Все форумы / Программирование Ответить