Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Shortern URIs using Huffman Coding, not a database

urizip-dot-populace-soho.appspot.com

Post reply on HN
Print view View original

1–10 of 87 posts

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#2

Post by ageitgey »

The url for this post is 45 characters:

https://news.ycombinator.com/item?id=14245119

If you encode it with this shortener, you get this 35 character string:

mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA

Assuming you were using this string as a key in a shortening service like this:

https://short.url/mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA

... you'd end up with a url longer than the original url! So it's not technically a url shortener :)

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#4

Post by zzzcpan »

ageitgey wrote: post #2

The url for this post is 45 characters: https://news.ycombinator.com/item?id=14245119 If you encode it with this shortener, you get this 35 character string: mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA Assuming you were using this string as a key in a shortening service like this: https://short.url/mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA ... you'd end up with a url longer than the original url! So it's not technically a url shor…

The idea is still interesting. I imagine using some dictionary based compression and crawled data to build a dictionary could get us somewhere.

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#5

Post by eriknstr »

fsiefken wrote: post #3

Neat but SMAZ has better performance :-) https://github.com/antirez/smaz/tree/master

Performance in terms of compression ratio or in terms of speed or in terms of both or in terms of something else like for example memory usage?

Is SMAZ encoded data URL safe?

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#7

Post by no_gravity »

Often urls can be most effectively shortened manually. I wish everybody who sends me something like this:

    https://www.booking.com/hotel/fr/hotelwestminster.html?label=gen173nr-1FCAEoggJCAlhYSDNiBW5vcmVmaDuIAQGYATHCAQN4MTHIAQzYAQHoAQH4AQKSAgF5qAID;sid=9b4fe19e9de68a3cb71714046bf9d64a;checkin=2017-05-12;checkout=2017-05-13;ucfs=1;highlighted_blocks=5190001_91458119_0_2_0;all_sr_blocks=5190001_91458119_0_2_0;room1=A;hpos=1;dest_type=city;dest_id=-1456928;srfid=49082c78468185e093631018c71495e7e11775c0X1;from=searchresults;highlight_room=#hotelTmpl
Would just take a look at the url and see that only this part is needed:

    https://www.booking.com/hotel/fr/hotelwestminster.html
Or that this:

    https://www.reddit.com/r/AskReddit/comments/68sgew/you_awake_one_morning_to_find_you_have_10_skill/"
Is just a sugarcoated version of this:

    https://www.reddit.com/r/AskReddit/comments/68sgew

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#8

Post by deepnet »

ageitgey wrote: post #2

The url for this post is 45 characters: https://news.ycombinator.com/item?id=14245119 If you encode it with this shortener, you get this 35 character string: mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA Assuming you were using this string as a key in a shortening service like this: https://short.url/mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA ... you'd end up with a url longer than the original url! So it's not technically a url shor…

Open standards for shortening URLs rather than private Hash Tables of random shortlinks is a great idea.

Being open source and predictable it would not be necessary to specify any particular shortening service so that part of the URL is extraneous.

Of course there would need to be some chars to refer to which particular open standard shortening encoder was used, still would be shorter than the oringal url for this post.

They could be reliably decoded, preventing the short link rot problem.

As the user could decode the URL themselves it also allows one to preview short link's URLs which can be reassuring and better security and prevent bait and switch shortlink destination changing tactics.

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#9

Post by usgroup »

zzzcpan wrote: post #4
ageitgey wrote: post #2

The url for this post is 45 characters: https://news.ycombinator.com/item?id=14245119 If you encode it with this shortener, you get this 35 character string: mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA Assuming you were using this string as a key in a shortening service like this: https://short.url/mNb:w9iIp7u8di:AKB2xrPUVYUFhfRUWHwA ... you'd end up with a url longer than the original url! So it's not technically a url shor…

The idea is still interesting. I imagine using some dictionary based compression and crawled data to build a dictionary could get us somewhere.

That's basically what a Huffman code is. Once you have a big list of examples, it's just a way to encode it to take advantage of frequency of occurrence.

Re: Show HN: Shortern URIs using Huffman Coding, not a database

#10

Post by Benjamin_Dobell »

no_gravity wrote: post #7

Often urls can be most effectively shortened manually. I wish everybody who sends me something like this: https://www.booking.com/hotel/fr/hotelwestminster.html?label=gen173nr-1FCAEoggJCAlhYSDNiBW5vcmVmaDuIAQGYATHCAQN4MTHIAQzYAQHoAQH4AQKSAgF5qAID;sid=9b4fe19e9de68a3cb71714046bf9d64a;checkin=2017-05-12;checkout=2017-05-13;ucfs=1;highlighted_blocks=5190001_91458119_0_2_0;all_sr_blocks=5190001_91458119_0_2_0;room1=A;hpo…

Oh, but distributing links with tracking tokens attached is a really great way to mess with sites that track users:

Well, we've had one user who really liked the new content. They viewed it 15,323 times... waaaaaait, damn it!

Post reply on HN