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

31–40 of 87 posts

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

#32

Post by peeters »

dafrankenstein2 wrote: post #21
peeters wrote: post #16

Earlier quoted context omitted.

Hmm, IMO it should be a valid URL with a protocol then. Something like zurl:Ma0t7asf...0a==. Something needs to identify how to handle it. I'm really not sure it's handling what URL shorteners are though. URL shorteners can take uber long URLs, like 150 characters, down to 10-20 characters. Huffman coding might be able to get that down to 120 characters, given how much of many long URLs is already random data that is…

an analysis can be done on that

You're right. I don't have the resources for a full analysis but I did "shorten" three Google Maps links (IMO a good candidate for link shortening).

The compression for the three ranged between 114% and 117% of the original. E.g.:

https://www.google.ca/maps/place/Rockefeller+Center/@40.7586...

Encoded:

    k:Yr5fL7YTHQz1AlBxKJrphUT0qAgf6ouSZ3Ze1yEQCNiTlmLclpycllFbllYTkxZcnJyY1hFTE0dUfkwV5SlgdREpEKLCUxjsWlLA6xpSJFMQx7EksQx6wsJCamsYViSIvoymS01Kch1NSlhIY2JOWYtyWWNESmNIbllYTkxZclpZRt

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

#33

Post by namanyayg »

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…

Which is actually just

  https://www.reddit.com/68sgew

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

#34

Post by grey-area »

I've got a suggestion for a better format called hurl, I'm working on the RFC as I write this.

It's constant length, doesn't require database storage, avoids collisions and compresses longer urls far better than the huffman coding method.

Here is the complete implementation (in go):

    func hurl(s string) string {
    	sum := sha256.Sum256([]byte(s))
    	return base64.RawURLEncoding.EncodeToString(sum[:])
    }
https://play.golang.org/p/JNYzKhLHs8

Here is a comparison of output:

    // For a short url *that doesn't really need shortened* huffman coding is better:
    // https://urizip-dot-populace-soho.appspot.com/
    // hurl:Y3h44nnzQH74AMEf-S2PAhgiP_CUH-4tZmkh78qXwdQ
    // huff:gtUrgo-kiv:hqL-ZG2:N1d-1j:bFFH:VAA

    // For longer urls, hurl wins hands down:
    // https://blogs.windows.com/devices/2017/05/02/introducing-surface-laptop-powered-by-windows-10-s/#xkgEy2SH0VVEG2dt.97
    // hurl:r0WGHoHvVmv4I51qW9FxCAIxX8NSfYlds1Pi-Of92ZI
    // huff:kNbXwsPYj:-GvsMIK65xSimsSIsqLFFqLEmqI4EUYj2GPtwpiHSjdyfABAm4yRudKbmciNxW3IomKbkRibopEQAx5BwcCRE1GdWJxcYGFTUhDTkxZgE

    // 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
    // hurl:-jf411UaJbZ1Pwl53dTLUxui31YB60GrwyX-n3RpkJU
    // huff 109% size
More seriously, since urls that need shortened are typically over 140 chars and contain random data, huffman coding isn't efficient enough. I do think some sort of predictable shortening algorithm would be much better than the current system of link databases that die though so this idea does have some merits but not sure trying to compress like this will work on the urls you need to shorten the most.

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

#35

Post by a3n »

Benjamin_Dobell wrote: post #10
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!

I habitually remove tracking and other non-essential cruft from shared URLs, for readability and for politeness to my correspondents. I don't think it's polite to associate their IP with my tracked activity.

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

#36

Post by defen »

grey-area wrote: post #34

I've got a suggestion for a better format called hurl, I'm working on the RFC as I write this. It's constant length , doesn't require database storage, avoids collisions and compresses longer urls far better than the huffman coding method. Here is the complete implementation (in go): func hurl(s string) string { sum := sha256.Sum256([]byte(s)) return base64.RawURLEncoding.EncodeToString(sum[:]) } https://play.golang.…

This might be a Poe's Law situation, but how am I supposed to reverse an arbitrary SHA256 hash without having that information stored somewhere?

e.g. how do you expect a client to turn "r0WGHoHvVmv4I51qW9FxCAIxX8NSfYlds1Pi-Of92ZI" into something useful?

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

#38

Post by grey-area »

defen wrote: post #36
grey-area wrote: post #34

I've got a suggestion for a better format called hurl, I'm working on the RFC as I write this. It's constant length , doesn't require database storage, avoids collisions and compresses longer urls far better than the huffman coding method. Here is the complete implementation (in go): func hurl(s string) string { sum := sha256.Sum256([]byte(s)) return base64.RawURLEncoding.EncodeToString(sum[:]) } https://play.golang.…

This might be a Poe's Law situation, but how am I supposed to reverse an arbitrary SHA256 hash without having that information stored somewhere? e.g. how do you expect a client to turn "r0WGHoHvVmv4I51qW9FxCAIxX8NSfYlds1Pi-Of92ZI" into something useful?

Sorry should't post jokes like this on the internet - I've moved 'more seriously' to the end to make it clearer.

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

#39

Post by tonmoy »

grey-area wrote: post #34

I've got a suggestion for a better format called hurl, I'm working on the RFC as I write this. It's constant length , doesn't require database storage, avoids collisions and compresses longer urls far better than the huffman coding method. Here is the complete implementation (in go): func hurl(s string) string { sum := sha256.Sum256([]byte(s)) return base64.RawURLEncoding.EncodeToString(sum[:]) } https://play.golang.…

How do you decode the shortened URL to get the original back??!!??

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

#40

Post by grey-area »

tonmoy wrote: post #39
grey-area wrote: post #34

I've got a suggestion for a better format called hurl, I'm working on the RFC as I write this. It's constant length , doesn't require database storage, avoids collisions and compresses longer urls far better than the huffman coding method. Here is the complete implementation (in go): func hurl(s string) string { sum := sha256.Sum256([]byte(s)) return base64.RawURLEncoding.EncodeToString(sum[:]) } https://play.golang.…

How do you decode the shortened URL to get the original back??!!??

I'm still working on that bit of the RFC.
Post reply on HN