Лучший алгоритм сжатия последовательности целых чисел

Question

У меня есть большой массив с целым числом целых чисел, которые в основном непрерывны, например, 1-100, 110-160 и т. Д. Все целые числа положительны. Какой был бы лучший алгоритм для сжатия этого?

Я пробовал алгоритм дефляции, но это дает мне только 50% сжатия. Обратите внимание, что алгоритм не может быть потерянным.

Все номера уникальны и постепенно увеличиваются.

Также, если вы можете указать мне на реализацию Java такого алгоритма, что было бы здорово.

Answer 1

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

Вы можете взглянуть на эти и другие алгоритмы без потерь here.

Answer 2

компресс строка «1-100, 110-160» или хранить строку в некотором двоичном представлении и разобрать его, чтобы восстановить массив со

Answer 3

Ну, я буду голосовать за разумный способ. Все, что вам нужно сохранить, это [int: startnumber] [int/byte/whatever: количество итераций] в этом случае, вы превратите свой массив примеров в значение 4xInt. После этого вы можете сжимать, как хотите.

Answer 4

Сначала предварительно обработайте список значений, взяв разницу между каждым значением и предыдущим (для первого значения, предположим, что предыдущий был равен нулю). Это должно в вашем случае дать в основном последовательность единиц, которые могут быть сжаты намного легче с помощью большинства алгоритмов сжатия.

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

Answer 5

Я бы объединил ответы, данные CesarB и Fernando Miguélez.

Сначала сохраните различия между каждым значением и предыдущим. Как отметил CesarB, это даст вам последовательность в основном из них.

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

Answer 6

Предлагаю взглянуть на Huffman Coding, специальный случай Arithmetic Coding. В обоих случаях вы анализируете свою начальную последовательность, чтобы определить относительные частоты разных значений. Более часто встречающиеся значения кодируются с меньшим количеством бит, чем менее часто встречающиеся.

Answer 7

Хотя вы могли бы разработать собственный алгоритм, специфичный для вашего потока данных, вероятно, проще использовать алгоритм кодирования с полки. Я провел несколько tests of compression algorithms available in Java и нашел следующие степени сжатия для последовательности одного миллиона последовательных целых чисел:

None  1.0 
Deflate  0.50 
Filtered 0.34 
BZip2  0.11 
Lzma  0.06 

Answer 8

Какого размера номер? В дополнение к другим ответам вы можете рассмотреть кодировку с расширенной длиной базы-128, которая позволяет хранить меньшие числа в одиночных байтах, сохраняя при этом большее число. MSB означает «есть еще один байт» - здесь described.

Объедините это с другими технологиями, чтобы сохранить «размер пропусков», «принять размер», «пропустить размер», «принять размер», но отмечая, что ни «пропустить», ни «принять» никогда не будет равным нулю, поэтому мы вычитаем один из каждого (что позволяет сохранить дополнительный байт для нескольких значений)

Итак:

1-100, 110-160 

является «перескочить 1» (предположим, что начинаются с нуля, как это делает вещи проще), «взять 100», «пропустить 9», «взять 51»; вычесть 1 из каждой, что дает (как знаков после запятой)

0,99,8,50 

, который кодирует, как (HEX):

00 63 08 32 

Если мы хотим, чтобы пропустить/принимать большее число - 300, например; мы вычитаем 1, давая 299 - но это превышает 7 бит; начиная с шатуном, мы кодировать блоки 7 бит и MSB, чтобы указать продолжение:

299 = 100101100 = (in blocks of 7): 0000010 0101100 

так, начиная с шатуном:

1 0101100 (leading one since continuation) 
0 0000010 (leading zero as no more) 

дает:

AC 02 

Так мы можем легко кодировать большие числа, но небольшие числа (которые типичны для пропусков/взятий) занимают меньше места.

Вы можете попробовать работает это через «сдуваться», но она не может помочь гораздо больше ...

---

Если вы не хотите иметь дело со всем, что грязный кодирования cruff сами .. если вы можете создать целочисленный массив значений (0,99,8,60) - вы можете использовать protocol buffers with a packed repeated uint32/uint64 - и он сделает всю работу за вас ;-p

