У меня есть файл, содержащий упорядоченные двоичные числа от до 2 n - 1 :
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111
7z не сжимал этот файл очень эффективно (при n = 20 22 МБ были сжаты до 300 кБ).
Существуют ли алгоритмы, которые могут распознать очень простую структуру данных и сжать файл до нескольких байтов? Также я хочу знать, в какой области КС или теории информации изучаются такие умные алгоритмы. «AI» будет слишком широким, пожалуйста, предложите более конкретные ключевые слова.
Понятие симметрии должно играть основополагающую роль в сжатии данных, но поисковые запросы «симметрия в сжатии данных» и «теория групп в сжатии данных» на удивление почти ничего не значат.
information-theory
data-compression
DSblizzard
источник
источник
Ответы:
В отличие от предложения DW «все или ничего», дельта-сжатие с кодированием по длине прогона может фактически дать разумные коэффициенты сжатия для некоторых простых реальных видов контента, таких как аудио с низким разрешением. (Таким образом, он подходит для сжатия звука низкого качества, с очень низкой задержкой и низким энергопотреблением.)
источник
Конечно, конечно, есть алгоритмы. Вот мой алгоритм:
Если нет, запишите 1 бит, затем запишите 7z-сжатие файла.
Это чрезвычайно эффективно для файлов этой конкретной структуры.
Дело в том, что в сжатии данных нет бесплатного обеда. Возможно, вам удастся создать алгоритм сжатия, который хорошо сжимает один тип файла, за счет сжатия других хуже. Но если вы априори знаете что-то о природе файлов, которые вы будете сжимать, вы можете оптимизировать свой алгоритм для этого конкретного типа файла.
Область "сжатие данных". Смотрите наш тег сжатия данных и читайте учебники по сжатию данных.
источник
Все, что использует BWT (преобразование Берроуза-Уилера), должно быть в состоянии сжать это достаточно хорошо.
Мой быстрый тест на Python:
(Числа здесь 'first_compressor second_compressor time_taken bytes_out')
(BWT взято отсюда )
Это по-прежнему «не просто несколько байтов», но, тем не менее, гораздо лучше, чем просто один gzip. Например, BWT + bz2 уменьшается до 237 байтов с 1114111 для 16-битного ввода.
Увы, BWT слишком медленные и требуют много памяти для многих приложений. Особенно учитывая, что это наивная реализация в Python - на моей машине до 2 ** 20 у меня не хватает оперативной памяти.
С Pypy я смог запустить полный ввод 2 ** 20, и он сжимает его до 2611 байт с BWT, за которым следует bz2. Но это заняло более 3 минут и более 4 ГБ оперативной памяти ...
Кроме того, к сожалению, этот подход по-прежнему составляет O (2 ^ n) выходного пространства, как кажется - по крайней мере, из подгонки кривой 1..20.
источник
eval
этого:for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):
иfOut = first.compress(inputData)
.4 times block size
памятью (например, ~ 4 МБ для этого) и со скоростью>10 MB/s
(я являюсь автором такого алгоритма библиотеки / сжатия bwt), который вполне пригоден для многих приложений. Обратите внимание, что даже gzip дает очень хорошие сжимаемые результаты. Спасибо, что поделились, я не знаю ни одного исследования по использованию bwt дважды.Кодировка PNG делает именно то, что вы хотите. Он также работает с реальными данными, а не только с чрезвычайно организованными данными.
В PNG каждая строка кодируется с помощью фильтра, из которых 4 указаны. Одним из них является «кодирование этого пикселя как разности между его значением и значением пикселя над ним». После фильтрации данные архивируются с использованием DEFLATE.
Эта фильтрация является конкретным примером дельта-кодирования, упомянутого leftaroundabout в его ответе, за исключением того, что вместо того, чтобы использовать кодировку длины выполнения, вы применяете более мощный алгоритм DEFLATE. Он выполняет ту же цель, только DEFLATE будет обрабатывать большее количество входных данных, в то же время обеспечивая желаемые коэффициенты сжатия.
Другим инструментом, который часто используется в научных данных, где простой фильтр + DEFLATE не так эффективен, является кодирование RICE. В RICE вы берете блок значений и выводите сначала все старшие значащие биты, а затем все вторые старшие биты, вплоть до младших значащих бит. Затем вы сжимаете результат. Для ваших данных это не так эффективно, как для фильтрации в стиле PNG (потому что ваши данные идеально подходят для фильтрации в формате PNG), но для многих научных данных это приводит к хорошим результатам. Во многих научных данных мы видим, что наиболее значимый бит имеет тенденцию к медленному изменению, а наименее значимый - почти случайный. Это отличает сильно предсказуемые данные от высокоэнтропийных данных.
источник
Любой практический алгоритм поиска конкретных структур будет ограничен только структурами, жестко закодированными в нем. Вы могли бы исправить 7z, чтобы распознать эту конкретную последовательность, но как часто эта конкретная структура будет встречаться в реальной жизни? Не достаточно часто, чтобы гарантировать время, необходимое для проверки входных данных для этого ввода.
Помимо практических возможностей, идеальный компрессор можно представить как алгоритм, который пытается построить самую короткую программу, которая дает заданный результат. Само собой разумеется, нет никаких практических способов сделать это. Даже если вы попробовали перебор всех возможных программ методом «грубой силы» и проверили, дали ли они желаемый результат ( не совсем безумная идея ), вы столкнетесь с проблемой остановки , то есть вам придется прервать пробные запуски после определенного числа шагов выполнения, прежде чем вы узнаете, может ли эта программа определенно не произвести желаемый вывод.
Дерево поиска для такого подхода грубой силы растет экспоненциально с длиной программы и не практично для всех, кроме самых простых программ (что-то вроде 5-7 инструкций).
источник
Коэффициенты сжатия полностью зависят от целевого декомпрессора. Если декомпрессор не может декодировать последовательные 4-байтовые числа более компактно, чем 4 байта на число, тогда вы SOL.
Существуют различные вещи, которые позволяют кодировать последовательные числа. Например, дифференциальное кодирование. Вы берете n байтов за раз, затем берете разность или xor битов и затем сжимаете результат. Это добавляет 4 варианта, чтобы попробовать для каждого байта: идентичность
a'[i] = a[i]
; разницаa'[i] = a[i-1]-a[i]
; обратная разницаa'[i] = a[i]-a[i-1]
; и хорa'[i] = a[i]^a[i-1]
. Это означает добавление 2 битов для выбора методов и количество байтов для 3 из 4 вариантов.Однако не все данные являются последовательностью записей фиксированной длины. Дифференциальное кодирование не имеет смысла для этого (если компрессор не может эмпирически доказать, что он работает для небольшого количества данных).
источник