Re: The duality on random compression and an algorithm that works on random sequences

Newsgroups	comp.compression
Date	2014-10-10 16:23 -0700
References	<a1e46888-40b3-42a3-9842-6a4d7519da47@googlegroups.com>
Message-ID	<b255c1d3-5e4e-4fbf-9d9d-26257b4b7a6f@googlegroups.com> (permalink)
Subject	Re: The duality on random compression and an algorithm that works on random sequences
From	Fábio Linhares <dreamhigh.worldwide@gmail.com>

Show all headers | View raw

Explaining the algorithm:

So this is Shannon perspective in a compact way:

"After establishing this, Shannon introduced the idea
of an information source being probabilistic by
posing the following question to the reader - If
an information source is producing messages by
successively selecting symbols from a finite set,
and the probability of a symbol appearing is
dependent on the previous choice, then what is the amount of information associated with this
source?
Shannon explained the answer to this question by de
scribing information in
terms of entropy. If a
communication source is not characterized by a large degree of randomness or choice, then the
information (or entropy) is low i.e.
1-(actual entropy/maximum entropy) = redundancy".

So if I think about what my algorithm does, taking into account the Shannon perspective, I can say that, when I first convert the information into a "compressible pattern" I am actually making an output that is equal to the initial conditions stated by Shannon, that is, it reduces both the "degree of randomness or choice", converting the information into data with "redundancy". Only after that I can compress the converted data.

Although I know the differences between Shannon theory and Kolmogorov complexity, there are some similarities, that is, in both cases the initial conditions, and their benefits are meet, in the case of Kolmogorov, the smallest "program" to generate a string is created given the fact that after I convert the information into data with redundancy, I compress it the smallest program possible. In both cases, the limits are meet, and exceeded (or in kolmogorov case I'm just reaching better levels in creating a smaller program - if you think that that's a better definition).

"Relating entropy" (Shannon) "and Kolmogorov complexity":

(Section 2.3 and Appendix A)
Although their pri-mary aim is quite different, and they are functions defined on different spaces, there are close relations between entropy and Kolmogorov complexity. The formal relation "entropy= expected Kolmogorov
complexity" is discussed in Section 2.3. The relation is further illustrated by
explaining 'universal coding' (also introduced by Kolmogorov in 1965) which combines elements from both Shannon's and Kolmogorov's theory, and which lies at the basis of most practical data compression methods. While related to the main theme of this paper, universal coding plays no direct role in the later sections, and therefore we delegated it to Appendix A.
Entropy and Kolmogorov Complexity are the basic notions of the two theories. They serve as building blocks for all other important notions in the respective theories. Arguably the most important of these notions is mutual information:

Mutual Information--Shannon and Kolmogorov Style
(Section 3) Entropy and Kolmogorov
complexity are concerned with information in a single object: a random variable (Shannon) or an individual sequence (Kolmogorov). Both theories provide a (distinct) notion of mutual information that measures the information that one object gives about another object. In Shannon's theory, this is the information that one random variable carries about another; in Kolmogorov's theory ('algorithmic mutual information'), it is the information one sequence gives about another. In an appropriate setting the former notion can be shown to be the expectation of the latter notion".

My algorithm works in half of all possible infinite sequences coming from a random source (dice, noise, whatever!). Also, it doesn't matter if the input data is redundant or not (yes, the algorithm works in data with redundancy, although it doesn't search for the usual patterns i.e. bsdfjduad11111111awdsgdv...).

I hope i have explained myself better this time.

Please, if you have a deeper understanding of Shannon and Kolmogorov, then give to me and the readers that explanation, so that we can have a better discussion..!

Thread

The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-06 04:35 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Jarek Duda <dudaj@interia.pl> - 2014-10-06 06:19 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Robert Wessel <robertwessel2@yahoo.com> - 2014-10-06 09:15 -0500
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-06 16:56 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-06 17:17 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-07 09:32 +0200
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 04:12 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-07 13:51 +0200
      Re: The duality on random compression and an algorithm that works on random sequences glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-07 17:58 +0000
        Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 18:39 -0700
          Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-08 06:00 -0700
      Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-09 03:41 +0200
        Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-08 19:02 -0700
          Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-08 19:09 -0700
            Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-10 05:41 +0200
            Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-10 09:25 +0200
              Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-10 07:10 -0700
                Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-10 20:58 +0200
                Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-10 21:08 +0200
                Re: The duality on random compression and an algorithm that works on random sequences Providence <psionic81@gmail.com> - 2014-10-10 12:30 -0700
                Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-11 00:29 +0200
                Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-11 10:59 +0200
                Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-12 07:45 +0200
                Re: The duality on random compression and an algorithm that works on random sequences Fibonacci Code <anglikai@gmail.com> - 2014-10-12 02:12 -0700
                Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-12 18:02 +0200
                Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-12 06:01 -0700
                Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-12 18:15 +0200
        Re: The duality on random compression and an algorithm that works on random sequences Providence <psionic81@gmail.com> - 2014-10-09 08:33 -0700
          Re: The duality on random compression and an algorithm that works on random sequences "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-10-10 05:42 +0200
            Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-10 06:24 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 06:42 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Robert Wessel <robertwessel2@yahoo.com> - 2014-10-07 09:21 -0500
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 08:15 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Robert Wessel <robertwessel2@yahoo.com> - 2014-10-07 10:38 -0500
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 08:38 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Robert Wessel <robertwessel2@yahoo.com> - 2014-10-07 11:03 -0500
      Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 09:51 -0700
        Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-07 10:05 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Providence <psionic81@gmail.com> - 2014-10-08 08:51 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-08 09:26 -0700
    Re: The duality on random compression and an algorithm that works on   random sequences Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-10-08 18:31 +0200
      Re: The duality on random compression and an algorithm that works on   random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-08 11:51 -0700
        Re: The duality on random compression and an algorithm that works on   random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-08 21:06 +0200
          Re: The duality on random compression and an algorithm that works on   random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-08 12:35 -0700
          Re: The duality on random compression and an algorithm that works on   random sequences Providence <psionic81@gmail.com> - 2014-10-08 13:04 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-10 07:24 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-10 07:27 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Providence <psionic81@gmail.com> - 2014-10-10 08:47 -0700
      Re: The duality on random compression and an algorithm that works on random sequences Providence <psionic81@gmail.com> - 2014-10-10 08:50 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-10 16:23 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-11 12:57 +0200
      Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-11 17:24 -0700
        Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-11 17:27 -0700
        Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-12 18:00 +0200
          Re: The duality on random compression and an algorithm that works on random sequences Noob <root@127.0.0.1> - 2014-10-12 23:59 +0200
  Re: The duality on random compression and an algorithm that works on random sequences jdallen2000@yahoo.com - 2014-10-11 09:24 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-11 15:55 -0700
  Re: The duality on random compression and an algorithm that works on random sequences Fábio Linhares <dreamhigh.worldwide@gmail.com> - 2014-10-12 17:22 -0700
    Re: The duality on random compression and an algorithm that works on random sequences Thomas Richter <thor@math.tu-berlin.de> - 2014-10-13 08:07 +0200
    Re: The duality on random compression and an algorithm that works on random sequences Noob <root@127.0.0.1> - 2014-10-13 08:58 +0200
    Re: The duality on random compression and an algorithm that works on random sequences Providence <psionic81@gmail.com> - 2014-10-14 12:17 -0700

csiph-web