We propose a family of Fibonacci-style codes, combining the advantages of higher-order Fibonacci numeration systems and the flexibility of binary mixed-digit codes. We establish the theoretical foundation of these new codes, proving a generalization of the Kraft inequality for prefix-free codes on mixed-digit numeration systems and the completeness of the new family of Fibonacci codes. Experiments on natural language text show that the proposed codes provide a coding structure that can adapt to various data distributions and capable of achieving superior compression ratios.

Previous work on non-binary Fibonacci codes is extended by the presentation of a new family of universal codes having the additional advantage of admitting more codewords for a given large enough length. These denser codes also share the other properties of instantaneous decipherability and robustness against transmission errors, and are proposed as an alternative to compress lists of very large integers, like those used in cryptography.

This paper extends the forward-looking approach to handle alphabets of words, which leads to further compression savings. It introduces an efficient encoding for the header information, specifically the exact frequencies of the alphabet elements. Moreover, an alternative ordering method for compressing word-based dictionaries is proposed, emphasizing the benefits of forward-looking adaptive compression. Experimental results demonstrate the effectiveness of the proposed approach.

A Compression Cryptosystem is a single coding process, the output of which is both reduced in space and secure against unauthorized decoding. Considering Huffman coding, this pa-per proposes to apply repeatedly minor changes to the compression model, with negligible deterioration of its optimality. The cumulative impact of a large number of such changes leads to completely different ciphertexts, which can be decoded only if a given secret key is known. The security of the system is based on the NP-completeness of a problem related to breaking the code. Several variants are suggested, and their results are tested in various settings, including for security against chosen plaintext attacks.

Unlike the uniform treatment of symbols in different locations of an input file, a new approach is taken in the weighted dynamic compression method suggested in [1], which assigns higher priority to closer to be encoded symbols by means of an increasing weight function. The weighted method is especially suited for the encoding of files with locally skewed distributions. Empirical results have shown that weighted techniques can improve beyond the lower bound given by the entropy for static encoding.

A particular form of lossless data compression is known as deduplication, which is often applied in a scenario in which a large data repository is given and we wish to store a new, updated, version of it, in which the changes account only for a tiny fraction of the accumulated information. The idea is then to find duplicated parts and store only one copy P of them; the second and subsequent occurrences of these parts can then be replaced by pointers to P. One of the approaches to solve the problem is based on classical hashing with the property that when changing even a single bit of the file, the resulting hash value should be completely different, which may not be appropriate in our case. This lead to the design of what could be called an Approximate Hash function. The current work is an extension, which applies similar techniques to string processing problems arising in Bioinformatics. We concentrate on the following two problems. The first problem is that of clustering a large collection of DNA strings into sub-collections forming clusters, in the sense that strings assigned to the same cluster may be considered as similar for practical biological purposes, whereas strings of different clusters are different enough to be judged not originating from the same source. The second problem is that of locating a single string within a large collection on the basis of one of its fragments, or rather, one of its fragments that has undergone some limited number of mutations. We show how our notion of an approximate hash may be adapted to these and similar problems. The idea is to produce a signature encapsulating the main features of the strings in a small number of bits by devising an occurrence map of the various substrings of length k, called k-mers, for k ≥ 1. The ith bit of the signature, corresponding to the i-th ordered k-mer, will be set to 1 if and only if the number of occurrences of this i-th k-mer within the given string is larger than some predetermined threshold t_k, depending on their average number of occurrences. This definition tries to catch underlying similarities, but to remain flexible enough to allow some fluctuations. The new techniques have been applied on artificial and real-life DNA strings, and compared to state of the art clustering methods. The outcome of the new procedure is very similar to the clustering and search results obtained by accurate tools, but in much less time and with less required memory.

