Identifying periodic patterns in time series data is crucial for uncovering hidden structures and predicting future events. Recognizing meaningful periodic patterns in real data requires handling approximation criteria since periodic phenomena are usually inexact. This paper introduces a suitable criterion and focuses on detecting Consecutive Periodic Patterns (CPPs) with$k \Delta$-errors, where$k$bounds the number of errors and$\Delta$limits the size of the error. We develop efficient algorithms to detect the Longest Pure Consecutive Maximal Periodic Pattern with bounded errors in both raw and compressed data, the latter by means of the Arithmetic Progressions Tree (APT) data structure.

Adaptive encoding plays a central role in data compression, allowing symbol probabilities to be estimated and updated dynamically. This paper presents a detailed comparison between the forward model, which assumes prior knowledge of the symbol frequencies, and the backward adaptive model, which increments the frequencies during encoding and decoding. We derive an exact expression for the bit-length difference between the two and show that for data distributed by Zipf's law, the forward encoding is beneficial even when we count the cost of information about symbols' frequencies. Extensive experiments conducted on real-world text corpora of varying sizes support the new theoretical results.

The Arithmetic Progressions Tree (APT) is a data structure storing an encoding of a monotonic sequence$\mathcal{L}$in$[1..n]$. While previous work on$\mathsf{APT}$focused on its theoretical and experimental compression guarantees, recently, it was shown that searches of sub-sequences, runs and periodic patterns over the$\mathsf{APT}$compressed data can be applied. This paper extends the set of supported operations and focuses on the computation of consecutively maximal periodic patterns directly over the APT. In particular, given the$\mathsf{APT}$compressed representation of$\mathcal{L}$, we show how: (1)One can find if a consecutive periodic pattern with difference$d_{P}$is represented by an$\mathsf{APT}$node in time$O(\log n)$and if positive, report its occurrences in$\mathcal{L}$in time proportional to the output size multiplied by$\log d_{P}$and the size of the$\mathsf{APT}$compressed representation of$\mathcal{L}$, while assuring that every reported consecutive occurrence is consecutively maximal. (2)Given a query periodic pattern difference,$d_{P}$, we can give a one-sided$O(\log d_{P})$-additive approximation for the length of the consecutively maximal periodic pattern with difference$d_{P}$that occurs in$\mathcal{L}$in time$O(\log n)$. (3)We give a one-sided$O(\log n)$-additive approximation for the maximum length of a consecutively maximal periodic pattern that occurs in$\mathcal{L}$in time$O(\sqrt{n}\log n)$.

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.

The Arithmetic Progressions Tree (APT) is an encoding of a monotonic sequence ℒ in [1..n]. Previous work on APT coding focused on its theoretical and experimental compression guarantees. This paper is the first to consider computations over APT compressed data. In particular: (1) We show how to perform a search for any sub-sequence of the monotone sequence ℒ in time proportional to the query sub-sequence length multiplied by the size of the APT compressed representation of ℒ. (2) We show how, given the APT compressed representation of the monotone sequence ℒ, we can find a minimum run-length of ℒ in constant time, a maximum run-length of ℒ in O(log n) time, and all runs of ℒ in constant time plus the output size. (3) Most importantly, we show how, given the APT compressed representation of the monotone sequence ℒ, we can answer whether a periodic pattern P appears in ℒ in O(log n) time and report its locations in the output size time. (4) In addition, we improve the APT construction algorithm time and space complexity.

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.

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.

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.

This paper introduces a new method called Bidirectional Delta file, which is to construct a two way delta file out of two given files. Previous work focuses on forwards and backwards delta files. Here we suggest efficiently combining them into a single file. Given two files $S$ and $T$, the paper designs a greedy algorithm, which produces an efficient bidirectional delta file in terms of the memory storage it requires. Given this encoding file and the original file $S$, one can decode it in order to produce $T$, and vice versa. Experiments show memory storage savings of at least $25\%$ between the implemented algorithm and the traditional way of using both forwards and backwards delta files

This work proposes a novel practical and general-purpose lossless compression algorithm named Neural Markovian Predictive Compression (NMPC), based on a novel combination of Bayesian Neural Networks (BNNs) and Hidden Markov Models (HMM). The result is an interesting combination of properties: Linear processing time, constant memory storage performance and great adaptability to parallelism. Though not limited for such uses, when used for online compression (compressing streaming inputs without the latency of collecting blocks) it often produces superior results compared to other algorithms for this purpose. It is also a natural algorithm to be implemented on parallel platforms such as FPGA chips.

Given a source file S and two differencing files Delta(S, T) and Delta(T, R), where Delta(A, Y) is used to denote the delta file of the target file Y with respect to the source file X, the objective is to be able to construct R. This is intended for the scenario of upgrading software where intermediate releases are missing, or for the case of file system backups, where non consecutive versions must be recovered. The traditional way is to decompress Delta(S, T) in order to construct T and then apply Delta(T, R) on T and obtain R. The Compressed Transitive Delta Encoding (CTDE) paradigm, introduced in this paper, is to construct a delta file A(S, R) working directly on the two given delta files, Delta(S, T) and Delta(T, R), without any decompression or the use of the base file S. A new algorithm for solving CTDE is proposed and its compression performance is compared against the traditional "double delta decompression". Not only does it use constant additional space, as opposed to the traditional method which uses linear additional memory storage, but experiments show that the size of the delta files involved is reduced by 15% on average.

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.

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. 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

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 presents a compressed pattern matching in Huffman encoded texts. A modified Knuth-Morris-Pratt (KMP) algorithm is used in order to overcome the problem of false matches. This paper also proposes a bitwise KMP algorithm that can move one extra bit in the case of a mismatch, since the alphabet is binary. The KMP algorithm is combined with two Huffman decoding algorithms called sk-kmp and win-kmp to handle more than a single bit per machine operation. However, skeleton trees are used for efficient decoding of Huffman encoded texts.

We consider in-place differential file compression; that is, compressing a file T of size n with respect to an existing file S of size m, where decompression is in-place by overwriting S with T, using at most MAX(m,n)+O(1) space. In previous work we presented the IPSW algorithm (in-place sliding window). IPSW is fast and the compression achieved compares well with other existing methods, including those that are not in-place. IPSW is most effective when S and T are reasonably well aligned (most large common substrings occur in approximately the same order). Here we present a preprocessing step for string alignment that can be employed when the encoder determines significant gains will be achieved.

Algorithms for in-place differential file compression were presented, where a target file of size n is compressed with respect to a source file of size m using no additional space; that is, the space for the source file is overwritten by the decompressed target file so that at no time is more than a total of MAX(m,n) space is used. From a theoretical point of view, an optimal solution (best possible compression) to this problem is known to be NP-hard. The constant-factor approximation algorithm is presented. Although NP-hardness implies that these algorithms cannot always be optimal, the asymptotic optimality for an information source of sliding window methods along with their ability for constant-factor approximation is evidence that they should work well for this problem in practice. The experiments indicate that these algorithms compare favorably with traditional approaches, even those that are not in-place, while at the same time having low encoding complexity and extremely low decoding complexity.

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.