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.
If it were to use a dictionary that defines a large subset of domain names and common strings found in URLs it could reduce the size somewhat more, but still seems too long to be viable. What might be more interesting is an Ethereum approach to URL shortening that is distributed amongst the Internet.
Unfortunately the longest urls, the ones you want to shorten the most, are the worst candidates for compression (with long query strings full of things like uuids).
I have an idea to identify the uuid and other identifier type parts and encode them up as numbers. The file radix_coder.js is working toward this. So we cover a few formats like guid base64 digits base36, to get a little bit more gain.
But my initial experiments suggest it's just a little gain. Digits go to 68%, base36 to 90%, and then we also have to add in the prefix to indicate we are switching encodings.
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.
Yes that is actually a rather faithful rendering of the types of ideas and possible future paths or use cases I had in mind. Thank you for saying that.
Yeah it's a challenge if we want to serve the code from a short domain name and prefix compressed strings with the domain name and on the client have the path section automatically decompressed and redirected.
Even a 1 letter host at a 2 letter tld like .co .in .ws .tk introduces 7 or 8 for the scheme, one for the slash, and 4 for the host. So a minimum of 14 to put it on a domain.
I haven't decided whether to put it on a domain or to use a scheme prefix like zurl: our something else.
The other possibility is this if not really about shortest, or Twitter, but more about, transport encoding and an efficient binary format, and something fun.
Thanks for commenting! If you have any ideas how to improve the compression or other things, please submit a PR!
A url shortener like tinyurl maintains a database of original urls linked to the shortened versions. Only they can translate between them, so 1) there's a risk the links will die if they die and 2) there are tracking implications.
This shortening scheme simply uses lossless data compression, like a zip. As long as the decompression algorithm is available, the link can be translated by anyone.
You can click on a tinyurl link. That's all that's required from the user.
I'm finding it really difficult to understand where this would be useful. Do we expect everyone to keep the handy decoder available and know to use it when they see random base64 encoded strings?
The end-game of the idea is that the decoder becomes embedded into browsers, so URLs can be shortened without requiring users to go through a third party service that tracks you. This method would be both faster than current URL shorteners (because it all happens client side - no extra round trip required) and much more suitable for archiving purposes (no single-point-of-failure that takes down millions of shortened URLs).
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 largely incompressible (past the reduced character set).
This URI has a lot of hex sections and numbers in it, and I'd like to point out this is still 85% of the Base64 encoded version of that URI, even tho its 114% of original.
I think we could get this size down below parity by encoding the numbers and hex sections.
Thanks for the comment! If you have some ideas how to improve the compression, I invite you to please submit an issue or PR, thank you very much.
I agree there ought to be a human readable prefix. Zurl is not bad!
I don't think compression can really compete with a hash table for key size. Because they're different beasts: compression finds the smallest representation for the entropy present in one text, hashing sort of finds the smallest distinguishable key for the entropy of the whole table space. Whatever that means! I'm no expert.
But competing can be a fun exercise to try get this to be smaller. And I've included versioning prefix bits so we know which version of the compression we're using.
So you can say it's sort of trying to compete with the hash table URL shorteners. It's not really, it's sort of trying to do something different as well. I just wanted something like a space efficient transport format for URLs that was going to just do better than base64 expanding them. And I liked that I send them a anywhere in an opaque block. That's pretty much all. Other motivations like we can avoid relying on an arbitrarily sized and growing database, swap that out for relying on a piece of distributable code, are sort of motivations, too.
But having the kind of fake-comparison Benchmark performance of URL shortner I think is also useful motivation to try to make this most space efficient as well. So I don't want to say that it's not competing because I think it's a use for motivation to try to get this shorter.
Yeah these ideas I've seen in this thread about blockchain a really good. But I just don't really know anything about blockchain. How would this work exactly? How much code would it take to do that? Could you do it from the browser?
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.
Then I pick select the second one from the top, let it load to be sure I
got a usable URL, then use that in my email. This is probably ideal, since anything more automated would probably get it wrong often enough that I'd go back to doing just this.
This would be great to achieve in code. I'm not confident of being able to do that now, sans machine learning or something like that. And I don't have any strong ideas about how to do the kind of semantic shortening that we as humans are mostly able to successfully do. But I think it would represent a kind of ideal. And if I was able to do what I'd like to include it in this code.
I agree Unicode emojis in URLs it's a really cool idea. I'm pretty sure that would still require database. So using a database is not the direction I would like to go in with this.
And if it was using compression to produce an encoding using unicode the first trouble is I'm not really sure how to do that encoding since Unicode is not straight up translating any sequence of bits into characters there are some restrictions and there's all kinds of rules I think and I don't really know how that works and I would like to keep it simple. And the second point is I want to keep it so it's very easy to transport which pretty much means we need to use base64 in my opinion.
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!
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.
This specific URL has a long hex component for the commit hash.
We might be able to get that size down by encoding the hex string at the end into numbers. I'm working toward this in radix_coder.js[1]. I'll open an issue[2]. Thanks!
In tests of strings not URIs I got 68% of original for digit strings, and 90% of original for base36 strings, after encoding as numbers then into base64.
More generally I see rates of 70% to 90% for URIs that have a mix of words and numbers. And more than 100% for strings with lots of identifiers.
I want to point out that yes, even tho it's longer than the URI by 2% , it is shorter than the Base64 encoding of the URI by 24%
For high entropy URIs with long identifier sections, this is common. While we may exceed the length of the original URI, we are almost always shorter than the Base64 version.
And this is just the first iteration of this algorithm. I think we can do better when we introduce some new ideas that people have suggested and are already in the works!
// 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.
I suppose the nice bit of this (original) proposal is that it works without any kind of connection or storage. You could use something like a blockchain to store this kind of thing, but you're still reliant on that existing in the future. Nice idea tho. You can also use hashing if you're the origin server (the idea behind content addressable stuff), and if you go away the data goes away anyway so it doesn't matter...
Proof of work. Hahaha. URLCoin. Cryptocurrency based on reversing hashed URLs to their Originals. Involves a lot of web crawling to verify as an added bonus. Proof of crawl.
This is so cool. I realize this might be some sort of a joke, even if the specification part is actually something you're working on! Stranger rfc's have happened right?
But I actually think something like a binary format for URLs that tries to be a space efficient as possible is pretty useful. At least it's something that I want. That's some of the idea that contributed to me trying to make this.
It was a little joke I'm afraid, because you can't reverse the hash, so you need to store it somewhere. Most of the existing link shorteners are a variant on this idea.
There are RFCs I think about content addressable storage if you're interested in that sort of thing, this is sort of like content addressable addresses if you see what I mean :), and someone else mentioned a distributed hash table, which is an interesting idea.
Yes, you totally understand this. This is a little bit like content addressable. :) Thank you for commenting, if you have any ideas about how to improve it I invite you to submit an issue or PR!
But I had the idea you might mean, it doesn't have a human readable prefix identifying what kind of encoding it is.
That's still something I'm considering. I haven't thought that much about it but some ideas that I've glanced at are : data:, urizip:, https://un.co as prefixes.
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:
Interesting. Thanks for sharing. It sounds like a highly technical project you're optimizing there and having some success. Keep up the good work! I might take a look.
edit: I looked at your gist and this is a totally great idea. I see what you're doing, converting it to make it more compressible. Very clever. If you have some ideas about how to improve my compression in this binary URI encoder, please do submit an issue or PR! Thanks for commenting!
Yeah there's a pretty big JavaScript load. And actually I did not test it on Firefox and Edge. I am sorry about that. Thanks for the report! I'll open an issue.
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.
86 comments
[ 0.24 ms ] story [ 160 ms ] threadhttps://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 :)
But my initial experiments suggest it's just a little gain. Digits go to 68%, base36 to 90%, and then we also have to add in the prefix to indicate we are switching encodings.
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.
Twitter has created some problems for the internet.
Even a 1 letter host at a 2 letter tld like .co .in .ws .tk introduces 7 or 8 for the scheme, one for the slash, and 4 for the host. So a minimum of 14 to put it on a domain.
I haven't decided whether to put it on a domain or to use a scheme prefix like zurl: our something else.
The other possibility is this if not really about shortest, or Twitter, but more about, transport encoding and an efficient binary format, and something fun.
Thanks for commenting! If you have any ideas how to improve the compression or other things, please submit a PR!
Is SMAZ encoded data URL safe?
This shortening scheme simply uses lossless data compression, like a zip. As long as the decompression algorithm is available, the link can be translated by anyone.
I'm finding it really difficult to understand where this would be useful. Do we expect everyone to keep the handy decoder available and know to use it when they see random base64 encoded strings?
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 largely incompressible (past the reduced character set).
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:
I think we could get this size down below parity by encoding the numbers and hex sections.
Thanks for the comment! If you have some ideas how to improve the compression, I invite you to please submit an issue or PR, thank you very much.
I don't think compression can really compete with a hash table for key size. Because they're different beasts: compression finds the smallest representation for the entropy present in one text, hashing sort of finds the smallest distinguishable key for the entropy of the whole table space. Whatever that means! I'm no expert.
But competing can be a fun exercise to try get this to be smaller. And I've included versioning prefix bits so we know which version of the compression we're using.
So you can say it's sort of trying to compete with the hash table URL shorteners. It's not really, it's sort of trying to do something different as well. I just wanted something like a space efficient transport format for URLs that was going to just do better than base64 expanding them. And I liked that I send them a anywhere in an opaque block. That's pretty much all. Other motivations like we can avoid relying on an arbitrarily sized and growing database, swap that out for relying on a piece of distributable code, are sort of motivations, too.
But having the kind of fake-comparison Benchmark performance of URL shortner I think is also useful motivation to try to make this most space efficient as well. So I don't want to say that it's not competing because I think it's a use for motivation to try to get this shorter.
[0] http://archiveteam.org/index.php?title=URLTeam#Dead_or_Broke...
Well, we've had one user who really liked the new content. They viewed it 15,323 times... waaaaaait, damn it!
So if Uppity shows me:
Then I pick select the second one from the top, let it load to be sure I got a usable URL, then use that in my email. This is probably ideal, since anything more automated would probably get it wrong often enough that I'd go back to doing just this.Firefox: Uppity https://addons.mozilla.org/en-US/firefox/addon/uppity/
Firefox: Navigate Up WE https://addons.mozilla.org/en-US/firefox/addon/navigate-up-w...
Chrome: Up https://chrome.google.com/webstore/detail/up/iohgglcbddjknne...
(And what is up with those chrome store URLs?)
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.
So the URl for this discussion becomes http://linkmoji.co/⭕ or http://xn--k7i.ws
And if it was using compression to produce an encoding using unicode the first trouble is I'm not really sure how to do that encoding since Unicode is not straight up translating any sequence of bits into characters there are some restrictions and there's all kinds of rules I think and I don't really know how that works and I would like to keep it simple. And the second point is I want to keep it so it's very easy to transport which pretty much means we need to use base64 in my opinion.
Issue: https://github.com/dosaygo-coder-0/urizip/issues/4
E.g. given character set a-z, 0: a 1: b 26: aa 27: ab
etc.
I probably had no idea what the interviewee was suggesting and tried and failed to explain my question any better.
Issue: https://github.com/dosaygo-coder-0/urizip/issues/3
Also "OK" isn't a great commit message for almost every commit:
https://github.com/dosaygo-coder-0/urizip/commits/master
This specific URL has a long hex component for the commit hash.
We might be able to get that size down by encoding the hex string at the end into numbers. I'm working toward this in radix_coder.js[1]. I'll open an issue[2]. Thanks!
In tests of strings not URIs I got 68% of original for digit strings, and 90% of original for base36 strings, after encoding as numbers then into base64.
More generally I see rates of 70% to 90% for URIs that have a mix of words and numbers. And more than 100% for strings with lots of identifiers.
Eg:
Is 89%And
Is 70%While
75%OK is not an informative commit message. Thanks for the prod. I'll open an issue.
Issue: https://github.com/dosaygo-coder-0/urizip/issues/5
And thanks for commenting! If you any ideas about how to improve the compression please submit a PR!
[1] https://github.com/dosaygo-coder-0/urizip/blob/master/radix_...
[2] https://github.com/dosaygo-coder-0/urizip/issues/6
For high entropy URIs with long identifier sections, this is common. While we may exceed the length of the original URI, we are almost always shorter than the Base64 version.
And this is just the first iteration of this algorithm. I think we can do better when we introduce some new ideas that people have suggested and are already in the works!
Thanks!
Encoder https://calendar.google.com/calendar/render#main_7 kF9DKUm9hMdDPUOCFu-QohzySQDx6pLN
Decoder kF9DKUm9hMdDPUOCFu-QohzySQDx6pLN https://calendar.google.com/calendar/renddabD
I'll open an issue.
Issue: https://github.com/dosaygo-coder-0/urizip/issues/1
Thanks for report :)
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):
https://play.golang.org/p/JNYzKhLHs8Here is a comparison of output:
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.e.g. how do you expect a client to turn "r0WGHoHvVmv4I51qW9FxCAIxX8NSfYlds1Pi-Of92ZI" into something useful?
[0]: https://github.com/juuso/BozoCrack
But I actually think something like a binary format for URLs that tries to be a space efficient as possible is pretty useful. At least it's something that I want. That's some of the idea that contributed to me trying to make this.
There are RFCs I think about content addressable storage if you're interested in that sort of thing, this is sort of like content addressable addresses if you see what I mean :), and someone else mentioned a distributed hash table, which is an interesting idea.
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.
But I had the idea you might mean, it doesn't have a human readable prefix identifying what kind of encoding it is.
That's still something I'm considering. I haven't thought that much about it but some ideas that I've glanced at are : data:, urizip:, https://un.co as prefixes.
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
edit: I looked at your gist and this is a totally great idea. I see what you're doing, converting it to make it more compressible. Very clever. If you have some ideas about how to improve my compression in this binary URI encoder, please do submit an issue or PR! Thanks for commenting!
Issue: https://github.com/dosaygo-coder-0/urizip/issues/2