A binary Write Once Memory (WOM) device is a storage mechanism in which a 0-bit can be overwritten much more easily than a 1-bit. A famous example is the flash memory technology, where 0→1 transitions are allowed, but 1 → 0 transitions require a costly erase procedure and are therefore prohibited. A WOM code is a coding scheme that permits multiple writes to the WOM without violating the WOM rule. The properties of WOM attracted attention even before flash memory was invented. Rivest and Shamir [2] proposed an elegant WOM code that uses 3 bits to write two rounds of any combination of 2 bits. As alternative, context sensitive rewriting codes have been considered [1], in which the new information stored in the second round utilizes certain portions of the output of the first round for unambiguous reuse. Some of these encodings are based on Fibonacci Codes, whose primary relevant property is that they contain no adjacent 1-bits, except as suffixes of all of their codewords.

Extending recently suggested methods, a new dynamic compression algorithm is proposed, which assigns larger weights to characters that have just been coded by means of an increasing weight function. Empirical results present its efficient compression performance, which, for input files with locally skewed distributions, can improve beyond the lower bound given by the entropy for static encoding, at the price of slower running times for compression, and comparable time for decompression.

Huffman coding is known to be optimal in case the alphabet is known in advance, the set of codewords is fixed and each codeword consists of an integral number of bits. If one of these conditions is violated, optimality is not guaranteed. In the dynamic variant of Huffman coding the encoder and decoder maintain identical copies of the model; at each position, the model consists of the frequencies of the elements processed so far. After each processed element σ, the model is updated by incrementing the frequency of σ by 1, while the other frequencies remain the same. An enhanced dynamic Huffman coding named forward looking coding [2] starts with the full frequencies, similar to the static variant, and then decreases them progressively. For this method, after each processed element σ, the model is altered by decrementing the frequency of σ by 1, while the other frequencies remain the same. Forward looking Huffman coding has been shown to be always better by at least m-1 bits than static Huffman coding. A hybrid method, exploiting both the classical backward and the new forward approaches is proposed in FKS, and has been shown to be always at least as good as the forward looking Huffman coding. If the model is learned adaptively, as in the traditional backward looking codings, no description of the model is needed, since the model is updated by the encoder and the decoder in synchronization. However, in the other mentioned versions, the details of the chosen model on which the method relies, are needed for the decoding and should be adjoined to the compressed file, for example, as an header. The contribution of this work is as follows: we first define a new generic coding method which we call weighted coding, encompassing all mentioned variants (static, forward and backward) as special cases. Second, a new special case called positional is suggested, and shown to be always at least as good as the forward looking coding. Third, we present empirical results that show practical improvements of the proposed method, even when the encoded file includes the model description. It is important to stress that all the methods can in fact be applied to every adaptive coding technique, in particular to arithmetic coding or PPM.

The famous Fibonacci series defined by F0= 0, F1= 1 and Fi=Fi-1+ Fi-2, for i ≥ 2, has contributed to several applications in Data Compression. Quite a few encodings have been suggested that are based on the properties of the Fibonacci sequence, and can be used as alternatives to fixed length codes. Interest in the Fibonacci sequence has shifted also to other adjacent areas, such as compressed matching[1], in which a pattern P is to be located in a text T, which is assumed to be given in some compressed form. The advantage of using Fibonacci codes in this context is the 11 separator, that acts as a border between adjacent codewords. Compressed matching is not limited to text files only, and in [3] the Fibonacci code was adapted to tools in image compression. Codes of order d are related to d-ary trees and there are several motivations for using such trees with d > 2. A d-ary tree is of height [logd|Σ|], which may improve the processing time for larger d, e.g., in higher order Wavelet trees, where instead of storing binary bitmaps in every internal node, one rather stores sequences over the alphabet {1,...,d}. Ferragina et al.[2] show how to handle rank and select of such sequences, that improve both time and space complexities. A Fibonacci Wavelet tree, in which pruning was applied for additional savings, was defined in [4]. This data structure has then been generalized to higher-order of another kind, namely by the use of higher order Fibonacci Codes in which each element of the underlying sequence is the sum of the k preceding ones, for k ≥ 2. The corresponding binary code has the property that there is no occurrence of a string of m consecutive 1s. We extend the binary Fibonacci code to d-ary codes, with d ≥ 2. This is motivated by future technological developments in which the basic unit of storage will not be just a 2-valued bit, but possibly an element that is able to distinguish between d different values. The proposed codes are prefix-free, complete and more robust than Huffman codes. Experimental results illustrate that the compression efficiency of non-binary Fibonacci codes are very close to the savings achieved by the corresponding non-binary Huffman coding of the same order.

