Каков наиболее компактный способ втиснуть список целых чисел в строку?

Цель:

Уменьшите размер массива целых чисел следующим образом: «[12, 1, -34, 55, 13, 341, 11, 56, 321, -3422, 1222, -4, 237]», сохраняя при этом возможность преобразовать его обратно. в исходное состояние. Сжатый вывод должен быть строкой.

Причина:

Из-за слишком длинных строк менеджер баз данных, который я использую, зависает при взаимодействии с ним. (Строки используются в качестве формата хранения для типов переменных, таких как массивы.)

Контекст:

По сути, я храню список координат сетки следующим образом: [Vector3(1,2,3), Vector3(4,5,6)] -> [1,2,3,4,5,6]

Я строю это в gdscript.


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

"c1-y.Td,y1.bU,w1-ym,cm-4,n7"

Путем присвоения связанных чисел > 9 нечисловому символу (например, 10 = a, 11 = b, 61 = Z) и размещать запятые только между преобразованными числами, состоящими из нескольких символов (а также использовать символ «-» в качестве своего рода запятой (это несколько сложно)). Это уменьшение размера в среднем на 48% без учета пробелов (проверено 200 случайно сгенерированных массивов).

Вопрос:

Есть ли лучший способ сделать то, что я пытаюсь сделать?


Окончательное редактирование:

Вот мое решение в gdscript, если оно кому-то понадобится.

extends Node
var negative_character_index = 50000
#skip all white space characters as well as "." and ","  and "()" 
#these are used for special cases
var start_char = 47

func num_to_char(num: int):
    var x = abs(num)
    if x > negative_character_index:
        #too large
        return
    else:
        x += start_char
        if num < 0:
            x += negative_character_index
        var char = String.chr(x)
        return char

func char_to_num(char : String):
    var x = char.unicode_at(0) - start_char
    if x == null:
        #maybe negative_character_index was changed
        breakpoint
    
    if x > negative_character_index:
        x -= negative_character_index
        x *= -1
        
    return x

#shorten int 
func int_to_compact_int_string(n:int):
    
    var compact_n = ""
    #largest convertable number
    var head = ""
    
    var last_head_int = null
    var last_char = null
    
    var get_zeros_code = func(head):
        
        var zeros = 0
        
        if head.begins_with("0"):
            
            for char2 in head:
                if char2 == "0":
                    
                    zeros += 1
                else:
                    break
            if head.right(1) == "0":
                
                zeros -=1
            if zeros > 0:
                return "("+str(zeros)+")"
        return ""
    
    for num in str(n):
        
        
        
        head += num
        print(head)
        if num != "-":
            
            var head_int = str_to_var(head)
            var char = get_zeros_code.call(head) + num_to_char(head_int)
            print(char)
            if last_head_int != null && char == null:
                compact_n += last_char
                head = ""
                head += num
                
                last_head_int = str_to_var(head)
                last_char = get_zeros_code.call(head) + num_to_char(last_head_int)
            else:
                last_head_int = head_int
                last_char = char
        print("~~~")
    if head != "":
        print(head)
        print(last_char)
        print("~~~")
        compact_n += last_char
    
    
    
    return compact_n



func int_arr_to_compact_str(int_arr):
    var compact_str = ""
    var is_multi = false
    for n in int_arr:
        
        var compact_n:String = int_to_compact_int_string(n)
        if compact_n.length() > 1: #seperate multicharacter compact numbers
            compact_str += ","
            is_multi = true
        elif is_multi:
            compact_str += "."
            is_multi =false
        
        
        
        compact_str += compact_n
        
    return compact_str


func new_compact_int_string_to_int(compact_n:String):
    
    
    var n = ""
    
    var is_zeros = false
    var zeros = ""
    
    for char in compact_n:
        if char == "(":
            is_zeros = true
            zeros = ""
        elif char == ")":
            is_zeros = false
            var i = 0
            
            while i < str_to_var(zeros):
                
                n += "0"
                i+=1
        elif is_zeros:
            zeros += char
        else:
            var index = char_to_num(char)
            if index > negative_character_index:
                index -= negative_character_index
                index *= -1
            
            n += str(index)
    
    
    return str_to_var(n)




