Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2542

Re: Detecting repetitions

Show all headers | View raw

Some more notes:

Given is an array of symbols (here: bits = boolean values).
Needed is a list of RLE blocks (pattern, repeatcount), nothing else.

The detected patterns should not contain repetitions, i.e. '110110' 
should result in pattern '110'. Some greedyness is required, of course, 
so that the pattern '110' is not separated again into 2*'1' and 1*'0'.

It can be assumed that the data contain (possibly large) repetitions of 
short patterns. If not, the data can be assumed as uncompressable - if 
that helps to increase analysis speed.

Preceding work assumes a fixed pattern size, e.g. 3 bits, throughout the 
whole input. I want to find out whether a variable (dynamic, 
adaptive...) pattern size will yield better results.

The blocks are assumed to be created by a loop in the automaton, 
replicating a pattern possibly very often before leaving that loop. 
That's why RLE seems to be the best choice for further processing.

The existence of such a loop can be detected in various ways (subject to 
current research), and when a loop is detected, the width of the block 
or contained pattern can be estimated either from the created output (by 
RLE analysis), or by performing another iteration of the loop and 
watching how far the automaton's head position has changed. This may 
allow for a direct determination of the RLE pattern, without further 
inspection of the output, but until then I want to know how to split 
given data into RLE blocks.

DoDi

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-30 06:13 +0200
  Re: Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-30 22:26 +0200
  Re: Detecting repetitions James Dow Allen <gmail@jamesdowallen.nospam> - 2014-08-31 03:29 +0000
    Re: Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-31 09:57 +0200
  Re: Detecting repetitions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-31 06:08 +0000
    Re: Detecting repetitions Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-08-31 12:07 +0200
  Re: Detecting repetitions "Skybuck Flying" <skybuck2000@hotmail.com> - 2014-09-09 08:00 +0200

csiph-web