Гость
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Несжимаемая последовательность байт / 25 сообщений из 73, страница 1 из 3
13.08.2020, 00:49
    #39989182
hVostt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Есть идеи, как сгенерировать последовательность байт, с какими-то гарантиями нулевой или около нулевой сжимаемости?
Условно говоря, если пропустить поток через какой-нибудь deflate, на выходе размер практически не изменится.
...
Рейтинг: 0 / 0
13.08.2020, 04:00
    #39989188
x1ca4064
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
hVostt
Есть идеи, как сгенерировать последовательность байт, с какими-то гарантиями нулевой или около нулевой сжимаемости?


Хороший генератор _случайных_ чисел + расчет энтропии, если энтропия мала, новая генерация.
Зачем?
...
Рейтинг: 0 / 0
13.08.2020, 06:25
    #39989201
x1ca4064
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
hVostt,
Хотя, на практике, достаточно и просто псевдослучайных байт - ужмется меньше, чем на 1%, если сжиматель не сделан специально под данный ГПСЧ
...
Рейтинг: 0 / 0
13.08.2020, 06:39
    #39989202
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Поток из ГПСЧ через deflate пропусти. Пожатое обычно не жмется
...
Рейтинг: 0 / 0
13.08.2020, 06:47
    #39989203
982183
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Мы для этих целей оцифровывали физический белый шум лет 20 назад....
...
Рейтинг: 0 / 0
13.08.2020, 09:21
    #39989225
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
hVostt,

Для очень коротких последовательностей поток deflate должен быть всегда больше чем исходная.
За счёт заголовков блоков.

Поэтому ты уточни что у тебя на входе.
...
Рейтинг: 0 / 0
13.08.2020, 13:29
    #39989338
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Я как-то рассеяно размышлял об архиваторе который будет вести бесконечно большой справочник файлов или текстовых
фрагментов. По моим расчетам у меня коэффициент выходил намного лучше известных PPM/LZW.

Но это концепт. И время работы его архивации просто зависит от размера справочника. И основные данные - это статьи
и журналы и книги.

Вобщем я и Бабушкин будем вести соревнование.
...
Рейтинг: 0 / 0
13.08.2020, 14:33
    #39989375
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Я в свое время читал что-то про "арифметическое сжатие", это последний этап сжатия в программах архивации, после чего сжать последовательность практически невозможно.
...
Рейтинг: 0 / 0
13.08.2020, 14:50
    #39989387
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
hVostt, JPEG подойдёт?
...
Рейтинг: 0 / 0
13.08.2020, 16:12
    #39989424
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Aklin
Я в свое время читал что-то про "арифметическое сжатие", это последний этап сжатия в программах архивации, после чего сжать последовательность практически невозможно.

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

Остался пустяк. Придумать быстрый детектор этих повторов. Здесь я застрял.
...
Рейтинг: 0 / 0
13.08.2020, 18:18
    #39989482
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
я не знаю, что подразумевается под deflate, поэтому предположу, что имеется ввиду произвольный алгоритм сжатия.

получить последовательность с нулевой или околонулевой сжимаемастью можно, но для конкретного алгоритма, т.е

CA(D) = CA(CA(D)) = CA( CA( CA(D) ) ) и т.д

CA - compression algorithm
D - data

в общем случае, думаю, что не получится, и exp98 как раз удачно упомянул JPEG (lossy compression algorithm),
т.е, меняя уровень потерь, на выходе мы каждый раз будем получать разные данные
...
Рейтинг: 0 / 0
13.08.2020, 18:26
    #39989486
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
...
Рейтинг: 0 / 0
13.08.2020, 18:28
    #39989488
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Без этого дефлейта не обходится ни один современный архиватор или файловый упаковщик.
И внутри Gif картинок он вобщем-то есть. И в Zip. И в jar/war/ear. И игровые форматы упаковки
ресурсов. И Андроидовские.
...
Рейтинг: 0 / 0
13.08.2020, 18:35
    #39989491
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
mayton,
спасибо, не знала

в конечном итоге все сведется к типу сжимаемых данных, математической модели и ее физической реализации
...
Рейтинг: 0 / 0
13.08.2020, 19:28
    #39989512
