Укоротить уже короткую строку в Java

Question

Я ищу способ максимально сократить уже короткую строку.

Строка является именем хоста: port combo и может выглядеть как " my-domain.se: 2121 "или" 123.211.80.4: 2122".

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

Поскольку алфавит ограничен 39 символами ( [az] [0-9] -:. ), каждый символ может уместиться в 6биты.Это уменьшает длину до 25% по сравнению с ASCII.Поэтому мое предложение выглядит следующим образом:

1. Кодирование строки в байтовый массив с использованием некоторой пользовательской кодировки
2. Декодирование байтового массива в строку UTF-8 или ASCII (эта строка, очевидно, не будет иметь никакого смысла).

А затем выполните обратный процесс, чтобы получить исходную строку.

Итак, на мои вопросы:

1. Может ли это работать?
2. Есть ли лучший способ?
3. Как?

Answer 1

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

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

class Encoder {
  public static final int BASE = 40;
  StringBuilder chars = new StringBuilder(BASE);
  byte[] index = new byte[256];

  {
    chars.append('\0');
    for (char ch = 'a'; ch <= 'z'; ch++) chars.append(ch);
    for (char ch = '0'; ch <= '9'; ch++) chars.append(ch);
    chars.append("-:.");
    Arrays.fill(index, (byte) -1);
    for (byte i = 0; i < chars.length(); i++)
      index[chars.charAt(i)] = i;
  }

  public byte[] encode(String address) {
    try {
      ByteArrayOutputStream baos = new ByteArrayOutputStream();
      DataOutputStream dos = new DataOutputStream(baos);
      for (int i = 0; i < address.length(); i += 3) {
        switch (Math.min(3, address.length() - i)) {
          case 1: // last one.
            byte b = index[address.charAt(i)];
            dos.writeByte(b);
            break;

          case 2:
            char ch = (char) ((index[address.charAt(i+1)]) * 40 + index[address.charAt(i)]);
            dos.writeChar(ch);
            break;

          case 3:
            char ch2 = (char) ((index[address.charAt(i+2)] * 40 + index[address.charAt(i + 1)]) * 40 + index[address.charAt(i)]);
            dos.writeChar(ch2);
            break;
        }
      }
      return baos.toByteArray();
    } catch (IOException e) {
      throw new AssertionError(e);
    }
  }

  public static void main(String[] args) {
    Encoder encoder = new Encoder();
    for (String s : "twitter.com:2122,123.211.80.4:2122,my-domain.se:2121,www.stackoverflow.com:80".split(",")) {
      System.out.println(s + " (" + s.length() + " chars) encoded is " + encoder.encode(s).length + " bytes.");
    }
  }
}

printints

twitter.com:2122 (16 chars) encoded is 11 bytes.
123.211.80.4:2122 (17 chars) encoded is 12 bytes.
my-domain.se:2121 (17 chars) encoded is 12 bytes.
www.stackoverflow.com:80 (24 chars) encoded is 16 bytes.

Я оставляю декодирование в качестве упражнения.;)

Answer 2

Прежде всего, IP-адреса рассчитаны на 4 байта, а номера портов - на 2. Представление ascii предназначено только для чтения людьми, поэтому сжатие для этого не имеет смысла.

Ваша идея сжатия строк доменного имени выполнима.

Answer 3

Вы можете кодировать их, используя Код дисплея CDC .Эта кодировка использовалась в старые времена, когда битов было мало, и программисты нервничали.

Answer 4

Первые два байта могут содержать номер порта. Если вы всегда начинаете с этого номера порта фиксированной длины, вам не нужно включать разделитель :. Вместо этого используйте бит, который указывает, следует ли IP-адрес (см. решение Карла Билефельда ) или имя хоста.

Answer 5

Ну, в вашем случае, я бы использовал специализированный алгоритм для вашего варианта использования. Признайте, что вы можете хранить что-то кроме строк. Так что для адреса IPv4: порт у вас будет класс, который захватывает 6 байтов - 4 для адреса и 2 для порта. Еще один тип для apha-числовых имен хостов. Порт всегда будет храниться в двух байтах. Например, сама часть имени узла может также иметь специализированную поддержку .com. Таким образом, примерная иерархия может быть:

    HostPort
       |
  +----+--------+
  |             |
IPv4        HostnamePort
                |
           DotComHostnamePort


public interface HostPort extends CharSequence { }


public HostPorts {
  public static HostPort parse(String hostPort) {
    ...
  }
}

В этом случае DotComHostnamePort позволяет вам удалить .com из имени хоста и сохранить 4 символа / байта, в зависимости от того, храните ли вы имена хостов в punyform или в форме UTF16.

Answer 6

То, что вы предлагаете, похоже на кодирование / декодирование base 64, и при рассмотрении некоторых из этих реализаций может потребоваться определенное расстояние (кодирование base 64 использует 6 бит).

Как стартер, если вы используете библиотеку Apache base 64

String x = new String(Base64.decodeBase64("my-domain.se:2121".getBytes()));
String y = new String(Base64.encodeBase64(x.getBytes()));
System.out.println("x = " + x);
System.out.println("y = " + y);

Это сократит вашу строку на несколько символов.Это, очевидно, не работает, так как то, с чем вы в итоге оказались, - это не то, с чего вы начали.