У меня есть большой массив с целым числом, которые в основном непрерывны, например, 1-100, 110-160 и т.д. Все целые числа являются положительными.
Какой был бы лучший алгоритм для сжатия этого?
Я попробовал алгоритм дефляции, но это дает мне только 50% сжатие.
Обратите внимание, что алгоритм не может быть потерянным.
Все номера уникальны и постепенно увеличиваются.
Также, если вы можете указать мне на реализацию java такого алгоритма, что было бы здорово.
Мы написали последние научные статьи, в которых рассматриваются лучшие схемы этой проблемы. Пожалуйста, смотрите:
Дэниел Лемрир и Леонид Бойцов, декодирование миллиардов целых чисел в секунду с помощью векторизации, Программное обеспечение: практика и опыт 45 (1), 2015. http://arxiv.org/abs/1209.2137
Даниэль Лемрир, Натан Курз, Леонид Бойцов, SIMD-компрессия и пересечение отсортированных целых чисел, Программное обеспечение: практика и опыт (для отображения) http://arxiv.org/abs/1401.6399
Они включают обширную экспериментальную оценку.
Вы можете найти полную реализацию всех методов в С++ 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
Во-первых, предварительно обработайте список значений, взяв разницу между каждым значением и предыдущим (для первого значения, предположим, что предыдущий был равен нулю). Это должно в вашем случае дать в основном последовательность из них, которая может быть сжата намного легче с помощью большинства алгоритмов сжатия.
Так формат PNG улучшает сжатие (он выполняет один из нескольких методов разности, за которым следует тот же алгоритм сжатия, который используется gzip).
Хорошо, я голосую более разумно. Все, что вам нужно сохранить, это [int: startnumber] [int/byte/whatever: количество итераций] в этом случае, вы превратите свой массив примеров в значение 4xInt. После этого вы можете сжимать, как хотите:)
Хотя вы могли бы разработать собственный алгоритм, специфичный для вашего потока данных, вероятно, проще использовать алгоритм кодирования с полки. Я провел несколько тестов алгоритмов сжатия, доступных в Java, и нашел следующие коэффициенты сжатия для последовательности из миллиона последовательных целых чисел:
None 1.0
Deflate 0.50
Filtered 0.34
BZip2 0.11
Lzma 0.06
Какой размер чисел? В дополнение к другим ответам вы можете рассмотреть кодировку с расширенной длиной базы-128, которая позволяет хранить меньшие числа в одиночных байтах, сохраняя при этом большее число. MSB означает "есть еще один байт" - здесь описывается .
Объедините это с другими методами, чтобы вы сохраняли "размер пропусков", "принимать размер", "пропускать размер", "принимать размер", но отмечая, что ни "пропустить", ни "принять" никогда не будет равным нулю, поэтому мы вычитаем один из каждого (что позволяет сохранить дополнительный байт для нескольких значений)
Итак:
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
Таким образом, мы можем легко кодировать большие числа, но небольшие числа (которые звучат типично для skip/take) занимают меньше места.
Вы можете попробовать выполнить это через "deflate", но это может не помочь значительно больше...
Если вы не хотите иметь дело со всем этим беспорядочным кодированием, то... если вы можете создать целочисленный массив значений (0,99,8,60) - вы можете использовать буферы протоколов с упакованным повторным uint32/uint64 - и он сделает всю работу для вас; -p
Я не "делаю" Java, но здесь полная реализация С# (заимствование некоторых битов кодирования из моего проекта 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;
}
}
сжать строку "1-100, 110-160" или сохранить строку в некотором двоичном представлении и проанализировать ее для восстановления массива
В дополнение к другим решениям:
Вы можете найти "плотные" области и использовать растровое изображение для их хранения.
Итак, например:
Если у вас 1000 номеров в 400 диапазонах между 1000-3000, вы можете использовать один бит, чтобы обозначить существование числа и двух значений для обозначения диапазона. Общее хранилище для этого диапазона составляет 2000 бит + 2 интервала, поэтому вы можете сохранить эту информацию в 254 байтах, что довольно удивительно, так как даже короткие целые числа будут занимать по два байта каждый, поэтому для этого примера вы получаете 7-процентную экономию.
Чем плотнее области, тем лучше этот алгоритм, но в какой-то момент только сохранение начала и конца будет дешевле.
Я бы объединил ответы, данные CesarB и Fernando Miguélez.
Сначала сохраните различия между каждым значением и предыдущим. Как отметил CesarB, это даст вам последовательность из большинства.
Затем в этой последовательности используйте алгоритм сжатия кодирования длины пробега. Он будет очень хорошо сжиматься из-за большого количества повторяющихся значений.
Я бы предложил взглянуть на Huffman Coding, особый случай Арифметическое кодирование. В обоих случаях вы анализируете свою начальную последовательность, чтобы определить относительные частоты разных значений. Более часто встречающиеся значения кодируются с меньшим количеством бит, чем менее часто встречающиеся.
Основная идея, которую вы, вероятно, должны использовать, - для каждого диапазона последовательных целых чисел (я буду называть эти диапазоны), чтобы сохранить начальный номер и размер диапазона. Например, если у вас есть список из 1000 целых чисел, но есть только 10 отдельных диапазонов, вы можете сохранить всего 20 целых чисел (1 начальный номер и 1 размер для каждого диапазона), чтобы представить эти данные, которые будут представлять собой степень сжатия 98 %. К счастью, вы можете сделать еще несколько оптимизаций, которые помогут в случаях, когда количество диапазонов больше.
Сохранить смещение стартового номера относительно предыдущего стартового номера, а не самого стартового номера. Преимущество здесь состоит в том, что для сохраненных вами номеров обычно требуется меньше бит (это может пригодиться в последующих предложениях по оптимизации). Кроме того, если вы только сохранили стартовые номера, все эти номера будут уникальными, а сохранение смещения дает шанс, что числа близки или даже повторяются, что может позволить еще большее сжатие другим методом, применяемым после.
Используйте минимальное количество бит для обоих типов целых чисел. Вы можете перебирать числа, чтобы получить наибольшее смещение стартового целого, а также размер самого большого диапазона. Затем вы можете использовать тип данных, который наиболее эффективно хранит эти целые числа, и просто указывать тип данных или количество бит в начале сжатых данных. Например, если наибольшее смещение стартового целого составляет всего 12 000, а наибольший диапазон - 9000, то вы можете использовать целое число без знака 2 байта для всех этих. Затем вы можете вставить пару 2,2 в начале сжатых данных, чтобы показать, что для обоих целых чисел используется 2 байта. Конечно, вы можете поместить эту информацию в один байт, используя немного бит-манипуляции. Если вам удобно выполнять много манипуляции с большими бит, вы можете сохранить каждое число как минимально возможное количество бит, а не соответствовать представлениям 1, 2, 4 или 8 байтов.
С помощью этих двух оптимизаций рассмотрим несколько примеров (каждый составляет 4000 байт):
БЕЗ ОПТИМИЗАЦИЙ
С ОПТИМИЗАЦИЯМИ
Ваше дело очень похоже на сжатие индексов в поисковых системах. Популярным алгоритмом сжатия является алгоритм PForDelta и алгоритм Simple16. Вы можете использовать библиотеку kamikaze для ваших потребностей в сжатии.
Если у вас есть серия повторяющихся значений, то RLE легче всего реализовать и может дать вам хороший результат. Тем не менее, другие более продвинутые алгоритмы, учитывающие энтрофию, такую как LZW, которая теперь не имеет патентов, обычно могут обеспечить гораздо лучшее сжатие.
Вы можете посмотреть эти и другие алгоритмы без потерь здесь.
Я знаю, что это старый поток сообщений, но я включаю в себя мой персональный PHP-тест идеи SKIP/TAKE, которую я нашел здесь. Я называю мой STEP (+)/SPAN (-). Возможно, кому-то это поможет.
ПРИМЕЧАНИЕ. Я реализовал возможность разрешать повторяющиеся целые числа, а также отрицательные целые числа, даже если исходный вопрос касался положительных, не дублированных целых чисел. Не стесняйтесь настраивать его, если вы хотите попробовать и побрить байт или два.
CODE:
// $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
--------------------------------------------------------------------------------
TurboPFor: быстрое сжатие целых чисел
Я не мог заставить мое сжатие быть намного лучше, чем примерно 0,11 для этого. Я сгенерировал свои тестовые данные с помощью интерпретатора python, и это список строк с разделителями строк с 1-100 и 110-160. Я использую фактическую программу как сжатое представление данных. Мой сжатый файл выглядит следующим образом:
main=mapM_ print [x|x<-[1..160],x`notElem`[101..109]]
Это просто Haskell script, который генерирует файл, который вы можете запустить через:
$ runhaskell generator.hs >> data
Размер файла g.hs составляет 54 байта, а данные, генерируемые на основе python, составляют 496 байт. Это дает 0,10887096774193548 в качестве коэффициента сжатия. Я думаю, что с большим количеством времени можно сжать программу или сжать сжатый файл (т.е. Файл haskell).
Еще один подход может состоять в том, чтобы сохранить 4 байта данных. Минимальные и максимальные значения каждой последовательности, а затем дают их производящей функции. Хотя при загрузке файлов будет добавлено больше символов для декомпрессора, добавив к декомпрессору большую сложность и большее количество байтов. Опять же, я представлял эту очень специфическую последовательность через программу и не обобщал ее, это сжатие, специфичное для данных. Кроме того, добавление общности делает декомпрессор более крупным.
Еще одна проблема заключается в том, что для этого нужно иметь интерпретатор Haskell. Когда я скомпилировал программу, она сделала ее намного больше. Я действительно не знаю, почему. Существует такая же проблема с python, поэтому, возможно, лучший подход - дать диапазоны, чтобы какая-то программа могла распаковать файл.