Простой Java-алгоритм для кодирования / декодирования следующей строки - PullRequest
1 голос
/ 01 августа 2011

Предположим, у меня есть
String input = "1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,3,0,4,0,0,0,4,0,3"; Я хочу закодировать его в строку с меньшим количеством символов и фактически скрыть фактическую информацию, представляя ее римским символом, IE.Выше кодируется что-то вроде "Adqwqkjlhs".Должен быть в состоянии декодировать в исходную строку, если задана закодированная строка.

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

Есть идеи?

Спасибо

Редактировать # 1
Число может быть от 0 до 99, и каждое число отделяется запятой для String.split (",")чтобы получить строку []

Редактировать # 2 (назначение кодированной строки)
Предположим, что приведенная выше строка кодируется в bmtwva1131gpefvb1xv, тогда я могу иметь URL-ссылку, например www.shortstring.com/input#bmtwva1131gpefvb1xv.Оттуда я бы расшифровал bmtwva1131gpefvb1xv в запятые отдельных чисел.

Ответы [ 5 ]

1 голос
/ 01 августа 2011

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

Кодировка: создайте строку, начинающуюся с «1», делая каждое из чисел в исходной строке 2 цифрами, таким образом, «0» становится «00», «5» становится «05», «99» становится «99» и т. д. Представьте полученное число в базе 36.

Декодирование: Возьмите число 36 / строку base 36, измените его на основание 10, пропустите первые «1», затем превратите каждые 2 цифры / буквы в int и восстановите исходную строку.

Пример кода:

    String s = "1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,3,0,4,0,0,0,4,0,3";

    // ENCODE the string
    StringTokenizer tokenizer = new StringTokenizer(s,",");
    StringBuilder b = new StringBuilder();
    b.append("1");  // This is a primer character, in case we end up with a bunch of zeroes at the beginning
    while(tokenizer.hasMoreTokens()) {
        String token = tokenizer.nextToken().trim();
        if(token.length()==1) {
            b.append("0");
            b.append(token);
        }
        else {
            b.append(token);
        }
    }

    System.out.println(b);
    // We get this String: 101020000000000000000000000000000000000010202030004000000040003

    String encoded = (new BigInteger(b.toString())).toString(36);
    System.out.println(encoded);
    // We get this String: kcocwisb8v46v8lbqjw0n3oaad49dkfdbc5zl9vn


    // DECODE the string

    String decoded = (new BigInteger(encoded, 36)).toString();
    System.out.println(decoded);
    // We should get this String: 101020000000000000000000000000000000000010202030004000000040003

    StringBuilder p = new StringBuilder();
    int index = 1;   // we skip the first "1", it was our primer
    while(index<decoded.length()) {
        if(index>1) {
            p.append(",");
        }
        p.append(Integer.parseInt(decoded.substring(index,index+2)));
        index = index+2;
    }

    System.out.println(p);
    // We should get this String: 1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,3,0,4,0,0,0,4,0,3

Я не знаю, как можно легко превратить большое число в основание 64. Тщательно выбранные символы (например, +, , -) вполне подходят для кодирования URL, поэтому 0-9, az, AZ, с "" и "-" составляет 64. Метод BigInteger.toString () принимает значение только до Character.MAX_RADIX, который равен 36 (без заглавных букв). Если вы можете найти способ взять большое число и перейти на основание 64, то результирующая закодированная строка будет еще короче.

РЕДАКТИРОВАТЬ: похоже, это делает это для вас: http://commons.apache.org/codec/apidocs/org/apache/commons/codec/binary/Base64.html

1 голос
/ 01 августа 2011

Как насчет того, чтобы сохранить его как базовый номер 36?

В Java это будет

new java.math.BigInteger("120000000000000000012230400403").toString(36)

, что будет равно "bmtwva1131gpefvb1xv"

Вы получитеисходное число с

new java.math.BigInteger("bmtwva1131gpefvb1xv", 36)

Хорошо, что это не обрабатывает начальные 0 (предложение Тило о добавлении ведущей 1 будет работать).О запятых: если бы числа были одинакового размера (01 вместо 1), я думаю, что запятых не было бы необходимости.

0 голосов
/ 01 августа 2011

Модифицированный UUENCODE: -

Разделить двоичный файл на группы по 6 битов

Создать массив из 64 символов (выберите допустимые и сохраните их в порядке ASCII для удобного поиска): - 0..9, A..Z, _, a..z, ~

Отображение между двоичным кодом и символами.

0 голосов
/ 01 августа 2011

Если числа от 0 до 255, вы можете создать байтовый массив из него.Если у вас есть байтовый массив, у вас есть варианты выбора:

  1. Использовать base64 для байтового массива, что создаст компактную строку (почти) URL-совместимую
  2. Преобразовать их в символы,используя собственный алгоритм, основанный на максимальных значениях
  3. . Преобразуйте их в длинные, а затем используйте Long.toString (x, 31).

Для обратного преобразования вам, очевидно, придетсяприменить выбранный алгоритм в обратном порядке.

0 голосов
/ 01 августа 2011

Предлагаем вам взглянуть на base64 , который обеспечивает 6 бит информации на символ - в общем, ваша эффективность кодирования составляет log 2 (K) бит на символ, где K - это число символы в наборе допустимых символов.

Для 8-битного набора символов многие из них недопустимы в URL-адресах, поэтому вам нужно выбрать несколько подмножеств, которые являются допустимыми символами URL.


Просто чтобы уточнить: я не имел в виду кодировать ваши "1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,1,2,2,3,0,4,0,0,0,4,0,3 "как base64 - я хотел выяснить, какую информацию вы действительно хотите кодировать, выраженную в виде строки raw двоичные байты и кодируют , что в base64. Он исключит управляющие символы (хотя вы можете использовать альтернативную форму , где все 64 символа могут использоваться в URL-адресах без экранирования) и будет более эффективным, чем преобразование чисел в печатную форму чисел.


Число может быть от 0 до 99, и каждое число отделяется запятой для String.split (",") для извлечения String []

Хорошо, теперь у вас есть четкое определение. Вот предложение:

Преобразование вашей информации из ее первоначальной формы в двоичный массив чисел / байтов. Если все, что у вас есть, это строка чисел от 0 до 99, разделенных запятыми, то вот два варианта:

  • (медленно) - обрабатывать как числа в базе 100, преобразовывать в BigInteger (например, n = n * 100 + x [i] для каждого числа x в массиве), преобразовывать в байтовый массив и не забудьте предшествовать всему этому по его длине, чтобы "0,0,0,0" можно было отличить от "0,0" (численно равных в базе 100, но оно имеет другую длину. Затем преобразуйте результат в base64 .

  • (более эффективно) - обрабатывать как числа в базе 128 (так как это степень 2) и использовать любое число от 100-127 в качестве символа завершения. Поэтому каждый блок из 6 чисел содержит 42 (= 6 * 7) бит информации, которые могут быть закодированы как строка из 7 символов с использованием base64. (Пэд с символами завершения, необходимыми для достижения четного кратного 6 оригинальных чисел.)

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

Для обратного алгоритма просто поменяйте местами шаги, и вы получите массив чисел от 0 до 99 - используя либо префиксную длину, либо символ завершения, чтобы определить размер массива - который вы можете преобразовать в удобочитаемая строка, разделенная запятыми.

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

...