Существуют ли алгоритмы сжатия случайных данных с конечным алфавитом?

Question

[chilicactus]

Итак, есть случайная строка заданной длины и с заданным алфавитом. Длину и алфавит исходной строки можно задавать как угодно. Нужно сократить количество символов не изменяя алфавит. Т.е. если на входе была строка из 256 цифр от 0 до 9, то и на выходе должна получиться строка состоящая только из цифр, но короче.

Я пробовал применять классику, вроде RLE, LZ и Хаффмана. Пробовал реализовывать сам, пробовал брать готовое, пробовал менять параметры строки, но в лучшем случае получал ту же длину, обычно размер только увеличивался. Либо я чего-то не понимаю, либо у входных данных слишком высокая энтропия.

1) Такие алгоритмы вообще существуют?
2) Если да, то хотелось бы пример реализации, на любом языке.
3) И пару книжек по теме для совсем тупеньких :)

Comments

[Довольный Айтишникъ]

должна получиться строка состоящая только из цифр, но короче

А куда в этой строке по вашему запишется информация о первоначальном расположении и количестве цифр? Как потом восстановить исходную строку?

[cicatrix]

А сжульничать нельзя? Если представить исходные данные в двоичном виде, то алфавит будет из 2 символов - 0 и 1.
После этого применить любой из доступных алгоритмов, который выдаст результат в том же алфавите 0 и 1.

[Labunsky]

Если данные совсем-совсем случайные, а сжатие очень-очень нужно, то можно пожертвовать их частью и использовать алгоритмы сжатия с потерями

Answer 1

[Rsa97]

Случайные данные - это наихудший вариант для сжатия. Практически все алгоритмы сжатия данных без потерь основаны на поиске закономерностей и повторяющихся последовательностей. В случайной последовательности нет ни того, ни другого.

Comments

[Роман]

Надо только добавить что при фиксированном алфавите и объеме сжимаемых данных стремящемуся к бесконечности, количество повторяющихся блоков данных так же будет стремится к бесконечности, что теоретически позволит их сжимать без потерь. Но эффективность такого сжатия будет сильно зависеть от взаимного соотношения этих двух бесконечностей, а это уже тема для отдельной беседы)

[Армянское Радио]

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

[Роман]

Армянское Радио, вчера полночи пытался сжать 10000 случайно сгенерированных чисел (равномерный ЗР) в диапазоне от 0 до 255. Результат есть, но столь незначительный, что можно считать погрешностью. Так что скорее соглашусь с вами чем не соглашусь

[Армянское Радио]

Роман, это элементарно следует из теории вероятностей. Вероятность встретить в совершенно случайном потоке (которым является Pi) какую-то напред заданную последовательность мала (например, для десятка нулей подряд в десятичной записи она равна 10^-10 степени).

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

[Роман]

Армянское Радио, я же вроде об этом же писал)))

...эффективность такого сжатия будет сильно зависеть от взаимного соотношения этих двух бесконечностей...

[Армянское Радио]

Роман, а я это и не оспариваю. Я оспариваю тот факт, что бесконечный поток истинно случайных данных можно сжать без потерь.

Не можно, иначе бы иррациональных чисел в математике бы не существовало.

[Роман]

Армянское Радио, спорить не буду, приведу данные тестов (которые в принципе лишь подтверждают сказанное вами но с оговорками)

объем пакуемых данных - 65536 знаков
алгоритм упаковки - сопоставление с псевдослучайной последовательностью
число экспериментов для каждой размерности алфавита - 1000
при алфавите в 8 знаков на выходе ~24000 знаков ( степень сжатия примерно 63%)
при алфавите в 16 знаков на выходе ~61000 знаков ( степень сжатия примерно 7%)
при алфавите в 32 знака на выходе 65536 знаков ( степень сжатия примерно 0%)

Таким образом сжимать все же можно, но как вы (да и я тоже) и сказали, комбинаторная мощность должна быть существенно меньше объема сжимаемых данных, что в свою очередь трудно достижимо для алфавита большой размерности.

Сам алгоритм и тесты выложу когда доработаю, пока что реализация не читаемая (лапша и костыли)))))

[Rsa97]

Роман, Обратите внимание на требование ТС - алфавит должен остаться неизменным.

[Роман]

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

