File compression

Mass storage systems are finding greater use in scientific computing research environments for retrieving and archiving the large volumes of data generated and manipulated by scientific computations. This paper presents a queuing network model that can be used to carry out capacity planning studies of hierarchical mass storage systems. Measurements taken on a Unitree mass storage system and a detailed workload characterization provided the workload intensity and resource demand parameters for the various types of read and write requests. The performance model developed here is based on approximations to multiclass Mean Value Analysis of queuing networks. The approximations were validated through the use of discrete event simulation and the complete model was validated and calibrated through measurements. The resulting model was used to analyze three different scenarios: effect of workload intensity increase, use of file compression at the server and client, and use of file abstractions.

A noiseless-channel coding system in which the source probabilities change continuously in time is introduced. Using a geometry defined by the second derivative matrix of the information-theoretic entropy function, a bound on the number of excess channel symbols (the redundancy) sent by a retrospective ncoder during a fixed time interval is derived. Results on minimal-cost coding and their implications for a real-time coding algorithm are then explored. Underlying most of the discussion here is the assumption made on the separability of the time scales corresponding to the (high) character ate as compared with the rate of change of the source probabilities. I.

A simple scheme was proposed by Knuth to generate balanced codewords from a random binary information sequence. However, this method presents a redundancy which is twice as that of the full sets of balanced codewords, that is the minimal achievable redundancy. The gap between the Knuth's algorithm generated redundancy and the minimal one is significantly considerable and can be reduced. This paper attempts to achieve this goal through a method based on information sequence candidates. The proposed scheme is suitable for various communication systems as it generates very efficient and less redundant balanced codes.

A simple scheme was proposed by Knuth to generate binary balanced codewords from any information word. However, this method is limited in the sense that its redundancy is twice as that of the full sets of balanced codes. The gap between Knuth's algorithm redundancy and that of the full sets of balanced codes is significantly considerable. This paper attempts to reduce that gap. Furthermore, many constructions assume that a full balancing can be performed without showing the steps. A full balancing refers to the overall balancing of the encoded information together with the prefix. We propose an efficient way to perform full balancing scheme which do not make use of lookup tables or enumerative coding.

Since the Boyer-Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers. These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer-Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.

Analysis of thermal data requires the processing of large amounts of temporal image data. The processing of the data for quantitative information can be time intensive especially out in the field where large areas are inspected resulting in numerous data sets. By applying a temporal compression technique, improved algorithm performance can be obtained. In this study, analysis techniques are applied to compressed and non-compressed thermal data. A comparison is made based on computational speed and defect signal to noise.

Since the Boyer-Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers. These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer-Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.

Here we propose GP-zip3, a system which uses Genetic Programming to find optimal ways to combine standard compression algorithms for the purpose of compressing files and archives. GP-zip3 evolves programs with multiple components. One component analyses statistical features extracted from the raw data to be compressed (seen as a sequence of 8-bit integers) to divide the data into blocks. These blocks are then projected onto a two-dimensional Euclidean space via two further (evolved) program components. K-means clustering is applied to group similar data blocks. Each cluster is then labelled with the optimal compression algorithm for its member blocks. Once a program that achieves good compression is evolved, it can be used on unseen data without the requirement for any further evolution. GP-zip3 is similar to its predecessor, GP-zip2. Both systems outperform a variety of standard compression algorithms and are faster than other evolutionary compression techniques. However, GP-zip2 was still substantially slower than off-the-shelf algorithms. GP-zip3 alleviates this problem by using a novel fitness evaluation strategy. More specifically, GP-zip3 evolves and then uses decision trees to predict the performance of GP individuals without requiring them to be used to compress the training data. As shown in a variety of experiments, this speeds up evolution in GP-zip3 considerably over GP-zip2 while achieving similar compression results, thereby significantly broadening the scope of application of the approach.

