下载

2下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 DBASE数据库全集dbase3压缩原理

DBASE数据库全集dbase3压缩原理.doc

DBASE数据库全集dbase3压缩原理

无为和为
2018-09-09 0人阅读 举报 0 0 暂无简介

简介:本文档为《DBASE数据库全集dbase3压缩原理doc》,可适用于IT/计算机领域

压缩原理 提起压缩大家都会想到WINZIP或者RAR之类的压缩软件实际上电脑压缩技术的内涵和应用绝不止于此。我们能够在在电脑上欣赏到精美的电影和悦耳的歌曲压缩技术立下了汗马功劳。在今天互联网的传送速度远不能满足我们需要的时候网络压缩技术也显得特别重要。正是有了它我们才得以实现网络视频音频的即时传送。压缩技术在不知不觉中改变着我们的生活。【预备知识】二进制与ASCII编码电脑里基本的存储单位是字节。ASCII码是一种以字节为单位对常用符号进行编码的方案因其合理性而较为流行。因为一个字节有位所以ASCII最多可对^=个字符进行编码其中前个称为标准ASCII码(二进制编号)后个称为扩展ASCII码(二进制编号)电脑里的汉字就是利用两个扩展ASCII码的组合来实现的(GB汉字编码方案)。比如汉字“王”占用的两个ASCII编码分别是和十六进制表示是CD和F化为二进制就是和。也就是说在电脑处理“王”这个汉字时电脑里的信息是“”这样一串数字。再如大写的英文字母“A”的ASCII编码是十六进制表示是在电脑里的信息实际上是“”。【缩位压缩】知道了上述原理后我们来介绍“缩位压缩”的原理。“缩位”就是缩减编码里没有必要使用的“位”。例如文件里一个汉字也没有也就是说内容中没有使用扩展ASCII码这样所有字符编码的第七位(最前面那一位)将都会是。利用这一点我们就可以缩掉这一位假设文件内容是ABCDEFGH。文件内容:ABCDEFGH二进制内容:压缩后文件内容:该内容中文状态下显示是乱码故无法写出二进制内容:这个压缩过程就是将原来顶头的全部去掉后每位重排这样原来占用个字节的文件就只占用了个字节。只要解压时再加上第七位的文件就可以恢复原样。这一压缩技术特别适用于对数字的压缩。因为~这十个阿拉件数字占用的ASCII编码是从其前四位全部都是“”。【直接压缩】直接压缩的原理最易理解因为有些时候文件里不可避免地存在着连续同样的字符比如在文件末尾加了一行“※※※※※※※※※※※※※※※※※※※※※※”符号。这样的话压缩时可以只记住这个符号以及重复的次数就可以迅速还原。【字典压缩】字典压缩是最重要的一种压缩技术也是应用最为广泛的一种压缩技术。该技术搜索文件中重复出现的字符串如“中华人民共和国”、“改革开放”等记录后(记录后的内容被称为“字典”)在正文中使用另一个简短的编码来代替它。想一想Windows系统里充满了多少的“Windows”和“Microsoft”这些字符你就会明白为什么这种压缩技术对Windows操作系统如此有效了。这种压缩方案对政治稿件和学术论文特别适用。字典压缩技术无论对文本文件还是可执行的代码文件都同样高效而且可以涵盖掉“直接压缩”技术。现在流行的ZIPARJ、RARAIN等压缩软件都采用了此项技术。但是此种技术中合适的字典长度很重要将字典设得太大或太小都严重影响压缩效果且进行压缩时速度相对较慢。多数压缩软件综合使用各项压缩技术。【矢量压缩】虽然字典压缩强劲有力但是对有些文件内容还是无能为力比如下面的内容:啊雹玻长触郸锭法这些看起来不成文的汉字实际上却有着内在的联系它们分别是GB编码中的第、、、、、、、区位的汉字。对于这种情况可以通过寻找它们之间的数学联系(如数列、方程等)进行记忆式的压缩。这种记忆式的压缩叫做矢量压缩是一种正在兴起的新压缩技术。矢量压缩有时可以带给我们意想不到的享受。很多人惊奇于FLASH能以如此小的体积带给我们如此丰富的信息就是因为FLASH里使用了矢量压缩技术。使用方程记忆一个点的运动轨迹远比记忆这个点的所有位置信息量要小得多的多。但另一面对于照片和录音这些资料现在的矢量化技术还做不到从中找到即高保真又有规律的方案来所以下一种压缩技术有了大显身手的空间。【有损压缩与VCD】VCD的产生要归功于联合图象专家组(JPEG)的努力。他们提出了一种全新的压缩技术标准也可以说是一种全新的压缩概念。这种概念催化了运动图象专家组(MPEG)标准的诞生及VCD工业化的实现。JPEG图象压缩技术以图象的每*个点的点阵做为一个处理单元在这个范围内如果全部都是某一色彩而只有极个别的其他色彩那么其他色彩将被忽略。这种压缩技术理论上的压缩比高达为:一个MB的文件现在只需MB就可以了?这实在很令人心动。为了进一步扩展压缩效果和提高该技术的适应范围JPEG做了灵活调整。允许用户自行设置处理单元的大小和忽略其他色彩的程度这也就是为什么JPEG图像有“质量”属性的原因。JPEG提出的这种“有损压缩”的概念使得该压缩技术有一定的局限性比如说JPEG不适合用来压缩工程图纸、医学影像等等资料。但其注重实用性的思路却大大启发了人们RealPlayer就是沿着这条路率先实现了网上视频的实时播放。而VCD中剥离了图象的声音则也渐渐形成了流行的MP音乐。(声音压缩的编码方案过于繁杂本文未予论述)【压缩文件缝隙】除这些压缩技术之外DOSWindows系统本身也留给了大家一个压缩的故事。在DOSWindows系统下磁盘存储空间被划分成一小块一小块地使用而不是象UNIX或者Novell那样在系统控制下所有文件都搅和在一起。这种开放式的磁盘文件使用格式虽然不安全(简直毫无安全可言)但是效率高易操作。这可能也是DOSWindows在家用和商用市场打败UNIX和Novell但在服务器领域却始终比不上他们的一个重要原因。因为每个分配块只能供一个文件使用所以即使文件(或文件的最后一块)只有一个字节也必须占用一个分配块。因为当时只留了两个字节来分配这种存储块(两个字节是位这种分配机制叫做FAT)所以不论分区有多么大最多都只能被分为^=个分配块。比如说一个GB的分区其分配块大小是KB当分区超过GB时分配块将不得不增长到KB。想一想如果一个字节的文件也要占掉你的KB时你能够不恼火?所以从WindowsOSR版本开始Microsoft推出了FAT解决方案。但是即使如此“文件缝隙”依然存在。Microsoft为了解决文件缝隙曾在DOS时代推出过DoubleSpace(DBLSPACE)后来改为DRVSPACE这东西在WindowsME上还依然存在。当时号称可以倍增硬盘容量令大家激动不已但是尝试过后高呼上当。原来Microsoft只不过是抄袭他人使用了“虚拟卷”技术而已该技术顶多可以省掉文件缝隙对于整盘只放了一个大文件的用户来说简直毫无用途。压缩文件缝隙现在有了一个较好的办法那就是把不常用的文件用WINZIP打成一个包尤其是大量的小文件和或在FAT的环境下使用这一方法可以节省你很多的磁盘空间。但是无论如何“文件缝隙”看来要在Windows系统中永远存在了。【越压越大?】文件会越压越大么?答案是:会的。因为压缩文件需要一个控制解压缩的文件头(文件格式及字典等)所以对已经“无以为压”的文件进行压缩时将徒增一个文件头文件当然会越来越大。另外虽然压缩后的文件更省空间更安全了(压缩文件可以加密而普通文本文件不行)但是如果一旦文件头损坏整个文件将无法解压。所以压缩文件的文件头是很重要的。这跟刚才讲过的FAT格式与UNIXNovell卷格式的差别比起来倒是有相形之处。但如果大家的ZIP文件损坏建议试一下DOS版的ZIP解压程序PKUNZIP也许还可以解救一部分。【可执行文件的压缩】不但文档文件和数据文件可以压缩可执行文件也可以进行压缩。致力于压缩技术的PKWAREInc公司在最早推出PKZIP软件时(大约是年的事情)就有三个主要程序分别是PKZIPEXE(压缩时用)、PKUNZIPEXE(解压缩时用)和PKLITEEXE(压缩可执行文件时用)。压缩可执行文件的过程很神奇文件名并不会被改变只是长度会变小。这样的压缩文件在执行时会在内存中自我释放然后重定位重加载再执行。因为电脑做起来是一瞬间的事情所以几乎感觉不到文件被压缩过。在软盘盛行的时代这个工具十分有用。Windows下的程序现在是越来越大了所以很多编程人都将自己的主程序进行压缩一方面也可以起到防盗版的作用著名的“RedAlert”就采取了这样的做法。随着互联网传播软件功能的发挥很多软件被打包为可执行程序点击后可以自行展开并进行安装这些也都是可执行文件的压缩的例子。【压缩技术的辨证分析】站在历史的观点上分析压缩技术是必然要灭亡的。我们现在看前年的DOS时代当时为了存储目的而实施的压缩工作现在已经淹没在海量的存储设备容量里。从理论上讲压缩毕竟浪费了我们的时间与精力如果存储空间足够我们没有需要压缩的理由。考察现在的压缩目的除了小部分是为了方便检索之外目前大量的压缩是为了适应互联网慢吞吞的传送速度。那么当网速能够满足我们随时将整个硬盘上的内容在网络上拖来拖去时我们还需要压缩吗?当光盘的容量足够大时我们还会容忍JPEG技术替我们扔掉那一两个色点吗?但是哲学指导我们事情总是在发展总是有其另一面的特性当容量不再成为压缩的目的时传送成了我们压缩的另一个目的。又有谁能够预料下一个压缩的目的会不会产生而又将是什么呢?我们使用计算机所做的事情大多都是对文件进行处理。每个文件都会占用一定的磁盘空间我们希望一些文件尤其是暂时不用但又比较重要不能删除的文件(如备份文件有点像鸡肋呀)尽可能少的占用磁盘空间。但是许多文件的存储格式是比较松散的这样就浪费了一些宝贵的计算机存储资源。这时我们可以借助压缩工具解决这个问题通过对原来的文件进行压缩处理使之用更少的磁盘空间保存起来当需要使用时再进行解压缩操作这样就大大节省了磁盘空间。当你要拷贝许多小文件时通过压缩处理可以提高执行效率。如果小文件很多操作系统要执行频繁的文件定位操作需要花费很多的时间。如果先把这些小文件压缩变成一个压缩文件后再拷贝时就很方便了。由于计算机处理的信息是以二进制数的形式表示的因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。为了有助于理解文件压缩请您在脑海里想象一幅蓝天白云的图片。对于成千上万单调重复的蓝色像点而言与其一个一个定义“蓝、蓝、蓝……”长长的一串颜色还不如告诉电脑:“从这个位置开始存储个蓝色像点”来得简洁而且还能大大节约存储空间。这是一个非常简单的图像压缩的例子。其实所有的计算机文件归根结底都是以“”和“”的形式存储的和蓝色像点一样只要通过合理的数学计算公式文件的体积都能够被大大压缩以达到“数据无损稠密”的效果。总的来说压缩可以分为有损和无损压缩两种。如果丢失个别的数据不会造成太大的影响这时忽略它们是个好主意这就是有损压缩。有损压缩广泛应用于动画、声音和图像文件中典型的代表就是影碟文件格式mpeg、音乐文件格式mp和图像文件格式jpg。但是更多情况下压缩数据必须准确无误人们便设计出了无损压缩格式比如常见的zip、rar等。压缩软件(compressionsoftware)自然就是利用压缩原理压缩数据的工具压缩后所生成的文件称为压缩包(archive)体积只有原来的几分之一甚至更小。当然压缩包已经是另一种文件格式了如果你想使用其中的数据首先得用压缩软件把数据还原这个过程称作解压缩。常见的压缩软件有winzip、winrar等。  MP的全称是MovingPictureExpertsGroupAudioLayerIII。简单的说MP就是一种音频压缩技术由于这种压缩方式的全称叫MPEGAudioLayer所以人们把它简称为MP。MP是利用MPEGAudioLayer的技术将音乐以:甚至:的压缩率压缩成容量较小的file换句话说能够在音质丢失很小的情况下把文件压缩到更小的程度。而且还非常好的保持了原来的音质。正是因为MP体积小音质高的特点使得MP格式几乎成为网上音乐的代名词。每分钟音乐的MP格式只有MB左右大小这样每首歌的大小只有兆字节。使用MP播放器对MP文件进行实时的解压缩(解码)这样高品质的MP音乐就播放出来了。MP格式什么是MP格式MP格式是什么文件如何保存成MP?:我的手机、MP随身听、MP音乐光盘等等里面存的都是MP格式的音乐文件MP格式相对WAV文件非常小基本上是M左右的文件播放时间是分钟而且音质还不错。(兆(M):计算机中数据存储单位M=KB)。你一定想了解mp是一种什么格式吧继续看:MP(MovingPictureExpertsGroupAudioLayerIII)简单的讲来是一种音频压缩技术由于这种压缩方式的全称叫MPEGAudioLayer所以人们把它简称为MP其文件扩展名是MP(还有MP读者可以大约明白过来)。MP是利用MPEGAudioLayer的技术将音乐以:甚至:的压缩率压缩成容量较小的文件。MP特点:MP能保证在音质丢失很小的情况下把文件压缩到最小的程度并较好的保持了原来的音质。正是因为MP体积小音质高的特点使得MP格式几乎成为网上音乐的代名词。每分钟音乐的MP格式只有MB左右大小这样每首歌的大小只有到M左右 压缩文件的基本原理是查找文件内的重复字节,并建立一个相同字节的"词典"文件,并用一个代码表示,比如在文件里有几处有一个相同的词"中华人民共和国"用一个代码表示并写入"词典"文件,这样就可以达到缩小文件的目的由于计算机处理的信息是以二进制数的形式表示的因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。为了有助于理解文件压缩请您在脑海里想象一幅蓝天白云的图片。对于成千上万单调重复的蓝色像点而言与其一个一个定义“蓝、蓝、蓝……”长长的一串颜色还不如告诉电脑:“从这个位置开始存储个蓝色像点”来得简洁而且还能大大节约存储空间。这是一个非常简单的图像压缩的例子。其实所有的计算机文件归根结底都是以“”和“”的形式存储的和蓝色像点一样只要通过合理的数学计算公式文件的体积都能够被大大压缩以达到“数据无损稠密”的效果。总的来说压缩可以分为有损和无损压缩两种。如果丢失个别的数据不会造成太大的影响这时忽略它们是个好主意这就是有损压缩。有损压缩广泛应用于动画、声音和图像文件中典型的代表就是影碟文件格式mpeg、音乐文件格式mp和图像文件格式jpg。但是更多情况下压缩数据必须准确无误人们便设计出了无损压缩格式比如常见的zip、rar等。压缩软件(compressionsoftware)自然就是利用压缩原理压缩数据的工具压缩后所生成的文件称为压缩包(archive)体积只有原来的几分之一甚至更小。当然压缩包已经是另一种文件格式了如果你想使用其中的数据首先得用压缩软件把数据还原这个过程称作解压缩。常见的压缩软件有winzip、winrar等。有两种形式的重复存在于计算机数据中zip就是对这两种重复进行了压缩。  一种是短语形式的重复即三个字节以上的重复对于这种重复zip用两个数字:重复位置距当前压缩位置的距离重复的长度来表示这个重复假设这两个数字各占一个字节于是数据便得到了压缩这很容易理解。  一个字节有共种可能的取值三个字节有**共一千六百多万种可能的情况更长的短语取值的可能情况以指数方式增长出现重复的概率似乎极低实则不然各种类型的数据都有出现重复的倾向一篇论文中为数不多的术语倾向于重复出现一篇小说人名和地名会重复出现一张上下渐变的背景图片水平方向上的像素会重复出现程序的源文件中语法关键字会重复出现(我们写程序时多少次前后copy、paste?)以几十K为单位的非压缩格式的数据中倾向于大量出现短语式的重复。经过上面提到的方式进行压缩后短语式重复的倾向被完全破坏所以在压缩的结果上进行第二次短语式压缩一般是没有效果的。  第二种重复为单字节的重复一个字节只有种可能的取值所以这种重复是必然的。其中某些字节出现次数可能较多另一些则较少在统计上有分布不均匀的倾向这是容易理解的比如一个ASCII文本文件中某些符号可能很少用到而字母和数字则使用较多各字母的使用频率也是不一样的据说字母e的使用概率最高许多图片呈现深色调或浅色调深色(或浅色)的像素使用较多(这里顺便提一下:png图片格式是一种无损压缩其核心算法就是zip算法它和zip格式的文件的主要区别在于:作为一种图片格式它在文件头处存放了图片的大小、使用的颜色数等信息)上面提到的短语式压缩的结果也有这种倾向:重复倾向于出现在离当前压缩位置较近的地方重复长度倾向于比较短(字节以内)。这样就有了压缩的可能:给种字节取值重新编码使出现较多的字节使用较短的编码出现较少的字节使用较长的编码这样一来变短的字节相对于变长的字节更多文件的总长度就会减少并且字节使用比例越不均匀压缩比例就越大。压缩原理下午:首先为了使用不定长的编码表示单个字符编码必须符合“前缀编码”的要求即较短的编码决不能是较长编码的前缀反过来说就是任何一个字符的编码都不是由另一个字符的编码加上若干位  或  组成否则解压缩程序将无法解码。看一下前缀编码的一个最简单的例子:  符号        编码   A              B              C              D              E           有了上面的码表你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了:  DABBDCEAAB要构造符合这一要求的二进制编码体系二叉树是最理想的选择。考察下面这棵二叉树:        根(root)         |                |      |             |     | |     |     a      | d     e       |            |     |     b     c要编码的字符总是出现在树叶上假定从根向树叶行走的过程中左转为右转为则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上任何一个字符的路径都不会是另一字符路径的前缀路径符合要求的前缀编码也就构造成功了:a    b    c    d    e  接下来来看编码式压缩的过程:为了简化问题假定一个文件中只出现了 abcd e五种字符它们的出现次数分别是a : 次b : 次c : 次d : 次e : 次如果用定长的编码方式为这四种字符编码: a :    b :    c :    d :    e : 那么整个文件的长度是 *  *  *  *  * = 用二叉树表示这四种编码(其中叶子节点上的数字是其使用次数非叶子节点上的数字是其左右孩子使用次数之和):          根           |            |        |           |    |     |    |          |   |   |   |    |   |              (如果某个节点只有一个子节点可以去掉这个子节点。)          根         |               |     |                |      |      |   |  |   |           现在的编码是: a :    b :    c :    d :    e :    仍然符合“前缀编码”的要求。第一步:如果发现下层节点的数字大于上层节点的数字就交换它们的位置并重新计算非叶子节点的值。先交换和由于个字节缩短了一位个字节增长了一位总文件缩短了位。           根            |              |        |           |      |     |     |               |     |   再交换和、和最终得到这样的树:           根            |              |        |              |      |    |     |                |   |     这时所有上层节点的数值都大于下层节点的数值似乎无法再进一步压缩了。但是我们把每一层的最小的两个节点结合起来常会发现仍有压缩余地。第二步:把每一层的最小的两个节点结合起来重新计算相关节点的值。在上面的树中第一、二、四三层都只有一或二个节点无法重新组合但第三层上有四个节点我们把最小的和结合起来并重新计算相关节点的值成为下面这棵树。           根            |              |         |            |      |    |     |                    |   |    然后再重复做第一步。这时第二层的小于第三层的于是可以互换有个字节增长了一位个字节缩短了一位文件总长度又缩短了位。然后重新计算相关节点的值。           根            |              |        |                         |    |                     |      |                     |   |           这时发现所有的上层节点都大于下层节点每一层上最小的两个节点被并在了一起也不可能再产生比同层其他节点更小的父节点了。这时整个文件的长度是 *  *  *  *  * = 这时可以看出编码式压缩的一个基本前提:各节点之间的值要相差比较悬殊以使某两个节点的和小于同层或下层的另一个节点这样交换节点才有利益。所以归根结底原始文件中的字节使用频率必须相差较大否则将没有两个节点的频率之和小于同层或下层其他节点的频率也就无法压缩。反之相差得越悬殊两个节点的频率之和比同层或下层节点的频率小得越多交换节点之后的利益也越大。在这个例子中经过上面两步不断重复得到了最优的二叉树但不能保证在所有情况下都能通过这两步的重复得到最优二叉树下面来看另一个例子:                         根                         |              +---------19--------+              |                   |      +------12------+            7      |              |  +---5---+      +---7---+  |       |      |       |+-2-+   +-3-+  +-3-+   +-4-+|   |   |   |  |   |   |   |1   1   1   2  1   2   2   2这个例子中所有上层节点都大于等于下层节点每一层最小的两个节点结合在了一起但仍然可以进一步优化:                         根                         |              +---------19--------+              |                   |      +------12------+            7      |              |  +---4---+      +---8---+  |       |      |       |+-2-+   +-2-+  +-4-+   +-4-+|   |   |   |  |   |   |   |1   1   1   1  2   2   2   2通过最低一层的第4第5个节点对换第3层的8大于第2层的7。到这里我们得出这样一个结论:一棵最优二叉编码树(所有上层节点都无法和下层节点交换)必须符合这样两个条件:1.所有上层节点都大于等于下层节点。2.某节点设其较大的子节点为m较小的子节点为nm下的任一层的所有节点都应大于等于n下的该层的所有节点。当符合这两个条件时任一层都无法产生更小的节点去和下层节点交换也无法产生更大的节点去和上层节点交换。上面的两个例子是比较简单的实际的文件中一个字节有种可能的取值所以二叉树的叶子节点多达个需要不断的调整树形最终的树形可能非常复杂有一种非常精巧的算法可以快速地建起一棵最优二叉树这种算法由DHuffman(戴·霍夫曼)提出下面我们先来介绍霍夫曼算法的步骤然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/12

DBASE数据库全集dbase3压缩原理

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利