哈希值的计算方法_gzip压缩比例

哈希值的计算方法_gzip压缩比例文章目录一.简介二.康托展开与逆康托展开1.思想2.实现3.代码4.逆康托展开三.二进制压缩1.思想2.实现3.应用4.bitset四.离散化1.思想2.实现3.代码五.哈希1.思想2.实现3.字

一.简介

时间复杂度和空间复杂度是衡量一段程序很重要的两个指标。利用映射思想可以大幅减少空间复杂度

有很多算法也是基于压缩空间的技巧实现的

二.康托展开与逆康托展开

1.思想

康托(Cantor)展开是一种全排列到数的映射,它的实质是通过排列的字典序建立的一个一一对应的双射

例:n=5时

排列 1 2 3 4 5 字典序是最小的,将其映射为0。

排列 1 2 3 5 4 映射为1。

排列 1 2 4 3 5 映射为2。

排列 1 2 4 5 3 映射为3。
……

性质:

康托展开是一种双射,即一个排列和一个数是一一对应的,因此也可以由一个数得到排列

意义:

用更小的空间储存排列

n=5的一个排列需要5个int型的整数来储存,康托展开后只需要1个int型整数即可存下

2.实现

例:[3 1 4 5 2]的康托展开

考虑第一位,若一个排列第一位为1或2,则其字典序必然小于[3 1 4 5 2],这样的排列有 2 ∗ 4 ! 2*4! 24!个(第一位取1或2,后面几位随便取所以是 4 ! 4! 4!

在第一位是3的情况下,考虑第二位,1已经是最小的了

在第一位是3、第二位是1的情况下,考虑第三位,1和3已经用过了,这一位还可以放2,所以还有 1 ∗ 2 ! 1*2! 12!个排列比原排列[3 1 4 5 2]小

同理,考虑第四位,1、3、4都已经用过了,这一位还可以放2,所以还有 1 ∗ 1 ! 1*1! 11!个排列比原排列小

第五位已经是最后一位不需要再考虑

综上,有 2 ∗ 4 ! + 0 ∗ 3 ! + 1 ∗ 2 ! + 1 ∗ 1 ! = 51 2*4!+0*3!+1*2!+1*1!=51 24!+03!+12!+11!=51个排列比原排列[3 1 4 5 2 ]小,即原排列是第52小的排列,将其映射为51

从上述推理中可以得到康托展开的一般计算方法

对于1~n的任意一个排列,其康托展开值为:

C a n t o r ( x ) = a 1 ∗ ( n − 1 ) ! + a 2 ∗ ( n − 2 ) ! + ⋅ ⋅ ⋅ + a n − 1 ∗ 1 ! Cantor(x)=a_1*(n-1)! +a_2*(n-2)!+\cdot\cdot\cdot+a_n-1*1! Cantor(x)=a1(n1)!+a2(n2)!++an11!

n-i表示第i位后面还有几个位

a i a_i ai表示在前几位已经确定的情况下,还有几个可以取的数比当前位的数更

而前几位已经确定意味着前几位没法选,可以取的数其实就在当前 a i a_i ai即后面n-i个数中比当前位的数小的个数,这么转化是为了方便代码的书写

3.代码

int Cantor(vector<int>p){ 
    int ret=0;//结果 int len=p.size(); for(int i=0;i<len;i++){ 
    int cnt=0; //统计有几个数小于p[i] for(int j=i+1;j<len;j++) if(p[j]<p[i]) cnt++; ret+=factor[len-i-1]*cnt; } return ret; } 

4.逆康托展开

仍以排列[3 1 4 5 2]为例,考虑如何由51这个数得到排列

回想一下51是怎么得到的:

C a n t o r ( x ) = a 1 ∗ ( n − 1 ) ! + a 2 ∗ ( n − 2 ) ! + ⋅ ⋅ ⋅ + a n − 1 ∗ 1 ! Cantor(x)=a_1*(n-1)! +a_2*(n-2)!+\cdot\cdot\cdot+a_n-1*1! Cantor(x)=a1(n1)!+a2(n2)!++an11!

逆康托展开:

①计算 51 / ( 5 − 1 ) ! 51/(5-1)! 51/(51)! 等于2余3,即得到 a 1 = 2 a_1=2 a1=2

②计算 3 / ( 5 − 2 ) ! 3/(5-2)! 3/(52)! 等于0余3,即得到 a 2 = 0 a_2=0 a2=0

③计算 3 / ( 5 − 3 ) ! 3/(5-3)! 3/(53)!等于1余1,即得到 a 3 = 1 a_3=1 a3=1

④计算 1 / ( 5 − 4 ) ! 1/(5-4)! 1/(54)!等于1余0,即得到 a 4 = 1 a_4=1 a4=1

回想 a i a_i ai的含义:有几个可以取的数比当前位上的数小

所以:

①第一位可以取的数{1,2,3,4,5}, a 1 = 2 a_1=2 a1=2,所以第一位上的数为3

②第二位上可以取的数{1,2,4,5}, a 2 = 0 a_2=0 a2=0,所以第二位上的数为1

③第三位上可以取的数{2,4,5}, a 3 = 1 a_3=1 a3=1,所以第三位上的数为4

④第四位上可以取的数{2,5}, a 4 = 1 a_4=1 a4=1,所以第四位上的数为5

⑤还剩下一个2没取,最后一位上的数为2

综上得到排列[3 1 4 5 2]

计算方法:

集合vis存放未被取过的数,从i=1开始不断对康托展开值除以 ( n − i ) ! (n-i)! (ni)!得到 a i a_i ai,从集合vis中找第 a i + 1 a_i+1 ai+1小的数,并将其从集合vis中移除

之所以可以这么做得到 a i a_i ai是因为可以保证 a i < = ( n − i ) a_i<=(n-i) ai<=(ni),所以 a i ∗ ( n − i ) ! < = ( n − i + 1 ) ! a_i*(n-i)!<=(n-i+1)! ai(ni)!<=(ni+1)!

对于 a 1 ∗ ( n − 1 ) ! + a 2 ∗ ( n − 2 ) ! + ⋅ ⋅ ⋅ + a n − 1 ∗ 1 ! a_1*(n-1)! +a_2*(n-2)!+\cdot\cdot\cdot+a_n-1*1! a1(n1)!+a2(n2)!++an11!,在除以 ( n − i ) ! (n-i)! (ni)!时,后面几项的值必然都小于 ( n − i ) ! (n-i)! (ni)!,所以做除法得到的结果必然是 ( n − i ) ! (n-i)! (ni)!前的系数

(原理类似进制转换的模n取余法)

代码:

void deCantor(vector<int>&ret,int n,int len){ 
    //ret存放排列 n为康托展开值 len表示排列的长度 bool vis[len+10]; //标记哪些点被取过 memset(vis,0,sizeof(vis)); for(int i=len-1;i>=0;i--){ 
    int temp=n/factor[i]; //当前位上的数是可以取的数中第temp+1小的 int cnt=0; for(int j=1;j<=len;j++){ 
    if(vis[j]) continue; if(cnt==temp) { 
    vis[j]=1; ret.push_back(j); break; } cnt++; } n%=factor[i]; } } 

