Сжатие большого числа (или строки) до небольшого значения

Question

Моя страница ASP.NET имеет следующий параметр строки запроса:

…?IDs=1000000012,1000000021,1000000013,1000000022&...

Здесь параметр IDs всегда будет иметь числа, разделенные чем-то, в данном случае ,. В настоящее время существует 4 числа, но обычно они находятся между 3 и 7.

Теперь я ищу метод для преобразования каждого большого числа сверху в наименьшее возможное значение; специально сжимая значение IDs параметра строки запроса. Оба, сжатие каждого числового алгоритма или сжатие всего значения IDs параметра строки запроса приветствуются.

1. Кодирование или декодирование не является проблемой; просто сжимаем значение IDs параметр строки запроса.
2. Создание некоторого уникального небольшого значения для IDs и последующее извлечение его значения из какого-либо источника данных выходит за рамки.

Существует ли алгоритм для сжатия таких больших чисел до небольших значений или для сжатия значения параметра строки запроса IDs все вместе?

Answer 1

Вам в основном нужно так много места для ваших чисел, потому что вы используете базу 10 для их представления. Улучшение было бы использовать основание 16 (гекс). Так, например, вы можете представить 255 (3 цифры) как ff (2 цифры).

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

A-Z, a-z, 0-9, '.', '-', '~', '_', '+'

Это дает вам базу из 67 символов для работы (см. Википедия по QueryString ).

Взгляните на этот пост о подходах к преобразованию базы 10 в произвольные базы чисел.

EDIT:

В связанном сообщении SO посмотрите на эту часть:

string xx = IntToString(42, 
            new char[] { '0','1','2','3','4','5','6','7','8','9',
            'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
            'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x'});

Это почти то, что вам нужно. Просто разверните его, добавив несколько пропущенных символов:

yz.- ~ _ +

В этом посте отсутствует метод возврата к базе 10. Я не собираюсь его писать :-), но процедура такая:

Определите счетчик, который я назову ВСЕГО.

Посмотрите на правый самый символ и найдите его позицию в массиве.
ИТОГО = (позиция символа в массиве) Пример: ввод BA1. ВСЕГО теперь 1 (так как «1» находится в позиции 1 в массиве)

Теперь посмотрите на следующий символ слева от первого и найдите его позицию в массиве. ВСЕГО + = 47 * (позиция символа в массиве) Пример: ввод BA1. ИТОГО сейчас (47 * 11) + 1 = 518

Теперь посмотрите на следующий символ слева от предыдущего и найдите его позицию в массиве. ВСЕГО + = 47 * 47 * (позиция символа в массиве) Пример: ввод BA1. Всего сейчас (47 * 47 * 10) + (47 * 11) + 1 = 243508

и т. Д.

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

Обратите внимание, что вы представляли 6-значное число из 10 базовых букв всего из 3 цифр из базы 47: -)

Answer 2

Вот еще одна очень простая схема, которая должна дать хорошее сжатие для набора чисел вида N + delta, где 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]. Это всего на один символ длиннее для этого примера

В любом случае, это лучше, чем универсальный алгоритм сжатия или схемы кодирования ... ДЛЯ ЭТОГО ВИДА ВВОДА.

Answer 3

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

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

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

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

Edit:

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

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;
        }
    }
}

Answer 4

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

Answer 5

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

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

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

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

Google "lzw library javascript"

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

Проблема в том, что браузер сжимает запрос ... и делает это независимо от браузера.

Answer 6

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

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

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

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

например, сопоставление с шаблоном: 1000100032 будет [{1000,2} {32}].

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

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