Я не «делаю» «Java, но вот полная реализация C# (заимствование некоторых битов кодирования из моего проекта protobuf-net):

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
static class Program 
{ 
    static void Main() 
    { 
     var data = new List<int>(); 
     data.AddRange(Enumerable.Range(1, 100)); 
     data.AddRange(Enumerable.Range(110, 51)); 
     int[] arr = data.ToArray(), arr2; 

     using (MemoryStream ms = new MemoryStream()) 
     { 
      Encode(ms, arr); 
      ShowRaw(ms.GetBuffer(), (int)ms.Length); 
      ms.Position = 0; // rewind to read it... 
      arr2 = Decode(ms); 
     } 
    } 
    static void ShowRaw(byte[] buffer, int len) 
    { 
     for (int i = 0; i < len; i++) 
     { 
      Console.Write(buffer[i].ToString("X2")); 
     } 
     Console.WriteLine(); 
    } 
    static int[] Decode(Stream stream) 
    { 
     var list = new List<int>(); 
     uint skip, take; 
     int last = 0; 
     while (TryDecodeUInt32(stream, out skip) 
      && TryDecodeUInt32(stream, out take)) 
     { 
      last += (int)skip+1; 
      for(uint i = 0 ; i <= take ; i++) { 
       list.Add(last++); 
      } 
     } 
     return list.ToArray(); 
    } 
    static int Encode(Stream stream, int[] data) 
    { 
     if (data.Length == 0) return 0; 
     byte[] buffer = new byte[10]; 
     int last = -1, len = 0; 
     for (int i = 0; i < data.Length;) 
     { 
      int gap = data[i] - 2 - last, size = 0; 
      while (++i < data.Length && data[i] == data[i - 1] + 1) size++; 
      last = data[i - 1]; 
      len += EncodeUInt32((uint)gap, buffer, stream) 
       + EncodeUInt32((uint)size, buffer, stream); 
     } 
     return len; 
    } 
    public static int EncodeUInt32(uint value, byte[] buffer, Stream stream) 
    { 
     int count = 0, index = 0; 
     do 
     { 
      buffer[index++] = (byte)((value & 0x7F) | 0x80); 
      value >>= 7; 
      count++; 
     } while (value != 0); 
     buffer[index - 1] &= 0x7F; 
     stream.Write(buffer, 0, count); 
     return count; 
    } 
    public static bool TryDecodeUInt32(Stream source, out uint value) 
    { 
     int b = source.ReadByte(); 
     if (b < 0) 
     { 
      value = 0; 
      return false; 
     } 

     if ((b & 0x80) == 0) 
     { 
      // single-byte 
      value = (uint)b; 
      return true; 
     } 

     int shift = 7; 

     value = (uint)(b & 0x7F); 
     bool keepGoing; 
     int i = 0; 
     do 
     { 
      b = source.ReadByte(); 
      if (b < 0) throw new EndOfStreamException(); 
      i++; 
      keepGoing = (b & 0x80) != 0; 
      value |= ((uint)(b & 0x7F)) << shift; 
      shift += 7; 
     } while (keepGoing && i < 4); 
     if (keepGoing && i == 4) 
     { 
      throw new OverflowException(); 
     } 
     return true; 
    } 
} 

Answer 9

В дополнение к другим решениям:

Вы могли бы найти «плотные» участки и использовать растровое изображение, чтобы сохранить их.

Так, например:

Если у вас есть 1000 номеров в 400 диапазоне между 1000-3000, вы можете использовать один бит для обозначения существования ряда и два целых чисел для обозначения диапазона. Общее хранилище для этого диапазона составляет 2000 бит + 2 интервала, поэтому вы можете сохранить эту информацию в 254 байтах, что довольно удивительно, так как даже короткие целые числа будут занимать по два байта каждый, поэтому для этого примера вы получаете 7-процентную экономию.

Чем плотнее области, тем лучше этот алгоритм, но в какой-то момент только сохранение начала и конца будет дешевле.

Answer 10

Основная идея, которую вы, вероятно, должны использовать, - для каждого диапазона последовательных целых чисел (я буду называть эти диапазоны), чтобы сохранить начальный номер и размер диапазона.Например, если у вас есть список из 1000 целых чисел, но есть только 10 отдельных диапазонов, вы можете сохранить всего 20 целых чисел (1 начальный номер и 1 размер для каждого диапазона), чтобы представить эти данные, которые будут представлять собой степень сжатия 98 %. К счастью, есть еще несколько оптимизаций, которые вы можете сделать, что поможет в случаях, когда число диапазонов больше.

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

