Требуется генерировать из последовательных целых, уникальные непоследовательные n-значные коды. Представьте хэши, серийники, или номера купонов. Целочисленному id от 0 до K соответствует строго один n-значный код. И важно, чтобы последовательно идущие коды сильно различались, а не одним-двумя символами.
Пример:
0 KXBR6Z
1 8FLWGG
2 PAZT73
Из-за коллизий и краткости требуемых кодов, популярные хэш-функции не подходят. Криптостойкость не требуется. Если злодеи разгадают алгоритм, пусть хоть все коды распечатают. Делается для красоты. Хотя, рассмотреть, от чего зависит сложность отгадывания алгоритма по X имеющимся на руках кодам тоже интересно!
Вопрос: подскажите алгоритм / функцию f(i) = s для соответствия между множествами 0..K и n-значными ABC123XYZ. Обратная функция была бы тоже интересна: f1(s) = i чтобы из кода получить целое, либо узнать, что код невалиден.
Наверняка, задача не нова, но не придумал, как искать ответ. Требуется human-трансляция. )
P.S. ищу именно "математику", алгоритм, а не способ забить в БД уникальные значения, каждый раз при создании нового, проверяя уникальность.
Ответ
С такой задачей хорошо справляются шифры подстановки. Первое, что Вам надо сделать - это расширить алфавит (перейти от цифр к буквам, где несколько букв будут соответствовать одной цифре). Если для Вас очень важно скрыть исходные значение, то имеет смысл предварительно зашифровать данные блочным или асиметричным шифрованием.
накидал пример кода с подстановкой, результат:
input/encoded/decoded - 123 / efg / 123
input/encoded/decoded - 456 / hij / 456
input/encoded/decoded - 789 / abc / 789
input/encoded/decoded - 012 / def / 012
input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188
сам код:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class Substitution {
private static final int NUMBER_COUNT = 10;
private static final int LETTER_COUNT = 26;
private static final int ZERO_ASCII_CODE = 48;
private static final int A_CHAR_ASCII_CODE = 97;
// substitution tables
private static final Map
// init tables
static {
// add list containers
for (int i = 0; i < NUMBER_COUNT; i++) {
numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)),
new LinkedList
// init substitution table
for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {
// number = (symbol ascii code) mod 9
Character num = Character
.valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE));
Character ch = Character.valueOf((char) i);
numToChar.get(num).add(ch);
charToNum.put(ch, num);
}
}
public static void main(String[] args) {
System.out.println("dumping straight substitution table");
for (Character num : numToChar.keySet()) {
System.out.println("num to char - " + num + ", replacements = "
+ numToChar.get(num));
}
System.out.println();
System.out.println("dumping reverse substitution table");
for (Character ch : charToNum.keySet()) {
System.out.println("char to num - " + ch + ", replacements = "
+ charToNum.get(ch));
}
// test
String[] nums = new String[] { "123", "456", "789", "012", "1157232188" };
String r = null;
for (int i = 0; i < nums.length; i++) {
r = decode(nums[i], true);
System.out.println("input/encoded/decoded - " + nums[i] + " / " + r
+ " / " + decode(r, false));
}
}
public static String decode(String input, boolean direction) {
// result buffer
StringBuilder b = new StringBuilder(input.length());
// ensure all latters are in lower case
String data = input.toLowerCase();
// store indexes (determines which letter to use when coding a number)
Map
// encode string
for (int i = 0; i < input.length(); i++) {
b.append(decode(indexes, data.charAt(i), direction));
}
return b.toString();
}
// straight - number to letter
// reverse - letter to number
private static Character decode(Map
// get index to use
Integer index = indexes.get(character);
if (null == index) {
index = Integer.valueOf(0);
}
// update index map
int next = index.intValue() + 1;
if (next == list.size()) {
next = 0;
}
indexes.put(character, Integer.valueOf(next));
return list.get(index);
}
return charToNum.get(character);
}
}
Данный пример строго "заточен" под цифры и буквы, но, по аналогии, можно сделать код который будет делать подстановки отдельных символов и/или их последовательностей
Комментариев нет:
Отправить комментарий