func new_compact_str_to_int_arr(compact_str):
    var int_arr = []
    
    var is_multi = false
    var multi_compiler = ""
    for char in compact_str:
        if char == ',' || char == '.':
            is_multi = char == ','
            
            #end compiler
            if multi_compiler.length() >0:
                int_arr.append(new_compact_int_string_to_int(multi_compiler))
                multi_compiler = ""
            
            
            
            
            
        else:
            if is_multi:
                multi_compiler += char
            else:
                int_arr.append(new_compact_int_string_to_int(char))
    
    if multi_compiler.length() > 0:
        int_arr.append(new_compact_int_string_to_int(multi_compiler))
        multi_compiler = ""
    
    return int_arr

func _ready():
    var arr2 = [237, 50001, -5000000003, 250000000]
    
    #print("---")
    #for i in range(999):
        #print(String.chr(i)+" -> "+str(i))
    #print("---")
    
    print(arr2)
    var comp = int_arr_to_compact_str(arr2)
    print(comp)
    var r_arr2 = new_compact_str_to_int_arr(comp)
    print(r_arr2)
the most compact way to cram a list of integers into a string такие, чтобы их можно было получить/восстановить.
greybeard 20.04.2024 12:26

Каков диапазон целых чисел?

Nick 20.04.2024 14:29
Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
0
2
92
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Ответ принят как подходящий

Вы можете преобразовать в коды UTF-16 (0–65535) со знаком:

const arr = [12, 1, -34, 55, 13, 341, 11, 56, 321, -3422, 1222, -4, 237];

const result = arr.map(n => (Math.sign(n) < 0 ? '-' : '') + String.fromCharCode(Math.abs(n))).join('');
console.info(result);
console.info(arr.join(',').length, '=>', result.length);

//decode
const out = [];
for(let i=0;i<result.length;i++){
  const sign = result[i]==='-'?-1:1;
  if (sign<0) i++;
  out.push(result[i].charCodeAt()*sign);
}
console.info(...out);

Вы можете использовать первый бит для хранения знака, хотя диапазон сужается до максимума 32768:

const arr = [12, 1, -34, 55, 13, 341, 11, 56, 321, -3422, 1222, -4, 237];

const result = arr.map(n => {
  let c = Math.abs(n);
  c = (c << 1) + (Math.sign(n) < 0 ? 1 : 0);
  return String.fromCharCode(c);
}).join('');
console.info(result);
console.info(arr.join(',').length, '=>', result.length);

//decode
const out = [];
for(let i=0;i<result.length;i++){
  const n = result[i].charCodeAt();
  out.push((n >> 1) * (n & 1 === 1 ? -1 : 1));
}
console.info(...out);

Начну с того, что кодировка, которую вы придумали, неплохая. Однако есть немного возможностей для улучшения.

Чтобы получить «идеальную» кодировку, вам нужно сделать всего 3 вещи:

  1. Выберите свой набор символов. Вы говорите, что вывод представляет собой «строку», но является ли это строкой с произвольными 8-битными символами, или UTF-8, или UTF-16, или ISO-8859-1, или что? В любом случае вам нужно решить, какие персонажи вам доступны. Похоже, вы сейчас используете число 63: 0–9, A–Z, a–z, плюс минус и запятая. Вероятно, у вас есть как минимум 100, которые вы можете использовать. Может быть, гораздо больше. Как вы уже обнаружили, использование большего количества символов позволяет поместить больше данных в строку того же размера.
  2. Убедитесь, что почти каждая строка выбранных вами символов соответствует допустимому вводу. Каждая недопустимая строка — это упущенная возможность сжатия. Например, похоже, что «,,» недопустимо в вашей текущей схеме, и это означает, что есть входные данные, которые в настоящее время сопоставляются с более длинной строкой, которая вместо этого могла бы быть сопоставлена ​​с этой.
  3. Убедитесь, что каждый символ вашего набора символов с одинаковой вероятностью появится в выводе после любого допустимого префикса. По сути, это означает, что ваши строки выглядят настолько случайными, что, зная любой префикс, вы не можете ничего угадать о следующем. Если это условие не выполняется, то вы упускаете некоторое возможное сжатие. Сколько вы упускаете, рассчитывается по расхождению Кульбака-Лейблера, но я предполагаю, что вы к этому не совсем готовы.

