精华内容
下载资源
问答
  • ZW编码 (Encoding) 核心思想其实比较简单,就是把出现过字符串映射到记号上,这样就可能用较短编码来表示长字符串,实现压缩,例如对于字符串: ABABAB 可以看到子串AB在后面重复出现了,这样我们可以用一...

    LZW算法原理--Wikipedia相关介绍

    一个简单的例子
    ZW编码 (Encoding) 的核心思想其实比较简单,就是把出现过的字符串映射到记号上,这样就可能用较短的编码来表示长的字符串,实现压缩,例如对于字符串:

    ABABAB

    可以看到子串AB在后面重复出现了,这样我们可以用一个特殊记号表示AB,例如数字2,这样原来的字符串就可以表示为:

    AB22

    这里我们称2是字串AB的记号(Symbol)。那么A和B有没有记号来表示?当然有,例如我们规定数字0表示A,数字1表示B。实际上最后得到的压缩后的数据应该是一个记号流 (Symbol Stream) :

    0122

    这样我们就有一个记号和字符串的映射表,即字典 (Dictionary) :

    Symbol String
    0 A
    1 B
    2 C

    有了压缩后的编码0122,结合字典,就能够很轻松地解码 (Decoding) 原字符串ABABAB。

    当然在真正的LZW中A和B不会用数字0和1表示,而是它们的ASCII值。实际上LZW初始会有一个默认的字典,包含了所有256个8bit字符,单个字符的记号就是它自身,用数字表示就是ASCII值。在此基础上,编码过程中加入的新的记号的映射,从256开始,称为扩展表(Extended Dictionary)。在这个例子里是为了简单起见,只有两个基础字符,所以规定0表示A,1表示B,从记号2开始就是扩展项了。

    字典的生成

    这里有一个问题:为什么第一个AB不也用2表示?即表示为222,这样不又节省了一个记号?这个问题实际上引出的是LZW的一个核心思想,即压缩后的编码是自解释 (self-explaining) 的。什么意思?即字典是不会被写进压缩文件的,在解压缩的时候,一开始字典里除了默认的0->A和1->B之外并没有其它映射,2->AB是在解压缩的过程中一边加入的。这就要求压缩后的数据自己能告诉解码器,完整的字典,例如2->AB是如何生成的,在解码的过程中还原出编码时用的字典。

    用上面的例子来说明,我们可以想象ABABAB编码的过程:

    1. 遇到A,用0表示,编码为0。
    2. 遇到B,用1表示,编码为1。
    3. 发现了一个子串AB,添加映射2->AB到字典里。
    4. 后面又出现了AB子串,都用2来编码。

    以上过程只是一个概述,并非真正LZW编码过程,只是为了表示它的思想。可以看出最前面的A和B是用来生成表项2->AB的,所以它们必须被保留在压缩编码里,作为表项2->AB生成的“第一现场”。这样在解码0122的时候,解码器首先通过01直接解析出最前面A和B,并且生成表项2->AB,这样才能将后面出现的2都解析为AB。实际上解码器是自己还原出了编码时2->AB生成的过程。

    编码和解码都是从前往后步步推进的,同时生成字典,所以解码的过程也是一个不断还原编码字典的过程。解码器一边解码,向后推进,一边在之前已经解出的原始数据上重现编码的过程,构建出编码时用的字典。

    LZW算法详解

    下面给出完整的LZW编码和解码的过程,结合一个稍微复杂一点的例子,来说明LZW的原理,重点是理解解码中的每一步是如何对应和还原编码中的步骤,并恢复编码字典的。

    • 编码算法

    编码器从原字符串不断地读入新的字符,并试图将单个字符或字符串编码为记号 (Symbol)。这里我们维护两个变量,一个是P (Previous),表示手头已有的,还没有被编码的字符串,一个是C (current),表示当前新读进来的字符

    1.初始状态,字典里只有所有的默认项,例如0->a,1->b,2->c。此时P和C都是空的。
    2.读入新的字符C,与P合并形成字符串P+C。
    3.在字典里查找P+C,如果:
         - P+C在字典里,P=P+C。
          - P+C不在字典里,将P的记号输出;在字典中为P+C建立一个记号映射;更新P=C。
    4.返回步骤2重复,直至读完原字符串中所有字符。

    以上表示的是编码中间的一般过程,在收尾的时候有一些特殊的处理,即步骤2中,如果到达字符串尾部,没有新的C读入了,则将手头的P对应的记号输出,结束。

    编码过程的核心就在于第3步,我们需要理解P究竟是什么。P是当前维护的,可以被编码为记号的子串。注意P是可以被编码为记号,但还并未输出。新的字符C不断被读入并添加到P的尾部,只要P+C仍然能在字典里找到,就不断增长更新P=P+C,这样就能将一个尽可能长的字串P编码为一个记号,这就是压缩的实现。当新的P+C无法在字典里找到时,我们没有办法,输出已有的P的编码记号,并为新子串P+C建立字典表项。然后新的P从单字符C开始,重新增长,重复上述过程。

    这里用一个例子来说明编码的过程,之所以用小写的字符串是为了和P,C区分。

    ababcababac

    初始状态字典里有三个默认的映射:

    Symbol String
    0 a
    1 b
    2 c

    开始编码:

    Step P C P+C P+C in Dict ? Action Output
    1 - a a Yes 更新P=a -
    2 a b ab No 添加3->ab,更新P=b 0
    3 b a ba No 添加4->ba ,更新P=a 1
    4 a b ab Yes 更新P=ab -
    5 ab c abc No 添加5->abc,更新P=c 3
    6 c a ca No 添加6->ca,更新P=a 2
    7 a b ab Yes 更新P=ab -
    8 ab a aba No 添加7->aba,更新P=a 3
    9 a b ab Yes 更新P=ab -
    10 ab a aba Yes 更新P=aba -
    11 aba c abac No 添加8->abac,更新P=c 7
    12 c - - - - 2

    注意编码过程中的第3-4步,第7-8步以及8-10步,子串P发生了增长,直到新的P+C无法在字典中找到,则将当前的P输出,P则更新为单字符C,重新开始增长。

    输出的结果为0132372,完整的字典为:

    Symbol String
    0 a
    1 b
    2 c
    3 ab
    4 ba
    5 abc
    6 ca
    7 aba
    8 abac

    这里用一个图来展示原字符串是如何对应到压缩后的编码的:
    在这里插入图片描述

    • 解码算法

    解码的过程比编码复杂,其核心思想在于解码需要还原出编码时的用的字典。因此要理解解码的原理,必须分析它是如何对应编码的过程的。下面首先给出算法:

    解码器的输入是压缩后的数据,即记号流 (Symbol Stream)。类似于编码,我们仍然维护两个变量pW (previous word) 和cW (current word),后缀W的含义是word,实际上就是记号 (Symbol),一个记号就代表一个word,或者说子串。pW表示之前刚刚解码的记号;cW表示当前新读进来的记号。

    注意cW和pW都是记号,我们用Str(cW)和Str(pW)表示它们解码出来的原字符串。

    1. 初始状态,字典里只有所有的默认项,例如0->a,1->b,2->c。此时pW和cW都是空的。
    2. 读入第一个的符号cW,解码输出。注意第一个cW肯定是能直接解码的,而且一定是单个字符。
    3. 赋值pW=cW。
    4. 读入下一个符号cW。
    5. 在字典里查找cW,如果:
           a. cW在字典里:
               (1) 解码cW,即输出 Str(cW)。
               (2) 令P=Str(pW),C=Str(cW)的第一个字符
               (3) 在字典中为P+C添加新的记号映射。
          b. cW不在字典里:
               (1) 令P=Str(pW),C=Str(pW)的第一个字符
                (2) 在字典中为P+C添加新的记号映射,这个新的记号一定就是cW。
                (3) 输出P+C。
    6. 返回步骤3重复,直至读完所有记号。

    显然,最重要的是第5步,也是最难理解的。在这一步中解码器不断地在已经破译出来的数据上,模拟编码的过程,还原出字典。我们还是结合之前的例子来说明,我们需要从记号流

    0 1 3 2 3 7 2

    解码出:

    a b ab c ab aba c

    这里我用空格表示出了记号是如何依次对应解码出来的子串的,当然在解码开始时我们根本不知道这些,我们手里的字典只有默认项,即:

    Symbol String
    0 a
    1 b
    2 c

    解码开始:
    首先读取第一个记号cW=0,解码为a,输出,赋值pW=cW=0。然后开始循环,依此读取后面的记号:

    Step pW cW cW in Dict ? Action Output
    1 0 1 Yes P=a,C=b,P+C=ab,添加3->ab b
    2 1 3 Yes P=b,C=a,P+C=ba,添加4->ba ab
    3 3 2 Yes P=ab,C=c,P+C=abc,添加5->abc c

    好,先解码到这里,我们已经解出了前5个字符 a b ab c。一步一步走下来我们可以看出解码的思想。首先直接解码最前面的a和b,然后生成了3->ab这一映射,也就是说解码器利用前面已经解出的字符,如实还原了编码过程中字典的生成。这也是为什么第一个a和b必须保留下来,而不能直接用3来编码,因为解码器一开始根本不知道3表示ab。而第二个以及以后的ab就可以用记号3破译出来,因为此时我们已经建立了3->ab的关系。

    仔细观察添加新映射的过程,就可以看出它是如何还原编码过程的。解码步骤5.a中,P=Str(pW),C=Str(cW)的第一个字符,我们可以用下图来说明:

    在这里插入图片描述
    注意P+C构成的方式,取前一个符号pW,加上当前最新符号cW的第一个字符。这正好对应了编码过程中遇到P+C不在字典中的情况:将P编码为pW输出,并更新P=C,P从单字符C开始重新增长。

    到目前为止,我们只用到了解码步骤5.a的情况,即每次新读入的cW都能在字典里找到,只有这样我们才能直接解码cW输出,并拿到cW的第一个字符C,与P组成P+C。但实际上还有一种可能就是5.b中的cW不在字典里。为什么cW会不在字典里?回到例子,我们此时已经解出了5个字符,继续往下走:

    Step pW cW cW in Dict ? Action Output
    4 2 3 Yes P=c,C=a,P+C=ca,添加6->ca ab
    5 3 7 No P=ab,C=a,P+C=aba,添加7->aba aba
    6 7 2 Yes P=aba,C=c,P+C=abac,添加8->abac c

    好到此为止,后面的 ab aba c 也解码出来了,解码过程结束。这里最重要的就是Step-5,新读入一个cW为7,可7此时并不在字典里。当然我们事实上知道7最终应该对应aba,可是解码器应该如何反推出来?

    为什么解码进行到这一步7->aba还没有被编入字典?因为解码比编码有一步的延迟,实际上aba正是由当前的P=ab,和那个还未知的cw=7的第一个字符C组成的,所以cW映射的就是这个即将新加入的子串P+C,也因此cW的第一个字符就是pW的第一个字符a,cW就是aba。

    总结

    好了,LZW的编码和解码过程到此就讲解完毕了。其实它的思想本身是简单的,就是将原始数据中的子串用记号表示,类似于编一部字典。编码过程中如何切割子串,建立映射的方式,其实并不是唯一的,但是LZW算法的严格之处在于,它提供了一种方式,使得压缩后的编码能够唯一地反推出编码过程中建立的字典,从而不必将字典本身写入压缩文件。试想,如果字典也需要写入压缩文件,那它占据的体积本身就会很大,可能到最后起不到压缩的效果。


    LZW算法实现

    编码与解码流程图

    基于C/C++语言的实现

    /**
    *	作者:戴文治
    *	时间:2017年11月3日
    *	描述:LZW编码译码算法
    *	特点:该代码具有可移植性,可在Dev-C++、VC++6.0、VS2010等多种平台完美运行
    *		  该代码具有可重用性,运行后可对多个测试用例进行顺序测试而不受影响
    */
    #include<iostream>
    #include<cstring>
    #define N 1000
    using namespace std;
    class LZW{ //LZW算法类
    public:
    	char encodeStr[N];		//要编码的字符串
    	int decodeList[N];		//要译码的数组
    	int firstDictionaryNum; //先前词典的大小 
    	int length;				//当前词典的大小 
    	char dictionary[N][N];	//先前词典
    	
    	
    	LZW(){					//构造函数 
    		encodeStr[0] = '\0';
    		
    		for(int i=0;i<N;i++){
    			this->decodeList[i]=-INT_MAX;
    		}
    		
    		for(int i=0;i<N;i++){
    			this->dictionary[i][0] = '\0';
    		}
    		
    		firstDictionaryNum = 0;
    		length = 0;
    	}
    	
    	
    	bool initDictionary() 		//初始化先前词典
    	{	
    		if(encodeStr[0]=='\0'){			//若没有要编码的字符串,则不能生成先前词典 
    			return false;
    		}
    		dictionary[0][0] = encodeStr[0];//将要编码的字符串的第一个字符加入先前词典 
    		dictionary[0][1] = '\0';
    		length = 1;
    		int i,j; 
    		for(i=1;encodeStr[i]!='\0';i++){//将要编码的字符串中所有不同的字符加入先前词典 
    			for(j=0;dictionary[j][0]!='\0';j++){
    				if(dictionary[j][0]==encodeStr[i]){
    					break;
    				}
    			}
    			if(dictionary[j][0]=='\0'){
    				dictionary[j][0] = encodeStr[i];
    				dictionary[j][1] = '\0';
    				length++;
    			}
    		}
    		firstDictionaryNum = length;			//先前词典的大小
    		return true;
    	}
    	
    	
    	void Encode() 	 		 	//编码
    	{
    		for(int g=0;g<firstDictionaryNum;g++){	//先前词典中的初始编码没有输出编码,故设置为-1 
    			decodeList[g]=-1;
    		}
    		int num = firstDictionaryNum;
    		char *q,*p,*c;
    		q =  encodeStr;						  	//q为标志指针,用来确认位置的 
    		p =  encodeStr; 						//p指针作为字符串匹配的首字符 
    		c = p;									//通过不断移动c指针实现匹配 
    		while(p-q != strlen(encodeStr)){		//若还没匹配完所有字符,则循环 
    			int i,j;
    			int index=0;
    			for(i=0;dictionary[i][0]!='\0'&&c-q!=strlen(encodeStr);i++){//通过不断向后移动c指针实现匹配
    				char temp[N]; 
    				strncpy(temp,p,c-p+1);			//每添加一个匹配字符,则已匹配字符串temp增加一个字符 
    				temp[c-p+1]='\0';
    				if(strcmp(temp,dictionary[i])==0){//字符匹配成功 
    					c++;
    					index = i;
    				}
    			}
    			decodeList[num++]=index;			//遇到一个不匹配的字符或者已经没有字符可以匹配,则输出已匹配的字符串 
    			if(c-q!=strlen(encodeStr)){			//若到一个不匹配的字符且还有字符未匹配,则说明出现了新的词典字段,加入词典 
    				strncpy(dictionary[length],p,c-p+1);
    				dictionary[length][c-p+1]='\0';
    				length++;
    			}
    			p = c;								//匹配下一个时,p指向c的指向 
    		}
     
    	} 
    	
    	
    	void Decode()    			//译码 
    	{
    		for(int i=1;decodeList[i]!=-INT_MAX;i++){	//根据输入代码来循环 
    			if(decodeList[i]<=length){				//若出现输入代码在先前词典可以找到,则输出上一个输出的全部+当前输出的第一个 
    				strcpy(dictionary[length],dictionary[decodeList[i-1]-1]);
    				char temp[2];
    				strncpy(temp,dictionary[decodeList[i]-1],1);
    				temp[1]='\0';
    				strcat(dictionary[length],temp);
    			}
    			else{									//若出现输入代码在先前词典找不到,则输出上一个输出的全部+上一个输出的第一个 
    				strcpy(dictionary[length],dictionary[decodeList[i-1]-1]);
    				char temp[2];
    				strncpy(temp,dictionary[decodeList[i-1]-1],1);
    				temp[1]='\0';
    				strcat(dictionary[length],temp);
    			}
    			length++;
    		}
    	}	
    };
     
     
    int main(){
    	while(true){
    		cout<<"\n\t1.编码\t\t2.译码\t\t3.退出\n\n";
    		cout<<"请选择:";
    		char x;
    		cin>>x;
    		LZW lzw;
    		if(x=='1'){
    			cout<<"请输入要编码的字符串:"<<endl<<endl;
    			cin>>lzw.encodeStr;
    			if(lzw.initDictionary()==false){
    				cout<<"请先设置要编码的字符串encodeStr属性"<<endl;
    			}
    			lzw.Encode();	//开始编码
    			cout<<endl<<"编码过程为:"<<endl<<endl;
    			cout<<"\t索引号\t\t\t词典\t\t\t输出"<<endl;
    			for(int i=0;i<lzw.length;i++){
    				cout<<"\t"<<i+1<<"\t\t\t"<<lzw.dictionary[i]<<"\t\t\t";
    				if(i>=lzw.firstDictionaryNum){
    					cout<<lzw.decodeList[i]+1;
    				}
    				cout<<endl;
    			}
    			cout<<"\t-\t\t\t-\t\t\t"<<lzw.decodeList[lzw.length]+1<<endl<<endl<<endl;
    		} 
    		else if(x=='2'){
    			cout<<"请按顺序输入初始先前词典:(例:1 A)(输入0结束)"<<endl;
    			int tempNum;
    			cin>>tempNum;
    			int index = 1; 
    			while(tempNum!=0){
    				if(tempNum<0){
    					cout<<"输入序号错误,重新输入该行"<<endl<<endl;
    					getchar();//两个getchar()是删除掉该行已经输入的字符 
    					getchar();
    					cin>>tempNum;
    					continue;
    				}
    				if(tempNum!=index){
    					cout<<"请以递增顺序输入序号,重新输入该行"<<endl<<endl;
    					getchar();
    					getchar();
    					cin>>tempNum;
    					continue;
    				}
    				cin>>lzw.dictionary[tempNum-1];
    				cin>>tempNum;
    				index++; 
    			}
    			lzw.firstDictionaryNum = index-1;
    			lzw.length = lzw.firstDictionaryNum; 
    			
    			cout<<endl<<"请输入要译的编码(输入0结束):"<<endl<<endl;
    			int temp;
    			int j=0;
    			cin>>temp;
    			while(temp!=0){
    				if(temp<0){
    					cout<<"输入要译的编码错误,重新输入该编码"<<endl<<endl;
    					cin>>temp;
    					continue;
    				}
    				lzw.decodeList[j] = temp;
    				j++;
    				cin>>temp;
    			}
    			lzw.Decode();	//开始译码 
    			cout<<endl<<"译码过程为:"<<endl<<endl;
    			
    			cout<<"    输入代码\t\t索引号\t\t词典\t\t输出"<<endl;
    			for(int i=0;i<lzw.firstDictionaryNum;i++){
    				cout<<"      \t\t\t   "<<i+1<<"  \t\t "<<lzw.dictionary[i]<<endl;
    			}
    			cout<<"\t"<<lzw.decodeList[0]<<"\t\t   -\t\t -\t\t  "<<lzw.dictionary[lzw.decodeList[0]-1]<<endl;
    			for(int i=1;lzw.decodeList[i]!=-INT_MAX;i++){
    				cout<<"\t"<<lzw.decodeList[i]<<"\t\t   "<<i+3<<"  \t\t "<<lzw.dictionary[i+3-1]<<"\t\t  "<<lzw.dictionary[lzw.decodeList[i]-1]<<endl;
    			}
    			cout<<endl<<endl;
    		}
    		else if(x=='3'){
    			break;
    		} 
    		else{
    			cout<<"请输入正确的选择!"<<endl<<endl<<endl;
    		}
    	}
    	return 0;
    }
    
    

    使用上面的示例“ababcababac”进行测试:(注意: 初始字典设置为1–a 2–b 3–c)
    编码:
    在这里插入图片描述
    解码:
    在这里插入图片描述
    编程中的注意事项:

    注意指针的使用。

    要求熟练掌握字符串处理函数,对这些函数的功能和效果要有很明确的意识,否则会出现很多BUG。

    最后,这次实验我遇见许多细微的问题,最后还是通过DEBUG调试才发现的。事实证明Dev-C++和VC++非常地难以调试,很不直观!而用VS2010调试程序的话,它会有一个程序变量的窗口,每执行一条语句,它会显示出当前所有变量的值,还会把此次修改的变量用红色标注出来,在此推荐通过VS2010来调试程序。


    转载自博文:

    1. 原理
    2. 流程图(内附有编解码不同的C++实现,以及实现对文件压缩的思路)
    3. C/C++实现
    展开全文
  • 无损压缩算法.ppt

    2019-12-14 00:58:53
    字典编码 * 南京大学多媒体研究所 * LZW编码 时间 1977年LZ77LZ78 1984年LZW 应用giftif 压缩比1:1.51:1.3 原理 LZW压缩算法基本思想是建立一个编码表(转换表)韦尔奇称之为串表将输入字符串映射成定长码字输出...
  • 数据挖掘--PCA原理

    千次阅读 2018-08-06 22:06:13
    PCA的思想是将n维特征映射到k维上(k&lt;n),这k维是全新的正交特征。这k维特征称为主成分,是重新构造出来的k维特征,而不是简单地从n维特征中去除其余n-k维特征。 算法流程: 输入:n为样本集,...

    一、PCA原理:

    主成分分析(Principal Components Analysis,以下简称PCA)是最重要的降维方法之一。在数据压缩消除冗余和数据噪音消除等领域都有广泛的应用PCA的思想是将n维特征映射到k维上(k<n),这k维是全新的正交特征。这k维特征称为主成分,是重新构造出来的k维特征,而不是简单地从n维特征中去除其余n-k维特征

    算法流程:

    输入:n为样本集D=(x^{(1)}, x^{(2)},...,x^{(m)}) ,设为 X, 需要降维到  {n}'

    输出: 降维后的样本集 {D}'

    (1)先对所有的数据集进行中心化:x^{(i)} = x^{(i)} - \frac{1}{m}\sum\limits_{j=1}^{m} x^{(j)}

    (2)计算样本的协方差矩阵 : XX^{T}

    (3)对协方差矩阵进行求特征值和特征向量

    (4)取出{n}' 个最大的特征值对应的特征向量(w_1,w_2,...,w_{n'}), 将所有的特征向量标准化,组成新的矩阵 w

    (5)输出矩阵:Y= WX  即为降 维到  {n}' 维后的数据

    基于最大投影方差:

           假设m个n维数据(x^{(1)}, x^{(2)},...,x^{(m)}) 都已经对其进行中心化处理了, \sum\limits_{i=1}^{m}x^{(i)}=0, 经过投影变换后得到的新坐标系为(w_1,w_2,...,w_{n'}),其中w 是标准正交基,即||w||_2=1, w_i^Tw_j=0

            如果我们将数据从n维降到n'维,即丢弃新坐标系中的部分坐标,则新的坐标系为\{w_1,w_2,...,w_{n'}\},样本点x(i)在n'维坐标系中的投影为:z^{(i)} = (z_1^{(i)}, z_2^{(i)},...,z_{n'}^{(i)}).其中,z_j^{(i)} = w_j^Tx^{(i)}是x(i)在低维坐标系里第j维的坐标。

    对于任意一个样本x(i),在新的坐标系中的投影为W^Tx^{(i)}  ,在新坐标系中的投影方差为W^Tx^{(i)}x^{(i)T}W,要使所有的样本的投影方差和最大,也就是最大化\sum\limits_{i=1}^{m}W^Tx^{(i)}x^{(i)T}W,即:

                                                                           \underbrace{arg\;max}_{W}\;tr( W^TXX^TW) \;\;s.t. W^TW=I

     u1方向上的投影的绝对值之和最大(也可以说方差最大),就是将x与u1做内积。将u1标准化为单位向量。

    使用拉格朗日函数可以得到:

    J(W) = tr( W^TXX^TW) + \lambda(W^TW-I)

    对W求导有XX^TW+\lambda W=0, 整理下即为:

                                                          XX^TW=\left ( -\lambda \right )W

    对W 的求导可以把 W^{T}W=W^{T}E W, 然后再使用下面的公式进行求导,两边都有个2 ,可以约去。

    对于矩阵的求导可以参考:https://blog.csdn.net/xueyingxue001/article/details/51829718

    几个常用的向量求导公式:

     如果 y = xT·A·x的话,y对向量x求偏导的结果是

    如果这时A有时对称阵,则:

    由于协方差矩阵是对称的,因此其特征向量正交。最后一步的矩阵乘法就是将原始样本点分别往特征向量对应的轴上做投影。

    如果数据集是100 X 10,100行10列的,需要保留4个特征量,即选出4个最大的特征值,使原数据(100 X 10)* (10 X 4)=(100 X 4 ),10乘4 代表4个重要的特征向量聚合。

     


    参考:https://blog.csdn.net/zhongkelee/article/details/44064401此文章讲的比较详细

               http://www.cnblogs.com/pinard/p/6239403.html

     

     

     

     

     

    展开全文
  • ②编程语言(映射的桥梁,应用基础):语法、特性、函数库(API)、类库、内存原理等; ③算法+数据结构(基本单位实现与优化基础):Arithmetic(base:查找、递归、排列、移位等,high:压缩、神经...

    一、关于编程

    ①设计模式(问题分解、系统设计的顶层):紧密相关的是业务逻辑、软件工程知识、核心语言及相关API、组件等;

    ②编程语言(映射的桥梁,应用的基础):语法、特性、函数库(API)、类库、内存原理等;

    ③算法+数据结构(基本单位实现与优化的基础):Arithmetic(base:查找、递归、排列、移位等,high:压缩、神经网络、空间性原理、退火、差值搜索、加密解密等)  and Data Structure(stack、队列、树、图等等);

    ④操作系统(提升效率与深入的提升):文件格式、内存管理、CPU管理、DLL、权限管理、各种标准、接口、网络管理等;

    ⑤平台汇编(调试、优化的提升):紧密相关的是编程语言、编译原理、相关平台(硬件)API、ASM语法等。

     

    掌握了这些“基础”,需要具体应用再了解相关领域知识(如游戏引擎、物理学、图形学、数学、业务逻辑、数据库、IM等)。

    ●大话设计模式、高质量C/C++、the art of computer programming、Windows程序设计、80386及其编程、汇编语言艺术、深入理解计算机系统等。

     

    二、关于数学

    ①初等代数、几何(三角函数、常用变换、函数&几何&集合等基本概念&原理);

    ②数学分析;

    ③数学建模。

     

    同理于编程,掌握基础很重要,但从来没去思考、总结一些东西、法则,将其“烂熟于心”,如解题法所用到原理、逻辑,为何如此?切入的关键点是什么?这个关键点是正确的么?能举一反三么?题目体现什么知识点?解法严密么?有其它解法么?同样知识基础下为什么不能联想到?知识没掌握好?如何应用?有什么关联?数学的共通点?数学的起源?(数学是与计算相关问题的思维“逻辑”的集合么?)

    ●三角函数超、高中数学基础、解题方法、概率论超、数学分析等。

     

    三、关于绘图

    ①结构(轮廓)原理与精准度;

    ②色彩原理;

    ③常用技法及原理;

    ④拓展的智慧(机械原理、工业设计、形态学、自然、相术、玄学等)。

     

    临摹是必要的,但观察及思考是首要的,将“步骤”与“成品”分解,细节决定成败!抓住灵魂,要自成一派就要有必不可少的原理、风格掌握(为什么这样表达?有其它方式么?这些方式有共同点么?这种方式能统一起来么?)。

    ●张旺的水墨,阮佳的写实与印象,AG+的水彩(传统技法),母春航的线。

     

    四、关于英语

    ①从听说开始,基于句子与情境;

    ②语法,基于基础句子与单词;

    ③体会语境与意群;

    ④应用方是王道。

     

    暂时只能敷衍了事了。

    ●赖世雄的语法,新概念的笔记与课文(烂熟),Friends与ActionEnglish情境。

     

          在基本技巧“烂熟”之后,往往能够一个钟头就看完一篇人家看十天半月也解不透的文章。 —— 华罗庚

          真正打好“基础”,有两个必经的过程,即“由薄到厚”和“由厚到薄”的过程。“由薄到厚”是学习、接受的过程,“由厚到薄”是消化、提炼的过程。 —— 华罗庚

          双节棍的花式是比较好掌握的,找到“转换的关键点”就大可不理会其它得出花式了,但基础不易打牢,基础不好就容易甩棍。 —— ME

          十几岁的少年天才到处都有,三十多岁的优秀设计师凤毛麟角,掌握一种力量是容易的,学会恰当地使用这种力量却难得多,这是聪明与智慧的差别。 —— Alexandersu

          编程,同样讲究熟能生巧。 —— 云风

          边学边“用”,善于联系总结创新,不能拘泥一格。 —— ME

    展开全文
  • 利用Banach压缩映射原理,结合层次系统的思想,提出一种自适应泛函网络循环结构和代数算法,该循环结构是由多层基本泛函网络构成,每层用代数算法训练结构的泛函参数,从而实现对整体网络结构的逼近学习。...
  • 哈希值空间通常远小于输入空间,是一种压缩映射。由于不同输入可能会散列成相同输出,因此无法从哈希值来确定唯一输入值。哈希方法主要思想是根据结点关键码值来确定其存储地址,即以关键码值自...

    一、哈希算法基本原理

    (一)哈希算法的相关概念

    哈希(Hash),也称为散列,是一种重要的存储方式,也是一种常见的检索方法。它是把任意长度的输入通过哈希算法变换成固定长度的输出。其中该输出就是哈希值。哈希值的空间通常远小于输入的空间,是一种压缩映射。由于不同的输入可能会散列成相同的输出,因此无法从哈希值来确定唯一的输入值。

    哈希方法的主要思想是根据结点的关键码值来确定其存储地址,即以关键码值自变量,通过一定的函数关系,计算出对应的函数值,并将该值解释为结点的存储地址。在进行数据检索时,用同样的方法计算地址,然后在哈希表相应单元中找到需要的结点,即可完成数据的快速检索。

    总的来说,哈希算法虽然被称为算法,但实际上它更像是一种思想。它没有一个固定的公式,因此只要符合哈希思想的算法都可以被称为是哈希算法。

    (二)哈希函数的构建

    首先,需要假设处理值为整型关键码,保证可以建立一种关键码与正整数之间一一对应的关系,从而把该关键码的检索转化为对应正整数的检索。然后,需要假定哈希函数的值落在0M1之间。另外,在选取哈希函数的过程中需要满足一定的原则:(1)运算尽可能简单(2)函数的值域必须在哈希表的范围内(3)尽可能使得结点均匀分布,让不同的关键码具有不同的哈希值(4)需要考虑各种因素,如关键码长度、哈希表大小、关键码分布情况、记录的检索频率等。

    常用的哈希函数构建方法包括除留余数法、乘余取整法、平方取中法、数字分析法、基数转换法等。

    1 除留余数法

    除留余数法是将关键码除以M并取余数作为存储地址。通常选择哈希表长度作为M值。该方法几乎是最简单的哈希方法。

    2 乘余取整法

    乘余取整法是先将关键码乘以常数A(0),提取乘积小数部分,然后乘以整数n并对结果向下取整作为存储地址。

    3 平方取中法

    平方取中法是先求关键码的平方值,从而扩大相近数的差别,然后根据哈希表长度取中间几位数作为哈希值。由于一个乘积的中间几位数与乘数的每一数位都相关,因此由此产生的存储地址较为均匀。

    4 数字分析法

    数字分析法是取数据元素关键字中某些取值较均匀的数字位作为存储地址的方法。该方法分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合,当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。需要注意的是,该方法只适用于所有关键字已知的情况。

    5 基数转换法

    基数转换法是将关键码值看成另一种进制的数再转换成原来进制的数,然后选其中几位作为存储地址。

    除此之外还有很多方法,如直接定址法、折叠法、随机数法、旋转法等。单一的构建方法往往具有一定的局限性,因此为了获得良好的哈希函数,可以将几种方法联合起来使用,比如先进行基数转换,再进行平方或者乘余取整等。理论上来说,只要哈希均匀就可以随意拼凑。

    (三)哈希算法处理冲突的方法

    通过构建性能良好的哈希函数可以一定程度上减少冲突,但是无法完全避免冲突,因此解决冲突是哈希算法的另一个关键问题。解决冲突常用的方法有四种,分别为开放定址法、再哈希法、链地址法和建立公共溢出区。

    1 开放定址法

    开放定址法是当关键字的存储地址出现冲突时,以现有地址为地址,产生另一个哈希地址,如果还有冲突就继续生成,知道找到一个不冲突的哈希地址,将相应元素存入其中。

    2 再哈希法

    再哈希法是同时构建多个不同的哈希函数,当地址发生冲突时,再按照下一种哈希函数计算存储地址,知道冲突不再产生。这种方法不易产生聚集,但是增加了计算时间。

    3 链地址法

    链地址法是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,使得查找、插入和删除主要在同义词链中进行。该方法主要适用于经常进行插入和删除的情况。

    4 建立公共溢出区

    建立公共溢出区是将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素一律填入溢出表。

    二、哈希算法在Python中的实现(一)hash()函数

    Python中有内置的哈希函数hash(),可以返回一个对象的哈希值。需要注意的是,这里的对象指的是数字、字符串,而不能直接用于listsetdictionary等。示例代码及结果如下:

    773bfc20aac33f94b068e6a17f4626fe.png

    运行代码发现,相同字符串在同一次运行时的哈希值是相同的,但是不同次运行的哈希值不同。这是由于Python的字符串哈希算法有一个启动时随机生成的机制,因此存在随机化现象,即对同一个字符串输入,不同解释器进程得到的哈希结果可能不同。因此当需要做可重现可跨进程保持一致性的哈希时,需要用到hashlib模块。

    (2)hashlib模块

    hashlib提供了常见的摘要算法,如MD5,SHA1等等。MD5算法示例代码如下:

    import hashlib

    md5 = hashlib.md5()

    data = "明天你好"

    md5.update(data.encode('utf-8'))

    print(md5.hexdigest())

    输出结果:

    57acf16ede2a016646f0a74461602969.png
    展开全文

空空如也

空空如也

1 2 3 4 5 6
收藏数 111
精华内容 44
关键字:

压缩映射原理的思想