三.二进制压缩

1.思想

二进制压缩是将n位的bool数组压缩成一个n位的二进制数

对于任意一个点,我们用0或1来表示它的状态。所以只需要一个二进制位的信息就可以存下该状态,那n个点理想情况下用n个二进制的位就可以存下其状态了

对于0/1的信息常用的方法是用bool型的变量来存,但是bool型变量在内存占一个字节,一个字节是8个位,因此浪费了很多空间。

所以我们可以选择用int型的数来存n个点的状态,并用位运算来实现对某一个点状态的读取

2.实现

(n>>k)&1可以取出第k位的信息:

>>表示右移,右移k位后的二进制最低位即原来的第k位,与1作且运算后即得到了该位的信息

n=(n|(1<<k))可以实现对第k位赋1:

<<表示左移,1左移k位后得到的数为第k位为1其它位都是0的二进制数,和n进行或运算后可以保证n的二进制下第k位为1

n=(n&(~(1<<k)))可以实现对第k位赋0:

~表示按位取反,1左移k位后按位取反得到的数第k位为0,其它位都是1,和n进行且运算后可以保证n的二进制下第k位为0

3.应用

二进制枚举就应用到了这一特点,不过目的并不是为了空间的压缩而是代码的简洁性

二进制压缩的思想是将一些点的状态(只能有两种状态)用一个数来表示,主要应用在状压dp和搜索时

