Генерация уникального URL?

Question

[Алексей Скобкин]

Имеется необходимость генерировать уникальный URL в связке php+mySQL по типу bit.ly или clck.ru.

Какие есть варианты? Генерация по unixtime, хеши?

URL нужен короткий, поэтому банальнейший вариант с MD5 отпадает сразу. Вариант с цифровым id плох тем, что сначала ссылки будут короткими, а потом удлинняться. Да и будут «Геты». Нужен такой вариант, чтобы «все равны».

Answer 1

[Bright]

По этим ссылкам можно найти исходники сокращалок:
code.google.com/p/phurl/
www.webresourcesdepot.com/7-open-source-and-free-url-shortener-scripts-to-create-your-own/
briancray.com/2009/08/26/free-php-url-shortener-script/

Насколько я знаю, все они работают по одному принципу. Типичную функцию для перевода можете посмотреть в исходнике phurl:
code.google.com/p/phurl/source/browse/phurl-includes/functions.php — функция compressNumber, которая некоторое случайное число переводит в 62-ричную систему счисления

Comments

[Алексей Скобкин]

Кстати, да. Спасибо.
Я как раз подумывал о том, чтобы сделать перевод в систему счисления со своим алфавитом из латинских символов разных регистров.

[Bright]

Кстати, как мне кажется, еще важно с умом подойти к выбору алфавита. Например, я бы не стал включать в него слишком похожие символы — 0 и O, 1 и l и I и другие. Плюс, регистрозависимость урла — тоже не лучший «побочный эффект».

У нас с товарищем тоже была задача генерации коротких ссылок, в итоге решили делать их по шаблону
[4 строчных латинских буквы][две цифры] — т.к. адреса всегда будут выглядеть единообразно их будет проще запомнить и сложнее ошибиться при наборе. Ну а количество вариантов (26^4)*(100) в нашем случае вполне достаточно.

[Алексей Скобкин]

Хорошие и здравые мысли, в принципе. Но это для случая, если короткий URL может понадобиться запомнить.

Answer 2

[agul]

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

Comments

[Алексей Скобкин]

Имеется в виду алгоритм при котором изначально все ссылки будут одинаковой длины. Естественно, что такое множество вариантов не является бесконечным, но оно имеет допустимый размер.
Или же, конечно, можно и алгоритм, который будет начинать с коротких URL-ов и если множество закончится — будет использоваться на один символ больше.
Главное — не численные идентификаторы. Ну, тоесть ссылки по типу тех, что я привел в пример: bit.ly, clck.ru.

Answer 3

[AusTiN]

а что мешает брать MD5 от текущего юникстайма и обрезать по длине, брать, допустим, первые 5 символов?

Comments

[Алексей Скобкин]

То, что MD5 такой уникальный только при полной своей длине.

[Shvonder]

Полный или урезанный MD5 — все равно требуется проверка на наличие сгенерированного шифра в базе. Тут следует говорить о вероятности повторения шифра двух разных строк. И чем короче шифр тем больше эта вероятность. И никакой другой алгоритм эту вероятность не уменьшит при одинаковом равномерном распределении результатов шифрования. Поэтому урезание MD5 вполне может применяться. Но лучше md5 брать не от времени а от самого URL к примеру. Если не уверены в равномерности md5 можно использовать генератор случайных чисел и потом преобразовывать числа в буквы по их коду. В любом случае будут повторы. Их можно исключать простым увеличением на единицу до тех пор пока шифр не станет уникальным. При равномерном распределении вам не понадобится много раз увеличивать шифр. Допустим у вас 45 млн комбинаций и 40 из них заняты. Тогда в среднем каждая 8 ячейка свободна. И так оно и будет на практике.

[Алексей Скобкин]

Нужно без проверки на наличие в базе. Поэтому вариант с переводом в систему счисления другую — лучший.

Answer 4

[047]

Может быть, такое?

$unique_name = uniqid(md5(rand()), true);

Comments

[Алексей Скобкин]

With an empty prefix, the returned string will be 13 characters long. If more_entropy is TRUE, it will be 23 characters.

Длинновато будет…

[Алексей Скобкин]

Так, походу, меня только что ввели в заблуждение. Но все равно то, что она увеличивает энтропию в случае короткого идентификатора не уменьшает шанс того, что получится повторение…

[047]

Коллизии неизбежны в любом случае. Но этот случай настолько минимален, что обращать на него внимание не имеет смысла.

Answer 5

[deactivatedtheelephant]

Если вы делаете сервис коротких ссылок, вам все равно надо хранить в БД «длинные» ссылки. Так что для генерации можно использовать ID таблицы.

Comments

[Алексей Скобкин]

Нет, не укорачиватель, но это не мешает хранить ID, да.

Answer 6

[Qwerty-B]

Поздно, но есть мысль (вдруг кому-нибудь пригодится) - ID из таблицы в 36-ричной системе счисления (0-9, a-z). А можно еще с другими символами, с разным регистром.