Теоретически можно и не включать, для этого опираемся на предположение что в достаточно большом объеме данных будут присутствовать все знаки словаря, а так как в вычислительной технике любые знаки представляются в виде нулей и единиц, то они могут быть отсортированы по возрастанию и индексы присвоены согласно порядковому номеру в сортировке. Но это конечно так себе решение (нет гарантии, что в данных будут представлены все символы алфавита)

[Rsa97]

Роман, А оценку размера упакованных данных вы делали уже после приведения их к исходному алфавиту?

[Роман]

Лентюй, про неверный ответ хотелось бы по подробнее для саморазвития

[Роман]

Rsa97, само собой разумеется)

Answer 2

[Adamos]

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

Answer 3

[Griboks]

Хотелось бы уведомить гениев наподобие Rsa97 и Adamos.
Для примера возьмём исходную случайную последовательность: 3333221 (всего 7 цифр).
Теперь используем известный алгоритм кодирования длин серий: 432211 (всего 6 цифр). Ура, нам удалось сжать "несжимаемое".
Остался вопрос: а когда этот алгоритм будет эффективным? Когда коэффициент асимметрии распределения значителен по модулю.

p.s.
Некоторые могут сказать, что моя последовательность неслучайна. Если так, то предлагаю этим умельцам продолжить её до 20 цифр. В противном случае последовательность является случайной по определению.

p.s.s
Некоторые люди подразумевают под случайностью равномерно распределённую случайную величину. В таком случае предлагаю использовать архиватор бабушкина - для 256 цифр он будет работать довольно быстро. Ну или просто перебрать все строки длины 256 и записать номер исходной.

Comments

[Saboteur]

на заметку гениям

1. Внимательно прочитал вопрос топикстартера. и не нашел там исходной случайной последовательности 3333221
Поэтому давайте возьмем случайную последовательность например 13241571872331, и попробуем сжать вашим алгоритмом кодирования серий. Что получаем?

2. "В таком случае предлагаю использовать архиватор бабушкина - для 256 цифр он будет работать довольно быстро"
Внимательно прочитал вопрос топикстартера, и не нашел там что входные данные могут быть ограничены 256 цифрами. Там был просто пример.
А так, алфавит может быть задан любыми знаками, длина может быть произвольной.
Важное правило, которое указал топикстартер - выходная последовательность должна состоять из того же набора символов что и входная.

[Роман]

это вы так свое эго повышаете, противопоставляя себя там, где и так все ясно?

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

Да и вообще, приводить частный случай в качестве доказательства общей тенденции это такое себе УГ...

[Robur]

можно развить вашу идею еще дальше и посрамить всех "гениев" еще больше:
Возьмем случайную последовательность "1289379238740". А теперь алгоритм, который всегда выводит "1289379238740". Ура, нам удалось сжать случайную последовательность до 0 байт.
Остался вопрос - когда этот алгоритм будет эффективным. Но это несущественные мелочи, приведенный выше пример явно показывает что любые случайные данные можно сжать до 0 байт.

[Griboks]

Saboteur, так а вы прочитайте ответы. Люди утверждают, что сжать невозможно. Вот вам несколько примеров, что это очень даже возможно.

А насчёт топикстартера- случайная последовательность не бывает дискретными цифрами,если только это не квантовый генератор. Также любой алфавит можно перевести в любой другой алфавит с точностью до количества символов. Кроме того, не забывайте, что он не указал и минимальную длину последовательности. Поэтому мой пример все ещё актуален.

[Griboks]

Роман, нет, я просто предостерегаю автора поверить вам. Один частный пример может опровергнуть всю теорию. А вот утверждать такие большие вещи - это действительно уг.

[Griboks]

Robur, да, так и есть. Я же написал про архиватор бабушкина. Вопрос только во времени кодирования. Если вам не известна исходная последовательность, то вам придётся запрограммировать все возможные алгоритмы.

[Роман]

Griboks, опять передергиваете.

то вам придётся запрограммировать все возможные алгоритмы.

А ничего, что количество этих алгоритмов настолько велико что индекс нужного алгоритма (количество нулей и едениц, необходимых чтобы этот индекс записать) будет сопоставимо с длинной кодируемых данных?

[Griboks]

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

Кстати, не забывайте и про распределение. А то формулировка "может сжать, а может и нет - 50 на 50" некорректна. Это как взять случайный инструмент и попытаться забить им гвозди. Да, конечно,
если мы возьмём случайные данные и прогоним их через случайный алгоритм, то получим случайный результат. Вот так новость!

