Сжатие большого количества (или строка) к маленькому значению

Каков диапазон ваших чисел? Предполагая, что они могут поместиться в 16-битное целое число, я бы:

• Сохранял бы все ваши числа как 16-битные целые числа (2 байта на число, диапазон от -32 768 до 32 767)
• Создайте байтовый поток 16-битных целых чисел ( XDR здесь может быть хорошим вариантом; по крайней мере, убедитесь, что правильно обрабатывает endianness )
• Base64 кодирует байтовый поток, используя измененная кодировка base64 для URL-адресов (net составляет примерно 3 символа на число)

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

В качестве альтернативы, если этого недостаточно , Я бы использовал zlib для сжатия потока целых чисел, а затем base64 сжатый поток zlib. Вы также можете переключиться на 32-битные целые числа, если 16-битное не является достаточно большой диапазон (например, если вам действительно нужны числа в диапазоне 1 000 000 000).

Изменить:

Может быть, слишком поздно, но вот реализация, которая может сделать то, что вам нужно:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Scratch {
    class Program {
        static void Main(string[] args) {
            //var ids = new[] { 1000000012, 1000000021, 1000000013, 1000000022 };
            var rand = new Random();
            var ids = new int[rand.Next(20)];
            for(var i = 0; i < ids.Length; i++) {
                ids[i] = rand.Next();
            }

            WriteIds(ids);
            var s = IdsToString(ids);
            Console.WriteLine("\nResult string is: {0}", s);
            var newIds = StringToIds(s);
            WriteIds(newIds);
            Console.ReadLine();
        }

        public static void WriteIds(ICollection<Int32> ids) {
            Console.Write("\nIDs: ");
            bool comma = false;
            foreach(var id in ids) {
                if(comma) {
                    Console.Write(",");
                } else {
                    comma = true;
                }
                Console.Write(id);
            }
            Console.WriteLine();
        }

        public static string IdsToString(ICollection<Int32> ids) {
            var allbytes = new List<byte>();
            foreach(var id in ids) {
                var bytes = BitConverter.GetBytes(id);
                allbytes.AddRange(bytes);                
            }
            var str = Convert.ToBase64String(allbytes.ToArray(), Base64FormattingOptions.None);
            return str.Replace('+', '-').Replace('/', '_').Replace('=', '.');
        }

        public static ICollection<Int32> StringToIds(string idstring) {
            var result = new List<Int32>();
            var str = idstring.Replace('-', '+').Replace('_', '/').Replace('.', '=');
            var bytes = Convert.FromBase64String(str);
            for(var i = 0; i < bytes.Length; i += 4) {
                var id = BitConverter.ToInt32(bytes, i);
                result.Add(id);
            }
            return result;
        }
    }
}

Вот еще одна очень простая схема, которая должна дать хорошее сжатие для набора чисел вида N + дельта , где N - большая константа.

public int[] compress(int[] input) {
    int[] res = input.clone();
    Arrays.sort(res);
    for (int i = 1; i < res.length; i++) {
        res[i] = res[i] - res[i - 1];
    }
    return res;
}

Это должно уменьшить набор {1000000012,1000000021,1000000013,1000000022} в список [1000000012,1,9,1] , который можно затем сжать, представив числа в кодировке base47 как описано в другом ответе.

Используя простую десятичную кодировку, это число увеличивается с 44 до 16 символов; т.е. 63%. (А использование base47 даст еще большее сжатие.)

Если сортировать идентификаторы неприемлемо, вы не получите столь же хорошего сжатия. В этом примере {1000000012,1000000021,1000000013,1000000022} сжимается в список [1000000012,9, -8,9] .

Если единственная проблема связана с длиной URL-адреса, вы можете преобразовать числа в символы base64 , а затем преобразовать их обратно в числа на стороне сервера

Насколько структурированы идентификаторы, которые вы получаете? если цифра за цифрой, идентификаторы случайны, тогда метод, который я собираюсь предложить, будет не очень эффективным. но если идентификаторы, которые вы указали в качестве примера, являются репрезентативными для типов, которые вы получите, то, возможно, следующее может сработать?

Я мотивирую эту идею примером.

у вас, например, 1000000012 в качестве идентификатора, который вы хочу сжать. почему бы не сохранить его как [{1}, {0,7}, {12}]? Это означало бы, что первая цифра - это 1, за которой следуют 7 нулей, за которыми следует 12. Таким образом, если мы используем обозначение {x}, которое будет представлять один экземпляр x, а если мы используем {x, y}, это будет означать, что x встречается y раз подряд.

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

например, сопоставление с образцом: 1000100032 будет [{1000,2} {32}]. если ваши идентификаторы состоят из 10 цифр, разделите идентификатор на два пятизначных числа и сохраните уравнение линии, проходящей через обе точки. если ID = 1000000012, у вас y1 = 10000 и y2 = 12. Следовательно, ваш наклон равен -9988, а ваш перехват - 10000 (при условии, что x1 = 0, x2 = 1). В данном случае это не улучшение, но если бы числа были более случайными, это могло бы быть. Точно так же вы можете хранить последовательность идентификаторов с кусочно-линейными функциями.

в любом случае, это в основном зависит от структуры ваших идентификаторов.

Я предполагаю, что вы делаете это как обходной путь для ограничения длины URL-адреса запроса ...

В других ответах предлагалось кодировать десятичные идентификаторы в шестнадцатеричном формате, base47 или base64, но вы можете ( теоретически) намного лучше, чем при использовании LZW (или аналогичного) для сжатия списка идентификаторов. В зависимости от того, насколько избыточны ваши списки идентификаторов, вы можете получить значительно более чем 40% -ное сокращение, даже после перекодирования сжатых байтов в текст.

В общем, я предлагаю вам найти не- встроенная библиотека сжатия текста, реализованная на Javascript и использующая ее на стороне клиента для сжатия списка идентификаторов. Затем закодируйте сжатую строку байтов с помощью base47 / base64 и передайте закодированную строку в качестве параметра URL. На стороне сервера сделайте обратное; т.е. декодирование с последующей распаковкой.

РЕДАКТИРОВАТЬ: В качестве эксперимента Я создал список из 36 различных идентификаторов, подобных тем, которые вы предоставили, и сжал его с помощью gzip. Исходный файл имеет размер 396 байт, сжатый файл - 101 байт, а сжатый файл + base64 - 138 байтов. Это в целом сокращение на 65%. И степень сжатия может действительно улучшиться для файлов большего размера. Однако, когда я попробовал это с небольшим набором входных данных (например, только с 4 исходными идентификаторами), у меня не было сжатия, и после кодирования размер был больше, чем исходный.

Google "lzw library javascript"

Теоретически , может быть более простое решение. Отправьте параметры как «данные публикации», а не в URL-адресе запроса, и заставьте браузер применить сжатие, используя одну из кодировок, которые он понимает.