Сокращение строки в Java

Question

У меня есть требование сократить строку из 6 символов, например "ABC123", в уникальную строку из 4 символов. Он должен быть повторяемым, чтобы входная строка всегда генерировала одну и ту же выходную строку. У кого-нибудь есть идеалы как это сделать?

Answer 1

Невозможно сделать полностью уникальное отображение из строки из 6 символов в строку из 4 символов. Это пример простой хеш-функции. Поскольку пространство диапазона меньше, чем пространство домена, у вас обязательно будут некоторые коллизии хешей. Вы можете попытаться свести к минимуму количество коллизий в зависимости от типа данных, которые вы собираетесь принимать, но в конечном итоге невозможно сопоставить каждую 6-символьную строку с уникальной 4-символьной строкой, так как у вас не будет 4-символьных строк.

Answer 2

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

Например, предположим, вы знаете, что он состоит только из заглавных букв и цифр. Следовательно, существует 36^6 возможных строк ввода.

Результат должен иметь меньше ограничений, например, вы можете использовать 216 различных символов (печатные расширенные ascii или что-то в этом роде).

По чистой случайности, 216^4 = 36^6, так что вам нужно отображение. Это просто, просто используйте алгоритм для преобразования числовых представлений от одного радиуса к другому.

Answer 3

Не уверен, что это можно сделать, так как могу поспорить, что существуют некоторые бизнес-ограничения (например, пользователь должен иметь возможность вводить ключ).

Идея состоит в том, чтобы "хешировать" значение в меньшем количестве мест. Для этого требуется набор символов, достаточно большой для обработки всех комбинаций.

Давайте предположим, что исходный ключ нечувствителен к регистру, у вас 26 + 10 = 32, а затем повышен до 6-й уникальной комбинации (2 176 782 336 уникальных комбинаций). Чтобы сопоставить это только с 4 символами, вы должны использовать набор символов с 216 уникальными символами, так как 216 ^ 6 равен 2 176 782 336 или первое число увеличивается до 4 с большим количеством комбинаций, чем нечувствительный к регистру ключ с числами. (нечувствительность к регистру, плюс цифры только приводит вас к 62).

Если мы возьмем стандартную клавиатуру США, у нас будет 26 букв x 2 регистра = 52 10 цифр 10 специальных символов на цифровых клавишах 11 других специальных символов * 2 = 22

Это 94 уникальных символа, или менее половины уникальных символов, которые вам нужны, чтобы получить безразличный 6-значный код из 4 цифр. Теперь на планете клингон, где клавиатуры намного больше...;-)

Если ключ нечувствителен к регистру, ваш набор символов должен быть расширен до 489 уникальных символов, чтобы поместиться в 4-значный "хэш". Ой!

Answer 4

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

public class Foo {

    public static int crunch(String str) {
        int y = 0;
        int limit = str.length() > 6 ? 6 : str.length();
        for (int i = 0; i < limit; ++i) {
            y += str.charAt(i) * (limit - i);
        }
        return y;
    }

    public static void main(String[] args) {
        String[] words = new String[]{
            "abcdef", "acdefb", "fedcba", "}}}}}}", "ZZZZZZ", "123", "!"
        };

        for (int idx = 0; idx < words.length; ++idx) {
            System.out.printf("in=%-6s out=%04d\n",
              words[idx], crunch(words[idx]));
        }
    }
}

Формирует:

in=abcdef out=2072
in=acdefb out=2082
in=fedcba out=2107
in=}}}}}} out=2625
in=ZZZZZZ out=1890
in=   123 out=0298
in=     ! out=0033

Answer 5

Вы должны сделать предположения о диапазоне значений, которые могут иметь символы, и о том, когда допустимый кодированный символ. Есть несколько способов сделать это. Вы можете упаковать строку в 1,2,3,4 или 5 символов в зависимости от ваших предположений.

Один простой пример, который даст вам 4 символа, - это предположить, что последние три буквы - это число.

public static String pack(String text) {
    return text.substring(0, 3) + (char) Integer.parseInt(text.substring(3));
}

public static String unpack(String text) {
    return text.substring(0, 3) + ("" + (1000 + text.charAt(3))).substring(1);
}

public static void main(String[] args) throws IOException {
    String text = "ABC123";
    String packed = pack(text);
    System.out.println("packed length= " + packed.length());
    String unpacked = unpack(packed);
    System.out.println("unpacked= '" + unpacked + '\'');

}

печать

packed length= 4
unpacked= 'ABC123'