Сжать число в виде строки, чтобы поместиться в 256 символов

Question

Я пытаюсь использовать битовую маску, чтобы предоставить как можно больше двоичных значений, чтобы окончательное значение сохранялось в памяти с ограниченным выделением для строки.Моя текущая методология состоит в том, чтобы найти максимальное число и преобразовать его в строку base-36.

value = (0 | (1<<1318)).to_s(36)

В результате получается 255 символов сжатого числа, из которого я могу извлечь свое исходное число 1318. Недостатокя ограничен 1318 двоичными значениями, и я хочу расширить это число.Есть ли в Ruby альтернативные стратегии для сжатия этого числа еще больше?

Answer 1

Числа неотрицательны

Если числа неотрицательны, мы можем кодировать каждые 8 ​​бит каждого числа в символ, который является частью строки, а затем декодироватьстрока путем преобразования каждого символа в 8 бит числа.

def encode(n)
  str = ''
  until n.zero?
    str << (n & 255).chr
    n = n >> 8
  end
  str.reverse
end

def decode(str)     
  str.each_char.reduce(0) { |n,c| (n << 8) | c.ord }
end

При этом используются следующие методы манипуляции битами в классе Integer : &, >>, << и |.

def test(n)
  encoded = encode(n)
  puts "#{n} => #{encoded} => #{decode(encoded)}"
end

test      1  #      1 => ["\u0001"]            =>      1
test     63  #     63 => ["?"]                 =>     63
test     64  #     64 => ["@"]                 =>     64
test    255  #    255 => ["\xFF"]              =>    255
test    256  #    256 => ["\u0001", "\u0000"]  =>    256
test 123456  # 123456 => ["\x01", "\xE2", "@"] => 123456

Например,

n = 123456
n.to_s(2)
  #=> "11110001001000000"

так

n = 0b11110001001000000
  #=> 123456

Байты этого числа можно визуализировать так:

00000001 11100010 01000000

Мы видим, что

a = [0b00000001, 0b11100010, 0b01000000]
a.map(&:chr)
  #=> ["\x01", "\xE2", "@"]

Числа могут быть отрицательными

Если кодируемые числа могут быть отрицательными, нам необходимо сначала преобразоватьк их абсолютным значениям добавьте некоторую информацию к закодированной строке, которая указывает, являются ли они неотрицательными или отрицательными.Для этого потребуется как минимум один дополнительный байт, поэтому мы можем включить "+" для неотрицательных чисел и "-" для отрицательных чисел.

def encode(n)
  sign = "+"
  if n < 0
    sign = "-"
    n = -n
  end
  str = ''
  until n.zero?
    str << (n & 255).chr
    n = n >> 8
  end
  (str << sign).reverse
end

def decode(str)
  n = str[1..-1].each_char.reduce(0) { |n,c| (n << 8) | c.ord }
  str[0] == '+' ? n : -n
end

test    -255  # -255    => ["-", "\xFF"]              => -255
test    -256  # -256    => ["-", "\u0001", "\u0000"]  => -256
test -123456  # -123456 => ["-", "\x01", "\xE2", "@"] => -123456
test  123456  #  123456 => ["+", "\x01", "\xE2", "@"] =>  123456

Answer 2

Вы всегда можете закодировать свой номер в базу s, а затем представить его как строку с любым алфавитом, который вам нужен.

def encode(n, alphabet)
  s = alphabet.size
  res = []
  while (n > 0)
    res << n % s
    n = n / s
  end
  res.reverse.map { |i| alphabet[i] }.join
end

Ваш метод эквивалентен encode(n, alphabet), где alphabetопределяется как

alphabet = ((0..9).to_a + ("a".."z").to_a).join
# => "0123456789abcdefghijklmnopqrstuvwxyz"

Но вы можете также использовать все возможные символы вместо только 36 из них:

extended_alphabet = (0..255).map { |i| i.chr }.join

Это дает в общей сложности (256 ** 255) возможностей, т.е.до (2 ** 2040), что намного лучше, чем фактическое (2 ** 1318).

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

---

Затем можно выполнить декодирование следующим образом:

def decode(encoded, alphabet)
  s = alphabet.size
  n = 0
  decode_dict = {}; i = -1
  alphabet.each_char { |c| decode_dict[c] = (i += 1) }
  encoded.each_char do |c|
    n = n * s + decode_dict[c]
  end
  n
end

Если вы собираетесь использовать фиксированный алфавит для всех ваших кодировок, я бы предложилвычисление словаря декодирования вне функции и использование его в качестве параметра вместо alphabet, чтобы избежать его вычисления при каждой попытке кодировать число.