This paper surveys a variety of data compression methods spanning almost 40 years of research, from the work of Shannon, Fano, and Huffman in the late 1940s to a technique developed in 1986. The aim of data compression is to reduce redundancy in stored or communicated data, thus increasing effective data density. Data compression has important application in the areas of file storage and distributed systems. Concepts from information theory as they relate to the goals and evaluation of data compression methods are discussed briefly. A framework for evaluation and comparison of methods is constructed and applied to the algorithms presented. Comparisons of both theoretical and empirical natures are reported, and possibilities for future research are suggested

A simple scheme was proposed by Knuth to generate balanced codewords from a random binary information sequence. However, this method presents a redundancy which is twice as that of the full sets of balanced codewords, that is the minimal achievable redundancy. The gap between the Knuth's algorithm generated redundancy and the minimal one is significantly considerable and can be reduced. This paper attempts to achieve this goal through a method based on information sequence candidates.  Index Terms-Balanced code, inversion point, redundancy, running digital sum (RDS), running digital sum from left (RDSL), running digital sum from right (RDSR), information sequence candidates.

In this paper, the construction of binary balanced codes is revisited. Binary balanced codes refer to sets of bipolar codewords where the number of "1"s in each codeword equals that of "0"s. The first algorithm for balancing codes was proposed by Knuth in 1986; however, its redundancy is almost two times larger than that of the full set of balanced codewords. We will present an efficient and simple construction with a redundancy approaching the minimal achievable one

The commonly used data compression techniques do not necessarily provide maximal compression and neither do they define the most efficient framework for transmission of data. In this thesis we investigate variants of the standard compression algorithms that use the strategy of partitioning of the data to be compressed. Doing so not only increases the compression ratio in many instances, it also reduces the maximum data block size for transmission. The partitioning of the data is made using a Markov model to predict if doing so would result in increased compression ratio. Experiments have been performed on text files comparing the new scheme to adaptive Huffman and arithmetic coding methods. The adaptive Huffman method has been implemented in a new way by combining the FGK method with Vitter's implicit ordering of nodes.

Data compression aims to reduce the size of data so that it requires less storage space and less communication channels bandwidth. Many compression techniques (such as LZ77 and its variants) su er from a problem that we call the redundancy caused by the multiplicity of encodings. The Multiplicity of Encodings (ME ) means that the source data may be encoded in more than one way. In its simplest case, it occurs when a compression technique with ME has the opportunity at certain steps, during the encoding process, to encode the same symbol in di erent ways. The Bit Recycling compression technique has been introduced by D. Dubé and V. Beaudoin to minimize the redundancy caused by ME . Variants of bit recycling have been applied on LZ77 and the experimental results showed that bit recycling achieved better compression (a reduction of about 9% in the size of les that have been compressed by Gzip) by exploiting ME . Dubé and Beaudoin have pointed out that their technique could not minimize...

Mass storage systems are finding greater use in scientific computing research environments for retrieving and archiving the large volumes of data generated and manipulated by scientific computations. This paper presents a queuing network model that can be used to carry out capacity planning studies of hierarchical mass storage systems. Measurements taken on a Unitree mass storage system and a detailed workload characterization provided the workload intensity and resource demand parameters for the various types of read and write requests. The performance model developed here is based on approximations to multiclass Mean Value Analysis of queuing networks. The approximations were validated through the use of discrete event simulation and the complete model was validated and calibrated through measurements. The resulting model was used to analyze three different scenarios: effect of workload intensity increase, use of file compression at the server and client, and use of file abstractions.

Our approach to deduplication and compression in cloud computing aims at reduction in storage space and bandwidth usage during file transfers. The design depends on multiple metadata structures for deduplication. Only a copy of the duplicate files is retained while others are deleted. The existence of duplicate files is determined from the metadata. The files are clustered into bins depending on their size. They are then segmented, deduplicated, compressed and stored. Binning restricts the number of segments and their sizes so that it is optimum for each file size. When the user requests a file, compressed segments of the file are sent over the network along with the file-to-segment mapping. These are the uncompressed and combined to create a complete file, hence minimizing bandwidth requirements.