Rewriting codes for flash memory enable the multiple usage of the same storage space, under the constraint that 0-bits can be changed into 1s, but not vice versa. Context sensitive rewriting codes extend this idea by incorporating also information gathered from surrounding bits. Several new and better context sensitive rewriting codes are presented and analyzed. Empirical simulations show a good match with the theoretical results.

Dynamic compression methods continuously update the model of the underlying text file to be compressed according to the already processed part of the file, assuming that such a model accurately predicts the distribution in the remaining part. Since this premise is not necessarily true, we suggest to update the model only selectively. We give empirical evidence that this hardly affects the compression efficiency, while it obviously may save processing time and allow the use of the compression scheme for cryptographic applications.

It seems reasonable to expect from a good compression method that its output should not be further compressible, because it should behave essentially like random data. We investigate this premise for a variety of known compression techniques, and find that, surprisingly, there is much variability in the randomness, depending on the chosen method. Arithmetic coding seems to produce perfectly random output, whereas that of Huffman or Ziv-Lempel coding still contains many dependencies. In particular, the output of Huffman coding has already been proven to be random under certain conditions, and we show here that arithmetic coding may produce an output that is identical to that of Huffman.

Huffman coding is known to be optimal, yet its dynamic version may yield smaller compressed files. The best known bound is that the number of bits used by dynamic Huffman coding in order to encode a message of n characters is at most larger by n bits than the number of bits required by static Huffman coding. In particular, dynamic Huffman coding can also generate a larger encoded file than the static variant, though in practice the file might often, but not always, be smaller. We propose here a new dynamic Huffman encoding approach, that provably always performs at least as good as static Huffman coding, and may be better than the standard dynamic Huffman coding for certain files.

Comparing pairs of ontologies in the same biomedical content domain often uncovers surprising differences. In many cases these differences can be characterized as “density differences,” where one ontology describes the content domain with more concepts in a more detailed manner. Using the Unified Medical Language System across pairs of ontologies contained in it, these differences can be precisely observed and used as the basis for importing concepts from the ontology of higher density into the ontology of lower density. However, such an import can lead to an intuitive loss of information that is hard to formalize. This paper proposes an approach based on information theory that mathematically distinguishes between different methods of concept import and measures the associated avoidance of information loss.

Hierarchical Clustering is widely used in Machine Learning and Data Mining. It stores bit-vectors in the nodes of a k-ary tree, usually without trying to compress them. We suggest a double usage of the extorting operations defining the Hamming distance used in the clustering process, extending it also to be used to transform the vector in one node into a more compressible form, as a function of the vector in the parent node. Compression is then achieved by run-length encoding, followed by optional Huffman coding, and we show how the compressed file may be processed directly, without decompression.

We suggest the usage of Fibonacci Codes instead of Elias' C γ code. The implementation requires 1.44 n Hk+n+o(n) bits of space, while retaining the searching functionalities. We used a less common variant of the Fibonacci code which was found to be often preferable for the encoding. This variant is constructed from the traditional Fibonacci code by omitting the rightmost 1-bit of every codeword and dropping those codewords that start with 0. As a result, every codeword now starts and ends with a 1-bit, so codeword boundaries may still be detected by the occurrence of the string 11. In order to obtain Φ[i], i mod b codewords need to be decoded. The traditional approach is to decode each codeword and add the decoded values. One of the advantages of using a Fibonacci based representation of the integers is that it is possible to perform this addition directly on the compressed form, without individually decoding each summand.

