Блог

Задано 15 случайных шестнадцатеричных чисел (60 бит), где в каждом 20-битном прогоне всегда есть по крайней мере 1 дубликат (5 шестнадцатеричных чисел).

Каков оптимальный способ сжатия байтов?

Вот несколько примеров:

 01230 45647 789AA
D8D9F 8AAAF 21052
20D22 8CC56 AA53A
AECAB 3BB95 E1E6D
9993F C9F29 B3130
  

Изначально я пытался использовать кодировку Хаффмана всего на 20 бит, потому что кодирование Хаффмана может варьироваться от 20 бит до ~ 10 бит, но для хранения таблицы требуется более 9 бит.

Вот разбивка, показывающая 20 бит -> 10 бит для 01230

 Character   Frequency   Assignment  Space Savings
0           2           0           2×4 - 2×1 = 6 bits
2           1           10          1×4 - 1×2 = 2 bits
1           1           110         1×4 - 1×3 = 1 bits
3           1           111         1×4 - 1×3 = 1 bits
  

Затем я попытался выполнить кодирование Хаффмана для всех 300 бит (пять 60-битных запусков), и вот сопоставление, приведенное в приведенном выше примере:

 Character   Frequency   Assignment  Space Savings
---------------------------------------------------------
a           10          101         10×4 - 10×3 = 10 bits
9           8           000         8×4 - 8×3 = 8 bits
2           7           1111        7×4 - 7×4 = 0 bits
3           6           1101        6×4 - 6×4 = 0 bits
0           5           1100        5×4 - 5×4 = 0 bits
5           5           1001        5×4 - 5×4 = 0 bits
1           4           0010        4×4 - 4×4 = 0 bits
8           4           0111        4×4 - 4×4 = 0 bits
d           4           0101        4×4 - 4×4 = 0 bits
f           4           0110        4×4 - 4×4 = 0 bits
c           4           1000        4×4 - 4×4 = 0 bits
b           4           0011        4×4 - 4×4 = 0 bits
6           3           11100       3×4 - 3×5 = -3 bits
e           3           11101       3×4 - 3×5 = -3 bits
4           2           01000       2×4 - 2×5 = -2 bits
7           2           01001       2×4 - 2×5 = -2 bits
  

Это дает экономию в 8 бит в целом, но 8 бит недостаточно для хранения таблицы Хаффмана. Из-за случайности данных кажется, что чем больше битов вы пытаетесь закодировать с помощью Хаффмана, тем менее эффективно это работает. Кодирование Хаффмана, казалось, лучше всего работало с 20 битами (сокращение на 50%), но сохранение таблицы в 9 или менее битах невозможно AFAIK.

В наихудшем случае для 60-битной строки все еще остается как минимум 3 дубликата, в среднем случае более 3 дубликатов (мое предположение). В результате, по крайней мере, 3 дубликатов, максимальное количество символов, которое вы можете иметь за 60 бит, составляет всего 12.

Из-за дубликатов плюс менее 16 символов я не могу не чувствовать, что существует какой-то тип сжатия, который можно использовать

Если я просто подсчитаю количество 20-битных значений, в которых по крайней мере две шестнадцатеричные цифры равны, их будет 524 416. Немного больше, чем 2 ¹⁹. Таким образом, максимум, что вы могли бы сэкономить, — это чуть меньше одного бита из 20.

Вряд ли это того стоит.

Если я разделю ваш вопрос на две части:

1. Как мне сжать (идеальные) случайные данные: вы не можете. Каждый бит — это некоторая новая энтропия, которая не может быть «угадана» алгоритмом сжатия.
2. Как сжать «один дубликат в пять символов»: существует ровно 10 вариантов, где может быть дубликат (см. Таблицу ниже). Это в основном энтропия. Просто сохраните, какой это параметр (возможно, сгруппированный для всей строки).

Это варианты:

 AAbcd = 1    AbAcd = 2    AbcAd = 3    AbcdA = 4    (<-- cases where first character is duplicated somewhere)
             aBBcd = 5    aBcBd = 6    aBcdB = 7    (<-- cases where second character is duplicated somewhere)
                          abCCd = 8    abCdC = 9    (<-- cases where third character is duplicated somewhere)
                                       abcDD = 0    (<-- cases where last characters are duplicated)
  

Итак, для вашего первого примера:

 01230 45647 789AA
  

Первый (01230) является опцией 4 , вторым 3 и третьим вариантом 0 .

Вы можете сжать это, умножив каждое последующее на 10: (4*10 3)*10 0 = 430 И распакуйте его, используя деление и деление по модулю: 430=0, (430/10)=3, (430/10/10)=4. Таким образом, вы могли бы сохранить свой номер таким образом:

 1AE 0123 4567 789A
^^^ this is 430 in hex and requires only 10 bit
  

Максимальное число для трех объединенных параметров равно 1000, поэтому достаточно 10 бит.

По сравнению с сохранением этих 3 символов обычно вы экономите 2 бита. Как кто-то уже прокомментировал — это, вероятно, того не стоит. Для всей строки это еще меньше: 2 бита / 60 бит = 3,3% экономии.

Если вы хотите сначала избавиться от дубликатов, сделайте это, затем посмотрите на ссылки внизу страницы. Если вы не хотите избавляться от дубликатов, то все равно посмотрите на ссылки внизу страницы:

 Array.prototype.contains = function(v) {
  for (var i = 0; i < this.length; i  ) {
    if (this[i] === v) return true;
  }
  return false;
};

Array.prototype.unique = function() {
  var arr = [];
  for (var i = 0; i < this.length; i  ) {
    if (!arr.contains(this[i])) {
      arr.push(this[i]);
    }
  }
  return arr;
}

var duplicates = [1, 3, 4, 2, 1, 2, 3, 8];
var uniques = duplicates.unique(); // result = [1,3,4,2,8]

console.log(uniques);
  

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

Smaz — это простая библиотека сжатия, подходящая для сжатия строк.

Если это не сработает, вы можете взглянуть на это:

http://ed-von-schleck.github.io/shoco/

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

Дайте мне знать, если это сработает!