Author name cluster

Dana Shapira

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2022 Journal Article

Weighted forward looking adaptive coding

Aharon Fruchtman
Yoav Gross
Shmuel T. Klein
Dana Shapira

Huffman coding is known to be optimal under certain constraints, yet its dynamic version, which constantly alters the Huffman tree as a function of the already processed characters, may be even more efficient in practice. A new forward looking variant of Huffman compression has been proposed recently, that provably always performs better than static Huffman coding by at least m − 1 bits, where m denotes the size of the alphabet, and has a better worst case size than the standard dynamic Huffman coding. This paper introduces a new generic coding method, extending the known static and dynamic variants and including them as special cases. In fact, the generalization is applicable to all statistical methods, including arithmetic coding. This leads then to the formalization of a new double-pass coding method that is adaptive in the sense that it uses changing statistics depending on the current position within the processed file, yet it behaves like static coding, as it assumes the knowledge of the distribution in the entire file; this is contrary to online variants that rely only on the text seen so far and adapt the model dynamically. We call the new method positional coding, and its compression performance, using global statistics, is provably always at least as good as that of the best dynamic variants known to date. Moreover, we present empirical results that show improvements by positional coding and its extensions over static and dynamic Huffman and arithmetic coding, even when the encoded file includes the model description.

Details DOI

AAAI Conference 2021 Short Paper

Deep Reinforcement Learning for a Dictionary Based Compression Schema (Student Abstract)

Keren Nivasch
Dana Shapira
Amos Azaria

An increasingly important process of the internet age and the massive data era is file compression. One popular compression scheme, Lempel–Ziv–Welch (LZW), maintains a dictionary of previously seen strings. The dictionary is updated throughout the parsing process by adding new encountered substrings. Klein, Opalinsky and Shapira (2019) recently studied the option of selectively updating the LZW dictionary. They show that even inserting only a random subset of the strings into the dictionary does not adversely affect the compression ratio. Inspired by their approach, we propose a reinforcement learning based agent, RLZW, that decides when to add a string to the dictionary. The agent is first trained on a large set of data, and then tested on files it has not seen previously (i. e. , the test set). We show that on some types of input data, RLZW outperforms the compression ratio of a standard LZW.

PDF Details

I&C Journal 2021 Journal Article

Integrated encryption in dynamic arithmetic compression

Shmuel T. Klein
Dana Shapira

A variant of adaptive arithmetic coding is proposed, adding cryptographic features to this classical compression method. The idea is to perform the updates of the frequency tables for characters of the underlying alphabet selectively, according to some randomly chosen secret key K. We give empirical evidence that with reasonably chosen parameters, the compression performance is not hurt, and discuss also aspects of how to improve the security of the system being used as an encryption method. To keep the paper self-contained, we add a short description of the arithmetic coding algorithm that is necessary to understand the details of the new suggested method.

Details DOI

TCS Journal 2021 Journal Article

Optimal skeleton and reduced Huffman trees

Shmuel T. Klein
Jakub Radoszewski
Tamar C. Serebro
Dana Shapira

A skeleton Huffman tree is a Huffman tree from which all full subtrees of depth h ≥ 1 have been pruned. Skeleton Huffman trees are used to save storage and enhance processing time in several applications such as decoding, compressed pattern matching and wavelet trees for random access. A reduced skeleton tree prunes the skeleton Huffman tree further to an even smaller tree. The resulting more compact trees can be used to further enhance the time and space complexities of the corresponding algorithms. However, it is shown that the straightforward ways of basing the constructions of a skeleton tree as well as that of a reduced skeleton tree on a canonical Huffman tree do not necessarily yield the least number of nodes. New algorithms for achieving such trees are given.

Details DOI

TCS Journal 2016 Journal Article

Compressed matching for feature vectors

Shmuel T. Klein
Dana Shapira

The problem of compressing a large collection of feature vectors is investigated, so that object identification can be processed on the compressed form of the features. The idea is to perform matching of a query image against an image database, using directly the compressed form of the descriptor vectors, without decompression. Specifically, we concentrate on the Scale Invariant Feature Transform (SIFT), a known object detection method, as well as on Dense SIFT and PHOW features, that contain, for each image, about 300 times as many vectors as the original SIFT. Given two feature vectors, we suggest achieving our goal by compressing them using a lossless encoding by means of a Fibonacci code, for which the pairwise matching can be done directly on the compressed files. In our experiments, this approach improves the processing time and incurs only a small loss in compression efficiency relative to standard compressors requiring a decoding phase.

Details DOI