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

I tried:

    https://github.com/dosaygo-coder-0/urizip/commit/cb2bfd2e04e8b814943e42a5bf87eeff31a77126

Got

    kl9oo67XTkQCETxduLJSW5iUfSNh5pW6iDuhqKmzprOoJCaUYmMo5M7kiMaYxrBRjTQsWzqDks9BlBQWEQKsrKImrQU

Which is longer.

Also "OK" isn't a great commit message for almost every commit:

https://github.com/dosaygo-coder-0/urizip/commits/master

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 :)

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

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.

A few ideas:

1. unicode URLs. Throw some emojis in there. A side project plan of mine has been to run an emoji link shortener service.

2. Another way would be to store it on the blockchain for a publicly verifiable lookup.

Hello, OP here. I went to bed with three points in 4 hours, thought this idea will never take here, and a few hours after I woke up I checked on my account. 54 points and so many comments. I'll try to make my way through them.

http://fnord.com => gR30sacA

but http://gR30sacA !=> http://fnord.com

gR30sacA => http://fnord.com

There's nothing about gR30sacA all by itself that tells me that this is a shortened URI.

If you use React with react-router[0] (or a comparable JS-based solution), you can just apply lz-string[1] to a stringified JS object and make the resulting string match a path. Then you need is some code to reverse the operation (lz-string -> JSON -> JS object). That's what I'm doing to create shareable state in an app I'm building for a research group.

Done naively, it will have the same problems others mentioned here: it barely shortens the URL. However, in the case of my specific app - a browser for data sets for single cell RNA sequencing - the state is largely dependent on the data set being viewed, and the data set is unchanging. What that means is that we can "externalise" the data being referred to, to pre-transform my JS object (which is an object tree) to nested arrays with integers (so a kind of "array tree") that use the data set as a look-up to reverse the operation. The latter is already a lot shorter when stringified, but also more compressible: the character set is limited to ten digits, commas and square brackets, and different values may be transformed into the same numbers, being distinguished by their position in the array tree.

To make this operation easier, I created a few helper functions to declare a "schema" that creates a recursive function for transforming the original JS object to said array of arrays, and vice-versa:

https://gist.github.com/JobLeonard/a47692a1f77bebc06c2518f32...

As you can see in the gist, that transformation shrunk a URL of 2466 characters down to a (admittedly still crazy) 638 characters.

I was thinking on putting it on NPM but it looked so specific in its applicability that I haven't bothered turning it into a proper package yet.

[0] https://github.com/ReactTraining/react-router

[1] https://github.com/pieroxy/lz-string

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

I don't really understand the motivation here, care to expand on that?

Doesn't support anchor links it seems:

Encoder https://calendar.google.com/calendar/render#main_7 kF9DKUm9hMdDPUOCFu-QohzySQDx6pLN

Decoder kF9DKUm9hMdDPUOCFu-QohzySQDx6pLN https://calendar.google.com/calendar/renddabD

Here's a silly trick we used for a similar problem: use zlib with a custom compression dictionary. Our application had tons of interlinks (think linked data) that we wanted to expose to the end user, but putting urls in urls is kinda ugly. So we ended up with our own custom compression dictionary and pushing them through zlib. Works like a charm.

I'm seeing errors:

    ReferenceError: urizip is not defined
       decoder.onsubmit()

Shame. I did consider using a DHT for storing shortened URLs once upon a time, to avoid the single point of failure. These days I guess there is already somebody trying to sell a solution using a blockchain!

I came up with a variant of this idea in an interview once. It did not go over too well. :)

Nice! By making it algorithmic and serverless the client could even expand it in situ when the mouse hovers over the link.

Only got it to work once and now the tab just crashes every time. Neat idea, though.