In previous work we have suggested a data structure based on pruning a Huffman shaped Wavelet tree according to the underlying skeleton Huffman tree. This pruned Wavelet tree was especially designed to support faster random access and save memory storage, at the price of less effective rank and select operations, as compared to the original Huffman shaped Wavelet tree. In this paper we improve the pruning procedure and give empirical evidence that when memory storage is of main concern, our suggested data structure outperforms other direct access techniques such as those due to Külekci, DACs and sampling, with a slowdown as compared to DACs and fixed length encoding.

Writing data on flash memory is asymmetric in the sense that it is possible to change a 0 into a 1-bit, but erasing a 1 back to value 0 is much more expensive and can only be done in blocks. This has triggered the development of rewriting codes in which new data can overwrite the old one, subject to the constraint of never changing a 1 into a zero.

Given a file T, and the Huffman encoding of its elements, we present a data structure that enables direct access to the i-th element of T by reordering the bits of the compressed file and using some additional space. When compared to a Wavelet tree for Huffman Codes, our different reordering of the bits requires less additional storage overhead by reducing the need for auxiliary rank structures, while improving processing time for extracting the ith element of T.

Semantic relationships are important components of ontologies. Specifying these relationships is work-intensive and error-prone when done by experts. Discovering domain concepts and strongly related pairs of concepts in a completely automated way from English text is an unresolved problem. This paper uses index terms from a textbook as domain concepts and suggests pairs of concepts that are likely to be connected by strong semantic relationships. Two textbooks on Cyber Security were used as testbeds. To show the generality of the approach, the index terms from one of the books were used to generate suggestions for where to place semantic relationships using the bodies of both textbooks. A good overlap was found.

A basic property of flash memory is that a 0-bit can be changed into a 1-bit, but not vice-versa, which severely limits the possibilities of reusing storage space with new data. A new coding method is presented that enables double use of the memory, effectively expanding the combined amount of stored data by 2.8 to 19.4%. This can then be used as a compression booster, adding an additional layer to, and improving the compression of some rewriting methods that are not context sensitive.

The problem of compressing a large collection of feature vectors so that object identification can further be processed on the compressed form of the features is investigated. The idea is to perform matching against a query image in the compressed form of the feature descriptor vectors retaining the metric. Specifically, we concentrate on SIFT (Scale Invariant Feature Transform), a known object detection method. Given two SIFT feature vectors, we suggest achieving our goal to compress them using a lossless encoding for which the pair wise matching can be done directly on the compressed files, by means of a Fibonacci code.

A new lossless image compression algorithm is presented, aimed at mask less lithography systems with mostly right-angled regular structures. Since these images appear often in slightly rotated form, an algorithm dealing with this special case is suggested, which improves performance relative to the state of the art alternatives.

The String-to-Dictionary Matching Problem is defined, in which a string is searched for in all the possible concatenations of the elements of a given dictionary, with applications to compressed matching in variable to fixed length encodings, such as Tunstall's. An algorithm based on suffix trees is suggested and experiments on natural language text are presented suggesting that compressed search might use less comparisons for long enough patterns, in spite of a potentially large number of encodings.

Recent publications advocate the use of various variable length codes for which each codeword consists of an integral number of bytes in compression applications using large alphabets. This paper shows that another tradeoff with similar properties can be obtained by Fibonacci codes. These are fixed codeword sets, using binary representations of integers based on Fibonacci numbers of order m ges 2. Fibonacci codes have been used before, and this paper extends previous work presenting several novel features. In particular, they compress better and are more robust, at the price of being slower.

A standard way of implementing Huffman's optimal code construction algorithm is by using a sorted sequence of frequencies. Using only partial order may speed up the code construction, which is important in some applications, at the cost of possibly increasing the size of the encoded file.

