１引言
一个文件的倒排文档索引包含两部分，词汇表（ｄｉｃｔｉｏｎａｒｙｆｉｌｅ）和出现情况列表（ｐｏｓｔｉｎｇｓｆｉｌｅ）。词汇表将存储原文中每一个独立的词，它的位置，以及它在出现情况列表文件中的倒排表的长度，有时还有其他数据。任一给定词的倒排表是一个指向该词所在文档的一个向量。
任一个给定词的倒排表是通过这样的一系列｛＜ｄ１，ｆ１＞，＜ｄ２，ｆ２＞，…，＜ｄｎ，ｆｎ＞｝来表示的，＜ｄ，ｆ＞是指给定词在文件ｄ中出现了ｆ次。通常我们对文件进行顺序索引，并给每个文件一个单独的编号，倒排表也就根据这个编号来进行排序整理。
通常情况下倒排表分为两部分来存储，也就是根据这两部分对倒排表进行表示。其中一个表：倒排文件表，按单调递增的顺序来存储文件编号。另一个表：倒排频率表，是每个文件的出现频率表。还有一个附加表：词出现的倒排表，用于邻接查询。向量｛ｗ１，ｗ２，…，ｗｎ｝被保存，其中ｗ代表在文件集合中的该给定词的序号。
当字典以Ｂ－树存储时，需要一个磁盘寻址和一个磁盘读取来检索任一个给定词的位置长度对（即上面所说的＜ｄ，ｆ＞对）。检索倒排表需要多花费一个磁盘寻址和一个磁盘读取。
ＺｏｂｅｌａｎｄＭｏｆｆａｔ（１９９５）ａｎｄＷｉｌｌｉａｍｓａｎｄＺｏｂｅｌ认为对倒排文档的压缩会使查询的吞吐量增大。因为用来载入和解压一个压缩过的倒排表所需的时间比用来载入一个未经压缩的倒排表的时间短，因此将增大吞吐量。
迄今为止已经提出了许多压缩倒排表的技术。它们主要把焦点放在压缩比上。压缩比是用存储整个文件集的所有倒排表的数据项ｄ的平均比特数来衡量的。但是载入和解压的时间往往被大家忽略。
２几种相关压缩技术
倒排文件和词的倒排表是严格按照单调递增的顺序来排列的数列。压缩这种类型的数列没有压缩等差数列的效率高。对于数列｛４，７，９，１１，１５｝，差值为｛４，３，２，２，４｝。经常出现的词有更长的表，所以差值也尽可能的小，因此这种压缩也更高效。对于一个在每个文件中都出现的词，其数列为｛１，１，１，…｝，可被压缩得非常高效。因此此类表可以用某种合适的压缩方案来压缩。
（１）ＶａｒｉａｂｌｅＢｙｔｅＣｏｄｉｎｇ（可变字节编码）
现代计算机设计的目标是快速处理字节和字节的序列。将整数编码成一列字节，在解压时可以利用优化的硬件操作，但同时，我们必须牺牲大小。
整数ｘ可以表示成一个７位的字符序列；每个整数都被编码成８位的字节序列，用一个１来表示字节序列中的最后一位，其它位用０填充。例如，整数１３５，可被转化成序列：０００００００１，１００００１１１。对于一个３２位的整数序列，压缩比最好
对几种倒排文件压缩技术的研究与分析
王虎王潜平
（中国矿业大学计算机科学与技术学院，江苏徐州２２１００８）
Ｅ－ｍａｉｌ：ｗａｎｇｈｕ＠ｃｕｍｔ．ｅｄｕ．ｃｎ
摘要要提高文件检索系统的性能，需要对倒排文件压缩技术进行研究与对比，以使文件检索系统在最大压缩比和最快的解压速度间寻找均衡，以到达最大的吞吐量。对Ｇｏｌｏｍｂ，Ｅｌｉａｓｇａｍｍａ，Ｅｌｉａｓｄｅｌｔａ，ＶａｒｉａｂｌｅＢｙｔｅＥｎｃｏｄｉｎｇ和ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ五种压缩技术通过在Ｗｉｎｄｏｗｓ操作系统下对ｔｈｅＴＲＥＣＷａｌｌＳｔｒｅｅｔＪｏｕｒｎａｌｃｏｌｌｅｃｔｉｏｎ文件系统进行存取与压缩，从ＣＰＵ时钟周期角度来对比各个算法的压缩比、压缩与解压缩的时间和对文件的读取和查询所花费的时间，并对它们进行了一个综合的评测。
关键词倒排文件索引压缩文本搜索
文章编号１００２－８３３１－（２００６）０７－０１６９－０５文献标识码Ａ中图分类号ＴＰ３１１．５２
ＲｅｓｅａｒｃｈａｎｄＡｎａｌｙｓｉｓｏｎＦｉｖｅＩｎｖｅｒｔｅｄＦｉｌｅｓＣｏｍｐｒｅｓｓｉｏｎＴｅｃｈｉｑｕｅｓ
ＷａｎｇＨｕＷａｎｇＱｉａｎｐｉｎｇ
（ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｉｎｇａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｕｚｈｏｕ，Ｊｉａｎｇｓｕ２２１００８）Ａｂｓｔｒａｃｔ：ＴｏｉｍｐｒｏｖｅｔｈｅｔｈｒｏｕｇｈｐｕｔｏｆＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌＳｙｓｔｅｍ，ｗｅｎｅｅｄｔｏｒｅｓｅａｒｃｈｉｎｔｏｉｎｖｅｒｔｅｄｆｉｌｅｃｏｍｐｒｅｓｓｉｏｎｔｅｃｈｎｉｑｕｅｓ，ｔｏｇｅｔｔｈｅｓｔａｔｕｅｓｑｕｅｐｏｉｎｔｂｅｔｗｅｅｎｂｅｓｔｃｏｍｐｒｅｓｓｉｏｎｒａｔｉｏａｎｄｔｈｅｆａｓｔｅｓｔｄｅｃｏｍｐｒｅｓｓｉｏｎｔｉｍｅ．ＩｎＷｉｎｄｏｗｓｏｐｅｒａｔｉｏｎｓｙｓｔｅｍ，ｆｒｏｍｔｈｅｉｄｅａｏｆｔａｋｉｎｇｄｏｗｎｔｈｅｃｌｏｃｋｐｅｒｉｏｄｓｏｆＣＰＵ，ｔｈｒｏｕｇｈｓｅａｒｃｈｉｎｇｉｎｔｈｅＴＲＥＣＷａｌｌＳｔｒｅｅｔＪｏｕｒｎａｌｃｏｌｌｅｃｔｉｏｎｆｉｌｅｓｙｓｔｅｍ，ｆｉｖｅｃｏｍｐｒｅｓｓｉｏｎｔｅｃｈｎｉｑｕｅｓ，Ｇｏｌｏｍｂ，Ｅｌｉａｓｇａｍｍａ，Ｅｌｉａｓｄｅｌｔａ，ＶａｒｉａｂｌｅＢｙｔｅＥｎｃｏｄｉｎｇａｎｄＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇａｒｅｓｔｕｄｉｅｄ．Ｔｈｅｅｆｆｅｃｔｏｎｆｉｌｅｓｉｚｅ，ｆｉｌｅｓｅｅｋｔｉｍｅ，ａｎｄｆｉｌｅｒｅａｄｔｉｍｅａｒｅａｌｌｍｅａｓｕｒｅｄａｓｄｅｃｏｍｐｒｅｓｓｉｏｎｔｉｍｅ．Ｉｎｔｈｅｅｎｄａｎｉｎｔｅｇｒａｔｉｖｅｅｖａｌｕａｔｉｏｎｏｆｔｈｅｆｉｖｅｔｅｃｈｎｉｑｕｅｓｉｓｄｒａｗｎｏｕｔ．
Ｋｅｙｗｏｒｄｓ：ｉｎｖｅｒｔｅｄｆｉｌｅｓ，ｄｏｃｕｍｅｎｔｉｎｄｅｘｉｎｇ，ｃｏｍｐｒｅｓｓｉｏｎ，ｔｅｘｔｓｅａｒｃｈｉｎｇ
作者简介：王虎（１９７７－），男，硕士研究生，主要研究方向：网络数据库，信息检索。王潜平（１９６８－），男，教授，博士后，主要研究方向：人工智能与专家系统，ＣＳＣＷ。
１６９
计算机工程与应用２００６．０７
的情况是２５％，最差１２５％。当整数变大时，字符所占的空间也就变大。
（２）Ｅｌｉａｓｇａｍｍａｃｏｄｉｎｇ
倒排表可以非常长，而信息检索是以磁盘为界限的。从磁盘检索一个长的倒排表要比对它进行其他的操作花更多的时间。为了能增大从磁盘上检索的信息量，我们需要针对整型数的更有效的编码方法。
在伽马编码（Ｅｌｉａｓ，１９７５年）中，一个整型数被表示成两部分，头部是’ｌｏｇ２ｘ」个０，尾部是ｘ的二进制表示。这样整数９表示为：０００，１００１，因为ｌｏｇ２ｘ＝３，所以头部是０００，尾部是１００１。
伽马编码对于小一些的整数其编码效率是很高的，因为头部的长度短。当数变大，存储空间也变大了。
（３）Ｅｌｉａｓｄｅｌｔａｃｏｄｉｎｇ
在ｄｅｌｔａ编码中，整数ｘ用两部分来表示。１＋’ｌｏｇ２ｘ」用伽马编码，尾部用ｘ的二进制表示，最高位去掉。这样整数９可以表示为序列００，１００，００１。
ｄｅｌｔａ编码需要更多的位数来存储小一点的整数，但是却能更有效地存储大一些的整数。
当一个整数数列大部分的整数都比较小时，我们选择伽马编码而不是ｄｅｌｔａ编码，对于信息检索而言，当一个词出现的次数增大，那它在倒排表中的密度也增大。以倒排文件表为例，当密度增大，等差数列倾向为｛１，１，１，…｝，这种情况用伽马编码会更高效。
（４）Ｇｏｌｏｍｂｃｏｄｉｎｇ
在Ｇｏｌｏｍｂ编码中，整数ｘ用两部分来表示，商和余数。商的计算公式为ｑ＝’（ｘ－１）／ｋ」，余数的计算公式为ｒ＝ｘ－（ｑ＊ｋ）－１，在这里ｋ是Ｇｏｌｏｍｂ编码算法的基础。
如果ｒ＜ｐ，整数可以用’ｌｏｇ２ｋ」位来存储，否则它将需要「ｌｏｇ２ｋ/，在这里ｐ是分界点，计算方法为ｐ＝２’ｌｏｇ２ｋ」＋１－ｋ。
当ｒ＜ｐ时，Ｇｏｌｏｍｂ编码用ｑ个０，１个１，还有ｒ的二进制表示。否则表示方法为ｑ个０，１个１，以及ｒ＋ｐ的二进制表示。这样，整数９可用ｋ＝３编码为００，１，１１。
对于这套编码方案来说，ｋ的选择是至关重要的。如果选择得不好，编码后的整数会变得非常大，需要很长时间来解压。Ｗｉｔｔｅｎｅｔａｌ．（１９９４）认为假定倒排表中的整数符合Ｂｅｒｎｏｕｌｌｉ模型，则一列整数ａ的ｋ值用ｋ≈０．６９×平均值（ａ）来计算。
对这些实验的ｋ值的选择用的是Ｗｉｔｔｅｎ的近似法。每一个倒排表都用自己的ｋ来压缩。存储ｋ的花费未被计算并且也没有包含在结果中。
ＷｉｌｌｉａｍｓａｎｄＺｏｂｅｌ描述了对Ｇｏｌｏｍｂ编码实施优化的方法，并且认为常规的对整数的Ｇｏｌｏｍｂ编码比Ｅｌｉａｓｇａｍｍａ编码和Ｅｌｉａｓｄｅｌｔａ编码解码更快并且更加节省空间。
（５）ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ（二进制插入编码）
二进制插入编码（Ｍｏｆｆａｔ和Ｓｔｕｉｖｅｒ１９９６，２０００）用相邻数的信息来编码一个单调递增的整数数列。
如果在整数数列Ｘ１中，对于任一给定的整数ｘｉ，前一个数ｘｉ－１和后一个数ｘｉ＋１是已知的，那么通过减法运算我们可以得到存储ｘｉ所需的最大位数。因为ｘｉ的大小是在（ｘｉ－１＋１，ｘｉ＋１－１）的范围内，所需的最大位数为ｌｏｇ２（ｘｉ＋１－ｘｉ－１－２）。解码时需要ｘｉ－１和ｘｉ＋１的信息，所以数列Ｘ２是从原先的Ｘ１得到的，也就是说每个从表Ｘ１得到的整数都在Ｘ２中，这样也就可以递归地进行编码。
在这里测试的是中心最小二进制编码（Ｈｏｗａｒｄ和Ｖｉｔｔｅｒ，１９９３）。当压缩一个序列１…ｎ，需要「ｌｏｇ２ｎ/位，但是有２「ｌｏｇ２ｎ/－ｎ位的编码就被浪费掉了。这些被浪费掉的编码可以被缩短成一位并被使用（只要这些短的编码不是长编码的前缀）。这些最小化的二进制编码被置于编码范围的中心。在进一步的处理过程中，当数列的长度不断缩小，数列的密度也就增大了。
压缩倒排文件表和词出现的倒排表直接在倒排表上进行操作，不需要取差值。通过计算每个文件上的累加和来得到频率值，而由频率值可以产生一个单调递增的数列。
３测试方法
３．１测试压缩
由于在压缩ｔｈｅＴＲＥＣＷａｌｌＳｔｒｅｅｔＪｏｕｒｎａｌｃｏｌｌｅｃｔｉｏｎ时的适应性问题，这里我们测试了５种压缩技术，ＶａｒｉａｂｌｅＢｙｔｅＣｏｍｐｒｅｓｓｉｏｎ，Ｅｌｉａｓｇａｍｍａ，Ｅｌｉａｓｄｅｌｔａ，Ｇｏｌｏｍｂ和ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ。
首先创建ＷＳＪ的倒排文档索引并用它来测试每种算法。对每个词创建三个倒排表，倒排文件表，倒排频率表，以及词出现的倒排表。每个倒排表都被按序读入并压缩来判定存储所需的位数。然后进行解压缩，解压的时间也将被记录。对于每种压缩技术，以及其对应的每种倒排表，在磁盘中写入三项内容（序列中的整数，压缩后的大小，解压时间）。
我们用平均每个整数的位数来衡量压缩比，使用和奔腾ＣＰＵ的位数相同的３２位整数，用平均每个整数解压所用的时钟周期来衡量解压的平均时间，在这里我们采用奔腾的ＲＤＴＳＣ指令（此指令可以测算经过的时钟周期数）。实验是在Ｗｉｎｄｏｗｓ２０００ＤｅｌｌＯｐｔｉＰｌｅｘＧｘ２００上进行的，ＣＰＵ为ＰｅｎｔｉｕｍＩＩＩ９２７ＭＨｚ。
３．２测试磁盘
载入倒排表需要三种操作，磁盘搜索，磁盘读取和解压，因此磁盘的性能也需要测量。电脑配置如下：ＩＢＭＤｅｓｋｓｔａｒＤＴＬＡ－３０７０１５ＡＴＡ／ＩＤＥ驱动，１５ＧＢ的磁盘驱动器。
在Ｗｉｎｄｏｗｓ２０００下用ＲＤＴＳＣ指令对磁盘的平均搜索时间和平均读取时间进行测量。磁盘吞吐量是用时钟周期来衡量的，以此对所有需要测量的时间维持统一的测量单位。
为了判定搜索距离是如何影响搜索时间的，需要生成一个大的文件然后对其进行分割。在基于随机距离进行搜索时进行计时，然后以图表的形式来表示时间。为了判定磁盘读取的时间，我们从文件随机的地址读入随机数目的扇区。
只要搜索、读取和解压的时间已知，我们就可以对每一种压缩方法的吞吐量进行建模。对不同长度倒排表对应的性能用图表示，这样可以让我们选择最合适的算法。
３．３测试结果
３．３．１压缩比
图１表示了存储压缩过的倒排表所需的位数与倒排表的长度的对应关系（以整数为单位）。
结论：对于倒排文件表和倒排频率表，用ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ（二进制插入编码）来压缩可以得到最大的压缩比。对于词出现的倒排表，Ｇｏｌｏｍｂ比ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ（二进制插入编码）要稍胜一筹。
１７０
２００６．０７计算机工程与应用
当数据呈聚集时，ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ（二进制插入编码）的性能非常好。如果一个词仅出现在一个长的文件序列中，压缩的效果很一般。当这个词的出现频率增大，它出现的文件数目也增加，有可能得到一个长的邻接序列，所以压缩会更有效。如果一个词在所有的文件都出现，压缩后的大小甚至可以为０字节。在图１（ａ），ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ（二进制插入编码）的图示证明这种聚集效应。当频率在０．５和１．０之间
时，被压缩的序列趋向０字节。
（ａ）对倒排文件表的压缩
（ｂ）对倒排频率表的压缩
（ｃ）对词出现倒排表的压缩
图１对倒排表的压缩情况
３．３．２解压速度
图２表示的是以时钟周期为单位测量的解压时间和未被压缩的序列长度（以整数为测量单位）之间的对应关系。
在所有情况下，ＶａｒｉａｂｌｅＢｙｔｅＣｏｄｉｎｇ（可变字节编码）都超过了其他几种编码方法，主要原因是这种编码方法是以字节为基础的，而其他几种算法是以位为基础的。对于Ｅｌｉａｓ或者Ｇｏｌｏｍｂ的解压来说，从字节解压到位非常耗费时间。从图１和图２我们可以得出，Ｇｏｌｏｍｂ编码无论是在压缩后的大小还是解压速度，都超出了Ｅｌｉａｓｇａｍｍａ和Ｅｌｉａｓｄｅｌｔａ。
尽管ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ在压缩上是最有效率的，但是它在解压方面的效率却是最低的。这点是由算法本身的递归性决定的，而其他算法是被反复执行的。
３．３．３磁盘
为了测量每种压缩方法的吞吐量，我们有必要测量磁盘的吞吐量，包括读取的时间和搜索的时间。
（ａ）对倒排文件表的压缩
（ｂ）对倒排频率表的压缩
（ｃ）对词出现倒排表的压缩
图２对倒排表的解压情况
将数据从磁盘转移到内存需要两种操作。一个是将磁头移动到正确的位置（搜索）。一个是从磁盘中读入一连串的扇区并将其转移到内存（读取）。
硬盘的生产厂家通常会提供产品的精确的性能参数（ＩＢＭＣｏｒｐｏｒａｔｉｏｎ２０００）。但是，这些信息往往没有考虑产品的运行环境。在这里的搜索和读取时间运行于Ｗｉｎｄｏｗｓ２０００下的ＩＢＭＤｅｓｋｓｔａｒＤＴＬＡ－３０７０１５ＡＴＡ／ＩＤＥ硬盘。
３．３．４搜索的时间
为了判定磁盘搜索的时间，我们先创建一个１．４ＧＢ文件，然后将其分块，用不带缓冲的Ｉ／Ｏ设备将其打开，在整个文档中选取１０２４个采样点。每个采样点是在文件的随机位置选取的，仅读出采样点所在的这个扇区的内容。
用奔腾的ＲＤＴＳＣ指令可以获得从现在地址搜索到采样点，然后读取它所在一个扇区的时间。这些结果将在内存予以校对并在实验结束时写回磁盘。
图３表示了寻址距离和时间之间的关系。通过对样本点的分析，我们可以得到寻址时间随着距离的增大而增大，并且具有高度的可变性。相当一部分是可以预期的，因为磁头需要在磁盘上移动进行寻址，所以距离越大所需时间也就越多。
寻址的时间也具有可变性，因为文件中相邻的部分在磁盘上不一定是相邻的。从某一扇区再做一次寻址，磁头可能并不移动（如果两个扇区在同一个磁道上），也可能磁头会移动（如果两个扇区不在一个磁道上）。当磁头移动到要求的地址，在进行读取之前磁盘的某一部分需要转动。因为当磁头移动到目标的磁道时，不太可能它正好停在正确的扇区。
１７１
计算机工程与应用２００６．０７
２００６．０７计算机工程与应用
ｂｐｏ－ｂｉｔｓｐｅｒｏｃｃｕｒｒｅｎｃｅ，ｂｐｒ－ｂｉｔｓｐｅｒｒｅｃｏｒｄ，ｃｐｏ－ｃｙｃｌｅｓｐｅｒｏｃｃｕｒｒｅｎｃｅ，ｃｐｒ－ｃｙｃｌｅｓｐｅｒｒｅｃｏｒｄ．
ＢｙｔｅＤｅｌｔａＧａｍｍａＧｏｌｏｍｂＩｎｔｅｒｐｏｌａｔｉｖｅＵｎｉｔ
Ｍｅａｎ
Ｂｉｔｓ
Ｒｅｃｏｒｄｓ
９．３５
８．６７８．４８６．１５５．９４ｂｐｏＯｃｃｕｒｒｅｎｃｅ８．００
４．５２
３．４３２．６９１．５７ｂｐｒＷｏｒｄｓ１３．９９１５．１５
１７．９８１２．３１１２．１１ｂｐｏＣｙｃｌｅｓＲｅｃｏｒｄｓ１１．４７１１２．５５１０１．０９９９．０９１４９．６２ｃｐｏＯｃｃｕｒｒｅｎｃｅｓ９．２４
６４．５２４４．９１４２．５２１０５．７１ｃｐｒＷｏｒｄｓ２１．８５１７．４８１８１．９９１８８．６２２０９．７８ｃｐｏ
Ｒｅｌａｔｉｖｅｍｅａｎ
Ｂｉｔｓ
Ｒｅｃｏｒｄｓ
１．５７１．４６１．４３１．０４１．００Ｏｃｃｕｒｒｅｎｃｅ５．０８
２．８７２．１８１．７１１．００Ｗｏｒｄｓ１．１６１．２５１．４８１．０２１．００ＣｙｃｌｅｓＲｅｃｏｒｄｓ０．０８０．７５０．６８０．６６１．００Ｏｃｃｕｒｒｅｎｃｅｓ０．０９
０．６１０．４２０．４０１．００Ｗｏｒｄｓ
０．１０
０．８１
０．８７
０．９０
１．００
实验数据表明平均搜索时间是７９５４０５４时钟周期，或者
８．６ｍｓ。这个数据超过了厂家说明中的８．５ｍｓ。平均寻址时间比
厂家提供的数据要大，据我们分析是因为操作系统的开销。
根据示例文件的平均寻址时间，我们可以计算出一个不同大小的文件的平均寻址时间。
图３
当距离增加时的寻址和读取时间
符合图３中采样点的公式是：
Ｔ１＝１．０２Ｂ＋Ｃ
（１）
Ｔ１是以时钟周期为单位的时间，Ｂ是寻址的扇区数目，Ｃ
是常量，值为７０３９００７，寻址的时间都以时钟周期为单位。两个文件的大小的比值是：
Ｒ＝Ｓ２／Ｓ１
（２）
Ｓ１是示例文件的大小，Ｓ２是新文件的大小。
则新文件的平均寻址时间为：
Ｔ２＝（Ｔ１－Ｃ）Ｒ＋Ｃ
（３）Ｔ２是计算出的新文件的平均寻址时间，Ｔ１是通过实验得到的示例文件的平均寻址时间。
３．３．５读取的速度
为了判定磁盘的读取时间，新建一个１．４ＧＢ的文件，分块，
用无缓冲的Ｉ／Ｏ设备打开。选取１０２４个样本来从文件中的随机位置读取随机数目的扇区（最多３２个扇区）。用奔腾ＲＤＴＳＣ指令测算时间，以时钟周期为单位。结果在内存中予以校对并在实验结束时写回磁盘。
图４表示的是以时钟周期为单位的每个扇区的读取时间和读取的扇区数目之间的关系，结果是可以预料的。当只有少量的扇区被读入，寻址对每个扇区的影响是很大的。当读取的长度增大，寻址的影响也就变得越发不重要。
从图中看，平均读取时间大约为每个扇区１８３２７个时钟周期，数据转移速率为
２４．６９ＭＢ／ｓ。这个数据比厂商说明的稳定后的持续数据转移速
率３７ＭＢ／ｓ要低，原因是操作系统的开销。
图４
当读取的数据量增大时读取一个扇区的时间
对于ｎ个整数，将压缩后的倒排表从磁盘读出的时间ｔ为：
ｔ＝「Ｅｎ
５１２×８
(×１８３２７
（４）在这里，Ｅ是压缩技术的有效性，单位为每个整数所需的
位数。当读入整数的数目增加时：
ｔ≈ＥｎＡ（５）
Ａ＝１８３２７
５１２×８
≈４．４７
（６）
３．３．６
磁盘
公式（３）描述了随机搜索一个任意大小的文件所耗费的时
间。公式（４）描述了从文件中读取一系列整数的耗费。实验得到的磁盘的特征基本符合生产商的说明，但是在寻址和读取两种情况下，都偏慢了一些。磁盘的平均寻址时间是扇区的平均读取时间的４００倍。这说明搜索的瓶颈不是读取，而是寻址。
当我们对小的分块的文件进行测试时，结果如下：寻址的时间在２００００００～１０００００００时钟周期范围内，读取时间是每块１８５００个时钟周期。
３．４
实验结果综合
将对硬盘的实验和压缩的实验所得到的结果综合起来，我
们才真实地清楚每一种算法的性能。
假定一个１．４ＧＢ的倒排表文件用最高效的方案进行压缩
（见表１），载入和解压的总耗费表示如下：
Ｕ≈Ｔ＋ＥｎＡ＋ｄｎ
（７）Ｕ是花费的时间，Ｔ是寻址的耗费，ＥｎＡ是读取的耗费，ｄｎ是内存中解压的耗费，ｎ是读取解压后整数的个数。
表１
压缩效果、解压速度和相对的性能
当ｎ变得非常大时，寻址的耗费就不重要了，解压方案的性能Ｐ决定于读取和解压时间：
Ｐ≈ＥＡ＋ｄ
（８）
当ｎ趋向于０，性能只取决于寻址：Ｐ≈Ｔ
从式（３）可得：Ｐ≈Ｔ＝（Ｍ－Ｃ）Ｒ＋Ｃ
在这里，Ｍ是测量的磁盘平均寻址时间。
从图５中，ＢｉｎａｒｙＩｎｔｅｒｐｏｌａｔｉｖｅＣｏｄｉｎｇ（二进制插入编码）当被编码的整数个数很少的时候性能是最好的。但是随着整数个数的增加，Ｇｏｌｏｍｂ编码很快超过了其它几种编码方法，当整数的数目变得很大时，ＶａｒｉａｂｌｅＢｙｔｅＣｏｄｉｎｇ（可变字节编码）就
成为最高效的编码方式。
４结论
对倒排索引的平均压缩比一直以来都是一种编码方式是
否合适的唯一标准。很少或者说没有对当倒排表增大时这几种方法的作用和性能如何的研究。因为对长的倒排表的处理成倒排文档信息检索系统的瓶颈，所以当倒排表增大时编码方法的性能如何才是更好的衡量标准。
１７２
计算机工程与应用２００６．０７
（上接１３６页）
５结论
论文基于中国剩余定理，结合差错控制理论中的（７，４）汉
明码，提出了一种对有效位数较长的数值型字段值引入少量误差进行水印嵌入的方法。该算法具有如下特点：
（１）安全性好，攻击者即使知道嵌入算法，也只能提取水印的分存值，无法恢复原始水印。
（２）抗剪切能力好，能够依靠部分数据恢复水印信息。（３）水印恢复，不需要原始数据库。
（４）隐蔽性好，水印信息嵌入有效位数多的数值型字段值的最低有效位中，嵌入水印所引入的误差非常微小。
（５）结合纠错编码理论，提高了水印抗攻击能力。（收稿日期：２００５年１１月）
参考文献
１．ＩｎｇｅｍａｒＪＣｏｘ，ＭａｔｔｈｅｗＬＭｉｌｌｅｒ，ＪｅｆｆｒｅｙＡＢｌｏｏｍ．ＤｉｇｉｔａｌＷａｔｅｒｍａｒ－
ｋｉｎｇ［Ｍ］．电子工业出版社，２００３－０７
２．张健沛．数据库原理及应用系统开发［Ｍ］．中国水利水电出版社，１９９９－０４３．张勇，赵东宁，李德毅．关系数据库数字水印技术［Ｊ］．计算机工程与应用，２００３；３９（２５）：１９３～１９５
４．ＲＡｇｒａｗａｌ，ＰＪＨａｓｓ，ＪＫｉｅｒｎａｎ．ＷａｔｅｒｍａｒｋｉｎｇＲｅｌａｔｉｏｎａｌＤａｔａｂａｓｅｓ［Ｃ］．Ｉｎ：２８ｔｈＩｎｔ’ｌＣｏｎｆｅｒｅｎｃｅｏｎＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓ，ＨｏｎｇＫｏｎｇ，２００２－０８
５．ＲＳｉｏｎ，ＭＡｔａｌｌａｈ，ＳＰｒａｂｈａｋａｒ．Ｏｎｗａｔｅｒｍａｒｋｉｎｇｎｕｍｅｒｉｃｓｅｔｓ［Ｃ］．Ｉｎ：ＰｒｏｃｅｅｄｉｎｇｓｏｆＩＷＤＷ２００２，ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＣＥＲＩＡＳＴＲ２００１－６０，Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００２
６．牛夏牧，赵亮，黄文军等．利用数字水印技术实现数据库的版权保护［Ｊ］．电子学报，２００３；３１（１２）：２０５０～２０５３
７．张勇，赵东宁，李德毅．水印关系数据库［Ｊ］．解放军理工大学学报，２００３；４（５）：１～４
８．陈景润．初等数论Ⅰ［Ｍ］．北京：科学出版社，１９７８：１７～２２
９．ＡＳｈａｍｉｒ．ＨｏｗｔｏＳｈａｒｅａＳｅｃｒｅｔ［Ｊ］．ＣｏｍｍｕｎＡＣＭ，１９７９；２２（１１）：６１２～６１３
１０．刘珺，罗守山，吴秋新等．基于中国剩余定理的数字水印分存技术［Ｊ］．北京邮电大学学报，２００２；１（５）：１７～２１
１１．唐朝京，雷菁．信息论与编码基础［Ｍ］．长沙：国防科技大学出版社
当倒排表很小的时候，吞吐量是由磁盘寻址时间决定的，这点和磁盘文件的长度是相联系的。使文件最小化可以使磁盘
寻址的长度最小，所以选择基于可以最小化文件大小的压缩方法是最好的，例如Ｇｏｌｏｍｂ。然而，当表的长度增加，磁盘的寻址变得不如原先重要了，吞吐量是跟压缩比和解压速率相关的，所以ＶａｒｉａｂｌｅＢｙｔｅＥｎｃｏｄｉｎｇ要更好些。
如果将磁盘空间作为一项附加要求，Ｇｏｌｏｍｂ编码压缩要好一些。用Ｇｏｌｏｍｂ要比用Ｅｌｉａｓｇａｍｍａ或者Ｅｌｉａｓｄｅｌｔａ更能减小文件大小，加快解压速度。
当文档号用Ｇｏｌｏｍｂ编码，出现频率用Ｅｌｉａｓｇａｍｍａ编码时，没有用Ｇｏｌｏｍｂ既为文档号又为出现频率编码高效。
为了能达到最优的性能，最好的方法是进行算法的综合。当倒排表小的时候，通过使文件尽量小来减少时钟周期。当倒排表长的时候就设法节省磁盘空间。Ｚｉｐｆ的法则认为大部分的词出现频率低，所以对于长的倒排表用ＶａｒｉａｂｌｅＢｙｔｅＥｎｃｏｄｉｎｇ编码，可使文件大小的总开销较小。（收稿日期：２００５年６月）
参考文献
１．ＺｏｂｅｌＪ，ＭｏｆｆａｔＪ．Ａｄｄｉｎｇｃｏｍｐｒｅｓｓｉｏｎｔｏａｆｕｌｌ－ｔｅｘｔｒｅｔｒｉｅｖａｌｓｙｓｔｅｍ［Ｊ］．ＳｏｆｔｗａｒｅＰｒａｃｔｉｃｅａｎｄＥｘｐｅｒｉｅｎｃｅ，１９９５；２５（８）：８９１～
９０３２．ＷｉｌｌｉａｍｓＨＥ，ＺｏｂｅｌＪ．Ｃｏｍｐｒｅｓｓｉｎｇｉｎｔｅｇｅｒｓｆｏｒｆａｓｔｆｉｌｅａｃｃｅｓｓ［Ｊ］．ＴｈｅＣｏｍｐｕｔｅｒＪｏｕｒｎａｌ，１９９９；４２（３）：１９３～
２０１３．ＶｏＡＮ，ＭｏｆｆａｔＣ．Ｃｏｍｐｒｅｓｓｅｄｉｎｖｅｒｔｅｄｆｉｌｅｓｗｉｔｈｒｅｄｕｃｅｄｄｅｃｏｄｉｎｇｏｖｅｒｈｅａｄｓ［Ｃ］．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２１ｓｔＡＣＭ－ＳＩＧＩＲＣｏｎｆｅｒｅｎｃｅｏｎＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌ，１９９８：２９０～
２９７４．ＭｏｆｆａｔＡ，ＳｔｕｉｖｅｒＪ．Ｂｉｎａｒｙｉｎｔｅｒｐｏｌａｔｉｖｅｃｏｄｉｎｇｆｏｒｅｆｆｅｃｔｉｖｅｉｎｄｅｘｃｏｍｐｒｅｓｓｉｏｎ［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌ，２０００；３（１）：２５～４７
５．ＩｎｔｅｌＣｏｒｐｏｒａｔｉｏｎ．ＵｓｉｎｇｔｈｅＲＤＴＳＣｉｎｓｔｒｕｃｔｉｏｎｆｏｒｐｅｒｆｏｒｍａｎｃｅｍｏｎｉ－ｔｏｒｉｎｇ．Ａｖａｉｌａｂｌｅａｔｃｅｄａｒ．ｉｎｔｅｌ．ｃｏｍ／ｓｏｆｔｗａｒｅ／ｉｄａｐ／ｍｅｄｉａ／ｐｄｆ／ｒｄｔｓｃｐｍ１．ｐｄｆ，２００２
１７３
上海电力学院 《高级程序设计C++》 课程设计 题目：学生综合测评系统 院系：计算机科学与技术学院 专业年级：计算机科学与技术 学生姓名：学号：20111695 指导教师： 2013年1月
目录 目录 (2) 1．需求分析 (3) 2．概要设计 (4) 3．详细设计 (6) 4．用户使用手册 (9) 4.1 环境设置 (9) 4.2 操作步骤 (10) 5．程序创新点.......................................... 错误！未定义书签。6．使用的主要技术.................................. 错误！未定义书签。7．总结 ..................................................... 错误！未定义书签。附录 ................................................................ 错误！未定义书签。
1．需求分析 本系统旨在便于学校管理和查阅学生信息并计算学生的考试成绩和名次以及综合测评成绩和名次。每个学生的信息为：学号、姓名、性别、家庭住址、联系电话、高等数学、物理、英语三门单科成绩、、同学互评分、品德成绩、任课教师评分。考试平均成绩、同学互评分、品德成绩、任课教师评分分别占综合测评总分的60%，10%，10%，20%。 程序的基本功能： 1．学生信息处理： (1) 输入学生信息、学号、姓名、性别、家庭住址、联系电话，按学号以小到大的顺序存入文件中。 (2) 插入（修改）同学信息。 (3) 删除同学信息。 (4) 浏览学生信息。 2．学生数据处理： (1) 按考试科目录入学生成绩并且按公式：考试成绩＝（语文+数学+外语）/3 计算考试成绩，并计算考试名次。 (2) 学生测评数据输入并计算综合测评总分及名次。 (3) 学生数据管理。 (4) 学生数据查询。 3．学生综合信息输出
实验三、存储管理 一、实验目的： ? 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。 在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验理解在分页式存储管理中怎样实现虚拟存储器。 在本实验中，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 二、实验题目： 设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 对分区的管理法可以是下面三种算法之一：（任选一种算法实现） 首次适应算法 循环首次适应算法 最佳适应算法 三．实验源程序文件名:cunchuguanli.c
执行文件名:cunchuguanli.exe 四、实验分析： 1)本实验采用可变分区管理，使用首次适应算法实现主存的分配和回收 1、可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并 且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表 ? 空闲区说明表格式如下：? 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 2、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。 有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分
为了方便文件的传输，我们很多文件都是需要进行压缩的，比如说pdf文件，有时我们需要传送的pdf文件太多或是对应的文件占用的内存过大，对传输时间和速度是有影响的。有时甚至还不能进行传输。接下来就让我们一起看看pdf怎么压缩大小的吧！ 压缩方法一：使用压缩软件 压缩工具：迅捷压缩 当我们需要进行pdf文件压缩时，可以使用专业的压缩软件，今天就以迅捷压缩为例给大家看下是怎么压缩pdf文件的。我们先打开电脑上的压缩工具，在该工具中找到对应的PDF压缩功能。 我们需要压缩的pdf文件比较多，那么就需要大家点击一下“添加文件夹”。这样就可以一次性的在该功能界面中添加多个pdf文件了。如果我们的文件不太多的话，选择“添加文件”就可以了。
在压缩文件之前，我们还有一些设置可以调整一下，如压缩设置是想要缩小优先、还是普通压缩、清晰压缩。大家在保存识别好的文件时要记得“保存至”中保存路径呀，这样方便我们找到压缩好的文件。当然这个保存的路径也是可以更改的。 最后我们只需要点击一下“开始压缩”就可以了。
压缩方法二：使用在线网站 压缩工具：在线PDF转换器 压缩pdf文件的大小除了使用专业的压缩软件，还可以在在线网站上实现pdf 压缩的操作。我们先在网页上找到迅捷PDF转换器在线网站，在“文档处理”中有“在线压缩”功能，我们点击一下需要的PDF压缩功能。 进入到pdf压缩的页面后，点击一下添加pdf文件的按钮，之后就会跳出一个“打开”的对话框，将我们需要的文件找到并添加进去就可以了。
如果没有什么需要调整的，点击一下“开始压缩”就完成pdf的压缩了。 pdf怎么压缩大小？现在大家学会了吧！以上的方法也是挺简单的，相信大家在看完之后是有所收获的，希望在工作中可以帮助到大家哦。
学生实验报告 院系：测绘学院 专业班级：测绘13级3班 学号：2013305517 学生姓名：王泽 指导教师：郭辉老师 2016年05月20日
安徽理工大学实验报告 实验课程名称：数据结构与软件开发上机实验 开课院系及实验室：测绘学院红楼二楼机房 实验1 编程基本知识练习 实验目的： 通过该实验课内容的练习，学生应掌握VB 编程的基本语法、变量的定义、数组（动态数组）的定义、VB 语言中子过程与函数的定义以及文本文件的读写等知识。 实验内容： 1）变量的定义动态数组的定义与应用； 2）矩阵的加、减、乘运算(定义Sub()子过程或Function()来实现)； 3）数据文件的建立、数据的读取与写入。 实验步骤： 1.编辑界面 1.1 打开VB 编程工具，进入编程主界面。
1.2 在窗体上新建“读入数据”和“输出数据”两个按钮。 1.3 双击“窗体”进入代码输入界面，进行代码编辑。 2.用VB 编写的源代码 2.1 矩阵基本运算源码详见附录一。 （1）两矩阵相加 （2）两矩阵相减 （3）矩阵转置 （4）两矩阵相乘 （5）矩阵求逆 2.2 文本文件(本实验中data.txt)的读取源代码 （1）建立文本文件并输入数据 在桌面上新建一“data.txt” ( 文本文件路径为C:\Users\ WH\Desktop\练习\data.txt”）。输入以下内容： 6,7,4,0.005 A,35.418 B,45.712 C,25.270
D,24.678 在桌面上新建一“result.txt” ( 文本文件路径为C:\Users\ WH\Desktop\练习\result.txt”）。（2）从文本文件中读数据 Dim linedata as string, m_GaochaN as integer,m_Pnumber as integer,m_knPnumber as integer,M as Double,k1 as integer 'linedata 为存储文本文件一行信息的字符串变量 Dim a() as String,H() as Double 'a()为存储点名，H()存储高程 Open“C:\Users\ WH\Desktop\练习\data.txt”For Input As #1 Line Input #1, linedata k = Split(linedata, ",") m_GaochaN = Val(k(0)) m_Pnumber = Val(k(1)) m_knPnumber = Val(k(2)) M = CDbl(k(3)) For k1 = 1 To m_knPnumber Line Input #1, linedata k = Split(linedata, ",") a（k1）= k(0) GetstationNumber (a) H(k1) = CDbl(k(1)) Next Close #1 （3）将读入点名存储到点名数组中，且返回该点名所对应编号 Function GetstationNumber(name As String) Dim i As Integer For i = 1 To m_Pnumber If P_Name(i) <> "" Then '将待查点名与已经存入点名数组的点比较 If P_Name(i) = name Then GetstationNumber = i Exit For End If Else '待查点是新的点名，将新点名放到P_Name 数组中 P_Name(i) = name GetstationNumber = i Exit For End If Next i End Function （4）从文本文件中写数据(将从data.txt 读入的数据，写入到result.txt 文件中) Open“C:\Users\ WH\Desktop\ 练习\result.txt” For Output As #1 outstring = outstring + str(m_GaochaN) +","
甘肃政法学院计算机科学学院Java程序设计课程设计 题目标准化考试系统 计算机科学学院计算科学与技术专业11级专升本班 学号：201181210115 姓名：刘昆明 指导教师：李瑞生 成绩：____________ 完成时间：2011年 11月
目录 1．设计内容及要求 (1) 1.1 标准化考试系统的基本要求 (1) 1.2 需实现的主要功能 (1) 2．需求分析 (2) 2.1数据库设计 (2) 2.2服务器端和客户端的数据传输方式 (2) 2.3 服务器端功能设计 (2) 2.4客户端功能设计 (3) 3．总体设计 (4) 3.1 总体功能图 (4) 3.2 总体流程图 (6) 4．数据库设计 (7) 4.1 数据库及表结构的建立 (7) 4.2 JAVA 数据库的连接 (8) 5. 主要功能设计流程 (8) 5.1服务器端设计流程图 (8) 5.2客户端设计流程图 (9) 6．代码实现 (10) 6.1类之间关系图 (10) 6.2 运行效果图 (11) 6.3 程序打包发布过程 (17) 7. 总结与说明 (18) 8. 参考文献 (18)
标准化考试系统设计与实现 【摘要】：在现今知识爆炸的年代里，教学的质量和怎样提高教师的工作效率成了各大院校的首要任务。找题、选题和出卷就成为一项非常重要的工作。每学期教师都要为各类考试付出大量的精力和工作，尤其是一位教师教授多门学科的时候，工作量将成倍增加。因此开发此考试系统，对各专业课程的问卷进行整理入库，以便在需要的时候能够及时、方便、快速的对学生进行各级测试，从而使考试过程趋于简单化，减少教师在这方面的工作负担。 因此，使用现在的新技术，开发出适应新的需求的新系统刻不容缓。 四年的大学生活转瞬既逝，在这四年中，我系统的学习了计算机科学与技术专业的所有课程。深入的学习了各个科目的理论知识，对专业知识有了整体的掌握。在即将毕业之际，为了理论联系实际，检验自己的学习成果，我选择了这个题目作为课程设计。在此毕业设计的完成过程中，我严格遵循软件开发的过程，将理论知识与具体问题相结合。在应用程序开发中我一方面学习了软件编程思想，另一方面具体的运用了JAVA语言。体会了他的诸多功能和特色。熟悉了数据库应用程序的开发原理。确实达到了学校和辅导教师对我们应届毕业生的各种要求。 【关键词】：J2ME；标准化考试；设计与实现 1
重庆科技学院 课程设计报告 院（系）:电气与信息工程学院专业班级: 学生姓名:学号: 设计地点（单位）________ _____ _ _ 设计题目:___ 仓库管理系统 _ _ _____ 完成日期： 201年月日 指导教师评语: ___________________________________________________________________ _______________________________________________________________________ ______________________________________________________________ __________ _ 成绩（五级记分制）:______ __________ 指导教师（签字）:________ ___ _____
重庆科技学院 课程设计任务书 设计题目：仓库管理系统程序设计 2016年 6月 19日
目录 目录 (3) 摘要 (4) 1 需求分析 (5) 1.1 系统设计目标 (6) 1.2 系统功能分析 (6) 1.2.1 系统功能概述 (6) 1.2.2 系统功能模块设计 (7) 1.2.3 系统功能模块图 (7) 1.2.4 系统流程图 (8) 1.5 数据库的主要设计——物理设计 (9) 2 系统功能实现 (10) 2.1 功能实现代码 (10) 2.1.1 注册成功 (10) 2.1.2 登陆成功 (11) 2.1.3 树状列表 (11) 2.1.4 表格显示 (12) 2.1 注册功能 (12) 2.2 登录功能 (13) 2.3 添加用户 (13) 2.4 删除用户 (14) 2.5更新用户 (14) 2.6 查询用户 (15) 2.7 添加产品 (15) 2.8 增加库存 (16) 2.9 产品出库 (17) 2.10 查询产品 (18) 总结 (19) 致谢 (20) 参考文献 (21)
**大学程序设计基础实验报告 实验名称：实验三分支结构 实验目的： 1、掌握IF-ELSE语句使用。 2、掌握ELSE-IF语句使用。 3、熟悉SWITCH语句使用。 实验内容： 在本地电脑中新建一个文件夹，用于存放C程序，文件夹的名字要求是“学号姓名-实验序号”，如E:\ 1920115555张三-03。启动C-Free，完成如下各题。 1、编程题：输入参数a,b,c,求一元二次方程ax2+bx+c=0的根（①a、b、c都为0，②a 和b为0，c不为0，③a为0，b不为0，c任意，④a不为0，且a、b、c满足b2-4ac ≥0，⑤a不为0，且a、b、c满足b2-4ac<0）。 2、编程题：输入职工的月薪salary,计算并输出应缴纳的个人所得税tax。tax=rate * (salary –850)，rate的计算方式如下： 当salary <= 850，则rate = 0; 当850 < salary <= 1350，则rate = 5%; 当1350 < salary <= 2850，则rate = 10%; 当2850 < salary <= 5850，则rate = 15%; 当salary > 5850，则rate = 20%;。 3、编程题：根据输入的3个边长a、b、c，判断它们是否能构成三角形，若能构成三 角形，则进一步判断此三角形是哪种类型的三角形（等边三角形、等腰三角形、直角三角形和一般三角形。等腰直角算作等腰）。 4、编程题：输入一个形式如“操作数运算符操作数”的表达式，对2个整数进行乘、 除或求余运算。【请分别用if语句和switch语句实现此题功能】 上交作业的方法： 1.将程序代码及注释和运行程序的窗口复制到实验结果下方对应的题号上，并把这 次实验上机操作中遇到的问题及解决方法、心得等填好完成实验报告。 2.保存以上所有按要求已调试通过，并形成.c（或.cpp）和.exe文件到以自己的“学 号姓名-03”命名的文件夹中，并将以自己的“学号姓名”命名的文件夹压缩后上 交到ftp://10.172.250.252:1161中的“作业上传”文件夹下的“报告上交02”文件 夹下的子文件夹“源文件压缩上交”中，同时把以“学号姓名-03”命名的word 文档上交到“报告上交03”文件夹下的另一子文件夹“word文件上交”中。 特别提醒：每次上传的文件名一定要是“学号姓名-实验序号. doc”(如1720115555张
实验报告 课程名称Java程序设计 实验项目实验一类和对象 系别_________计算机_________ 专业/班级_______计算机类/1402______ 姓名_____李馨雪________ 实验日期______2015.10.10______ 成绩_______________________ 指导教师
一、实验题目：实验一类和对象 二、实验内容： （1）用类描述计算机中CPU的速度和硬盘的容量。要求Java应用程序有4个类，名字分别是PC、CPU、HardDisk和Test，其中Test是主类。 1）PC类与CPU类和HardDisk类关联的UML图如图所示。 其中，CPU类要求getSpeed()返回speed的值，setSpeed(int m)方法 将参数m的值赋值给speed。 HardDisk类要求getAmount()返回amount的值，setAmount(int m)方 法将参数m的值赋值给amount。 PC类要求setCPU(CPU c)将参数c的值赋值给cpu，要求setHardDisk (HardDisk h)方法将参数h的值赋值给HD，要求show()方法能显示 cpu的速度和硬盘的容量。 2）主类Test的要求 main()方法中创建一个CPU对象cpu，其speed设置为2200； main()方法中创建一个HardDisk对象disk，其amount设置为200； main()方法中创建一个PC对象pc， pc调用setCPU方法，实参是cpu；调用setHardDisk方法，实参是 disk；调用show方法。 （2）设计一个动物声音“模拟器”，希望模拟器可以模拟许多动物的叫声，要求如下： 1）编写接口Animal，有2个抽象方法cry()和getAnimaName()； 2）编写模拟器类Simulator，该类有一个playSound(Animal animal)方法，其形参是Animal类型，可以调用实现Animal接口的类所重写的cry()方法播放具体动物的声音，调用重写方法显示动物种类的名称； 3）编写实现Animal接口的Dog类和Cat类。具体的UML图如下所示：4）编写主类Application，其main方法中至少包含如下代码： Simulator si=new Simulator();
《高级语言程序设计》课程设计 说明书 设计题目《等级考试报名系统》 目录 1.C语言课程设计目的及要求………………………………………… 1.1 目的…………………………………………………… 1.2 要求…………………………………………………… 2.设计任务书……………………………………………………… 2.1 题目与要求…………………………………………… 2.2 本程序涉及的知识点………………………………… 3. 程序代码设计………………………………………… 3.1输入函数………………………………………………
3.2输出函数……………………………………………… 4.部分模块流程图………………………………………… 5.C程序设计总结………………………………………… 6.致谢……………………………………………………… 参考文献…………………………………………………… 1、C语言课程设计目的及要求 目的： 根据课堂讲授内容，学生做相应的自主练习，消化课堂所讲解的内容；通过调试典 型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学 生的编程能力、用计算机解决实际问题的能力。 要求： 1．熟悉 C 的编程环境、主要菜单功能。 2．通过上机验证运算符、表达式、函数使用。 3．熟练使用C语言的典型语句编写简单程序。 4．调试典型例题或习题。 5．提高上机编程能力 2、设计任务书 2.1题目与要求 等级考试报名系统设计 说明：近年来,参加计算机考试的人员日益增多,用计算机来降低工 作量成为了一种迫切需求,为此目的编写软件 基本功能： 报名信息维护 等级分类 等级查询 身份证号查询 姓名查询
三招轻松教会你如何压缩PDF文件的大小 说起PDF文件大家肯定不陌生，日常的工作和学习中我们都经常会接触到PDF格式的文件。PDF相比Word格式，优点在于传输过程中的稳定性，用PDF来传输文件能最大程度地保证文件的完整度。但是如果PDF文件过大的话，会给传输工作造成很大的不便，占用的内存也较大，所以我们需要对PDF文件进行压缩。今天就来分享三个压缩PDF文件大小的技巧给大家。 一、迅捷PDF转换器在线版 ①搜索“迅捷PDF转换器在线版”，进入网页后，点击【文档处理】一栏，选择【PDF压缩】功能； ②接下来单击【点击选择文件】按钮，选中需要压缩的PDF文件并添加到网页上后，点击【开始压缩】；
③等待PDF文件压缩完成后，点击【立即下载】按钮将文件下载下来即可。 二、使用迅捷PDF转换器 ①将迅捷PDF转换器下载安装至电脑上，打开软件后选择【PDF的其他操作】栏目，点击【PDF压缩】功能按钮；
②之后点击上方的【添加文件】按钮，选择要压缩的PDF文件添加到软件中； ③待要压缩的PDF文件被成功添加后，点击【开始转换】按钮，等待转换完成后即可。
三、使用迅捷PDF虚拟打印机 ①将迅捷PDF虚拟打印机下载安装到我们的电脑上运行，然后点击【应用程序设置】按钮； ②在弹出的设置窗口中，依次选择【打印机】-【默认设置】-【高压缩比（文件较小）】，选择好后点击
保存； ③打开我们要压缩的PDF文件，在文件中点击【打印】按钮，在【选择打印机】处选择“迅捷PDF虚拟打印机”，再点击【打印】按钮即可。
四、压缩前后文件大小对比压缩前的文件：
《C程序设计》实验教学大纲 一、适用范围 大纲适用信息管理专业本科教学使用。 二、课程名称 C程序设计 三、学时数与学分 总学时：90 总学分： 4 实验学时：28 实验学分：1 四、教学目的和基本要求 目的：通过C程序设计实验，培养学生对学习程序设计的兴趣，加深对讲授内容的理解，尤其是通过上机来掌握语法规则，使学生全面了解 C 语言的特点，熟练掌握C 语言程序设计的基本方法和编程技巧。 基本要求：了解和熟悉C语言程序开发的环境；学会上机调试程序，善于发现程序中的错误，并且能很快地排除这些错误，使程序能正确运行，达到实验知识和理论知识的融会贯通。上机实验前，学生必须事先根据题目的内容编好程序，然后在实验时输入程序、调试程序、直至运行结果正确为止，上机结束后，应整理出实验报告。 注：带*的实验项目为选做实验项目 六、教材、讲义及参考书 《C程序设计题解与上机指导》谭浩强主编清华大学出版社 七、实验成绩评定办法 实验成绩=平时实验表现+实验报告。实验成绩占总成绩的20%。 实验成绩以等级形式给出，评定等级分优、良、中、及格、不及格五类。 1、平时考核：上机实验前，学生必须事先根据题目的内容编好程序，然后在实验时输入程序、调试程序、直至运行结果正确为止。在实验中，教师可根据学生编程操作能力、观察和分析及运用知识能力、程序编制正确性以及学生的课堂纪律、实验态度、保持实验室卫生等方面的表现进行综合考核。
2、实验报告：学生实验后应按时完成实验报告。 八、实验教学大纲说明 本大纲共安排28学时的实验，其中带*号实验项目为选做实验项目，实际课时为18学时。实验项目多为设计性实验项目，每个设计性实验项目中都包含数个小的设计性题目，其中带*号的题目为选做题目，有时间和有能力的同学可以选做。 九、实验项目 实验一 C程序的运行环境和运行一个C程序的方法 一、实验目的 1.了解Visual C++编译系统的基本操作方法，学会独立使用该系统。 2.了解在该系统上如何编辑、编译、连接和运行一个C程序。 3.通过运行简单的C程序，初步了解C源程序的特点。 二、实验内容 1.用编辑程序，输入教材第一章例程序，并进行编译和运行。应了解所用的系统是用什么命令进行编译和连接运行的。编译和连接后所得到的目标程序的后缀是什么形式的 2.编写一个C程序，输出以下信息： **************************** very good! **************************** 3.输入并运行教材第一章中例，了解如何在运行时向程序变量输入数据。 实验二数据类型、运算符和表达式 一、实验目的 1.掌握C语言数据类型，熟悉如何定义一个整型、字符型、实型变量，以及对它们赋值的方法，了解以上类型数据输出时所用格式转换符。 2.学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加(++)和自减(--)运算符的使用。 二、实验内容 1.输入并运行以下程序： main( ) { char c1,c2; c1=97;c2=98; printf(“%c %c\n”,c1,c2); printf(“%d %d\n”,c1,c2); } 在此基础上 ①将第三行、第四行改为: c1=321;c2=353; 再使之运行，分析其运行结果。 ②将第二行改为： int c1,c2; 再使之运行，分析其运行结果。。 2.输入并运行以下程序： main( ) {int i=8,j=10,m,n; m=++i;n=j++;
万维考试系统C语言题库含题目程序设计题导 出道 Standardization of sany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#
一、程序设计共113题（共计1130分） 第1题（分）题号:390 /*------------------------------------------------【程序设计】 --------------------------------------------------功能：编写函数求1~100中奇数的平方和。 结果为。 ------------------------------------------------*/ #include <> void wwjt(); float sum(int n) { /**********Program**********/ /********** End **********/ } 答案：---------------------- float s=0; int i; for(i=1;i<=n;i=i+2) s=s+i*i; return(s); ---------------------- 第2题（分）题号:320 /*------------------------------------------------【程序设计】 --------------------------------------------------功能：在键盘上输入一个3行3列矩阵的各个元素的值（值为整数），然后输出主对角线元素的积,并在fun() 函数中输出。 ------------------------------------------------*/ #include <> void wwjt(); main() { int i,j,s,a[3][3];; for(i=0;i<3;i++) { for(j=0;j<3;j++) scanf("%d",&a[i][j]); } s=fun(a); printf("Sum=%d\n",s);
存储管理的主要功能之一是合理地分配空间。请求页式管理是 一种常用的虚拟存储管理技术。 本课程设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。 1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50％的指令是顺序执行的； ②25％的指令是均匀分布在前地址部分； ③25％的指令是均匀分布在后地址部分； #具体的实施方法是： A. 在[0， B. 319]的指 C. 令地址之间随机选区一起点M; B. 顺序执行一条指E. 令，F. 即执行地址为M+1的指G. 令； C. 在前地址[0，I. M+1]中随机选取一条指J. 令并执行，K. 该指L. 令的地址为M’; D. 顺序执行一条指N. 令，O. 其地址为M’+1； E. 在后地址[M’+2，Q. 319]中随机选取一条指R. 令并执行； F. 重复T. A—E，U. 直到执行320次指V. 令。 2．指令序列变换成页地址流 设：（1）页面大小为1K； （2）用户存容量为4页到32页； （3）用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条—第9条指令为第0页（对应虚存地址为[0，9]）； 第10条—第19条指令为第1页（对应虚存地址为[10，19]）； 。。。。。。。。。。。。。。。。。。。。。 第310条—第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。
3. 计算并输出下述各种算法在不同存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法（先淘汰最不常用的页地址） D. LFR最少访问页面算法 E. NUR最近最不经常使用算法 二、课程设计环境要求 1、硬件环境 PC机一台，0.99G存，2.00GHZ 主频 2、软件环境 Windows XP/2000系统，编程软件VC++。 三、设计任务介绍及系统需求分析 本课程设计主要的目的是编制页面置换算法FIFO、LRU、LFU、NUR和OPT的模拟程序,并模拟其在存的分配过程。同时根据页面走向，分别采用FIFO、LRU、LFU、NUR和OPT算法进行页面置换，统计命中率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。 本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。该程序能按要求随机确定存大小，随机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。 四、概要设计 系统分为4个子模块：初始化模块，FIFO、LRU、LFU、NUR和OPT的五个算法模块。
4种方法教你学会如何压缩pdf文件大小 在传文件的时候，如果文件太大的话，所需要的上传和下载时间就会较长，那么，要如何有效的解决这一问题呢？其实，我们可以通过压缩文件来改变文件的大小。 一、使用压缩工具 大家的电脑上自带有压缩工具，我们可以通过创建压缩包的形式，上传文件，既方便，又快捷。 通过右击文件，然后选择【添加到压缩文件】，然后在弹出的页面中，将【压缩配置】选为【体积最小】 二，使用在线pdf转换器 除了创建压缩包外，我们还可以直接压缩pdf文件。这时就需要借助软件了。当然，我们可以通过迅捷pdf转换器的在线版本来操作，也不用下载软件。 在网页中搜索迅捷pdf转换器的在线版本，点击【pdf压缩】功能。 进入该压缩页面后，点击【点击添加文件】，将需要压缩的文件导入其中，完成后选择
【开始压缩】即可。 压缩后不要忘记将文件保存到电脑上 三，利用word的二次转换功能 我们也可以直接通过转换来改变pdf文件的大小。先将文件转成word格式，然后，在将其转回pdf格式。 具体的操作可以使用上文中的迅捷pdf转换器来转换，选择相应的功能后，添加文件就可以操作了。
上面三种方法都是对现有的盘点文件进行处理，其实，我们也可以直接输出压缩后的pdf文件，这时，就需要借助另一款软件了——迅捷pdf虚拟打印机。 四、使用迅捷pdf虚拟打印机 下载安装好迅捷pdf虚拟打印机后，在页面找到【应用程序设置】。 点击进入后，找到【打印机】，选择【高压缩比】选项，然后点击保存。
设置完成后，之后“打印”出来的pdf文件就已经是压缩好的文件了。以上就是4种压缩pdf文件的方法，希望对大家有所帮助。
数据结构实验报告记录文件压缩
————————————————————————————————作者：————————————————————————————————日期：
数据结构与程序设计实验 实验报告 课程名称数据结构与程序设计实验课程编号0906550 实验项目名称文件压缩 学号年级 姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静 实验室名称地点21B276 哈尔滨工程大学
实验报告四 实验课名称：数据结构与程序设计实验 实验名称：文件压缩 班级：学号：姓名：时间：2016.04.21 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat 中。 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt 文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。 二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。 1.使用结构体数组统计词频，并存储: typedef struct Node{ int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }LeafNode[N]; 2.使用结构体数组存储哈夫曼树: typedef struct{ unsigned int weight;//权值 unsigned int parent, LChild, RChild; }HTNode,Huffman[M+1]; //huffman树 3.使用字符指针数组存储哈夫曼编码表： typedef char *HuffmanCode[2*M]; //haffman编码表 三、算法设计 1.读取文件，获得字符串 void read_file(char const *file_name, char *ch){ FILE *in_file = Fopen(file_name, "r"); unsigned int flag = fread(ch, sizeof(char), N, in_file); if(flag == 0){ printf("%s读取失败\n", file_name); fflush(stdout); } printf("读入的字符串是: %s\n\n", ch); Fclose(in_file); int len = strlen(ch);
软件综合化项目实训在线上机通用考试系统 用户界面设计报告 淮安信息职业技术学院计算机科学与工程系
版本历史
目录 0. 文档介绍 ........................................................................................... 错误！未定义书签。 0.1文档目的 (4) 0.2文档范围 (4) 0.3读者对象 (4) 0.4参考文献 (4) 0.5术语与缩写解释 (4) 1. 应当遵循的界面设计规范 ................................................................ 错误！未定义书签。 2. 界面的关系图和工作流程图 (4) 3. 主界面 (5) 4. 子界面A (5) 5. 子界面B (5) 6. 美学设计 (6) 7. 界面资源设计 (11) 8. 其他 (11)
文档介绍 0.1 文档目的 0.2 文档范围 0.3 读者对象 0.4 参考文献 提示：列出本文档的所有参考文献（可以是非正式出版物），格式如下：[标识符] 作者，文献名称，出版单位（或归属单位），日期 例如： [AAA]作者，《立项建议书》，机构名称，日期 [SPP-PROC-SD] SEPG，系统设计规范，机构名称，日期 0.5 术语与缩写解释
2. 界面的关系图和工作流程图 3. 界面1：登录界面 用户名 口令 [登录] [重置] 学生教师管理员 4. 界面2：系统管理界面 当选择管理员登录后，进入系统管理界面，主要负责对专业、班级、学生、教师等信息的维护。页面采用框架结构设计，右侧为功能页面。 [学生管理]2-1 <班级管理>2-1-1 <学生维护>2-1-2 [教师管理]2-2 <教师维护>2-2-1 ｛各个功能页面显示区｝[专业管理]2-3 <专业设定>2-3-1 <专业课程>2-3-2 [系统管理]2-4 <用户管理>2-4-1 5. 界面2-1-1：班级管理界面
不管是在上学时，还是在工作中，大家都有遇到过大体积的文件，之前对文件的压缩不是很了解，只知道选中文件鼠标右击一下选择压缩文件夹即可。但是那样会对我们的文件质量有所影响。比如说PDF文件吧，当我们需要发送给别人一些较大的PDF文件时，为了快速发送，我们可以使用专业压缩PDF文件的工具进行压缩，这样我们的文件就不会被损坏了。下面给大家看两种简单的压缩方法。 PDF压缩方法一：专业压缩软件 使用工具：迅捷压缩软件 迅捷压缩软件可以对不同的文件进行压缩操作，其中支持的功能有图片压缩、PDF压缩、视频压缩等。 首先，需要我们在电脑里将对应的压缩软件给打开，然后进入软件的主界面，选择一下“PDF压缩”功能。 进入PDF压缩的界面后，接下来要做的是添加PDF文件了。在PDF压缩的功能页面内有多种添加文件的方法，点击“添加文件”或是“添加文件夹”，使用拖拽文件的方式等都是可以的。
在压缩文件之前，大家需要对一些压缩设置做调整，如通用设置中的压缩设置可以选择清晰优先。之后再点击压缩的按钮就可以了。 PDF压缩方法二：PDF转换器 使用工具：迅捷PDF转换器 PDF转换器并不仅仅是一种支持PDF文件转换的工具，它还具有不少的其他功能，如PDF压缩、PDF合并、PDF添加密码。 使用PDF转换器也是需要先将软件给打开，然后再选择出压缩PDF文件的功能。即点击“PDF操作”中的压缩功能。
在进入PDF压缩的页面后，接下来要做的同样是添加文件，该转换器和压缩软件添加文件的方式差不多，同样是点击添加文件的按钮进行文件的添加。需要压缩的文件添加成功之后，简单对压缩设置调整一下，就可以点击转换按钮进行压缩了。 PDF压缩大小怎么做？使用上面方法都是可以实现的，并且上面的软件还支持文件PDF操作，有兴趣的小伙伴可以实际操作一下啊！
南京晓庄学院 《JAVA程序设计》 课程设计报告 Java聊天室的设计与实现题 目 姓名：戴佳伟 学号：14552019 班级：14软件工程3班 指导教 王峥 师： 完成时间2016.10.7 成绩： 信息工程学院 2016年6月
目录 1引言.............................. . (3) 1.1 java 聊天室开发背景.................................... (3) 1.1java 聊天室开发的目的和意义........ (3) 1.2完成的主要工作.................... (4) 2 需求分析和总体设计................ (5) 2.1 需求分析与设计思路................ (5) 2.1.1 关键技术说明 .................................... . (5) 2.1.2 需求分析..................... ....................... 6 2.1.3 java 聊天室设计方案与思路 (6) 2.1.4 java 聊天室目录结构说明....... (7) 2.2 java 聊天室功能结构 .................................... (8) 3 详细设计.......................... (10) 3.1 java 聊天室模块实现 .................................... (10) 3.1.1 XX 模块实现.................. ..................... 10 4 java 聊天室运行结果.................................... (13) 5课程设计总结...................... .. (15)