13

I understand that compression methods may be split into two main sets:

  1. global
  2. local

The first set works regardless of the data being processed, i.e., they do not rely on any characteristic of the data, and thus need not to perform any preprocessing on any part of the dataset (before the compression itself). On the other hand, local methods analyze the data, extracting information that usually improves the compression rate.

While reading about some of these methods, I noticed that the unary method is not universal, which surprised me since I thought "globality" and "universality" referred to the same thing. The unary method does not rely on characteristics of the data to yield its encoding (i.e., it is a global method), and therefore it should be global/universal, shouldn't it?

My primary questions:

  • What is the difference between universal and global methods?
  • Aren't these classifications synonyms?
Society of Data Scientists
  • 590
  • 5
  • 16
Rubens
  • 4,097
  • 5
  • 23
  • 42
  • 2
    Can you link to/reference where you read that the unary method is not universal? Context may help. – Air Jun 18 '14 at 16:06
  • 3
    I... am not sure how this relates to data science. It seems off-topic for this stack exchange. Could you possibly relate this back to data science? – Slater Victoroff Jun 18 '14 at 16:14
  • @SlaterTyranus I... am not sure too (and that made me think about some two other questions I posted). My idea was to add this question since compression methods are largely used in information retrieval (mainly during indexing). In general, I find this related to efficiency, and it may be put in the *hacking skills* area of this [Venn diagram](http://en.wikipedia.org/wiki/Data_science). Anyway, I guess it'd be nice to discuss whether this kind of question is on topic. – Rubens Jun 18 '14 at 16:33
  • @Rubens That seems like a reasonable discussion, in my mind efficiency talk fits much more into something like theoretical CS than explicit *hacking skills*. In my mind, hacking skills are much more related to things like databases, deployment, and knowledge of tools. – Slater Victoroff Jun 18 '14 at 18:08
  • @SlaterTyranus Hope you join the discussion [here](http://meta.datascience.stackexchange.com/questions/65/are-hacking-skills-questions-off-topic). I've tried to point what I consider to be *hacking skills*. Although I understand theoretical CS to be "the place for algorithms", there are some *pratical* concepts that may would be nice to be added to this site. – Rubens Jun 18 '14 at 18:41
  • Have you looked at *middle-out* compression algorithms? http://www.piedpiper.com/ – Brandon Loudermilk May 19 '16 at 10:32
  • @SlaterTyranus This is strongly related to information theory and thus very much a part of the fundamentals of data science. Compressing a dataset is in a way learning a pattern. But Ruben, what do you mean with aren't these classification synonyms? Could you elaborate on that? – S van Balen Jan 03 '17 at 08:32
  • 1
    @SvanBalen Two major points: 1. Information theory is important in some approaches to data science, but irrelevant in many others. 2. Fundamentals are inherently off topic, asking a detailed question about statistics or linear algebra would similarly be off topic even though both of those are strictly required for useful data science. – Slater Victoroff Jan 03 '17 at 15:54

1 Answers1

3

Consider the following chunk of data:

1010010110100101

Universal - these are generic compression algorithms that are data agnostic. A crude version of run length encoding would fall into this category. The advantage is that it is very fast to compress and decompress. The downside is that it may be extremely ineffective based on the data to be compressed.

1111111111111111 -> 16 1 (lucky case)

1010010110100101 -> 1010010110100101 (unlucky case)

Local - this method would consider smaller segments of a fixed length, say 4, look for patterns and compress them. Eg. This data only contains these two types of patterns - 1010 and 0101. These patterns can be represented as 0s and 1s and the overall data will be a table representing the mappings, and something like 0101. This has the potential to result in a much smaller compressed size.

1010010110100101 -> 1010 0101 1010 0101 -> 0101 (0=1010,1=0101)

Global - this method would look at the entire data and find the optimal / much better patterns to compress the data. The example data contains just one pattern 10100101 and represent it as 00 along with the mapping table. This has the potential to obtain the smallest possible compressed size, but is also computationally the heaviest.

1010010110100101 -> 10100101 10100101 -> 00 (0=10100101)

doodhwala
  • 169
  • 4