Abstract XML documents combine features from classical IR systems allowing free text, with explicit structures as in databases. Many query languages have been specially designed for IR applications on XML documents. This work concentrates on a special type of language for which the problem of processing queries including metrical constraints is investigated. The main question is how to define the distance between terms in different locations of the XML tree in an intuitively justifiable way, without jeopardizing the ability to get good retrieval results in terms of recall and precision. A new definition is given and its usefulness is shown on several examples from the INEX collection.

This work deals with ways to accelerate the processing, concentrating on the decoding of Fibonacci encoded texts, by adapting a method originally suggested for the fast decoding of Huffman codes, which suffer from the same problem as the variable length Fibm codes. The method uses a set of partial decoding tables that are prepared in advance and depend only on the code, not on the actual text to be decoded, by means of which the decoding is then performed by blocks of k bits at a time, rather than bit per bit

We explore the full compressed delta encoding problem in compressed texts, defined as the problem of constructing a delta file directly from the two given compressed files, without decompressing. We concentrate on the case where the given files are compressed using LZSS and propose solutions for the special cases involving substitutions only

Summary form only given. Multilingual text compression depends primarily on the ability to match the corresponding parts of related texts by identifying semantic correspondences across the various sub-texts, a task generally referred to as text alignment. Savings in storage space can be obtained by replacing words and phrases with pointers to their translations, determined by any alignment algorithm. The suggested method was tested on an English-French corpus of the European Union. The French part was compressed using pointers towards the English part. The obtained compression rate (22.0%) is similar to the performances of Bzip and HuffWord and better than that of Gzip. However, Bzip and Gzip's performances degrade when small sub-sections are processed separately, which makes them inappropriate for systems which often decode only small pieces.

Summary form only given. We introduce a new model of differencing encoding, that of compressed differencing. Given two files for which at least one is in compressed form, the goal is to create a third file which is the delta file of the two original files, in time proportional to the size of the input, that is, without decompressing the compressed files. We also present an optimal algorithm in terms of processing time for constructing the delta encoding when both files are compressed using LZW. To improve the compression performance of the delta file, we check whether successive ordered pairs refer to successive substrings and can thus be combined

New variants of partial decoding tables are presented that can be used to accelerate the decoding of texts compressed by any prefix code, such as Huffman's. They are motivated by a variety of tradeoffs between decompression speed and required auxiliary space, and apply to any shape of the tree, not only the canonical one. Performance is evaluated both analytically and by experiments, showing that the necessary tables can be reduced drastically, with hardly any loss in performance.

Summary form only given. We concentrate on two-dimensional compressed matching in which the given encoded text is an image encoded by the standard JPEG baseline scheme and the pattern consists of a image fragment we are looking for. Baseline JPEG uses a static Huffman code, without which compressed matching would not always be possible, since our underlying assumption is that all occurrences of the pattern are encoded by the same binary sequence. The compressed matching starts by encoding the pattern using the same JPEG algorithm as the one used for the original image. The search process has to be repeated for each matching attempt.

This paper discusses the semilossless text compression. The data compression method is classified into lossless and lossy methods. Lossless methods include usually those applied on text files or other data for which no loss of information can be tolerated, lossy techniques are generally applied to image files as well as to video and audio data, for which the overall knowledge a user might extract does not seem significantly reduced even if a part of the data is omitted.

Summary form only given. A novel compression method that allows the selective decoding of small portions of the compressed file is described. The method constructs a static context tree, which is used to transform the original input into a more compressible form. However, the RCT algorithm is suggested to split the data into pieces, even quite small ones, without too much affecting the compression ratio.

We introduce two new methods to represent a prefix omission method (POM) file so that direct search can be done in these compressed dictionaries. The processing time is typically twice as fast for the Fibonacci variant than for the Huffman based algorithm, and also compared to decoding a Huffman encoded POM file and searching on the uncompressed version. We see that in the case of small files, which is the important application since dictionaries are usually kept in small chunks, the Fibonacci variant is much faster than decoding and searching or than the POM-Huffman method. Even though the compression performance might be slightly inferior to the character version of Huffman (but still generally better than the bit version), this might well be a price worth paying for faster processing.

