算法与计算机科学bellard.org编辑精选
NNCP：用神经网络做无损数据压缩
NNCP: Lossless Data Compression with Neural Networks (2019)
2019 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
NNCP 是 Fabrice Bellard 开发的无损压缩工具：用神经网络（LSTM/Transformer）预测下一符号的概率分布，再配合算术编码，压缩率达到当时最先进水平，但速度极慢（每秒仅几 KB）。页面提供论文、程序与基准数据。
为什么经久不衰：它展示了'用更大的模型换更高压缩率'这一思路的极限，是今天大模型压缩讨论的先声，加上出自 Bellard 之手，至今仍是神经压缩的代表作。
HN 评论精选
解释原理：神经网络预测下一符号概率加算术编码，模型参数隐式更新、无需传输，因此网络可以任意大。
推荐看论文引言，它用极精炼的语言讲清了全部原理：每一时刻 t，编码器用神经网络根据之前所有符号计算下一符号的概率分布，实际符号用算术编码器以约 −log2(p) 比特编码，随后模型根据该符号更新；解码器对称工作，因此无需传输模型参数，编解码双方以完全相同的方式更新模型。对熟悉哈夫曼编码的人来说这就是算术编码，允许自适应地动态调整符号概率，只不过这里概率由神经网络建模。魔法在于网络参数是隐式定义的：不需要传输参数，所以网络可以要多大有多大。解码时网络从零开始用刚解码的数据持续训练，方式与编码时完全一致。
GistNoesis查看英文原文
I'd like to highlight the Introduction of nmcp.pdf which explains in a very compressed form how it works which encompass all the magic. "The lossless data compressor employs the traditional predictive approach: at each time t, the encoder uses the neural network model to compute the probability vector p of the next symbol values t knowing all the preceding symbols s0 up to st−1. The actual symbol value st is encoded using an arithmetic encoder with approximately −log2 ( pst ) bits. Then the model is updated knowing the symbol st. The decoder works symmetrically so there is no need to transmit the model parameters. It implies both encoder and decoder update their model identically. When no preprocessing is done, st represents the byte at position t. Hence there are Ns= 256 different symbol values from 0 to Ns−1." For those usually familiar with Huffman coding this is using an Arithmetic coding https://en.wikipedia.org/wiki/Arithmetic_coding It allows adaptive coding (i.e. changing the probabilities of symbols dynamically). Here these probabilities are modelled dynamically using a neural network. The magic is that the neural network parameters are defined implicitly : You don't need to transmit the neural network parameters, therefore you can use as big as you want neural network. During the decoding the from scratch network is continuously trained using the freshly decoded data, in the same way that it was during the encoding. The more data you compress, the more you train the internal neural network parameters, and the better the prediction for next character gets. You decode 20 bytes, you update the model with this new data, you decode 20 new bytes with the new model, you update the model,... , every 1000000 bytes you can even update your model multiple times using all currently available data to make the network converge faster. Of course this only works if everything is exactly deterministic, which Fabrice Bellard took great effort in guaranteeing, which is no small engineering feat.
压缩率极高但压缩解压都只有约 2KB/s，'压缩即服务'的创业设想因此行不通。
压缩速度约 2 KB/秒（论文给出的数字），比 xz 慢 1000 倍，而 xz 又比 gzip 慢 1000 倍。我一直琢磨压缩服务能否做成生意，按 NNCP 的压缩率配这个速度似乎可行——适合需要把数据压到极致、再分发给海量接收者的场景（比如游戏厂商分发补丁）。但那类服务曾败在解压太慢，而论文写着'NNCP v2 的解压速度与压缩速度相当'，所以我的绝妙（且偷懒的）创业点子泡汤了，不过这东西依然迷人。
eps查看英文原文
Compression speed is around 2 KB/sec. The figure is given in nncp_v2.1.pdf. This is 1000x slower than xz, which in turn is 1000x slower than gzip. I have always wondered if a compression service could be a viable commercial offering and with NNCP rates and its compression speed, it looks like it could! That's for cases when you need to really compress the heck out of something, e.g. prior to distributing a large static piece of data to a very large number of recipients. I think there was a service like this, used by AAA game developers for distributing patches, but it didn't take because it had a very slow decompression... and, now reading further through the paper, it looks like an issue with NNCP too - The NNCP v2 decompression speed is similar to its compression speed. So it's a no-go for my brilliant and lazy startup idea, but fascinating stuff nonetheless.
给出具体速度对比：NNCP 仅 2~3kB/s，处理 1TB 需十年以上，任何场景都不实用。
论文中的速度数据：gzip = 17 MB/s，xz = 1 MB/s，CMIX = 1.6 kB/s，NNCP = 2~3 kB/s（注意 NNCP 用的是 RTX 3090）。这不仅对热/温数据不可接受，对冷数据也不实际：压缩或解压 1 TB 要花 10~16 年。
esjeon查看英文原文
FYI, the compression speed numbers from the paper: gzip = 17 MB/s xz = 1 MB/s CMIX = 1.6 kB/s NNCP = 2~3 kB/s (Note that NNCP is using RTX 3090 here.) Not only this is unacceptable for hot/warm data, also it's still impractical for cold data. It takes 10~16 years to compress or decompress 1 TB data.
简单的 LSTM 压缩器以 10 倍速度达到与最先进算法相当的压缩率，印证 Bellard 的实力。
这正是 Fabrice Bellard 常被当作'10x 程序员'例子的原因：他这个相对简单的基于 LSTM 的神经网络压缩器，压缩率与更复杂的最先进算法相当，速度却快了 10 倍。
raphlinus查看英文原文
And this is why Fabrice Bellard is so often cited as an example of a 10x programmer: his relatively simple LSTM-based neural net compressor is 10x faster than one of the more complex state of the art algorithms while delivering comparable compression ratios.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选