On Feb 22, 5:26 am, joe <jcha...@gmail.com> wrote:
> Hello anyone knows how to write a funtion to genereate a tiny url with
> letters and numbers only. Something almost always unique. THanks.
As mentioned by santosh, in practice you can essentially try to
duplicate what the site "tinyUrl.com" does, however, either way it
requires that you solve the more general problem of mapping limitless
strings to fixed sized hashes that are "almost always unique". So let
us solve this latter problem before we address the whole problem.
To map a set of variable length strings to something "pseudo-unique"
fundamentally requires an understanding of "The Birthday
Paradox" (look it up on Wikipedia.) However to make a long story
short you should study "secure hashing". Open source implementations
of SHA-256 and WHIRLPOOL exist, which are probably the "safest" bets
right now. The upshot of this is that you can transform variable
length strings to something like 160 or 256 bits in a way that even an
expert adversary cannot find any collisions in.
Now for something like an URL, however, you are going to need to
transform the output to text. So use Base-64 or hex encoding or
something like that to turn the binary to alphanumerics. Lets call
this a "long encoding" of the URL.
Now as for making it tiny, the only way I can see how to do this is to
basically retain a database of all such hashings done and always
return the shortest possible truncated version of the "long
encoding" (which is calculated as described above) that is unique.
Then you can just make the URL something like: www.smalladdress.com/<URL>
and you would probably use some Apache configuration trick to turn
this into a call to php or cgi which takes the <URL> and looks it up
in your DB and produces the original URL as a redirect. I assume that
this, roughly speaking, is what tinyurl.com does.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Similar Threads
