Генерация уникальных кодов в PHP / MySQL?

StackOverflow https://stackoverflow.com/questions/219475

Вопрос

Я работаю с клиентом, которому необходимо сгенерировать миллионы буквенно-цифровых кодов, используемых в журнальных скретч-картах, призах в виде крышечек от бутылок и так далее.Они должны быть достаточно короткими, чтобы печатать в шапке, они хотят убедиться, что неоднозначные символы, такие как 1 и I, 0 и O и т.д.они не включены, и их нужно явно сохранить для использования в будущем - у нас не может быть просто алгоритма, который определяет "действительность", когда кто-то пытается их активировать.Наконец, они хотят убедиться, что коды распределены случайным образом внутри большого "кодового пространства", чтобы люди не могли просто угадать дополнительные коды, прогуливаясь по алфавиту.

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

Это было полезно?

Решение

Если вам нужно около 10 миллионов уникальных ключей (например), лучший подход - выбрать пространство для ключей, которое экспоненциально больше, и начать случайную генерацию.Читайте о Парадокс Дня рождения -- это главное, о чем тебе следует беспокоиться.Если вам нужны 2 ^ n уникальных и защищенных ключей, убедитесь, что существует по крайней мере 2 ^ (2 * n) возможных значения.Вот приблизительный алгоритм O (n log n):

  • Используйте пространство ключей не менее 2 ^ 50 (то есть, другими словами, допускайте 2 ^ 50 возможных уникальных значений), и у вас практически не будет коллизий во всем вашем наборе данных - и любой, кто грубо использует ваши ключи, будет иметь примерно равные шансы получить ключ, если попробует использовать 2 ^ 25 из них.
  • генерируйте столько случайных чисел, сколько вам нужно
  • проиндексируйте базу данных по вашему ключу (это шаг O (n lg n):тот самый сорт)
  • просмотрите базу данных и выполните итерацию по всему набору данных, чтобы обрезать дубликаты (псевдокод ниже).
  • Удалите дублирующиеся строки, и все готово.

Псевдокод:

$last = null;
while ($current = getnext()) {
    if ($last == $current) {
        push($toDelete, $current);
    }
    $last = $current;
}

Другие советы

Предположим, вы можете использовать набор символов, скажем, из 40 символов, состоящих из однозначных верхних, нижних и цифровых символов.

Для последовательности из n символов у вас есть 40n комбинации

  • 404 = 2,560,000
  • 405 = 102,400,000
  • 406 = 4,096,000,000
  • 407 = 163,840,000,000
  • 408 = 6,553,600,000,000

Таким образом, 8 символов дают довольно хорошее пространство для работы - если вы сгенерировали 10 миллионов кодов, вам пришлось бы перепробовать сотни тысяч комбинаций, чтобы выполнить перебор кода.

Или вы заходите с другой стороны - назовите номер возможный коды, сколько кодов следует вы создаете, чтобы избежать ловушки, которую они называют Парадокс Дня рождения?

Принимая 8-символьный код, 6 553 600 000 000 - это приблизительно 242, таким образом , вы могли бы разумно сгенерировать 221 коды из него, или 2,097,152

Использовать алгоритм одноразового пароля?

RFC4225 детализирует один на основе алгоритма HMAC.

http://www.ietf.org/rfc/rfc4226.txt

но вместо кодировки base10 цифр 0-9 используйте base32.

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

Как ни странно, со следующим исходным кодом я смог сгенерировать только 32 уникальные строки.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

С более длинным исходным кодом я смог сгенерировать гораздо больше - успешно сгенерировал 40 000 уникальных строк.

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top