Алгоритм генерации уникальной последовательности цифр

[beba]

Алгоритм генерации уникальной последовательности цифр

Здравствуйте.

Подскажите пож-та идею, как можно получить уникальную (в той или иной степени) последовательность цифр.
Исходное слово, для формирования последовательности принят емэйл адрес. Необходимо получить 10 цифр.

На данный момент делается так.

1. Сохраняю md5 от емэйладерса.
2. Выделяю 5 частей по 6 символов, начиная сначала полученного результата от md5. (получается в общем затрагиваю 30 символов, и 2 остаются я их не трогаю)
3. Нахожу сумму элементов каждой части (она максимум равна 96 - в случае если часть будет ffffff).
4. Соединяю все эти суммы получаю число размером 10 символов.

но примерно на 5500ом человеке, выдало совпадение..

подскажите пож-та, может какой другой алгоритм.. буду признателен..

Спасибо.

p.s. Пока буду думать над другим алгоритмом.

 

[c0dex]

Зачем?

 

[Adelf]

md5 уже дает тебе число. Записанное в шестнадцатеричной системе.

 

[Ragazzo]

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

 

[beba]

c0dexнужно генерировать уникальный штрихкод EAN13 для покупателя.
Adelf сори, я хотел написать но не пометил.. мне нужно 10 цифр.
Ragazzo поэтому я и написал "получить уникальную (в той или иной степени)"

 

[AmdY]

uniqid ?

 

[beba]

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

 

[c0dex]

beba
Ты сам просил уникальности, так в чем дело? Нужно цифровое соответствие для какой-то строки? Тогда чем просто md5 не угодил?

 

[beba]

c0dex
> Нужно цифровое соответствие для какой-то строки?
можно сказать и так..
> Тогда чем просто md5 не угодил?
количество цифр, нужно 10.

 

[Beavis]

beba
переведи в десятичную систему и отрежь 10 цифр

 

[HraKK]

Добавь в таблицу юзеров поле EAN13 и дай ему UNIQUE KEY и генерируй что тебе вздумается.

 

[dimagolov]

beba, md5 дает 2^128 значений, то есть 3.4*10^38 значений. Тебе нужно отобразить это в 10^10 значений, то есть полученное значение md5 поделить на 3.4*10^28 степени.

In your case, since MD5 is a 128-bit hash, the probability of a collision is less than 2-100. You'd need about 264 records before the probability of a collision rose to 50%.

Исходя из этого вероятность совпадения результата деления на 3.4*10^28 будет 2^28 / 10 ^10 ~ 2.7% что реально дофига (кстати, не ошибся ли где-то на порядок и правильна ли цитата?)

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

п.с. а почему нельзя просто последовательно выдавать номера?

 

[zerkms]

кстати, не ошибся ли где-то на порядок и правильна ли цитата?

кстати, ошибся вероятность повторного выпадения 10-значного числа в случае равномерного распределения равна точно 1 / 10^10 (внезапно)

 

[dimagolov]

zerkms, а откуда у нас взялось равномерное распределение? md5 подобного ведь не обещает... иначе с чего бы у автора коллизия при 5500 то есть 1.8 / 10^4, что на 6 порядков ниже.

 

[c0dex]

автор ни кода не привел, ничего. Как он там складывает - можно только гадать, потому еще не факт, что это не в его коде трабл.

 

[beba]

Всем большое спасибо за ответы!

Beavis Да, но не получится ли похожая ситуация как у меня получилась..? т.к. вроде бы первоначальный план казалось бы тоже был неплох..

HraKK Тут получается опять же проблема с повторной генерацией... т.е. генерировать все же нужно по какому либо алгоритму..

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

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

 

[zerkms]

dimagolov

md5 подобного ведь не обещает...

вообще - оно обязано обещать. более-менее равномерное распределение, иначе это говно, а не функция свертки.

иначе с чего бы у автора коллизи

с того, что входные данные такие.

-~{}~ 04.11.10 00:45:

действительно 2.7% будет многовато

цифра взята с потолка. но если тебе так спокойнее - пусть так и будет

-~{}~ 04.11.10 00:46:

На последовательности 1 - 10^6 вероятность коллизии для первых десяти цифр от десятичного md5 составляет 0.0147%

Выводы делаем сами

 

[beba]

вот код:

$code = strtolower(md5($cInfo['customers_email_address']));

$sub[] = substr($code,0,6);
$sub[] = substr($code,6,6);
$sub[] = substr($code,12,6);
$sub[] = substr($code,18,6);
$sub[] = substr($code,24,6);

$barcode_str = "";

foreach ($sub as $k=>$v) {
  $sum = hexdec(substr($v,0,1))+hexdec(substr($v,1,1))+hexdec(substr($v,2,1))+hexdec(substr($v,3,1))+hexdec(substr($v,4,1))+hexdec(substr($v,5,1));
  $barcode_str.= $sum;
};

$new_barcode = trim(tep_get_ean_customer($barcode_str));

-------
tep_get_ean_customer - добавляет префикс (две цифры) в начало и расчитывает контрольную сумму.

 

[zerkms]

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

любая функция свёртки подвержена коллизии. в твоём случае коллизия приравнивается к невозможности скрипту работать дальше в принципе.

отдельная таблица соответствия "сущность -> случайная уникальная (а тут она будет по-настоящему уникальная) строка" - лучшее решение.

 

[dimagolov]

beba, про магазины. если их до 10 и покупатели распределены равномерно, то юзай один разряд как код магазина.

я уже изложил тебе алгоритм. и не случайный и с коррекцией коллизий. из какого-то хеша собираешь себе как-то 7-8 цифр, потом проверяешь коллизию и добавляешь счетчик коллизий в 1-2 разряда.

ну а проще всего конечно это разделить диапазон на непересекающиеся банки для разных магазинов и просто выдавать последовательно.