基于布尔函数的图像编码

由于二值图像可以认作一幅布尔函数的映射，因此该文提出了基于布尔函数最小化表示的布尔值图像的编码方法。它与4叉树等树型表示比较，获得了更好的存储压缩。结果表明，所提出的方法表示一幅二值图像所需求的代码数目大约仅是4叉树的一半左右。     

一种基于LFU置换的BWT压缩算法的改进

BWT算法是目前广泛关注的一种基于块压缩的无损压缩算法。由BWT变换,MTF变换和熵编码三部分组成。本文对其做了具体介绍和分析并在此基础上提出了一种基于LFU缓冲区置换策略的MTF变换的改进方法,实验结果表明改进后的算法使压缩比有所提高。     

A large‐alphabet‐oriented scheme for Chinese and English text compression

In this paper, a large‐alphabet‐oriented scheme is proposed for both Chinese and English text compression. Our scheme parses Chinese text with the alphabet defined by Big‐5 code, and parses English text with some rules designed here. Thus, the alphabet used for English is not a word alphabet. After a token is parsed out from the input text, zero‐, first‐, and second‐order Markov models are used to estimate the occurrence probabilities of this token. Then, the probabilities estimated are blended and accumulated in order to perform arithmetic coding. To implement arithmetic coding under a large alphabet and probability‐blending condition, a way to partition count‐value range is studied. Our scheme has been programmed and can be executed as a software package. Then, typical Chinese and English text files are compressed to study the influences of alphabet size and prediction order. On average, our compression scheme can reduce a text file's size to 33.9% for Chinese and to 23.3% for English text. These rates are comparable with or better than those obtained by popular data compression packages. Copyright © 2005 John Wiley & Sons, Ltd.     

Quasi-acyclic propositional Horn knowledge bases: optimalcompression

Horn knowledge bases are widely used in many applications. The paper is concerned with the optimal compression of propositional Horn production rule bases-one of the most important knowledge bases used in practice. The problem of knowledge compression is interpreted as a problem of Boolean function minimization. It was proved by P.L. Hammer and A. Kogan (1993) that the minimization of Horn functions, i.e., Boolean functions associated with Horn knowledge bases, is NP complete. The paper deals with the minimization of quasi acyclic Horn functions, the class of which properly includes the two practically significant classes of quadratic and of acyclic functions. A procedure is developed for recognizing in quadratic time the quasi acyclicity of a function given by a Horn CNF, and a graph based algorithm is proposed for the quadratic time minimization of quasi acyclic Horn functions     

基于系数矩阵变换的最优MPRM求解方法

针对多输出布尔函数,给出一种求解混合极性Reed-Muller(MPRM)的系数矩阵变换算法。以MPRM中的乘积项数为化简标准,采用穷举策略进行极性空间搜索,求解最优MPRM。在MCNC和ISCAS基准电路上的测试结果表明,与采用列表技术相比,该系数矩阵变换算法能平均缩短55.8%的最优MPRM求解时间。     

逻辑函数的双逻辑综合与优化

针对传统布尔逻辑在电路面积优化中存在的不足,提出了一种用传统布尔逻辑和Reed-Muller(RM)逻辑相结合的双逻辑优化算法.通过将原逻辑函数的乘积项转化为不相交乘积项,并利用不相交乘积项的位操作,将逻辑函数的覆盖分成2个部分,使之分别适合布尔逻辑综合和RM逻辑综合;同时提出了适合双逻辑函数的逻辑功能验证方法.双逻辑优化算法用C语言编程实现并用MCNC标准电路进行测试.实验结果表明,与单一的布尔逻辑综合结果相比,在绝大多数情况下文中算法可使电路面积获得进一步优化.     

Burrows-Wheeler post-transformation with effective clustering and interpolative coding

Lossless compression methods based on the Burrows-Wheeler transform (BWT) are regarded as an excellent compromise between speed and compression efficiency: they provide compression rates close to the PPM algorithms, with the speed of dictionary-based methods. Instead of the laborious statistics-gathering process used in PPM, the BWT reversibly sorts the input symbols, using as the sort key as many following characters as necessary to make the sort unique. Characters occurring in similar contexts are sorted close together, resulting in a clustered symbol sequence. Run-length encoding and Move-to-Front (MTF) recoding, combined with a statistical Huffman or arithmetic coder, is then typically used to exploit the clustering. A drawback of the MTF recoding is that knowledge of the character that produced the MTF number is lost. In this paper, we present a new, competitive Burrows-Wheeler posttransform stage that takes advantage of interpolative coding—a fast binary encoding method for integer sequences, being able to exploit clusters without requiring explicit statistics. We introduce a fast and simple way to retain knowledge of the run characters during the MTF recoding and use this to improve the clustering of MTF numbers and run-lengths by applying reversible, stable sorting, with the run characters as sort keys, achieving significant improvement in the compression rate, as shown here by experiments on common text corpora.     

