用C++写的压缩程序的原理是什么?

用C++写的压缩程序的原理是什么?,第1张

数据压缩目前主要有如下几大类算法:

1 统计编码,主要包括霍夫曼编码和算术编码,用途广泛

2 字典编码,主要包括lz77,lz78,lzw等,zip,rar等压缩软件基本用这类算法

3 变换编码,主要包含傅里叶变换、离散余弦变换(DCT)、小波变换等,图像、视频领域使用

4 预测编码,ADPCM等,语音、图像、视频领域使用

你问的压缩程序应该指的是字典编码,这种压缩编码就是扫描待压缩数据,每次都到前面去找,当前的字符串是否在前面出现过,如果出现过就用一个距离和长度来代替这个字符串,例如:

外星人遇到另一个外星人

那么最后这个 "外星人" 就保存为 (-8, 3),表示 "外星人"这个字符串在前面出现过,位置是前面的第8个字符,长度为3。

这种算法就是以色列人1977年提出的算法,实际上现在的压缩软件都是从这种算法改进来的,无论他怎样改,就没有脱离这个思路。

当然,目前实际上已经有了更好的算法,但是都无法推广,因为这些更好的算法都有专利。

中文WINDOWS95的DOS方式自己带有汉字系统,提供了拼音、双拼、国标、区位几种汉字输入方法,但是由于没有五笔字型输入法,使许多计算机用户深感不便。笔者通过摸索,找到了一种解决的办法,具体方法如下: 一、将中文版MS-DOS6.22的外部命令DICTMAN.EXE拷贝到WIN95的COMMAND目录下。 二、按以下格式创建五笔字型编码文件: C:\WINDOWS\COMMAND\〉TYPEWBX.DIC [Description] Name=五笔字型 MaxCodes=4 UsedCodes=abcdefghijklmnopqrstuvwxy WildChar=z Sort=0 [TEXT] 工a 式aa 恭恭敬敬aaaa …… 言yyyy 其中[TEXT]段内的每一行的左边为汉字或词组,右边为该汉字或词组的五笔字型编码。 三、运行DICTMAN.EXE程序,在菜单上选“编码词典”,在文件名处输入WBX.DIC按回车进行排序。在编码词典文件名处输入:WBX.TBL,选码元类型为16进制数字。选“确认”按钮生成WBX.TBL文件。 四、在WIN9/COMMAND目录下的PDOS95.BAT文件中加入一句:instdictwbx 重新运行PDOS95.BAT,就可以在WINDOWS95的中文DOS方式下使用五笔字型输入法了。 段洪杰 目前,MS-DOS6.22系统是PC机中用得最多的磁盘 *** 作系统,但是,人们通常只是使用了它的西文 *** 作界面,而很少有人使用它的中文界面。笔者认为,这其中原因之一可能是人们认为它的汉字输入法太古老。其实不然,它的输入法还是比较灵活的。MS-DOS6.22系统本身带有区位、双拼、全拼和国标四种汉字输入法,而且还提供了字典转换程序和输入法生成程序。这就是我们可以挂接其它输入法的根本所在。最近,笔者成功地将UCDOS汉字系统下的五笔字型输入法移植到了中文MS-DOS系统下。下面说明其形成过程: 一、安装MS-DOS6.22系统,启动该汉字系统,并且驻留一种汉字输入法。 在CONFIG.SYS文件中应有下列命令行: DEVICE=C:\PDOS\PBIOS.SYS 在C:\PDOS\PDOS.BAT文件中应有类似下面的内容:FONT16 HZVIO HZKBD INSTDICTPINYINA_F3 CTRLPAN 二、将UCDOS下的五笔字型编码字典反编译成文本方式的编码源文件: CD\UCDOS\DRV IMDMNGWB.IMDWB.DIC 笔者使用的是UCDOS6.0,所生成的WB.DIC文件长度接近400KB,这样大的文件可用MS-DOS提供的EDIT程序进行处理,删除该文件前面的文字说明部分,此时亦可加入您常用的字词。 三、将WB.DIC文件移到C:\PDOS目录下: MOVEC:\UCDOS\DRV\WB.DICC:\PDOS 四、生成五笔字型字典文件WBZX.TBL: CD\PDOS 启动DICTMAN,黑色光带位于“编码字典”处; 按Enter键,按Tab键,用光标键选择WB.DIC文件,按Enter键,光标将会位于“WB.TBL”处,按回车键; 启动一种汉字输入方式,在“方案名称”处输入“五笔型”,按回车键;在最大码长处输入4,按回车键; 在“快速输入”选项处按Space键,其前面的“[]”处将出现“X”,再按Tab键; 在“匹配查询”选项处按Space键,其前面的“[]”处将出现“X”; 在“匹配符”选项处输入Z,按两次Tab键; 再按回车键,系统便开始生成WB.TBL文件,这要花去几分钟的时间(可以去喝一小杯咖啡)。生成工作结束后,按左光标键将黑色光带移到“退出”处,按回车键,此程序结束,返回到DOS。在DOS命令行执行:INSTDICTWBA_F5即可按组合键启动五笔字型输入法。也可将此命令行加入到批命令文件PDOS.BAT中。 有兴趣的读者不妨一试。

