Сжатие без потерь (математика)

Сжатие без потерь (математика)

Звук является простой волной, а цифровой сигнал является представлением этой волны. Это достигается запоминанием амплитуды аналогового сигнала множество раз в течение одной секунды. Например, в обыкновенном CD сигнал запоминается 44100 раз за секунду. Так как CD работает со стерео, мы запоминаем сигнал для левой и правой колонки параллельно. Для каждого замера используются 16 битовые числа. Обычный WAV-файл — это поток информации, представленный массивом R, L, R, L…. Поэтому нетрудно посчитать, что одна секунда звучания занимает (16 + 16) * 44100 = 1411200 бит или 176400 байт.

Сжатие без потери качества (lossless)

• Переход к X, Y (сделать сигнал более сглаженым)

Первым шагом в сжатии будет представление каналов аудио L и R, более эффективным образом, представив их некими числами X, Y согласно следующему алгоритму

X = (L + R) / 2
Y = (L − R)

Понятно, что это преобразование не теряет информации и является эквивалентным оригинальному

Примечание: (L+R)/2 теряет 0,5 при конверсии в INTEGER, когда, например, L четно, а R нечетно, но, проверив четность (L-R), легко восполняем, где надо.

• Предикатор (представить данные как можно меньшими числами)

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

В данном случае весь процесс направлен на представление массивов X, Y минимально возможными числами, все еще сохраняя обратимость процесса. Есть множество способов сделать это. Один из них - преобразование с использованием линейной алгебры:

PX = (2 * X_-1) − X_-2
PY = (2 * Y_-1) − Y_-2

Если X = (2, 8, 24, ?), то в ряду PX на четвертом месте будет P4 = (2 * X_4-1) − X_4-2 = (2 * 24) − 8 = 40
То есть, если X = (2,8,24,27,25,28,21,17), то PX = (2,8,14,40,30,…)

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

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

Пусть число m лежит в диапазоне 0 … 1024. Для массива PX выполняется серия преобразований с разными значениями m следующим образом:

X = (2, 8, 24, ?), тогда соответственно
PX = (2 * X_-1) − X_-2 = (2 * 24) − 8 = 40

Если ? = 45 и m = 512, тогда конечное значение = ? − (PX * m / 1024) = 45 − (40 * m / 1024) = 45 − (40 * 512 / 1024) = 45 − 20 = 25

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

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

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

Приведем пример нескольких уравнений, как это следует из технической литературы

P0 = 0
P1 = X_-1
P2 = (2 * X_-1) − X_-2
P3 = (3 * X_-1) − (3 * X_-2) + X_-3

• Кодирование. Алгоритм Райса

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

Меньшие числа предпочтительней тем, что их представление в бинарном представлении короче. Например, необходимо закодировать следующий ряд:

Базис по основанию 10: 10, 14, 15, 46

Или тот же ряд в бинарном виде

Базис по основанию 2: 1010, 1110, 1111, 101110

Теперь если требуется представить этот в виде строки, где для каждого числа зарезервировано 32 бита (диапазон всех возможных значений), то это будет неэффективно, поскольку понадобится 128 бит. Однако существует более эффективный метод. Наилучшим решением было бы просто записать бинарные числа 1010, 1110, 1111, 101110 без запятых, получив ряд вида 101011101111101110. Проблема в том, что после нет возможности узнать границы каждого числа. В качестве решения подобной задачи, как правило, используется алгоритм Райса.

Кодирование Райса - это способ представить маленькие числа одной строкой, сохраняя способность их различать.

Примечание: алгоритм тем эффективнее, чем меньше числа, поэтому необходимо изначально позаботиться об этом

На каком-то этапе кодирования данные представлены в виде числа n. Закодированное, оно добавляется справа к строке уже закодированных чисел таким образом, чтобы был возможен обратный процесс.

Основная идея представить число n как n = q * k + r, так что бы 0 <= r < k.

Так как в машинном языке существует сверхбыстрая команда ротации числа, соответствующая делению числа на степени двойки, достаточно использовать k=log n/log 2, округленное до наименьшего целого числа. Таким образом, в алгоритме гарантированно выполняются условия для k.

Далее в процессе возникают числа q и r. Наиболее простой способ их определения состоит в том, что:

n = 46 (десятичное) = 101110 (двоичное)
k = 4 (например)

запоминаются k правых цифр (1110 или 14 в десятичной системе). Производится побитовое смещение числа вправо на k, получается (10 или 2 в десятичной системе). То есть

46 = 2 * 2⁴ + 14

Далее строится кодированное число по следующей схеме. Первыми идут нули, количеством в q штук [00]. Далее справа к нулям добавляется маркировочный бит [1], что бы знать когда кончаются нули. А за ними пишется остаток r [1110], длинной в k бит.

То есть число 46 в закодированном виде выглядит [00][1][1110] = 0011110

Теперь, с учетом определенности k, которым кодировалось число, можно с легкостью его расшифровать:

(количество нулей) * 2⁴ + (k бит следующих за маркировочным битом) = 2*2⁴+14 = 46

Следующее число начинается сразу же со следующего бита.

Если данные кодируются с помощью слишком большого числа k, например k=32, тогда способ превращается в описанный в начале раздела метод, когда каждому числу соответствует 32 бита, только оно предваряется бесполезным маркировочным битом. В случае малого k, то количество нулей экспоненциально возрастает — для k=0. Для представления числа 46 понадобится 46 нулей и 1 маркировочный бит. Оптимальный вариант, учитывая, что в ряду калибровочные изменения минимальны, - это кодировать среднестатистическим значением для k, например для кодирования сотого числа k высчитывается как среднестатистический размер чисел в массиве под индексами 0…99.

Оптимальное k может быть вычислено и экспериментальным способом: например, любое k между 16…128 нормально работает. В любом случае, если известен примерный диапазон закодированных значений, то оптимальное значение для k = log n / log 2.