Abstract | ||
---|---|---|
One knows from the Algorithmic Complexity Theory 1 1 This theory is also called the Kolmogorov complexity or Algorithmic Information theory. [2–5, 8, 14] that a word is incompressible on average. For words of pattern x m , it is natural to believe that providing x and m is an optimal average representation. On the contrary, for words like x ⊕ y (i.e., the bit to bit x or between x and y ), providing x and y is not an optimal description on average. In this work, we sketch a theory of average optimal representation that formalizes natural ideas and operates where intuition does not suffice. First, we formulate a definition of K-optimality on average for a pattern, then demonstrate results that corroborate intuitive ideas, and give worthy insights into the best compression in more complex cases. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1016/S0304-3975(97)00275-2 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Optimal coding,optimal coding,Kolmogorov complexity,kolmogorov complexity,optimal representation,information theory,compression,Information theory,Compression | Journal | 200 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 3 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
E. Rivals | 1 | 8 | 2.22 |
Jean-Paul Delahaye | 2 | 325 | 54.60 |