April 2020
Intermediate to advanced
210 pages
4h 47m
Chinese
Content preview from 数据压缩入门
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
26
｜
第
3
章
为什么这样做能节省空间
我们知道，对于包含
N
个整数，取值范围为
0~
N
–1
不重复的全排列，一共有
N
！（ 称
为
N
的阶乘）种可能。因此，第一个值出现后，我们就知道它不会再次出现。也就是
说，去掉第一个值后，就只剩下
(
N
–1)!
种可能；而去掉第二个值后，就只有
(
N
–2)!
种
可能了，以此类推。在某个点时，
LOG((
N
–
X
)!)
的下标值与
LOG(
N
!)
的下标值之差就
能变成整数。因此，可以用更少的二进制位来确定还剩下哪些可能性。
无论排列的大小多大，这种方法都适用。通过这种方法来编码，总能确保最终所产生
的数据流比通过熵计算的小。例如，如果你遇到的是包含从
0
到
65 535
这些整数的一
个排列，不管这些整数的顺序如何混乱，你总可以将这些数据压缩到原空间的
90%
。
实际上，只节省这么少的空间通常不值得我们这样去做。
解码工作则以相反的方式进行。最开始时，我们有一个空的数组，然后从数据流中读
出
LOG2
（
#
没有赋值的元素个数）个二进制位，这表示的是该元素的下标，通过下
标我们就知道它原来所代表的值。具体操作如下。
(1)
一共有
8
个没有赋值的元素，因此从输入流中读出前
3
个二进制位，这里是
101
。
(2)
二进制
101
对应的值为
5
，下标
5
对应的值为
5
，因此第一个数是
5
。现在，将
5
从数组中删除。
(3)
还有
7
个没有值的元素，我们需要读取接下来的
LOG2(7)
（即
3
）个二进制位，其
值为
110
，对应的十进制下标为
6
，因此第二个数是
7
。
(4)
接下来，请按照上面的方法解码剩下的元素。
3.5
信息论与数据压缩
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.