The possibility of locating a pattern directly in a text which has been encoded by a static Huffman code is investigated. The main problem is one of synchronization, as an occurrence of the encoded pattern in the encoded text does not necessarily correspond to an occurrence of the pattern in the text. A simple algorithm is suggested which reduces the number of false hits. The probability of false matches is analyzed and empirically tested.

A practical adaptive compression algorithm based on LZSS is presented, which is especially constructed to solve the compressed pattern matching problem, i.e., pattern matching directly in a compressed text without decompressing.

A simple parallel algorithm for decoding a Huffman encoded file is presented, exploiting the tendency of Huffman codes to resynchronize quickly in most cases. An extention to JPEG decoding is mentioned.

Methods for the correct and efficient handling of annotations in a full-text retrieval system were investigated. The problem with annotations is that they cannot be treated as regular text, since this would disrupt proximity searches, but on the other hand, they cannot be ignored, as they may carry important information. Moreover, in some cases, a user may wish to restrict a search to prespecified subsets of annotations. We suggest a new way of processing the database to overcome the above dilemma.

Information Retrieval Systems identify content bearing words, and possibly also assign weights, as part of the process of formulating requests. For optimal retrieval efficiency, it is desirable that this be done automatically. This article defines the notion of serial clustering of words in text, and explores the value of such clustering as an indicator of a word's bearing content. This approach is flexible in the sense that it is sensitive to context: a term may be assessed as content-bearing within one collection, but not another. Our approach, being numerical, may also be of value in assigning weights to terms in requests. Experimental support is obtained from natural text databases in three different languages. © 1998 John Wiley & Sons, Inc.

Many of the most effective compression methods involve complicated models. Unfortunately, as model complexity increases, so does the cost of storing the model itself. This paper examines a method to reduce the amount of storage needed to represent a Markov model with an extended alphabet, by applying a clustering scheme that brings together similar states. Experiments run on a variety of large natural language texts show that much of the overhead of storing the model can be saved at the cost of a very small loss of compression efficiency.

