Какого размера цифры? В дополнение к другим ответам, вы могли бы рассмотреть кодирование по варианту длины base-128, которое позволяет хранить меньшие числа в отдельных байтах, в то же время допуская большие числа. MSB означает «есть еще один байт» - это описано здесь.
Объедините это с другими приемами, чтобы вы сохранили «размер пропуска», «размер взятия», «размер пропуска», «размер взятия», но отметив, что ни «пропуск», ни «взятие» никогда не будут нулевыми мы вычтем по одному из каждого (что позволяет сэкономить дополнительный байт для нескольких значений)
Итак:
1-100, 110-160
означает «пропустить 1» (предположим, что начинать с нуля, поскольку это облегчает задачу), «взять 100», «пропустить 9», «взять 51»; вычтите 1 из каждого, давая (как десятичные дроби)
0,99,8,50
, который кодируется как (шестнадцатеричное):
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
Таким образом, мы можем легко кодировать большие числа, но маленькие числа (которые звучат типично для пропуска / извлечения) занимают меньше места.
Вы можете попробовать , запустив это через "deflate", но это может не помочь намного больше ...
Если вы не хотите самостоятельно разбираться со всей этой грязной кодировкой ... если вы можете создать целочисленный массив значений (0,99,8,60) - вы можете использовать буферы протокола с упакованным повторяющимся 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;
}
}