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

61–70 of 87 posts

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

#61

Post by 19eightyfour »

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…

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.

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

#62

Post by 19eightyfour »

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 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.

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

#63

Post by 19eightyfour »

a3n wrote: post #37

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.

I'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 as prefixes.

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

#64

Post by 19eightyfour »

Hansi wrote: post #31

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

Oh, 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

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

#66

Post by 19eightyfour »

codefined wrote: post #17
larrik wrote: post #6

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

A _lot_ of shorteners die, with millions of links dying every day [0]. This method would be reproducible, so they'd never die. [0] http://archiveteam.org/index.php?title=URLTeam#Dead_or_Broke...

That's one motivation, definitely

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

#67

Post by 19eightyfour »

jmkb wrote: post #12
larrik wrote: post #6

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

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.

That's another motivation definitely.

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

#68

Post by 19eightyfour »

peeters wrote: post #16
mytherin wrote: post #15

Earlier quoted context omitted.

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…

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…

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.

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

#69

Post by 19eightyfour »

ravenstine wrote: post #55

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

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.

Issue: https://github.com/dosaygo-coder-0/urizip/issues/2

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

#70

Post by 19eightyfour »

mason55 wrote: post #19
jmkb wrote: post #12

Earlier quoted context omitted.

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.

Maybe we could store the translation of shortcode -> full URL on the blockchain

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?
Post reply on HN