我希望读者了解shannon的信息理论,该理论认为与概率为p(a)的事件a相关的信息内容是-log(p(a)).在外行术语中,如果您需要表示0-7范围内的数字,则至少需要-log(1/8)= log(8)(其中base为2),即3位.
假设有一个整数数组,范围从0到255.我不是将数组存储为8位数,而是先按升序对数组进行排序(保留一个备份).不是将每个数组元素编码为8位整数,而是输出它在排序数组中的位置.现在的问题是让解码器或接收器知道这个排序的数组.我将输出第一个(最小)整数值作为8位数,然后将增量添加到此数字并很快.首先是所有排序的数组,后跟元素的顺序,即位置值.
例如:原始阵列 - > 231,3,45,0,23,32,78
排序数组 - > 0,3,23,32,45,78,231
编码信息为0(排序数组的第一个元素为8位数)然后是3(这是0的增量)然后是20然后是9然后是13,然后是33然后是153.
在发送第一个数字和连续的增量后,我将发送订单,即因为这里有7个整数,我将需要一个三位数的订单,3(原始数组中的0的位置)然后1(3的位置)然后4 (位置23)然后5(位置32)然后2(位置45)然后6(位置78)然后0(位置231).
即位置值现在为3,1,4,5,2,6,0
分析看这个方案是否会压缩:
第一个数字 - > 8位(实际上可能需要更少的位,因为它是最小的)
接下来的6个数字 - > 5位(问题是我们可以编码0,3,20,9,13,5位但不是33和153,我们可能需要编码为31(最大为5位))
每个3位的7个位置 - > 21位
总计 - > 8 + 6*5 + 21 = 59.这超过了我们每次需要编码7个8位数所需要的56位,并且我们已经实现了扩展而不是压缩,并且我们的方案是有损的,因为我们还没有能够很好地代表一些大数字.
让我们为这个方案增加一些复杂性.
我将第一个0编码为8位数,紧接着是最后一个数字231的代码.然后我将发送代码为3,下一个增量超过0然后代码为153,减量超过231然后是20然后是33,9,13
即我发送了不同的顺序 - >而不是0,3,20,9,13,33,153我将发送为3,153,20,33,9,13
我得到的是你观察到的动态范围的连续减少,我们已经发送了0然后是231然后是3然后153这时值的范围减小了我的意思是下一个增加到3将是20不能大于第二个最后数字即78,数字20不能超过75(如果它去,那么第三个数字(3 + 76(比方说))将大于78明显违反我们的排序假设.
如果你已经理解了这个想法到现在为止我有一个进一步改进的方案,使用二进制搜索的想法来进一步减少动态范围,并把这个技术放在类固醇上.这是排序的数组
0,3,23,32,45,72,231
观察排序的数组有7个数字,中间的数字是32.所以现在我们将用32位编码32,然后我们将按顺序发送增量.即32之后的下一个数字将是3,其将被编码为29(即32-3),下一个将被编码为46(78-32),然后0编码为3(3-0)然后23编码为20 (23-3)然后45编码为33(78-45),然后最后一个231编码为153(231-78).
如果您现在看到我们可以根据具体情况决定每个号码使用多少位.
我们将排序的数组发送为32(范围0-255,即8位),29(范围0-32,所以6位),46(范围32-255,所以8位),3(范围0-3所以2位) ),20(范围3-32所以5位),33(范围32-78所以6位),153(范围78-255所以8位)
总共8 + 6 + 8 + 2 + 5 + 6 + 8 = 43这是无损的,超过我们初始估计的38(8位+ 5*6位)所以这增加了7个位置值,每个3位总共43 + 21 = 64超过56.我们的计划仍在扩大.
我们可以对21位的位置数做什么改进.因为每次我们发送位置信息,如果我们有7个位置要发送,位置数减少一个,那么位数是log(7)+ log(6)+ log(5)....这就是log(事实) (7))所有对数都是2的位.
观察我使用了公式log(a)+ log(b)= log(ab) …