#include<iostream>

using namespace std

int C(int r,int n)

{

int answer=1

int a=1,b=1

if(r!=0)

{

for(int i=ni>n-ri--)

{

a=a*i

}

for(int j=2j<=rj++)

b=b*j

answer=a/b

}

return answer

}//这个函数以及组合的详细见下面的解释A。

int main ()

{

int i,j

char ch[10]

int ch1[10]

cin>>ch//输出当前字符串Ch

int n=strlen(ch)//判断字符串长度

int sum=1

int start=1

for(i=1i<ni++)//计算 当前位数为N的字符串Ch的 前(n-1),(n-2)```1,个字符串组合的总数

sum+=C(i,26)

for(i=0i<ni++)//将输入!字符串!的每一位转化为数字以确定字符串中每一位 !字符! 在a,b,c...z中的第几位以及该!字符!之前有几个!字符!(注意字符和字符串)

ch1[i]=ch[i]-96

for(i=ni>=1i--)//确定Ch的位数后,对每一位进行排列组合的分析,假设 Ch = “bdfr”,则先判断第一位b之前的四位字符串总和 ,下面解释都是以第一次循环做解释

{

for(j=startj<ch1[n-i]j++)//计算第一位“b”之前的四位字符串总和,ch1[n-i](i此时为n)此时表示第四位字符“b”在字母表中的排位,第2,即j<2

{

sum+=C(i-1,26-j)//排列组合 见解释B

}

start=ch1[n-i]+1//计算第一位“b”之前的四位字符串总和之后,开始计算第二位“d”之前的四位字符串总和,此时第一位已经固定 ,第二位应该从(第一位+1)的字符开始考虑····所以start=ch1[n-i]+1

}

cout<<sum<<endl

system("pause")

return 0

}

解释A。题目的意思,假设我输出的是四位字符串,那么就是相当于从26个字母中选择4个插入四个并列空格子1 -2 -3 -4 ,因为这字符顺序是固定的,所以我只需求出26个字母中每4个不同的字母一共有多少种组合方式即为这个四位字符串总共有多少个,以此类推,当我输出的是N位字符串,那么我从M个任意取出N个不同的组合,公式C = M! / [ (M -N )! * N! ]

解释B。计算第一位“b”之前的四位字符串总和,第一位为b,那么b之前只有a,即求所有a为第一位的四位字符串,因为首位a固定,后面即是从25个字母中取出3个进行组合,C = 25!(22!*3!);

解释的很详细了 不懂追问,组合不明白的话建议看下概念,还有,之前的程序没问题,楼上说的aa 。ba,cb什么的都是不符合题意要求的字符串。程序中的C()函数已经排除了这些不合要求的字符串,所以只要输入的字符串符合要求,得出的结果一定是正确的


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/11733848.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-18
下一篇 2023-05-18

发表评论

登录后才能评论

评论列表(0条)

保存