4.bitset

当要表示的点的个数超过了int所能表示的最大二进制位数时(比如100个点的状态用int是存不下的),可以用int型的数组,但是stl库中也提供了一个更方便的容器——bitset

可以将bitset理解为一个多位的二进制数,每8位占用一个字节节,空间效率非常高,所占空间是相同位数下bool数组的 1 8 \frac{1}{8} 81

在这里插入图片描述
上图列出了位数为801时bitset和bool数组存储空间的比较,为什么bitset占字节数是104而不是101呢?因为其以32位(4个字节)为一个单位进行管理,也就是说创建位数为1~32的bitset占用字节数都是4

bitset可以被视为一个二进制数,其操作如下:

bitset<100>a; //创建格式 bitset<100>b; //100为位数 a[i]; //可以利用[]操作符对其某一位进行赋值或取值 ~,&,|,^,>>,<<,==,!= //支持二进制运算 a.count(); //count函数计算1的个数 a.any(); //若a中至少含有1个1返回True a.none(); //a中不含1则返回True 

四.离散化

1.思想

离散化其实也是一种哈希,将无穷大集合中的若干数映射为有限集合以便于统计。其实现方法又和康托展开很像,是排序后将一个数映射为其在有序序列中的下标

2.实现

①将所有可能出现的数放到数组d中

②排序并去重

③二分查找下标

即将一个很大的数映射为它在数组ret(即去重后的d数组)中的位置,显然这也是一一对应的双射,可以通过查找下标来找到值

3.代码

int cnt=0; void discrete(){ 
    sort(d,d+t); for(int i=0;i<t;i++) if(!i||d[i]!=d[i-1]) ret[cnt++]=d[i]; } int Query(int x){ 
    return lower_bound(ret,ret+cnt,x)-ret; } 

可以做下CF上的一道例题感受一下:传送门

我写的这道题的题解:传送门

五.哈希

1.思想

哈希是一种压缩映射,即将复杂的信息压缩到一个可以维护的小区间的映射,离散化就是比较简单的一种哈希。而ACM中常用的哈希利用的是取模运算,即将一个大值X转化为X%P(P是一个比较大的质数),并采用链地址法解决冲突,下面的介绍的就是这种哈希的做法。

2.实现

假设P=13,X=1,Y=14,可以发现X%P和Y%P是相同的,这就是所谓的冲突。采用链地址法可以解决冲突:

创建一个类似邻接表的结构,建立一个表头数组head,head数组中的每个元素存放的都是一个链表的头节点。head[i]存放的是%P后值等于i的所有结点,也就是上面的X=1和Y=14都存放在head[1]的链表中

这样做的目的在于减少查询,对于一份随机的数据,其%P后的值应该相对均匀的分布在0~P-1中,这样就大大减小了查询的代价。要查一个特定的值X,只需要去遍历head[X%P]的链表就可以找到X。

3.字符串哈希

字符串Hash可以将一个字符串映射为一个非负整数(数显然比字符串要好操作的多)

实现:

将字符串看成一个P进制数(一般为131或13331),取模数M(一般取 2 64 2^{64} 264),将26个字母各赋一个值(a=1、b=2、……z=26),由此便可由一个字符串得到一个非负整数而且冲突概率非常低

之所以取 2 64 2^{64} 264为模数是为了取消低效的模运算,因为这个数正好是unsigned long long 的上限,超过上限相当于自动取模

4.map

哈希本质上利用的是映射的思想,将信息映射到一个较小的可以维护的区间。stl库中的map也可以实现映射,从而达到哈希的目的。

今天的文章
哈希值的计算方法_gzip压缩比例分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/80144.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注