A Huffman code is a particular type of optimal prefix code that is commonly used for loss-less data compression. The process of finding such a code is known as Huffman coding. The output from Huffman's algorithm can be viewed as a variable-length code table for encoding a source symbol. The algorithm derives this table from the estimated probability or frequency of occurrence for each possible value of the source symbol. In this paper, we present a new approach to measure the performance and redundancy that work on two methods of coding like Huffman coding and Minimum Variance Huffman Coding. After getting the code-word for each symbol, we compress it on the basis of its binary values like 0 and 1 using binary coding. This is applied to both the approaches; this process is called as Double Huffman Coding. Finally we produce a better result than Huffman coding.

The bit recycling compression technique has been introduced to minimize the redundancy caused by the multiplicity of encoding feature present in many compression techniques. It has achieved about 9% as a reduction in the size of the files compressed by Gzip. In this paper, we propose to adapt bit recycling to arithmetic code instead of Huffman code. This adaptation enables bit recycling to achieve better compression and a much wider applicability. A theoretical analysis that estimates the average amount of data compression that can be achieved by this adaptation is presented as well.

We consider the problem of source coding. We investigate the cases of known and unknown statistics. The efficiency of the compression codes can be estimated by three characteristics: 1) the rebundancy (r), defined as the maximal difference between the average codeword length and Shannon entropy in case the letters are generated by a Bernoulli source;

Research has been a challenge for most academic institutions. There are tools available to find research articled, but It is still hard to get inputs from experts, or experienced people, since most of the time researchers are assigned with just one adviser to guide them in their study. The study proposed to develop an application that will store copies of research articles by students and faculty, which will act as a digital library. It will also allow collaboration between different users, through their inputs and suggestions, or even endorse other user as an expert in a certain field of study. The study will use a ranking algorithm based on different factors, to rank different articles. Articles can be searched using keywords which will be parsed, using Boyer-Moore-Horspool string pattern search algorithm. The study will also use compression algorithm to improve application and server performance. With this, the study aims to develop a more effective and efficient tool in conducting research,
 

A novel fast recursive coding technique is proposed. It operates with only integer values not longer 8 bits and is multiplication free. Recursion the algorithm is based on indirectly provides rather effective coding of symbols for very large alphabets. The code length for the proposed technique can be up to 20-30% less than for arithmetic coding and, in the worst case it is only by 1-3% larger.

A novel fast recursive coding technique is proposed. It operates with only integer values not longer 8 bits and is multiplication free. Recursion the algorithm is based on indirectly provides rather effective coding of symbols for very large alphabets. The code length for the proposed technique can be up to 20-30% less than for arithmetic coding and, in the worst case it is only by 1-3% larger.

The web has become a resourceful tool for almost all domains today. Search engines prominently use inverted indexing technique to locate the web pages having the users query. The performance of inverted index fundamentally depends upon the searching of keyword in the list maintained by search engine. Text matching is done with the help of string matching algorithm. It is important to any string matching algorithm to locate quickly the occurrences of the user specified pattern in large text. In this paper a new
string matching algorithm for keyword searching is proposed. The proposed algorithm relies on new technique based on pattern length and FML (First-Middle-Last) character match. This proposed algorithm is analysed and implemented. The extensive testing and comparisons are done with Boyer-Moore, Naïve, Improved Naïve, Horspool and Zhu Takaoka. The result shows that the proposed
algorithm takes less time than other existing algorithm.

Our approach to deduplication and compression in cloud computing aims at reduction in storage space and bandwidth usage during file transfers. The design depends on multiple metadata structures for deduplication. Only a copy of the duplicate files is retained while others are deleted. The existence of duplicate files is determined from the metadata. The files are clustered into bins depending on their size. They are then segmented, deduplicated, compressed and stored. Binning restricts the number of segments and their sizes so that it is optimum for each file size. When the user requests a file, compressed segments of the file are sent over the network along with the file-to-segment mapping. These are the uncompressed and combined to create a complete file, hence minimizing bandwidth requirements.