hVostt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
exp98
hVostt, JPEG подойдёт?


Нет, нужно генерировать последовательность.
В практической плоскости можно брать уже пожатые данные как исходник.

А я говорю про генерацию )
...
Рейтинг: 0 / 0
13.08.2020, 19:37
    #39989518
hVostt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Я взял криптографический генератор случайных чисел, пожал дефлейтом, получил незначительное увеличение полученного размера. Чем больше объём данных, тем меньше оверхед.

В целом это решает задачу :)


x1ca4064
Хороший генератор _случайных_ чисел + расчет энтропии, если энтропия мала, новая генерация.
Зачем?


Dima T
Поток из ГПСЧ через deflate пропусти. Пожатое обычно не жмется


Вы оказались чертовски правы

Зачем? Хотел закостылить поток для расчёта пропускной скорости канала, при максимально плохих исходных данных.

Всем спасибо!
...
Рейтинг: 0 / 0
13.08.2020, 21:22
    #39989560
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Хоть решение уже и принято...
hVostt
В практической плоскости можно брать уже пожатые данные как исходник.
А я говорю про генерацию )
И я говорю про генерацию. И я говорил брать уже пожатые данные как исходник.
JPEG ,ZIP, RAR ... выше предлагали уже. Генерируешь псевдослуч. Называешь это рисунком. Делаешь JPEG ,ZIP, RAR ... Делаешь SubString(), чтобы избавиться от текстов. А дальше сжимай и проверяй, там 1% или больше.
...
Рейтинг: 0 / 0
13.08.2020, 21:43
    #39989566
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
mayton
Остался пустяк. Придумать быстрый детектор этих повторов. Здесь я застрял.
А за счёт памяти, индексирования триплетов/квартетов, и многоуровневости? Кратко так: 3плет сравнился -->переход на уровень выше и там уже продолжаем сравнивать представителей от бОльших кусков. Правда не знаю, насколько это быстро, не изучал.
Я 10-15 лет назад примерно так хотел авторефераты без словаря. Что-то игрушечное получалось. В конкретных деталях конечно далеко не так как я написал здесь.
...
Рейтинг: 0 / 0
13.08.2020, 22:18
    #39989576
hVostt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
exp98
И я говорю про генерацию. И я говорил брать уже пожатые данные как исходник.


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

Это не интересно )
...
Рейтинг: 0 / 0
13.08.2020, 22:26
    #39989579
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
exp98,

Я последний раз термин триплет слышал когда мы с Semantic Web работали. Там это было частью орграфа знаний. Типа subject, predicate, object.

Но ты очевидно имел в виду другое? Триграмма? Три символа?
...
Рейтинг: 0 / 0
13.08.2020, 22:58
    #39989594
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
mayton, 3 символа.
hVostt, про интерес в вопросе не было.
...
Рейтинг: 0 / 0
13.08.2020, 23:34
    #39989611
hVostt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
exp98
hVostt, про интерес в вопросе не было.


Было чётко сказано про генерацию.
Взять готовое и сказать, что это генерация -- халтура :)
...
Рейтинг: 0 / 0
14.08.2020, 11:34
    #39989726
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
Любой криптографический ГПСЧ гарантирует нам отсутствие легких зависимостей
в последовательности. Можете взять

Код: sql
1.
Random random = new SecureRandom();


если вы - счастливый обладатель JDK.
...
Рейтинг: 0 / 0
14.08.2020, 13:57
    #39989810
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
В продолжение Тяпничной веревки для Льва Николаича (ps. не переживайте это такая стуктура
данных а не то что вы подумали) я хотел помимо гибкой строки, реализовать еще свой полнотекстовый поиск
с блекджеком и куртизанками на три-граммах.
...
Рейтинг: 0 / 0
14.08.2020, 14:11
    #39989819
Roman Mejtes
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Несжимаемая последовательность байт
может взять алгоритм Хоффмана, сгенерировать последовательность кодов (к примеру до 24 бит) и просто плеваться ими в случайном порядке?
я конечно не уверен, но мне кажется, там будет высокий уровень энтропии
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Несжимаемая последовательность байт / 25 сообщений из 73, страница 1 из 3
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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