2. Используйте минимальное количество бит для обоих типов целых чисел. Вы можете перебирать числа, чтобы получить наибольшее смещение стартового целого, а также размер самого большого диапазона. Затем вы можете использовать тип данных, который наиболее эффективно хранит эти целые числа, и просто указывать тип данных или количество бит в начале сжатых данных. Например, если наибольшее смещение стартового целого составляет всего 12 000, а наибольший диапазон - 9000, то вы можете использовать целое число без знака 2 байта для всех этих. Затем вы можете вставить пару 2,2 в начале сжатых данных, чтобы показать, что для обоих целых чисел используется 2 байта. Конечно, вы можете поместить эту информацию в один байт, используя немного бит-манипуляции. Если вам удобно выполнять много манипуляции с большими битками, вы можете сохранить каждое число как минимально возможное количество бит, а не соответствовать представлениям 1, 2, 4 или 8 байтов.

С этими двумя оптимизаций позволяет взглянуть на пару примеров (каждый составляет 4000 байт):

1. 1000 целых чисел, самое большое смещение 500, 10 диапазонов
2. 1000 целых чисел, самое большое смещение 100, 50 диапазонов
3. 1 000 целых чисел, самое большое смещение 50, 100 диапазонов

БЕЗ ОПТИМИЗАЦИЙ

1. 20 целых чисел, по 4 байта = 80 байт. COMPRESSION = 98%
2. 100 целых чисел, по 4 байта = 400 байт. COMPRESSION = 90%
3. 200 целых чисел, по 4 байта = 800 байт. КОМПРЕССИЯ = 80%

с оптимизацией

1. 1 байт заголовка + 20 номеров, 1 байт каждый = 21 байт. COMPRESSION = 99.475%
2. 1 байтовый заголовок + 100 номеров, по одному байту = 101 байт. COMPRESSION = 97.475%
3. 1 байтовый заголовок + 200 номеров, по одному байту = 201 байт.СЖАТИЕ = 94,975%

Answer 11

Ваш случай очень похож на сжатие индексов в поисковых системах. Популярным алгоритмом сжатия является алгоритм PForDelta и алгоритм Simple16. Вы можете использовать библиотеку kamikaze для ваших потребностей в сжатии.

Answer 12

Мы написали последние научные статьи, в которых рассматриваются лучшие схемы этой проблемы. Пожалуйста, смотрите:

Daniel Lemire и Леонид Бойцов, Декодирование миллиарды чисел в секунду с помощью векторизации Программное обеспечение: Практика & Опыт 45 (1), 2015. http://arxiv.org/abs/1209.2137

Daniel Lemire, Натан Kurz, Леонид Бойцов, SIMD Сжатие и пересечение сортированных целых чисел, программное обеспечение: практика и опыт (отображаются) http://arxiv.org/abs/1401.6399

Они включают обширную экспериментальную оценку.

Вы можете найти полную реализацию всех методов в C++ 11 онлайн: https://github.com/lemire/FastPFor и https://github.com/lemire/SIMDCompressionAndIntersection

Есть также C библиотеки: https://github.com/lemire/simdcomp и https://github.com/lemire/MaskedVByte

Если вы предпочитаете Java, пожалуйста, смотрите https://github.com/lemire/JavaFastPFOR

Answer 13

Я знаю, что это старый поток сообщений, но я включаю в себя мой персональный PHP-тест идеи SKIP/TAKE, которую я нашел здесь. Я называю мой STEP (+)/SPAN (-). Возможно, кому-то это поможет.

ПРИМЕЧАНИЕ. Я реализовал возможность разрешать повторяющиеся целые числа и отрицательные целые числа, даже если исходный вопрос включал положительные, не дублированные целые числа. Не стесняйтесь настраивать его, если вы хотите попробовать побрить байт или два.

КОД:

