# Tagged Questions

The tag has no usage guidance.

8 views

### Data Compression Algorithm for Less repetitive pattern (redundancy) [duplicate]

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Which data compression method/algorithm deals with less repetitive pattern (...
56 views

### Are some real world compression algorithms sometimes producing unexpectedly large files?

Lossless compression is not magic. It just gives the common patterns a short notation, compensating by the less common patterns ending up with a longer notation. By that logic, all lossless ...
41 views

### Data Compression Algorithm for Less repetitive pattern (redundancy) [on hold]

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Which data compression method/algorithm deals with less repetitive ...
300 views

### Using Data Compression on the output of Data Compression

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Is there a data compression method/algorithm that uses another data ...
14 views

### Clustering with probabilities / vector quantization with arbitrary distance measures

Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$). ...
43 views

### Hash for verifying both compressed and uncompressed data?

Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart? Trivially one could just use a hash function twice (once ...
29 views

### How are the number of bytes less than the number of pixels in an image?

Lets take, for example this jpeg image here The image there is 400 x 300, or 120000 pixels and The file size of the image (on my computer) is shown to be 65171 bytes. This means the computer ...
5k views

### Why are these (lossless) compression methods of many similar png images ineffective?

I just came across the following thing: I put multiple identical copies of a png image into a folder and then tried to compress that folder with the following methods: ...
71 views

### What decompression algorithms have the shortest implementations?

I am writing an executable compressor for small (roughly 1 kilobyte) executable files. I am exploring compression algorithms that are well suited for this task. The amount of time required to ...
37 views

### Compression of a complete Directed Acylcic Graph

Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$: $g ::= l \enspace \bar{g}$ This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths ...
35 views

### Can file entropy be predictable?

I am working on some lossless compression topic and looking on any resources or prior studies on lossless file entropy predictability. Assuming we know type of the file (we can tell its belongs to ...
15 views

### Compression of Memoryless Sources

Are there any compression algorithms outside of entropy encodings that yield a significant compression ratio for memoryless sources (not the Markov kind, but this kind)? More concretely, if a million ...
28 views

### Lossless Condensing, Modification, and Decondensing

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where $f(\alpha)=\beta$,...
150 views

### Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?

Karlheinz Brandenburg depicts a MP3 encoder like this: Source: MP3 and AAC Explained I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the ...
1k views

### Compressing two integers disregarding order

Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to ...
61 views

### Please check my Huffman tree [closed]

My professor gave an example of Huffman tree. Given inputs a 80 b 10 c 20 d 50 e 100 f 35 g 60 … then the tree will be: But when i tried to solve it at home, ...
120 views

### When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
25 views

### Algorithm for grouping identical neighbors in a list

I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries. Example list: ...
26 views

### Does JPEG compression use a heuristic model similar to MP3?

I know that MP3 uses a compression heuristic that allows it to exclude storing frequency data outside a certain range due to the limits of human hearing. Does JPEG employ some sort of non-linear ...
341 views

### Algorithm for compressing binary data that can efficiently be partially decompressed

So I have been given the following problem and since I have no experience at all in this field, I would really appreciate some advice/guidance. These are the requirements: So three times per second ...
83 views

### Generalization of XOR Linked Lists

Are there any results generalizing XOR Linked Lists to other types of data structures? For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
32 views

### Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
64 views

### How to efficiently represent any possible mutations to a string of a given length?

I'm trying to find a "language" or a way to express any change that has occurred to a string. I'm given two strings; a seed string and a new string of the same length that came from it. I'm trying to ...
22 views

### Integer Arithmetic Coding misunderstanding of parameters

Given this alphabet $\{a,b,c\}$ where $P(a) = 2/5$, $P(b) = 2/5$, $P(c) = 1/5$. Encode this string : $bcba$. I have to encode this using 5 bits. I have been looking in the Introduction to Data ...
32 views

### Average prefix code length of every 4-sized frequency vector is bounded at 2

I'm trying to show that for every frequency vector $(p_1, p_2, p_3, p_4)$ such that $\sum_{i=1}^4 p_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w_1,w_2,w_3,w_4)$ ...
63 views

### Succinct data structure for “bookkeeping problem”

I have a "standard" problem, but I can't remember its "official" name: I have to keep track of the presence of the absence of value in an array. Currently I use an each bits of an other array to ...
17 views

### Time spent on hashing and rate of compression of a set

I've read: (here why not just use a random number generator as a hash function?) "A hash function usually means a function that compresses, meaning the output is shorter than the input". Since then ...
126 views

### Why should I use Huffman enoding if it makes my data longer?

I have a requirement to reduce the size of the request / response XML by compressing repetitive productID data in compatible tag. My request / response xml looks something like below ...
47 views

### Encryption on a compressed file

Can I do encryption on a compressed file and again decompress the file after decryption to get the original data?
4k views

### Is there a known maximum for how much a string of 0's and 1's can be compressed?

A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that). This is of course not ...
295 views

### How do incompressible strings and random strings share the same properties?

I came across the following theorem in Sipser's about incompressible strings. Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0$, the property $\;f$ ...
49 views

### Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
203 views

### Is there a generalization of Huffman Coding to Arithmetic coding

In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of fuffman coding to be related to the problem of fractional ...
21 views

### Approach to data compression with unknown patterns [closed]

Let's say I have a file with symbols of an alphabet [0,N-1], N around 50. The actual data is a file with a lot of lines, each containing 100 of these symbols. I want to compress this data. By doing a ...
25 views

### Heuristics for space-efficient storing of Unordered Finite Sets in a DFA

I've got an algorithm I'm working on that generates, stores, and iterates through a large number of finite sets. I'm finding that memory is a bottleneck long before time is. The finite sets are ...
79 views

### Is this a new compression approach?

I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is. The approach is to: Convert ...
30 views

### Viewing images that compressed using lossless algorithms

I am just trying to understand a few minor details regarding images that are compressed with lossless algorithms such as RLE. If a bmp image is compressed using RLE, when does the decompression ...
45 views

### How to design Hash Functions for the problem of Set Intersection?

This is a specific question about [1]. Before the question, I must explain and organize some topics: 1) In section 3.2, during the "Pre-processing Stage", a hash function maps an element to a bit-...
65 views

