31 ms·
Show HN: Shortern URIs using Huffman Coding, not a database
- a3n 9y agohttp://fnord.com http://fnord.com => gR30sacA but http://gR30sacA http://gR30sacA !=> http://fnord.com http://fnord.com gR30sacA => http://fnord.com http://fnord.com There's nothing about gR30sacA all by itself that tells me that this is a shortened URI.
- 19eightyfour 9y agoI'm not sure I understand this one. 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 https://un.co as prefixes.
- 19eightyfour 9y agoIf you've got some ideas about how to improve it please submit an Issue or PR! Thanks for commenting!
- ageitgey 9y agoThe url for this post is 45 characters: https://news.ycombinator.com/item?id=14245119 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 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 :)
- zzzcpan 9y agoThe idea is still interesting. I imagine using some dictionary based compression and crawled data to build a dictionary could get us somewhere.
- usgroup 9y agoThat'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.
- ciphre 9y agoIf 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.
- grey-area 9y agoUnfortunately 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).
- 19eightyfour 9y agoI 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.
- deepnet 9y agoOpen 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.
- 19eightyfour 9y agoYes 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.
- matt_heimer 9y agoI think you missed the part about it being serverless. I think the idea is to integrate the logic into the client.
- aqme28 9y agoBut what's the benefit to turning a readable url into an unreadable one that's only about 3/4 the size?
- marcosdumay 9y agoObviously, it's sending network packets with 90% of padding instead of just 80%. Twitter has created some problems for the internet.
- 19eightyfour 9y agoYeah 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!
- fsiefken 9y agoNeat but SMAZ has better performance :-) https://github.com/antirez/smaz/tree/master https://github.com/antirez/smaz/tree/master
- eriknstr 9y agoPerformance 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?
- fsiefken 9y agoI meant compression ratio, but I overlooked the rather important fact that it's not URL safe
- 19eightyfour 9y agoOh great! I was looking for a compression algorithm for small strings. Thank you
- larrik 9y agoI don't really understand the motivation here, care to expand on that?
- jmkb 9y agoA 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.
- peeters 9y agoYou 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?
- mytherin 9y agoThe 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).
- peeters 9y agoHmm, 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).
- no_gravity 9y agoOften 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
- Benjamin_Dobell 9y agoOh, 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!
- dafrankenstein2 9y agonice entertainment
- a3n 9y agoI 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.
- paulryanrogers 9y agoDo you have any tools to automate that process?
- a3n 9y ago
- captn3m0 9y agoA 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.
- edent 9y agoRe (1) - that's linkmoji - http://www.xn--vi8hiv.ws/ http://www.xn--vi8hiv.ws/ So the URl for this discussion becomes http://linkmoji.co/⭕ http://linkmoji.co/⭕ or http://⭕..ws http://xn--k7i.ws
- 19eightyfour 9y agoI 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.
- stevekemp 9y agoI'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!
- 19eightyfour 9y agoThanks for the report. I'm sorry about that. I forgot to test on edge and ff before posting. Pretty stupid oversight actually. I'll open an issue. Issue: https://github.com/dosaygo-coder-0/urizip/issues/4 https://github.com/dosaygo-coder-0/urizip/issues/4
- 19eightyfour 9y agoOkay I think this is fixed now! https://github.com/dosaygo-coder-0/urizip/issues/4#issuecomment-298907333 https://github.com/dosaygo-coder-0/urizip/issues/4#issuecomm... Thanks for report. Please reopen if still happens, thanks! :)
- pmiller2 9y agoI came up with a variant of this idea in an interview once. It did not go over too well. :)
- asimpletune 9y agoWhat was the feedback the gave you?
- proksoup 9y agoI was asking for a function that converted a number (auto incremented id) to a string, such that all possible shortest urls would be iterated through. 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.
- pmiller2 9y agoHe just said "Yeah, ok, that could work, now do it with a database." :P
- 19eightyfour 9y agoIf you come up with some ideas how to improve the compression, please do submit an issue or PR! Thanks for commenting!
- anon1253 9y agoHere'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.
- 19eightyfour 9y agoOkay I will try this, thank you! I'll open an issue. Issue: https://github.com/dosaygo-coder-0/urizip/issues/3 https://github.com/dosaygo-coder-0/urizip/issues/3
- gumby 9y agoNice! By making it algorithmic and serverless the client could even expand it in situ when the mouse hovers over the link.
- 19eightyfour 9y agoTrue, that's a niceidea, I hadn't thought of that, thanks! If you have some more ideas for how to improve it I invite you to make an issue or PR!
- tghw 9y agoI 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 https://github.com/dosaygo-coder-0/urizip/commits/master
- zackify 9y agoIt isn't great.... it's just ok
- adm_hn 9y agohttps://github.com/dosaygo-coder-0/urizip/blob/master/build#L48 https://github.com/dosaygo-coder-0/urizip/blob/master/build#...
- 19eightyfour 9y ago102% yeah. 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: https://www.citylab.com/housing/2017/05/the-new-suburban-crisis/521709/?utm_source=SFTwitter Is 89% And http://www.saveur.com/chinatown-produce-prices Is 70% While https://www.gov.uk/search?q=Grants&filter_organisations%5B%5D=hm-treasury 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 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_coder.js https://github.com/dosaygo-coder-0/urizip/blob/master/radix_... [2] https://github.com/dosaygo-coder-0/urizip/issues/6 https://github.com/dosaygo-coder-0/urizip/issues/6
- 19eightyfour 9y ago
- Hansi 9y agoDoesn't support anchor links it seems: Encoder https://calendar.google.com/calendar/render#main_7 https://calendar.google.com/calendar/render#main_7 kF9DKUm9hMdDPUOCFu-QohzySQDx6pLN Decoder kF9DKUm9hMdDPUOCFu-QohzySQDx6pLN https://calendar.google.com/calendar/renddabD https://calendar.google.com/calendar/renddabD
- 19eightyfour 9y agoOh, that's a bug! Thank you. Fragment links ought to work. I'll open an issue. Issue: https://github.com/dosaygo-coder-0/urizip/issues/1 https://github.com/dosaygo-coder-0/urizip/issues/1
- 19eightyfour 9y agoOkay fixed now! https://github.com/dosaygo-coder-0/urizip/compare/4b5be28...master https://github.com/dosaygo-coder-0/urizip/compare/4b5be28...... Thanks for report :)
- grey-area 9y agoI'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 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.
- defen 9y agoThis 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?
- grey-area 9y agoSorry should't post jokes like this on the internet - I've moved 'more seriously' to the end to make it clearer.
- vanderZwan 9y agoIf 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/a47692a1f77bebc06c2518f321fa7efc 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 https://github.com/ReactTraining/react-router [1] https://github.com/pieroxy/lz-string https://github.com/pieroxy/lz-string
- 19eightyfour 9y agoInteresting. 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!
- ravenstine 9y agoOnly got it to work once and now the tab just crashes every time. Neat idea, though.
- 19eightyfour 9y agoYeah 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. Issue: https://github.com/dosaygo-coder-0/urizip/issues/2 https://github.com/dosaygo-coder-0/urizip/issues/2
- 19eightyfour 9y agoHello, 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.