// $integers_array can contain any integers; no floating point, please. Duplicates okay. 
    $integers_array = [118, 68, -9, 82, 67, -36, 15, 27, 26, 138, 45, 121, 72, 63, 73, -35, 
        68, 46, 37, -28, -12, 42, 101, 21, 35, 100, 44, 13, 125, 142, 36, 88, 
        113, -40, 40, -25, 116, -21, 123, -10, 43, 130, 7, 39, 69, 102, 24, 
        75, 64, 127, 109, 38, 41, -23, 21, -21, 101, 138, 51, 4, 93, -29, -13]; 

    // Order from least to greatest... This routine does NOT save original order of integers. 
    sort($integers_array, SORT_NUMERIC); 

    // Start with the least value... NOTE: This removes the first value from the array. 
    $start = $current = array_shift($integers_array);  

    // This caps the end of the array, so we can easily get the last step or span value. 
    array_push($integers_array, $start - 1); 

    // Create the compressed array... 
    $compressed_array = [$start]; 
    foreach ($integers_array as $next_value) { 
    // Range of $current to $next_value is our "skip" range. I call it a "step" instead. 
    $step = $next_value - $current; 
    if ($step == 1) { 
     // Took a single step, wait to find the end of a series of seqential numbers. 
     $current = $next_value; 
    } else { 
     // Range of $start to $current is our "take" range. I call it a "span" instead. 
     $span = $current - $start; 
     // If $span is positive, use "negative" to identify these as sequential numbers. 
     if ($span > 0) array_push($compressed_array, -$span); 
     // If $step is positive, move forward. If $step is zero, the number is duplicate. 
     if ($step >= 0) array_push($compressed_array, $step); 
     // In any case, we are resetting our start of potentialy sequential numbers. 
     $start = $current = $next_value; 
    } 
    } 

    // OPTIONAL: The following code attempts to compress things further in a variety of ways. 

    // A quick check to see what pack size we can use. 
    $largest_integer = max(max($compressed_array),-min($compressed_array)); 
    if ($largest_integer < pow(2,7)) $pack_size = 'c'; 
    elseif ($largest_integer < pow(2,15)) $pack_size = 's'; 
    elseif ($largest_integer < pow(2,31)) $pack_size = 'l'; 
    elseif ($largest_integer < pow(2,63)) $pack_size = 'q'; 
    else die('Too freaking large, try something else!'); 

    // NOTE: I did not implement the MSB feature mentioned by Marc Gravell. 
    // I'm just pre-pending the $pack_size as the first byte, so I know how to unpack it. 
    $packed_string = $pack_size; 

    // Save compressed array to compressed string and binary packed string. 
    $compressed_string = ''; 
    foreach ($compressed_array as $value) { 
     $compressed_string .= ($value < 0) ? $value : '+'.$value; 
     $packed_string .= pack($pack_size, $value); 
    } 

    // We can possibly compress it more with gzip if there are lots of similar values.  
    $gz_string = gzcompress($packed_string); 

    // These were all just size tests I left in for you. 
    $base64_string = base64_encode($packed_string); 
    $gz64_string = base64_encode($gz_string); 
    $compressed_string = trim($compressed_string,'+'); // Don't need leading '+'. 
    echo "<hr>\nOriginal Array has " 
    .count($integers_array) 
    .' elements: {not showing, since I modified the original array directly}'; 
    echo "<br>\nCompressed Array has " 
    .count($compressed_array).' elements: ' 
    .implode(', ',$compressed_array); 
    echo "<br>\nCompressed String has " 
    .strlen($compressed_string).' characters: ' 
    .$compressed_string; 
    echo "<br>\nPacked String has " 
    .strlen($packed_string).' (some probably not printable) characters: ' 
    .$packed_string; 
    echo "<br>\nBase64 String has " 
    .strlen($base64_string).' (all printable) characters: ' 
    .$base64_string; 
    echo "<br>\nGZipped String has " 
    .strlen($gz_string).' (some probably not printable) characters: ' 
    .$gz_string; 
    echo "<br>\nBase64 of GZipped String has " 
    .strlen($gz64_string).' (all printable) characters: ' 
    .$gz64_string; 

    // NOTICE: The following code reverses the process, starting form the $compressed_array. 

    // The first value is always the starting value. 
    $current_value = array_shift($compressed_array); 
    $uncompressed_array = [$current_value]; 
    foreach ($compressed_array as $val) { 
    if ($val < -1) { 
     // For ranges that span more than two values, we have to fill in the values. 
     $range = range($current_value + 1, $current_value - $val - 1); 
     $uncompressed_array = array_merge($uncompressed_array, $range); 
    } 
    // Add the step value to the $current_value 
    $current_value += abs($val); 
    // Add the newly-determined $current_value to our list. If $val==0, it is a repeat! 
    array_push($uncompressed_array, $current_value);  
    } 

    // Display the uncompressed array. 
    echo "<hr>Reconstituted Array has " 
    .count($uncompressed_array).' elements: ' 
    .implode(', ',$uncompressed_array). 
    '<hr>'; 