[Adamos]

Saboteur,

1. Внимательно прочитал вопрос топикстартера

Тогда зачем вы спорите с человеком, который этого не сделал? ;)
ТС сразу сказал, что сжать данные популярными алгоритмами у него - не получалось. И спрашивал - за алгоритмы. Зная, например, что такое энтропия.
Но тут вышел комментатор весь в белом и начал что-то выковыривать у себя из носа... Громко заявляя, что все вокруг пишут чушь (потому что их ответов он тоже не читал, но ему так показалось). С чем тут спорить?..

[Saboteur]

Griboks,
Архиватор Бабушкина - это не архиватор, а шутка.
Архивировать таким образом можно КОНКРЕТНУЮ а не случайную последовательность.
Потому что размер архиватора для всех случайных последовательностей (а у топикстартера ни длина ни алфавит не ограничены) - займет больше места, чем есть ресурсов.

В любой последовательности можно найти закономерность

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

Поэтому прекратите демагогию.

[Роман]

Saboteur, поддерживаю.

[Griboks]

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

Тот факт, что автор не задал ограничения ещё вовсе не значит, что:
а) последовательность очень длинная или наоборот очень короткая,
б) последовательность действительно случайная, а не псевдослучайная,
в) последовательность имеет равномерный закон распределения,
г) неизвестна природа ГСЧ.
Та же логика относится и к алфавиту. Между прочим, демагогию разводите вы и ваши друзья, переводя стрелки с вопроса и ответов на гадание на кофейной гуще и разнообразные теоретические рассуждения.

[Adamos]

Griboks, согласен, давайте прекратим демагогию и перейдем к конкретике.
Просто ответьте ТС по второму и третьему пункту его вопроса.

Answer 4

[Wataru]

Очень мешает ограничение на фиксированный выходной алфавит, если в этом алфавите не степень двойки символов (как для цифр от 0 до 9). Так-то многие алгоритмы сжатия пользуются тем, что можно записать минимально возможную единицу информации - один бит. Иначе неэффективно сжимается. А на случайных данных без какой-то структуры и с большой энтропией и так все хреново работает.

Советую посмотреть в сторону Burrows-Wheeler transform и потом попробовать RLE или LZ присобачить сверху. Может, ваши данные будут им хорошо сжиматься.

Еще вам тут сильно помогло бы что-то вроде Base64 encode/decode. Допустим у вас k символов в алфавите. Значит каждый символ несет log_2(k) бит. И если у вас символов N, то ваша входная строка содержит N*log_2(k) бит информации. Округлите это число вверх и сгенерируйте столько битов. Это фактически преобразование из k-ичной системы счисления в двоичную. На больших строках будет тормозить, потому что пока мне не очевидно, как для произвольного k делать преобразование быстро, а не делить большое число на 2 с остатком. Если только у вас k не степень двойки, тогда как в base64 можно быстро преобразовывать по блокам.

Потом можно эту битовую строку сжать каким угодно алгоритмом (разбить на блоки, скажем, 8 бит и хоть хаффманом, хоть lz). Потом надо сжатую битовую строку преобразовать назад в k-ичную систему счисления.

Можно комбинировать сжатие на исходном тексте и запись произвольной битовой строки в вашем алфавите. Например после BW-transform вы гоните LZ на тексте из цифр. LZ для эффективности надо уметь писать произвольные битовые строки. Вот вы где-то в памяти отдельно собираете новые символы, которые замыкают новые строки-эталоны (цифры в вашем примере), и отдельно битовую строку. Потом эту строку переведите в k-ичную систему счисления и запишите перед просто символами (как-то закодировав ее длину в скольки-то первых символах заголовка).

Answer 5

[ComodoHacker]

Универсальные алгоритмы сжатия не смогут сжать случайные данные (см. ответ Rsa97). Но если знать специфику данных, откуда они поступают, может что-то и получится. Например, все же выявить какие-то закономерности.

Comments

[Rsa97]

Соглашусь. Если символы псевдослучайные, то достаточно знать алгоритм и стартовое значение (seed).

[Rsa97]

Лентюй, Почему? ЕМНИП, одним из требований к генератору псевдослучайных чисел является многократная воспроизводимость результата.