### Data structure for optimal deduplication of common subsets

Consider a database with the following properties: It stores symbols (represented as 64-bit integers) and sets of symbols Sets may contain thousands of symbols, and there may be thousands of sets ...
439 views

### Why does a color video compress better than a black and white video?

It was asked in an exam why a color video compress better than a black and white (grayscale) video using MPEG but can't find anything explaining it. In other words, we would apparently get a better ...
488 views

### Compression type that can be searched

Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
83 views

### Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$ The size of a grammar is defined as the total length of all right-hand ...
3k views

### Data compression using prime numbers

I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data. Basically ...
43 views

### Do compression tables exist and where are they used?

Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, ...
121 views

### How to calculate Huffman code length without generating the actual huffman code?

Given a vector of elements, how can I calculate the length of the Huffman codewords without generating the Huffman code itself? Using Matlab, I was able to compute the Huffman code and and get the ...
998 views

### Are there any compression algorithms based on PI?

What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence). I've seen recently some prototype of πfs which assume that every file ...
109 views

### How to compress a bit string? [closed]

I'm aware of some techniques to compress a string of characters such as Huffman coding. I need to know whether there is any technique to compress a long string of arbitrary bits? (ideally with high ...
571 views

### Why don't we use simple binary values to compress data?

In Huffman's algorithm, we form a tree and than replace each character with the tree value of 1 and 0. Why don't we simply use the binary digits like $a=0$, $b=1$, $c=10$, $d=01$, $e=11$ and so on ...