URL Shortener algoritme?
Ik heb onlangs dit domein gekocht en zou dus een persoonlijke url shortener willen maken.
Nu zou ik een algoritme nodig hebben voor de URL's te linken in de DB, dit kan uitraard gewoon met cijfers (id van de url bv) maar dat is niet echt netjes en gaat na verloop van tijd ook niet meer effectief zijn bv meer dan 10000 zijn al meteen 5 characters extra terwijl je met 4 cijfers & letters veel meer mogelijkheden hebt.
Een random string genereren met een lijst characters is een optie, maar dan zou ik voor elke mogelijkheid moeten kijken of dit nog niet in de DB bestaat en dat lijkt mij ook niet de ideale oplossing, stel dat er 100 mogelijke combinaties zijn en 99 zijn er al van gebruikt en het script moet dan telkens een nieuwe string genereren en vergelijken.. Dat kan niet de manier zijn.. Of wel?
Iemand suggesties hoe je dit het best aanpakt?
En voornamelijk hoe je van een decimaal getal naar bijvoorbeeld een hexadecimaal getal gaat?
Nu, stel dat je nu een stelsel hebt voor 62 (0-9a-zA-Z). Dan worden de decimale getallen in dst stelsel dus:
0 - 0
9 - 9
10 - a
11 - b
60 - Y
61 - Z
62 - 10
63 - 11
123 - 1Z
124 - 20
Zo kan je dus al een heel eind verder gaan en toch gewoon je auto_increment gebruiken in je database.
Dat komt wel aardig in de buurt volgens mij...
Maar hoe wil je die juist genereren en checken of ze al bestaan?
Gewijzigd op 18/04/2012 19:44:45 door Jurgen B
Jurgen B op 18/04/2012 19:44:18:
... kan je deze methode ook toepassen op een 62 tallig stelsel ...
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
function omrekenen($getal, $soort, $return = '')
{
$chars = array_merge(range('0','9'),range('a','z'),range('A','Z'));
switch($soort)
{
case 10: if($getal > 61)
{
$return .= omrekenen(floor($getal / 62), $soort, $return);
}
$return .= $chars[($getal) % 62];
return $return;
case 62: for($i=0; $i<strlen($getal); $i++)
{
$search = (ord($getal[$i]) < 64) ? ord($getal[$i])-48 : $getal[$i];
$return += pow(62, strlen($getal)-$i-1) * array_search($search, $chars, true);
}
return $return;
default: return 'Error';
}
}
$random = rand(0,14776335);
$code = omrekenen($random, 10);
$getal = omrekenen($code, 62);
echo $random . ' => ' . $code . ' => ' . $getal . '<br />';
?>
function omrekenen($getal, $soort, $return = '')
{
$chars = array_merge(range('0','9'),range('a','z'),range('A','Z'));
switch($soort)
{
case 10: if($getal > 61)
{
$return .= omrekenen(floor($getal / 62), $soort, $return);
}
$return .= $chars[($getal) % 62];
return $return;
case 62: for($i=0; $i<strlen($getal); $i++)
{
$search = (ord($getal[$i]) < 64) ? ord($getal[$i])-48 : $getal[$i];
$return += pow(62, strlen($getal)-$i-1) * array_search($search, $chars, true);
}
return $return;
default: return 'Error';
}
}
$random = rand(0,14776335);
$code = omrekenen($random, 10);
$getal = omrekenen($code, 62);
echo $random . ' => ' . $code . ' => ' . $getal . '<br />';
?>
MAAR
Stel ik heb 13.000.000 links gegeneerd met het script van SanThe.. Dan heb je 90% kans dat de URL al bestaat, hoe los je dit op? Elke keer checken of hij al in de DB zit en indien wel opnieuw genereren?
Vb: bij het generen van 10K items heb ik al meteen 6 duplicates http://pastie.org/3815467
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
<?php
set_time_limit(60);
error_reporting(E_ALL);
function calculate($getal, $soort) {
$return = '';
$chars = array_merge(range('0','9'), range('a','z'), range('A','Z'));
switch($soort) {
case 10:
if($getal > 61) {
$return .= calculate(floor($getal / 62), $soort, $return);
}
$return = $chars[($getal) % 62];
return $return;
break;
case 62:
for($i = 0; $i < strlen($getal); $i++) {
$search = (ord($getal[$i]) < 64) ? ord($getal[$i])-48 : $getal[$i];
$return += pow(62, strlen($getal)-$i-1) * array_search($search, $chars, true);
}
return $return;
break;
default:
return false;
break;
}
}
$array = $found = array();
for($j = 0; $j < 10000; $j++) {
$string = '';
for($i = 0; $i < 4; $i++) {
$string .= calculate(rand(0,14776335), 10);
}
echo $string . " ";
if(!in_array($string, $array)) {
$array[] = $string;
}
else {
$found[] = $string;
}
}
echo "\n\n\n";
echo "Found " . count($found) . " duplicates (" . round((count($found) / (count($found) + count($array))) * 100, 2) . "%) on " . (count($found) + count($array)) . " items.";
echo "\n\n";
echo "Duplicates: \n";
foreach($found as $item) {
echo $item . "\n";
}
?>
set_time_limit(60);
error_reporting(E_ALL);
function calculate($getal, $soort) {
$return = '';
$chars = array_merge(range('0','9'), range('a','z'), range('A','Z'));
switch($soort) {
case 10:
if($getal > 61) {
$return .= calculate(floor($getal / 62), $soort, $return);
}
$return = $chars[($getal) % 62];
return $return;
break;
case 62:
for($i = 0; $i < strlen($getal); $i++) {
$search = (ord($getal[$i]) < 64) ? ord($getal[$i])-48 : $getal[$i];
$return += pow(62, strlen($getal)-$i-1) * array_search($search, $chars, true);
}
return $return;
break;
default:
return false;
break;
}
}
$array = $found = array();
for($j = 0; $j < 10000; $j++) {
$string = '';
for($i = 0; $i < 4; $i++) {
$string .= calculate(rand(0,14776335), 10);
}
echo $string . " ";
if(!in_array($string, $array)) {
$array[] = $string;
}
else {
$found[] = $string;
}
}
echo "\n\n\n";
echo "Found " . count($found) . " duplicates (" . round((count($found) / (count($found) + count($array))) * 100, 2) . "%) on " . (count($found) + count($array)) . " items.";
echo "\n\n";
echo "Duplicates: \n";
foreach($found as $item) {
echo $item . "\n";
}
?>
Gewijzigd op 19/04/2012 10:44:46 door Wouter De Schuyter
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<?php
set_time_limit(60);
function omrekenen($getal, $soort, $return = '')
{
$chars = array_merge(range('0','9'),range('a','z'),range('A','Z'));
switch($soort)
{
case 10: if($getal > 61)
{
$return .= omrekenen(floor($getal / 62), $soort, $return);
}
$return .= $chars[($getal) % 62];
return $return;
case 62: for($i=0; $i<strlen($getal); $i++)
{
$search = (ord($getal[$i]) < 64) ? ord($getal[$i])-48 : $getal[$i];
$return += pow(62, strlen($getal)-$i-1) * array_search($search, $chars, true);
}
return $return;
default: return 'Error';
}
}
$array = $found = array();
for($j = 0; $j < 10000; $j++) {
$string = omrekenen(rand(0,14776335), 10);
echo $string . " ";
if(!in_array($string, $array)) {
$array[] = $string;
}
else {
$found[] = $string;
}
}
echo "\n\n\n";
echo "Found " . count($found) . " duplicates (" . round((count($found) / (count($found) + count($array))) * 100, 2) . "%) on " . (count($found) + count($array)) . " items.";
echo "\n\n";
echo "Duplicates: \n";
foreach($found as $item) {
echo $item . "\n";
}
?>
set_time_limit(60);
function omrekenen($getal, $soort, $return = '')
{
$chars = array_merge(range('0','9'),range('a','z'),range('A','Z'));
switch($soort)
{
case 10: if($getal > 61)
{
$return .= omrekenen(floor($getal / 62), $soort, $return);
}
$return .= $chars[($getal) % 62];
return $return;
case 62: for($i=0; $i<strlen($getal); $i++)
{
$search = (ord($getal[$i]) < 64) ? ord($getal[$i])-48 : $getal[$i];
$return += pow(62, strlen($getal)-$i-1) * array_search($search, $chars, true);
}
return $return;
default: return 'Error';
}
}
$array = $found = array();
for($j = 0; $j < 10000; $j++) {
$string = omrekenen(rand(0,14776335), 10);
echo $string . " ";
if(!in_array($string, $array)) {
$array[] = $string;
}
else {
$found[] = $string;
}
}
echo "\n\n\n";
echo "Found " . count($found) . " duplicates (" . round((count($found) / (count($found) + count($array))) * 100, 2) . "%) on " . (count($found) + count($array)) . " items.";
echo "\n\n";
echo "Duplicates: \n";
foreach($found as $item) {
echo $item . "\n";
}
?>
@Chris: zou dat de correcte oplossing zijn? Zou het zo zijn dat bit.ly het bv doet? Lijkt mij nogal omslachtig..
Gewijzigd op 19/04/2012 12:46:18 door Wouter De Schuyter
@SanThe: hehe, dat is waar. Maar ik ga niet alle hashes uit de DB laden in een array en dan kijken of ze in die array zitten of wel? Stel dat je 14 miljoen records hebt kan dat niet echt performant zijn?
Code (php)
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
<?php
do
{
// genereer code
// SELECT code
}
while (mysql_num_rows() == 1);
// INSERT code
?>
do
{
// genereer code
// SELECT code
}
while (mysql_num_rows() == 1);
// INSERT code
?>
Maar ik denk dat de query wel sneller is dan alle bij langs lopen en kijken of ze al bestaan:
Code (php)
1
SELECT short_code FROM short_list WHERE used='0' ORDER BY RAND() LIMIT 1
Gewijzigd op 19/04/2012 15:35:28 door gerhard l
Wouter DS op 19/04/2012 15:25:54:
@Kees wat zou dat voor problemen kunnen geven? MySQL?
Omdat je met MySQL veel sneller en lastiger moet opschalen als je tientallen miljoenen URL's opslaat. Tevens zal het niet goed performen als je over miljoenen URL's stats gaat genereren.
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
function encode($id, $hashSize = 100)
{
$privateKey = 16546354324; // Moet je even checken wat de MAX_LONG waarde is
$num = $id * $hashSize + ($id * $privateKey) % $hashSize;
return base_convert($num, 10, 62);
}
function decode($string, $hashSize = 100)
{
$privateKey = 16546354324;
$num = (int) base_convert($string, 62, 10);
$hash = $num % $hashSize;
$id = ($num - $hash) / $hashSize;
if($hash != ($id * $privateKey) % $hashSize)
return false; // Foute hash
return $id;
}
?>
function encode($id, $hashSize = 100)
{
$privateKey = 16546354324; // Moet je even checken wat de MAX_LONG waarde is
$num = $id * $hashSize + ($id * $privateKey) % $hashSize;
return base_convert($num, 10, 62);
}
function decode($string, $hashSize = 100)
{
$privateKey = 16546354324;
$num = (int) base_convert($string, 62, 10);
$hash = $num % $hashSize;
$id = ($num - $hash) / $hashSize;
if($hash != ($id * $privateKey) % $hashSize)
return false; // Foute hash
return $id;
}
?>
Door hashSize te variëren kan je je URL veiliger maken. hashSize = 100 betekent dat je max 100 pogingen nodig hebt om de URL te gokken als je het ID weet.
Deze code werkt trouwens niet omdat base_convert maart to base 36 gaat, maar het idee lijkt me duidelijk.
Toevoeging op 19/04/2012 15:41:49:
@Kees,
Maar noSQL is dan toch niet per se de beste vervanging? Een simpele key->value DB lijkt me een stuk nuttiger.