URL Shortener algoritme?
- SanThe - op 19/04/2012 15:34:04:
Als het in een database staat zou ik het zo ongeveer doen:
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
?>
Codes blijven genereren tot dat hij niet gevonden werd?
Hoelang kan zo iets duren als je bv 10.000.000 codes in je DB hebt?
Als je gewoon het ID naar een string omzet, heb je ook nog het voordeel dat je begint met kleine strings.
Encode de ID naar een string, zodat je het kort kan houden.
Mijn script heeft dan nog een extratje, waardoor het 'onmogelijk' is URLs te raden. Zo kan je bijvoorbeeld afgeschermde pagina's maken, zoals youtube dat doet.
Het werkt als volgt:
Neem het ID
Maak een hash:
hash = ID * privatekey (dit maakt een groot, onvoorspelbaar nummer)
% (modulo) hashlength.
De modulo zorgt ervoor dat je een kleine hash overhoudt die random lijkt te zijn en bijna onmogelijk te raden is, maar toch makkelijk te berekenen.
De hashSize bepaalt de sterkte van deze beveiliging. Grote size is een betere beveiliging, maar ook langere strings.
Het uiteindelijke getal is dan
ID * hashSize + hash
Stel dat de hashsize dan 100 is, dan heb je gewoon de ID met een getal tussen de 0 en de 99 erachter.
Je hebt nu een getal dat je omzet naar basis 62 met een script zoals dat van SanThe. 62 wordt dan iets als 10 en 71 1a. De string wordt hierdoor heel compact.
Dit alles heeft als voordeel dat als mensen 1 URL krijgen/vinden, ze niet meteen alle verkorte URLs te pakken hebben, wat me niet ideaal lijkt.
Toevoeging op 19/04/2012 22:35:09:
Een hashSize van 1000, wat ervoor zorgt dat je gemiddeld 500 pogingen nodig hebt lijkt me voldoende. Uitgaande van basis 62 [a-zA-Z0-9] voegt dat maximaal maar 2 karakters toe (62log 1000 = 1.7). Je kan dan dus de eerste 1000 IDs in max 4 karakters kwijt en dan heb je ook nog een goede beveiliging. Lijkt me prima.
Gewijzigd op 19/04/2012 22:35:58 door Pim -