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


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

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

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

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

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

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

Остался пустяк. Придумать быстрый детектор этих повторов. Здесь я застрял.
...
Рейтинг: 0 / 0
Несжимаемая последовательность байт
    #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
Несжимаемая последовательность байт
    #39989486
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Несжимаемая последовательность байт
    #39989488
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Без этого дефлейта не обходится ни один современный архиватор или файловый упаковщик.
И внутри Gif картинок он вобщем-то есть. И в Zip. И в jar/war/ear. И игровые форматы упаковки
ресурсов. И Андроидовские.
...
Рейтинг: 0 / 0
Несжимаемая последовательность байт
    #39989491
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
спасибо, не знала

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


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

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

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


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


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


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

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

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


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

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

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

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


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

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


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


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