The tag has no usage guidance.

learn more… | top users | synonyms (1)

0
votes
0answers
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 ...
1
vote
0answers
33 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 ...
1
vote
0answers
14 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 ...
0
votes
0answers
27 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$,...
6
votes
1answer
144 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 ...
19
votes
4answers
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 ...
0
votes
1answer
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, ...
3
votes
1answer
88 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 ...
3
votes
1answer
22 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: ...
3
votes
1answer
21 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 ...
2
votes
4answers
219 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 ...
3
votes
0answers
75 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 ...
3
votes
0answers
31 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 ...
0
votes
0answers
63 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 ...
-1
votes
1answer
20 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 ...
0
votes
1answer
30 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)$ ...
1
vote
2answers
62 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 ...
0
votes
0answers
16 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 ...
1
vote
1answer
121 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 ...
-2
votes
1answer
44 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?
34
votes
5answers
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 ...
6
votes
1answer
292 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$ ...
4
votes
0answers
48 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, ...
4
votes
1answer
198 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 ...
1
vote
0answers
19 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 ...
3
votes
1answer
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 ...
0
votes
1answer
74 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 ...
2
votes
1answer
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 ...
0
votes
0answers
44 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-...
3
votes
1answer
62 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 ...
3
votes
1answer
401 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 ...
7
votes
2answers
486 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?
6
votes
4answers
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 ...
16
votes
5answers
2k 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 ...
1
vote
1answer
42 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, ...
5
votes
1answer
117 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 ...
6
votes
3answers
926 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 ...
0
votes
1answer
101 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 ...
1
vote
1answer
546 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 ...
0
votes
0answers
163 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
7
votes
4answers
420 views

Compression functions are only practical because “The bit strings which occur in practice are far from random”?

I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question. Andrej explains that given the set of all bit strings of length 3 or ...
2
votes
0answers
28 views

Looking for some lossless compression theory [duplicate]

I'll apologize in advance if anything in here is ineloquent. Suppose we have a pair of lossless compression (C) and decompression (...
5
votes
3answers
382 views

Compression of Random Data is Impossible?

A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
0
votes
1answer
113 views

Using Huffman Encoding to improve Lempel-Ziv Encoding

Can anyone think of a way to use Huffman Encoding to improve the compression rate of Lempel-Ziv Encoding? My initial idea was to encode with higher probabilities given to shorter strings (i.e. the ...
3
votes
0answers
153 views

LZ-type compression vs. entropy-encoding of BWT data

Why does there seem to be a preference for using Huffman (or Arithmetic) coding instead of a Lempel-Ziv type compression algorithm for Burrows-Wheeler Transformed data? I noticed that data ...
1
vote
1answer
53 views

Temporal compression protocol

Recently it occurred to me that one could potentially design an interactive "compression" scheme which seems to allow for arbitrarily high compression ratios, at the sole expense of time. This already ...
2
votes
1answer
322 views

How can GIF compression be lossless if the maximum # of colors is 256?

I'm reading "Computer Science Made Simple" by V. Anton Spraul, and in the chapter about Graphics, he describes GIF files as follows: A GIF file uses lossless compression to store an image with a ...
4
votes
0answers
53 views

Polynomial time algorithms on strings [closed]

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ...
2
votes
1answer
168 views

Shannon-Fano puzzle

I was playing around with Shannon-Fano (SF) entropy encoding when I ran into this issue. I am aware that the compression that can be achieved with SF is sometimes inferior to that of Huffman ...
3
votes
1answer
203 views

Designing a prefix code for integers?

trying to figure out how to approach this problem. Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not ...