Top all-time · #2720
marknelson.us
Personal blog · marknelson.usprogrammingdata
marknelson.us is a personal blog at marknelson.us about programming and data. Since 2007, 27 different Hacker News readers have linked it 30 times, most often “Data Compression with Arithmetic Coding”. No feed was found, so read it on the site itself.
Too few sampled comments (10) to say how often HN recommends it.?
Why HN links it
HN readers link Mark Nelson's blog for explanations of data compression, suffix trees and tries, and convex hull code. The Random Compression Challenge post is often cited on compressing random data.
Summarised by Claude from a sample of 10 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
Most-linked posts?
- Data Compression with Arithmetic Coding4 people · 4 mentions · first linked 2020-12-13
- Fast String Searching With Suffix Trees4 people · 4 mentions · first linked 2007-08-18
- An introduction to data compression with arithmetic coding3 people · 4 mentions · first linked 2011-04-04
- /2012/10/09/the-random-compression-challenge-turns-ten/2 people · 2 mentions · first linked 2014-04-22
- The Byzantine Generals Problem2 people · 2 mentions · first linked 2010-11-09
- Gawker Considered Stupid – Criminally Stupid2 people · 2 mentions · first linked 2011-02-07
What Hacker News says?
You should take a look at the almost 15 year old (and unsolved) "Random Compression Challenge" http://marknelson.us/2012/10/09/the-random-compression-chall...
Comment linking /2012/10/09/the-random-compression-challenge-turns-ten/
on ““Should you encrypt or compress first?””Submitted Data Compression with Arithmetic Coding as a story · 11 points
HN discussionI should clarify: There's still room for improvement in the speed of lossless compression/decompression operations, and that's where most improvements happen nowadays. But there's little room for improvement in compression ratio , because most modern algorithms produce outputs that are very close to random already. More background: https://marknelson.us/posts/2006/06/20/million-digit-challen...
Comment linking /posts/2006/06/20/million-digit-challenge.html
on “The Hitchhiker's Guide to Compression”Submitted Cruelty Redefined: Undergraduates vs. C++ on Linux as a story · 10 points
HN discussionFor anyone (like me) that isn't familiar with what this would be used for should have a look at the first link the Stack Overflow OP references: http://marknelson.us/1996/08/01/suffix-trees/
Comment linking /1996/08/01/suffix-trees/
on “Ukkonen's suffix tree algorithm explained in plain English”Submitted The Multicore Kerfuffle and a Dose of Reality as a story · 8 points
HN discussionpersonally I prefer this intro: http://marknelson.us/1996/08/01/suffix-trees/ or this one which is slightly harder: http://linux.thai.net/~thep/datrie/datrie.html
Comment linking /1996/08/01/suffix-trees/
on “Introduction to Tries”Submitted The Never-ending Awesomeness of Bash as a story · 7 points
HN discussionThere's a challenge posted online to compress a file of one million presumably random digits, and it's been running for 10+ years without anyone claiming the prize: http://marknelson.us/2012/10/09/the-random-compression-chall...
Comment linking /2012/10/09/the-random-compression-challenge-turns-ten/
on “The Quest for Randomness”Submitted Fast String Searching With Suffix Trees as a story · 6 points
HN discussionI once found a really great article explaining arithmetic encoding¹, and I felt I understood what was going on and managed to re-implement the article's example from MS-DOS-era C to modern Python, but when I tried to use it for anything else it didn't work and I wasn't smart enough to debug it. The claim that asymmetric numeral systems are simpler than arithmetic encoding is quite interesting, but as a working progr…
Comment linking /1991/02/01/arithmetic-coding-statistical-modeling-data-compression/
on “Asymmetric numeral systems (2014)”Submitted The Byzantine Generals Problem as a story · 5 points
HN discussionAnother good source for convex hull code (I was using this recently): http://marknelson.us/2007/08/22/convex/
Comment linking /2007/08/22/convex/
on “Building a Minimal Convex Hull”Submitted C++11 – Threading Made Easy as a story · 4 points
HN discussionIt is one of your primary duties to safeguard the best interest of your organization. Incontrovertibly, the best interest is not served by storing passwords in plaintext as this can result in grave harm to your organization. Accordingly, while I would not share any details with the outside world, I would advise you to strongly push the issue internally, from the position of an educator. Here are four articles that m…
Comment linking /2011/02/06/gawker-considered-stupid-criminally-stupid/
on “Banking site stores passwords in plaintext. Coworkers think it's no big deal.”Submitted Data Compression with Arithmetic Coding (2014) as a story · 3 points
HN discussionI'm fairly certain compressing random data is nonsensical. In fact there's a cash prize challenge for doing it that has been unmet for 20 years. https://marknelson.us/posts/2012/10/09/the-random-compressio... Not sure I can explain it properly myself but it think it's impossible by definition. Intuitively, if you could compress any random data then you should be able to compress 2 bits into 1, which is clearly impos…
Comment linking /posts/2012/10/09/the-random-compression-challenge-turns-ten.html
on “My adventures in random data compression”Submitted An introduction to data compression with arithmetic coding as a story · 3 points
HN discussionWas it maybe Dr Dobb's? Mark Nelson had an excellent series of articles about compression which opened up that world for me. I ended up working on compression for my PhD many years later. I can't find any archives for Dr Dobb's, but some articles are in his personal site, for example this one about arithmetic coding: https://marknelson.us/posts/1991/02/01/arithmetic-coding-sta...
Comment linking /posts/1991/02/01/arithmetic-coding-statistical-modeling-data-compression.html
on “Data Compression Drives the Internet. Here’s How It Works”Submitted The Byzantine Generals Problem - explained, and with code. as a story · 3 points
HN discussionSubmitted Gawker Considered Stupid – Criminally Stupid as a story · 3 points
HN discussionSubmitted Fast String Searching With Suffix Trees as a story · 3 points
HN discussionSubmitted Hash Functions for C++ Unordered Containers as a story · 2 points
HN discussion- ot · 2015-01-14
Submitted Highlights of ISO C++14 as a story · 2 points
HN discussion Submitted Data Compression with the Burrows-Wheeler Transform (1996) as a story · 2 points
HN discussionSubmitted Mark Nelson: Google Is a Scary Lifeline as a story · 2 points
HN discussionSubmitted Data Compression with Arithmetic Coding as a story · 1 points
HN discussionSubmitted Data Compression with Arithmetic Coding as a story · 1 points
HN discussionSubmitted Arithmetic Coding and Statistical Modeling = Data Compression (1991) as a story · 1 points
HN discussionSubmitted Arithmetic Coding + Statistical Modeling = Data Compression (1991) as a story · 1 points
HN discussion