ВЫХОД:

-------------------------------------------------------------------------------- 
Original Array has 63 elements: {not showing, since I modified the original array directly} 
Compressed Array has 53 elements: -40, 4, -1, 6, -1, 3, 2, 2, 0, 8, -1, 2, -1, 13, 3, 6, 2, 6, 0, 3, 2, -1, 8, -11, 5, 12, -1, 3, -1, 0, -1, 3, -1, 2, 7, 6, 5, 7, -1, 0, -1, 7, 4, 3, 2, 3, 2, 2, 2, 3, 8, 0, 4 
Compressed String has 110 characters: -40+4-1+6-1+3+2+2+0+8-1+2-1+13+3+6+2+6+0+3+2-1+8-11+5+12-1+3-1+0-1+3-1+2+7+6+5+7-1+0-1+7+4+3+2+3+2+2+2+3+8+0+4 
Packed String has 54 (some probably not printable) characters: cØÿÿÿÿ ÿõ ÿÿÿÿÿÿ 
Base64 String has 72 (all printable) characters: Y9gE/wb/AwICAAj/Av8NAwYCBgADAv8I9QUM/wP/AP8D/wIHBgUH/wD/BwQDAgMCAgIDCAAE 
GZipped String has 53 (some probably not printable) characters: xœ Ê» ÑÈί€)YšE¨MŠ“^qçºR¬m&Òõ‹%Ê&TFʉùÀ6ÿÁÁ Æ 
Base64 of GZipped String has 72 (all printable) characters: eJwNyrsNACAMA9HIzq+AKVmaRahNipNecee6UgSsBW0m0gj1iyXKJlRGjcqJ+cA2/8HBDcY= 
-------------------------------------------------------------------------------- 
Reconstituted Array has 63 elements: -40, -36, -35, -29, -28, -25, -23, -21, -21, -13, -12, -10, -9, 4, 7, 13, 15, 21, 21, 24, 26, 27, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 51, 63, 64, 67, 68, 68, 69, 72, 73, 75, 82, 88, 93, 100, 101, 101, 102, 109, 113, 116, 118, 121, 123, 125, 127, 130, 138, 138, 142 
-------------------------------------------------------------------------------- 

Answer 14

TurboPFor: Fastest Integer Compression

• для C/C++, включая Java Критические Natives/JNI интерфейс
• SIMD-ускоренным целое сжатие
• Скалярной + Интегрированное (SIMD) дифференциал/зигзаг кодирования/декодирования для отсортированного/несортированного целого числа списков
• Полных диапазон 8/16/32/64 битых interger перечисляет
• Прямого доступ
• Тест приложение

Answer 15

Я не мог заставить мое сжатие быть намного лучше, чем примерно 0,11 для этого. Я сгенерировал свои тестовые данные через интерпретатор python, и это список строк с разделителями строк с 1-100 и 110-160. Я использую фактическую программу как сжатое представление данных.Мой сжатый файл выглядит следующим образом:

main=mapM_ print [x|x<-[1..160],x`notElem`[101..109]] 

Это просто скрипт Haskell, который генерирует файл, который вы можете запустить через:

Размер файла G.hs составляет 54 байта, а Данные, генерируемые python, составляют 496 байт. Это дает 0,10887096774193548 в качестве коэффициента сжатия. Я думаю, что с большим количеством времени можно сжать программу или сжать сжатый файл (т. Е. Файл haskell).

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

Еще одна проблема заключается в том, что для этого требуется интерпретатор Haskell. Когда я скомпилировал программу, она сделала ее намного больше. Я действительно не знаю, почему. Существует такая же проблема с python, поэтому лучше всего использовать диапазоны, чтобы какая-то программа могла распаковать файл.