在文本压缩中联合使用LZSS和LZW

本文分析了LZ77和LZ78算法在文本压缩中各自的长处和不足,以它们的实用算法LZSS和LZW的中文文本改进算法LZSSCH和LZWCH为基础,设计了联合使用LZ77和LZ78原理的LZSWCH算法。算法具有良好的通用性、实时性,对9个各种长度的样本文本文件取得的压缩比均高于LZSS和LZW,高出幅度分别达到6～19％。算法无须任何预处理,并可用于压缩其它文字的文本文件。     

Double encoding—a technique for reducing storage requirement of text

Many recent advances have been made in data storage and communications media. However, the explosive proliferation of information and the continuous growth of data applications are outgrowing any technological advances in storage devices and communications tools. Data compression offers an attractive approach to alleviate many of the problems associated with data proliferation. In this paper, we present a new double compression scheme for text, program source and documentation files. The first phase of compression is a dictionary-based method that also uses run-length encoding. The second phase of compression is based on utilizing the distributional and correlational properties of the output of the first phase. The technique achieves high degrees of compression and is further enhanced by the hardware assistance that VLSI technology will eventually offer to the realization of data compression techniques.     

海量教育资源中小文件的存储研究

Hadoop作为成熟的分布式云平台,能提供可靠高效的存储服务,常用来解决大文件的存储问题,但在处理海量小文件时效率显著降低。提出了基于Hadoop的海量教育资源中小文件的存储优化方案,即利用教育资源小文件间的关联关系,将小文件合并成大文件以减少文件数量,并用索引机制访问小文件及元数据缓存和关联小文件预取机制来提高文件的读取效率。实验证明,以上方法提高了Hadoop文件系统对小文件的存取效率。     

基于混沌和运动矢量的视频水印算法*

针对新一代视频压缩标准H.264,提出一种基于混沌置乱以及运动矢量域的视频水印方案.该方案在运动矢量域自适应嵌入水印和提取经过混沌置乱的水印信息,再经过置乱逆变换恢复得到原水印信息.混沌序列的伪随机性和初值敏感性为水印的安全性提供了保证.实验结果表明,主客观视频质量都与原始视频序列相当,码率误差小.     

Algorithms for optimal partial matching of free-form objects with scaling effects

A free-form object matching problem is addressed in this paper. Two methods are proposed to solve a partial matching problem with scaling effects and no prior information on correspondence or the rigid body transformation involved. The first method uses umbilical points, which behave as fingerprints of a surface and their qualitative properties can be used for matching purposes. The second method uses an optimization scheme based on the extension of the KH curvature matching method [Comput. Aided Design 35 (2003) 913], first introduced in the context of a matching problem without scaling effects. Two types of curvatures, the Gaussian and the mean curvatures, are used to establish correspondences between two objects. The curvature matching method is formulated in terms of minimization of an objective function depending on the unknown scaling factor, and the rigid body transformation parameters. The accuracy and complexity of the proposed methods as well as the convergence for the optimization approach are analyzed. Examples illustrate the two methods.     

Exploiting Regularities for Boolean Function Synthesis

The "regularity" of a Boolean function can be exploited for decreasing its minimization time. It has already been shown that the notion of autosymmetry is a valid measure of regularity, however such a notion has been studied thus far either in the theoretical framework of self-dual Boolean functions, or for the synthesis of a particular family of three-level logic networks. In this paper we show that the degree of autosymmetry of an arbitrary function can be computed implicitly in a very efficient way, and autosymmetry can then be exploited in any logic minimization context. Our algorithms make crucial use of Binary Decision Diagrams. A set of experimental results on the synthesis of standard benchmark functions substantiates the practical relevance of our theoretical results.     

Context-based embedded image compression using binary wavelet transform

Binary wavelet transform (BWT) has several distinct advantages over the real wavelet transform (RWT), such as the conservation of alphabet size of wavelet coefficients, no quantization introduced during the transform and the simple Boolean operations involved. Thus, less coding passes are engaged and no sign bits are required in the compression of transformed coefficients. However, the use of BWT for the embedded grayscale image compression is not well established. This paper proposes a novel Context-based Binary Wavelet Transform Coding approach (CBWTC) that combines the BWT with a high-order context-based arithmetic coding scheme to embedded compression of grayscale images. In our CBWTC algorithm, BWT is applied to decorrelate the linear correlations among image coefficients without expansion of the alphabet size of symbols. In order to match up with the CBWTC algorithm, we employ the gray code representation (GCR) to remove the statistical dependencies among bi-level bitplane images and develop a combined arithmetic coding scheme. In the proposed combined arithmetic coding scheme, three highpass BWT coefficients at the same location are combined to form an octave symbol and then encoded with a ternary arithmetic coder. In this way, the compression performance of our CBWTC algorithm is improved in that it not only alleviate the degradation of predictability caused by the BWT, but also eliminate the correlation of BWT coefficients in the same level subbands. The conditional context of the CBWTC is properly modeled by exploiting the characteristics of the BWT as well as taking advantages of non-causal adaptive context modeling. Experimental results show that the average coding performance of the CBWTC is superior to that of the state-of-the-art grayscale image coders, and always outperforms the JBIG2 algorithm and other BWT-based binary coding technique for a set of test images with different characteristics and resolutions.     