An earlier paper developed a procedure for compressing concordances, assuming that all alements occurred independently. The models introduced in that paper are extended here to take the possiblity of clustering into account. The concordance is conceptualized as a set of bitmaps, in which the bit locations reporesent documents, and the one-bits represent the occurrence of given terms. Hidden Markov Models (HMM's) are used to describe the clustering of the one-bits. However, for computational reasons, the HMM is approximated by traditional Markov models. A set of criteria is developed to constrain the allowable set of n -state models, and a full inventory is given for n ≤ 4. Graph-theoretic reduction and complementation operations are defined among the various models and are used to provide a structure relating the models studied. Finally, the new methods were tested on the concordances of the English Bible and of two of the world's largest full-text retrieval systems: the Tre´sor de la Langue Franc¸aise and the Responsa Project.

InformationRetrieval Systems typically distinguish between content bearing words and terms on a stop list.But "content-bearing " is relative to a collection.For optimal retrieval efficiency, it is desirable to have automated methods for custom building a stop list.This paper defines the notion of serial clustering of words in text, and explores the value of such clustering as an indicator of a word bearing cent ent.The numerical measures we propose may also be of value in assigning weights to terms in requests.Experimental support is obtained from natural text databases in three different languages.

An efficient variant of an optimal algorithm is presented, which, in the context of a large dynamic fulltext information retrieval system, reorganizes data that has been compressed by an on-the-fly compression method based on LZ77, into a more compact form, without changing the decoding procedure.The algorithm accelerates a known technique based on a reduction to a graph-theoretic problem, by reducing the size of the graph, without affecting the optimality of the solution.The new method can thus effectively improve any dictionary compression scheme using a static encoding method.

An earlier paper developed a procedure for compressing concordances, assuming that all elements occurred independently. In this paper, the earlier models are extended to take the possibility of clustering into account. The authors suggest several models adapted to concordances of large full-text information retrieval systems, which are generally subject to clustering.>

Much of compression theory assumes knowledge of exact statistics of the alphabet being encoded. In practice, codes are often based on approximations of true statistics. This paper examines the consequences of random fluctuations on coding efficiency. It shows that exact statistics permit more efficient encoding, but when the error is due to random fluctuation, the savings are small and of magnitude of the extra table needed for decoding.>

Article Is Huffman coding dead? (extended abstract) Share on Authors: Abraham Bookstein View Profile , Shmuel T. Klein View Profile , Timo Raita View Profile Authors Info & Claims SIGIR '93: Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrievalJuly 1993 Pages 80–87https://doi.org/10.1145/160688.160697Online:01 July 1993Publication History 5citation1,017DownloadsMetricsTotal Citations5Total Downloads1,017Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors discuss concordance compression using the framework now customary in compression theory. They begin by creating a mathematical model of concordance generation, and then use optimal compression engines, such as Huffman or arithmetic coding, to do the actual compression. It should be noted that in the context of a static information retrieval system, compression and decompression are not symmetrical tasks. Compression is done only once, while building the system, whereas decompression is needed during the processing of every query and directly affects the response time. One may thus use extensive and costly preprocessing for compression, provided reasonably fast decompression methods are possible. Moreover, compression is applied to the full files (text, concordance, etc.), but decompression is needed only for (possibly many) short pieces, which may be accessed at random by means of pointers to their exact locations. Therefore the use of adaptive methods based on tables that systematically change from the beginning to the end of the file is ruled out. However, their concern is less the speed of encoding or decoding than relating concordance compression conceptually to the modern approach of data compression, and testing the effectiveness of their models.>

This paper considers the problem of compressing a set of bit maps, exploring the possibility of exploiting the structure between as well as within them to compress the whole bit-table. It describes several particularly simple models of bit occurrence. Two of these are based on detailed assumptions of bit-independence. The third uses regression models. The strategy of separating model construction and compression method continues the well-established practice of basing compression on an explicit model of message generation. Flexible encoding is distinguished from adaptive and static approaches.>

block is then encoded using Huffman or arithmetic coding.Preliminary experimental results indicate improvements over previous methods.

Bitmaps are data structures occurring often in information retrieval. They are useful; they are also large and expensive to store. For this reason, considerable effort has been devoted to finding techniques for compressing them. These techniques are most effective for sparse bitmaps. We propose a preprocessing stage, in which bitmaps are first clustered and the clusters used to transform their member bitmaps into sparser ones, that can be more effectively compressed. The clustering method efficiently generates a graph structure on the bitmaps. The results of applying our algorithm to the Bible is presented: for some sets of bitmaps, our method almost doubled the compression savings.

Text compression is of considerable theoretical and practical interest. It is, for example, becoming increasingly important for satisfying the requirements of fitting a large database onto a single CD-ROM. Many of the compression techniques discussed in the literature are model based. We here propose the notion of a formal grammar as a flexible model of text generation that encompasses most of the models offered before as well as, in principle, extending the possibility of compression to a much more general class of languages. Assuming a general model of text generation, a derivation is given of the well known Shannon entropy formula, making possible a theory of information based upon text representation rather than on communication. The ideas are shown to apply to a number of commonly used text models. Finally, we focus on a Markov model of text generation, suggest an information theoretic measure of similarity between two probability distributions, and develop a clustering algorithm based on this measure. This algorithm allows us to cluster Markov states, and thereby base our compression algorithm on a smaller number of probability distributions than would otherwise have been required. A number of theoretical consequences of this approach to compression are explored, and a detailed example is given.

: The emergence of the CD-ROM as a storage medium for full-text databases raises the question of the maximum size database that can be contained by this medium. As an example, the problem of storing the Tr'esor de la Langue Fran¸caise on a CD-ROM is examined in this paper. The text alone of this database is 700 MB long, more than a CD-ROM can hold. But in addition the dictionary and concordance needed to access this data must be stored. A further constraint is that some of the material is copyrighted, and it is desirable that such material be difficult to decode except through software provided by the system. Pertinent approaches to compression of the various files are reviewed and the compression of the text is related to the problem of data encryption: specifically, it is shown that, under simple models of text generation, Huffman encoding produces a bit-string indistinguishible from a representation of coin flips. Categories and Subject Descriptors: E.3 E.4 H.3.2 J.5 General terms: ...

The emergence of the CD-ROM as a storage medium for full-text databases raises the question of the maximum size database that can be contained by this medium. As an example, the problem of storing the Trésor de la Langue Française on a CD-ROM is examined in this paper. The text alone of this database is 700 megabytes long, more than a CD-ROM can hold. In addition, the dictionary and concordance needed to access these data must be stored. A further constraint is that some of the material is copyrighted, and it is desirable that such material be difficult to decode except through software provided by the system. Pertinent approaches to compression of the various files are reviewed, and the compression of the text is related to the problem of data encryption: Specifically, it is shown that, under simple models of text generation, Huffman encoding produces a bit-string indistinguishable from a representation of coin flips.

The concordance of a full-text information retrieval system contains for every different word W of the data base, a list L(W) of “coordinates”, each of which describes the exact location of an occurrence of W in the text. The concordance should be compressed, not only for the savings in storage space, but also in order to reduce the number of I/O operations, since the file is usually kept in secondary memory. Several methods are presented, which efficiently compress concordances of large fulltext retrieval systems. The methods were tested on the concordance of the Responsa Retrieval Project and yield savings of up to 49% relative to the non-compressed file; this is a relative improvement of about 27% over the currently used prefix-omission compression technique.

In static full-text retrieval systems, which accommodate metrical as well as Boolean operators, the traditional approach to query processing uses a “concordance”, from which large sets of coordinates are retrieved and then merged and/or collated. Alternatively, in a system with l documents, the concordance can be replaced by a set of bit-maps of fixed length l, which are constructed for every different word of the database and serve as occurrence maps. We propose to combine the concordance and bit-map approaches, and show how this can speed up the processing of queries: fast ANDing and ORing of the maps in a preprocessing stage, lead to large I/O savings in collating coordinates of keywords needed to satisfy the metrical and Boolean constraints. Moreover, the bit-maps give partial information on the distribution of the coordinates of the keywords, which can be used when queries must be processed by stages, due to their complexity and the sizes of the involved sets of coordinates. The new techniques are partially implemented at the Responsa Retrieval Project.

The “concordance” of an information retrieval system can often be stored in form of bit-maps, which are usually very sparse and should be compressed. Hierarchical bit-vector compression consists of partitioning a vector vi into equi-sized blocks, constructing a new bit-vector vi+1 which points to the non-zero blocks in vi, dropping the zero-blocks of vi, and repeating the process for vi+1. We refine the method by pruning some of the tree branches if they ultimately point to very few documents; these document numbers are then added to an appended list which is compressed by the prefix-omission technique. The new method was thoroughly tested on the bit-maps of the Responsa Retrieval Project, and gave a relative improvement of about 40% over the conventional hierarchical compression method.

Although it is well-known that Huffman Codes are optimal for text compression in a character-per-character encoding scheme, they are seldom used in practical situations since they require a bit-per-bit decoding algorithm, which has to be written in some assembly language, and will perform rather slowly. A number of methods are presented that avoid these difficulties. The decoding algorithms efficiently process the encoded string on a byte-per-byte basis, are faster than the original algorithm, and can be programmed in any high level language. This is achieved at the cost of storing some tables in the internal memory, but with no loss in the compression savings of the optimal Huffman codes. The internal memory space needed can be reduced either at the cost of increased processing time, or by using non-binary Huffman codes, which give sub-optimal compression. Experimental results for English and Hebrew text are also presented.