Все это звучит не так уж сложно, но на самом деле шаг 3 — это вся работа по сжатию данных без потерь. Это было бы легко, если бы не фраза «одинаково вероятно» двусмысленная. Он предполагает статистическую модель входных данных, и чем лучше эта модель, тем большее сжатие вы можете получить. Эти модели могут быть довольно сложными.

Поскольку это действительно так сложно, если вас это действительно волнует, вам обычно следует использовать надежный компрессор, например:

  1. gzip-сжать ваш массив
  2. закодируйте вывод в base64 или используйте любой эквивалент кодировки base64 для выбранного вами набора символов.

Однако если вас это не особо волнует, то вот простая схема, которая оптимальна для распространенных распределений целых чисел, симметричных относительно 0. Допустим, ваш набор символов состоит из M символов, которые мы будем называть «цифрами». «от 0 до М-1. Чтобы закодировать целое число:

// encode integer to string with M digits

encodeInt(int n) -> string:
    // exactly one representation for 0
    if (n === 0):
        return digits[0];
    // range of remaining digits
    rangestart = 1
    rangeend = M
    if (n > 0):
        // N is positive. move first possibility to 0
        n-=1
        // use lower half of range
        rangeend = ceil((rangeend + rangestart)/2)
    else:
        // N is negative.  Flip sign move first possibility to 0
        n = -n - 1
        // use upper half of range
        rangestart = ceil((rangestart + rangeend)/2)

    T = thresholds[0]    
    if (n < T):
        // n is small, encode in one character
        return digits[rangestart+n];

    //n is big
    //remove small encodings from range
    rangestart += T
    range = rangeend-rangestart

    //Encode n%range in the first digit, and the rest in next digits
    return digits[n%range] + encodePos(floor(n/range), 1) // + is string concatenation

// encode positive integer to string with M digits

encodePos(int n, int place) -> string:
    T = thresholds[place]
    if (n < T):
        // n is small, encode in one character
        return digits[n];

    // n is big
    range = M - T
    return digits[n%range] + encodePos(floor(n/range), place+1)

Обратите внимание, что есть параметры, которые я не указал — массив thresholds.

Чтобы получить «оптимальную» кодировку, эти пороги следует выбирать так, чтобы вероятность увидеть n >= или < порога была пропорциональна количеству символов, доступных выше или ниже порога.

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

Это похоже на проблему XY - если у вас нет миллионов таких коллекций, можете ли вы подготовить сопоставление с какой-то новой справочной таблицей и получить их из другой таблицы?

Вам нужно будет подумать, как они будут отображаться обратно, но, возможно, вы сможете получить более хорошее решение, возможно, сериализовав каждый отдельный Vector (или просто его элементы) вместо N элементов векторов в отдельные поля или N неупакованных векторов, добавив NULL поля. для отслеживания различной длины и т. д.

Таблица 1

ключ значение1 значение2 ключ Т2 фу первый А 1 бар второй Б 2 Баз третий С 3

Таблица 2

ключ 1 12 1 -34 55 13 341 11 56 321 -3422 1222 -4 237

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

DED 22.04.2024 21:00

У меня нет возможности протестировать ваш конкретный сценарий, но в этом действительно преимущество нескольких таблиц; скромный SELECT * FROM _ JOIN _ ON _ WHERE _ удивительно быстр и должен привести к сопоставимому общему объему передачи данных.. хотя учтите, что вы можете получить дополнительное замедление и выгоду от дизайна, в котором у вас есть несколько таблиц целых чисел с разной длиной столбцов для учета очень разных длин векторной распаковки

ti7 24.04.2024 20:49

Другие вопросы по теме