Пользовательские типы данных Сжатие

Question

В настоящее время у меня есть приложение, которое требует от меня отправлять данные с наименьшим количеством бит. Например, если я даю направление в градусах, то диапазон равен 0 -359. это означает, что с 9 бит, у меня есть число 0 - 511 с разрешением 1. Было бы «отходы» из 152 возможных результатов. Я мог бы использовать эти возможные результаты для обработки ошибок, но мне интересно, есть ли какой-либо метод, который можно было бы использовать для упаковки в некоторые другие данные.

Единственная другая мысль, которую я имел, я мог бы добавить коэффициент умножения 359/511, чтобы я мог сжать немного более точно.

Edit: Дополнительная информация:

1. Следует исходить из того, что не все сообщения будут проходить через

некоторые примеры полей:

Направление базовой (360) дня основания (366) час основа (24) минута основа (60)

Wit h эти три примера, общее количество исчисленных исходов составляет 905.

Answer 1

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

Вы можете передавать несколько номеров одновременно в базе 360. Вот как кодировать и три номера:

int encoded = num0 + 360 * num1 + 360 * 360 * num2; 
var decoded0 = encoded/1 % 360; 
var decoded1 = encoded/360 % 360; 
var decoded2 = encoded/360/360 % 360; 

Если вы должны были использовать BigInteger вы могли бы достичь теоретически оптимальным кодируя этот путь в случае бесконечно (или практически очень многих) чисел.

Или вы можете использовать вариант arithmetic coding, который поддерживает более 2 альтернатив. С арифметическим кодированием вы можете кодировать числа пошагово и извлекать биты по мере их появления. Вам нужна только постоянная память.

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

Answer 2

Для конкретного примера, который вы указали: «Основание направления (360) Основание базы (366)» (24) минутное основание (60) », получается, что два из них очень хорошо вписываются в 55 бит. (360 x 366 x 24 x 60) - это всего лишь кусочек менее 2 . Поэтому для кодирования и декодирования вы просто используете умножение и деление (получение как частного, так и остального) соответственно. Это можно сделать с помощью 64-битной арифметики, поэтому не требуются большие целые процедуры. Фактически, только 0,001 бит из 55 бит теряются!

Так что для direction:day:hour:minute с диапазонами 1..360, 1..366, 1..24, 0..59 и, то последовательность {a:b:c:d, e:f:g:h} кодируется как (((((((a - 1) * 366 + (b - 1)) * 24 + (c - 1)) * 60 + d) * 360 + (e - 1)) * 366 + (f - 1)) * 24 + (g - 1)) * 60 + h. Для декодирования возьмите оставшуюся часть деления на 60, чтобы получить h. Возьмите этот фактор, а затем остаток деления на 24, чтобы получить g - 1 и так далее.

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

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

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