海量样本数据集中小文件的存取优化研究

针对Hadoop分布式文件系统（Hadoop Distributed File System,HDFS）在海量样本数据集存储方面存在内存占用多、读取效率低的问题,以及分布式数据库HBase在存储文件名重复度和类似度高时产生访问热点的问题,结合样本数据集的特点、类型,提出一种面向样本数据集存取优化方案,优化样本数据集中小文件的写入、读取、添加、删除和替换策略。该方案根据硬件配置测得大、小文件的分界点,通过变尺度堆栈算法按样本数据集的目录结构将小文件合并存储至HDFS;结合行键优化策略将文件索引存储在HBase数据表中;搭建基于Ehcache缓存框架的预取机制。实验结果表明,该方案降低了主节点的内存消耗,提高了文件的读取效率,实现了对海量样本数据集中小文件的高效存取。     

Space Efficient Algorithms for the Burrows-Wheeler Backtransformation

The Burrows-Wheeler transformation is used for effective data compression, e.g., in the well known program bzip2. Compression and decompression are done in a block-wise fashion; larger blocks usually result in better compression rates. With the currently used algorithms for decompression, 4n bytes of auxiliary memory for processing a block of n bytes are needed, 0<n<2³². This may pose a problem in embedded systems (e.g., mobile phones), where RAM is a scarce resource.     

Lightweight Boolean Network Tomography Based on Partition of Managed Networks

Boolean network tomography is a promising technique to achieve fault management in networks where the existing IP-based troubleshooting mechanism cannot be used. Aiming to apply Boolean network tomography to fault management, a variety of heuristic methods for configuring monitoring trails and paths have been proposed to localize link failures in managed networks. However, these existing heuristic methods must be executed in a centralized server that administers the entire managed network and the methods present scalability problems when applied to large-scale managed networks. Thus, this paper proposes a novel scheme for achieving lightweight Boolean network tomography in a decentralized manner. The proposed scheme partitions the managed network into multiple management areas and localizes link failures independently within each area. This paper also proposes a heuristic network partition method with the aim of efficiently implementing the proposed scheme. The effectiveness of the proposed scheme is verified using typical fault management scenarios where all single-link failures and all dual-link failures are localized by the least number of monitoring paths on predetermined routes. Simulation results show that the proposed scheme can greatly reduce the computational load on the fault management server when Boolean network tomography is deployed in large-scale managed networks. Furthermore, the degradation of optimality in the proposed scheme can be mitigated in comparison with a centralized scheme that utilizes heuristics to reduce the computational load on the centralized server.     

基于图像重构的MNIST对抗样本防御算法

随着深度学习的应用普及,其安全问题越来越受重视,对抗样本是在原有图像中添加较小的扰动,即可造成深度学习模型对图像进行错误分类,这严重影响深度学习技术的发展。针对该问题,分析现有对抗样本的攻击形式和危害,由于现有防御算法存在缺点,提出一种基于图像重构的对抗样本防御方法,以达到有效防御对抗样本的目的。该防御方法以MNIST为测试数据集,核心思路是图像重构,包括中心方差最小化和图像缝合优化,中心方差最小化只针对图像中心区域进行处理;图像缝合优化将重叠区域纳入补丁块选取的考量,并以补丁块的1/2大小作为重叠区域。使用FGSM、BIM、DeepFool以及C&W攻击方式生成对抗样本来测试两种方式的防御性能,并与现有的3种图像重构防御方式（裁剪与缩放、位深度压缩和JPEG压缩）效果对比。实验结果表明,所提中心方差最小化和图像缝合优化算法,对现有常见对抗样本的攻击起到了较好的防御效果。图像缝合优化对4种攻击算法生成的样本分类正确率都达到了75%以上,中心方差最小化的防御效果在70%左右。而用作对比的3种图像重构算法则对不同攻击算法的防御效果不稳定,整体分类正确率不足60%。所提中心方差最小化...     

基于Ceph存储系统的小文件存储优化方案

针对Ceph存储系统面对小文件存储时存在元数据服务器性能瓶颈、文件读取效率低等问题.本文从小文件之间固有的数据关联性出发,通过轻量级模式匹配算法,提取出关联特征并以此为依据对小文件进行合并,提高了合并文件之间的合理性,并在文件读取时将同一合并文件内的小文件存入客户端缓存来提高缓存读取命中率,经过实验验证本文的方案有效的提高了小文件的访问效率.