Методы сжатия

Я знаю, что большинство методов сжатия основаны на повторении некоторых данных, чтобы быть эффективными. Например, строка «AAAAAaaaQWERTY» может быть представлена ​​как «5A3aQWERTY» для без потерь и что-то вроде «8aqwerty» для с потерями (это только для примера, а не фактические методы работы). Насколько мне известно, все алгоритмы сжатия учитывают повторения ->константных‹- строк символов.

Здесь возникает проблема со строкой «abcdefghijklmnopqrstuvwxyz». Здесь ничего не повторяется, но, как вы, вероятно, видите, информацию в строке можно представить гораздо короче. В регулярном выражении str. будет "[a-z]" или, может быть, "for(x=0;x‹25;++){ascii(97+x)}".

Рассмотрим также строку "0149162536496481100121" - она ​​может быть представлена ​​как "for(x=0;x‹11;++){x*x}".

Строка "ABEJQZer" может быть представлена ​​как "for(x=0;8;++){ascii(64+x*x)}"

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

как и в изображениях svg (которые имеют в файле только алгоритмы) размер меньше, чем jpeg.

Мой вопрос в том, есть ли способ сжатия, который берет данные и пытается найти эффективные алгоритмы, которые могут их представить. Например, векторизация растрового изображения (например, http://vectormagic.com/), которая работает и с другими данными.

Рассмотрим аудиоданные (поскольку они могут быть сжаты с потерями) - файлы проектов некоторых аудиоредакторов (например, audacity) содержат информацию типа «генерировать постоянную частоту 120 Гц с амплитудой 0,8 от времени 0 до времени 2 минуты 45,6 секунды» (audacity хранит информацию в формате xml ). Эти метаданные занимают очень мало памяти, и когда проект экспортируется в wav или mp3, программа «преобразует» информацию в фактические сэмплы в экспортированном формате.

В этом случае компрессор должен обратить процесс рендеринга вспять. Он должен взять файл wav или mp3, выяснить, какие алгоритмы могут представлять образцы (если это с потерями, алгоритмы должны произвести некоторое приближение образцов - например, vectormagic.com аппроксимирует изображение) и создать сжатый файл.

Я понимаю, что время сжатия будет невероятно долгим, но существуют ли такие (или подобные) алгоритмы сжатия?


compression algorithm math theory sequences
person user1328370    schedule 15.04.2014    source источник
comment
Я думаю, что серия алгоритмов сжатия без потерь PAQ — это то, что вам нужно.   -  person Evgeny Kluev    schedule 27.04.2014

Ответы (3)


arrow_upward
0
arrow_downward

Все методы сжатия таковы: вывод — это набор параметров для набора алгоритмов, которые рендерят ввод, или что-то похожее на ввод.

Например, аудиокодек MP3 разбивает входные данные на блоки по 576 сэмплов и преобразует каждый блок в частотно-амплитудное пространство, удаляя то, что не может быть услышано человеком. Результат эквивалентен «в течение следующих 13 миллисекунд воспроизводить частоты x, y, z с амплитудами a, b, c». Это хорошо работает для аудиоданных, а аналогичный подход, используемый в JPEG, хорошо работает для фотографических изображений.

Аналогичные методы можно применить и к упомянутым вами случаям. Последовательности, такие как 987654 или 010409162536, например, генерируются последовательными значениями полиномов и могут быть представлены как коэффициенты этого полинома, первый как (9, -1) для 9-x, а второй как (1, 2,1) для 1+2x+x².

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

person Joni    schedule 15.04.2014

arrow_upward
0
arrow_downward

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

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

person ki92    schedule 15.04.2014

arrow_upward
0
arrow_downward

Вы можете попробовать дедупликацию данных:http://en.m.wikipedia.org/wiki/Data_deduplication . Это немного другое и более интеллектуальное сжатие данных.

person Gigamegs    schedule 15.04.2014