|
|
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
Roman Mejtes, а как можно сгенирировать последовательность по алгоритму Хаффмана? :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 16:16 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
Любая симметричная криптография - тоже нулевая сжимаемость. Попробуйте сами. Вернее сказать это один из нужных побочных эффектов. У атакующего нет никакой информации вообще о характере и роде энтропии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 16:17 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mayton, я не верю в генерацию последовательности Хаффмана :-) у меня сейчас по плану AVL Trees (self balanced binary search trees), два дня ушло только на то, чтобы разобраться как делать балансировку ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 17:57 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mini.weblab mayton, я не верю в генерацию последовательности Хаффмана :-) Я не консультирую в вопросах веры. Спроси как-нибудь по другому. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 18:32 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mayton Я не консультирую в вопросах веры. Спроси как-нибудь по другому. Ну типа, как напрямую сделать Хаффмана максимально не эффективным? Без трюков с криптографией и гпсч? Последовательность может быть простая, но не сжимаемая. Никаких атак здесь не подразумевается, как и защиты от неё. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 21:39 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
Ну-у, навскидку что-то вроде того: 1)Маленькое разнообразие коротких последовательностей, часто встречающихся. 2)1-2 очнь длинноых, но редких послед-стей. 3) Они все не пересекаются. ИМХО И, Хвост, почему же у криптогр. трюки? Это просто методы равномерного размазывания исходного набора символов по более обширному набору. Просто есть готовые. А что, теперь нужно ещё один придумать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 22:55 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt mayton Я не консультирую в вопросах веры. Спроси как-нибудь по другому. Ну типа, как напрямую сделать Хаффмана максимально не эффективным? Без трюков с криптографией и гпсч? Последовательность может быть простая, но не сжимаемая. Никаких атак здесь не подразумевается, как и защиты от неё. Смысл хаффмена - кодирование частых символов - короткими бит-последовательностями префиксных кодов. А редких символов - длинными. На выходе имеем равномерно шумящие биты. Но не идеальные. Придумайте такую гистограмму (относительную частоту алфавита) при которой гистограмма длин префиксных кодов Хаффмена будет максимально непропорциональна относительным частотам вашего алфавита. Дальше - не хочу теоретизирвать. Берите просто русский алфавит. И смотрите что получится на выходе. Закодируйте хотя - бы 100 букв и посчитайте длину кода в битах. И сравните например с 32х символьным идеальным белым шумом. ПОсчитайте в битах. Чем ближе ваш Хаффмен к белому шуму по длине - тем вы лучше его сломали. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.08.2020, 23:43 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
exp98 И, Хвост, почему же у криптогр. трюки? Это просто методы равномерного размазывания исходного набора символов по более обширному набору. Просто есть готовые. А что, теперь нужно ещё один придумать? Математика на вас нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 00:49 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mayton Чем ближе ваш Хаффмен к белому шуму по длине - тем вы лучше его сломали. Практически задача решена, берём КГПСЧ и получаем то, что нужно. А вот алгоритмически -- нет :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 00:51 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt mayton Чем ближе ваш Хаффмен к белому шуму по длине - тем вы лучше его сломали. Практически задача решена, берём КГПСЧ и получаем то, что нужно. А вот алгоритмически -- нет :) Мне кажется что ты прикалываешься. Сам давно уже решил задачу - но чего то ещё хочешь в топике намутить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 08:25 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mayton Сам давно уже решил задачу - но чего то ещё хочешь в топике намутить. Ничего не хочу намутить, сказал же практически задача решена. Но алгоритма, который изначально генерирует не случайную последовательность символов, которая не жмётся дефлейтом у меня нет. Т.е. алгоритмически задача не решена. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 14:58 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
А чем тебе псевдослучайные числа - не алгоритм? А последовательность целых (монотонная) не алгоритм? А последовательность после shuffle - не алгоритм? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 16:17 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
А я понял его так, что мы все юзеры. Т.е. берём готовое, а своё придумать не можем или не умеем. Касательно себя я не особенно и протестую. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 22:46 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
Я точно юзер своего смартфона. Даже и в мыслях не было что-то в нем накодить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 22:53 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mayton А чем тебе псевдослучайные числа - не алгоритм? И микроскопом можно прекрасно забить гвоздь. Просто так получилось, что псевдослучайные числа плохо жмутся. Однако, это не исключает ситуации, когда некоторая сгенерированная последовательность пожмётся очень даже хорошо. mayton А последовательность целых (монотонная) не алгоритм? Если она жмётся максимально плохо -- это отвечает практическим и алгоритмическим требованиям. mayton А последовательность после shuffle - не алгоритм? Shuffle обычно реализуется на некотором рандоме. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 23:06 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt Однако, это не исключает ситуации, когда некоторая сгенерированная последовательность пожмётся очень даже хорошо. А чтобы дожить, выше предлагалось пропускать послед-сть через фильтр. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 23:38 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt Shuffle обычно реализуется на некотором рандоме. Предлагаю свести рандом к конечному автомату над булевыми значениями и таким образом поставить детерминистическую точку в этом споре. Рандом - это метафора. Конечный автомат который выдает циклическую последовательность целых - реален. Алгоритм? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.08.2020, 23:46 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
exp98 Только я до этого не доживу. А чтобы дожить, выше предлагалось пропускать послед-сть через фильтр. Это ещё не доказано :) mayton Предлагаю свести рандом к конечному автомату над булевыми значениями и таким образом поставить детерминистическую точку в этом споре. Извините, я был не в курсе, что мы о чём-то спорим. Я ведь уже давно согласился, что практически задача решена. mayton Рандом - это метафора. "Стальные нервы" -- вот это метафора. А "радном" это "случайный" в прямом смысле слова :) В контексте нашего обсуждения, это ГПСЧ. mayton Конечный автомат который выдает циклическую последовательность целых - реален. Алгоритм? ++i :) Берём алгоритм сжатия, конкретный, например deflate. Теперь нужно сформировать бесконечную последовательность байт, которая гарантировано 100% +бесконечность никогда не будет сжата дефлейтом. Вот это алгоритмическое решение. Если что, я как бы не настаиваю, если у кого нет идей, то на нет и суда нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 00:57 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt, авторТеперь нужно сформировать бесконечную последовательность байт, которая гарантировано 100% +бесконечность никогда не будет сжата дефлейтом. ответ: нет, невозможно (имхо) 1) гарантировать 100% можно для конечной последовательности 2) для бесконечной последовательности можно гарантировать сходимость по распределению ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 02:03 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
кстати! насчет алгоритма АВЛ, вот что я обнаружила: авторАдельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263—266. Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. English translation by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 02:15 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt, Да. Гарантировано не будет сжата. Она бы сжалась, если бы deflate был идеален. Но он ограничен по размеру справочника поэтому гпсч победит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 11:35 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
mini.weblab кстати! насчет алгоритма АВЛ, вот что я обнаружила: ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 16:23 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
hVostt exp98 Только я до этого не доживу. А чтобы дожить, выше предлагалось пропускать послед-сть через фильтр. ...5. Класс множеств, строго представимых в данном базисе, вообще говоря, не замкнут уже относительно таких операций, как объединение и пересечение множеств, проектирование множества на алфавит и др. Для каждой из этих операций нетрудно построить базис порождения и строго представимые в этом базисе множества такие, что результат применения операции к соответствующим множествам не является строго представимым в этом базисе. Для последних двух операций то же утверждение остается верным и при переходе к строгой представимости при помощи перечислимого множества алгорифмов. С. Ю. Маслов, О некоторых способах задания множеств в базисах порождения, Докл. АН СССР, 1963, том 153, номер 2, 266–269 a joke ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 17:38 |
|
||
|
Несжимаемая последовательность байт
|
|||
|---|---|---|---|
|
#18+
exp98, Ну ладно-ладно, давайте вашу зачётку :)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2020, 20:57 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39989892&tid=1339749]: |
0ms |
get settings: |
8ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
28ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
70ms |
get tp. blocked users: |
1ms |
| others: | 13ms |
| total: | 156ms |
| 0 / 0 |
